Boolean Algebra


The primary goal here is to explain Boolean Algebra in very simple language for myself. A secondary personal goal is to do so in Bulgarian.

Basics:
For me, algebra is a formal language with special symbols. In fact, it is a good idea to think of computer programming language as algebra. That is now one of the main reasons that we are very interested in algebra.

The word formal means that there are exact rules for the combination of these symbols and their simplification or reduction.

Let us imagine that we have just two numbers, 0 and 1.
[ We will associate these with two logical values, F(alse) and T(rue), respectively. ]

We can add the numbers according to usual rules: (The word law is often used in place of rule.)

0 + 0 = 0,
0 + 1 = 1 + 0 = 1
1 + 1 = 0 // this rule being the strange one!

Writing x and y to stand for numbers, we can express addition by x + y

Now it is time to talk about how to read this addition operation.
When we see an expression such as "x + y" how do we read it?
One might read it as "x PLUS y".
One must NOT read it as "x AND y".
The best reading is "x OR y".

There is an intimate relation between this Boolean algebra and Boolean logic.
It might be best to write "x ⋁ y" (logic) or even "x ⋃ y" (set theory) or even "x ⊔ y" (description logic).
Since there are so many possibilities, it is easy to say why one might be old-fashioned as use "x + y" :)

Note: For an interesting historical account on these notations, see Existential Graphs, MS 514 by Charles Sanders Peirce with commentary by John F. Sowa
{2005-12-03}.
Rules for addition:

x + y = y + x // this is known as the rule of symmetry. Another word used is commutativity (Комутативност).

x + (y + z) = (x + y) + z // this is the association rule. You can call it the associativity law {2005-11-18} if you like.

The symbols ( and ) are called parentheses or round brackets. In modern e-communication we have found new algebraic uses for such symbols:

1 + 1 = 0 :) versus 1 + 1 = 0 :(

Indicating a certain emotional reaction to this rule.

Algebra is written like sentences, such as this one. The use of parentheses is the way we talk about trees.

What does this mean exactly?

Well, it is true that x + (y + z) = (x + y) + z in terms of eventual value. But in terms of structure, they are very different.
In other words, from a structure point of view

x + (y + z) /= (x + y) + z

This structure view is essential in computer programming.

Specifically, x + (y + z) means add y to z FIRST AND THEN add x to the result.
(x + y) + z means add x to y FIRST AND THEN add the result to z.

We have also learned how to write down these trees in another linear way:

x + (y + z) can be written as xyz++ and
(x + y) + z can be written as xy+z+

These are words is postfix (or postscript) form which capture exactly the structure according to stack rules.

Before we move on to other simple things, it is good to realize that our simple number symbols can be put together to form words.
First, let us look at the ten digits of our two hands. We map number symbols
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
to each digit. The number symbols we also call digits.

We have learned to put digits together to form words such as 117
This is usually understood to mean one hundred (100) and seventeen (17).
The seventeen is (10+7). In other words, the word 117 has a particular numerical value according to another rule.

If we think of our simple system 0, 1 as binary (2) digits, abbreviated bits, then we can form binary words, such as 11010110.
And, if we think of 0 as OFF and 1 as ON then we have the basis for the computer itself.

Multiplication is straightforward:
0 . 0 = 0
0 . 1 = 1 . 0 = 0
1 . 1 = 1

Again using x and y, then multiplication is expressed by x . y
Traditionally, the multiplication symbol is often left out and we write xy.

We usually read "x . y" as "x AND y". Alternative notations are
"x ⋀ y" (logic), "x ∩ y" (set theory), "x ⊓ y" (description logic).


Wiki: Basic Definitions {2005-11-17} (in Bulgarian).

Posted: Thu - November 17, 2005 at 05:19 p.m.          

©