What are the postulates of Boolean Algebra?
A quick way to see where and why the similarities and differences between our familiar arithmetic algebra and Boolean Algebra occur is to look at the postulates of Boolean Algebra. Hopefully this study will spotlight where possible confusion may exist between the algebras and will help you to master Boolean Algebra sooner. Once you understand how Boolean Algebra works then you will be able to fearlessly look at Boolean equations and verify or figure out the truth or logic in them. Like regular algebra, you will be able to simplify Boolean equations. You will eventually be able to design circuits that will work, once you have come up with the right Booean equation.
I am going to list them in a
most general and classical form and then
I will show how they work with examples.
I will also be comparing them to the way regular algebra works.
You will see that in these classical ways of expressing the postulates, instead of using numbers, we will
be using letters which can
then be treated like variables or
like terms or even like placeholders for inserting pieces of more complicated algebraic "formulas" or expressions.
You will also notice words in the way the
postulates are expressed that come from logic and suggest theory (ie, the terms "class" and "element", suggesting "set" and "subset").
I should warn you that the first major difference between Boolean Algebra and regular algebra (even though they may look the same when first looking at the following postulates)
is in the way the operators such as + and * behave. They may look the same but they have different names and mean different things.
In Boolean Algebra the + doesn't really ADD, but combines a pair of "sets" into a larger set.
And the * in Boolean Algebra doesn't "multiply" but "mutually filters out" to form a set that gives you what is common in the
sets that were "combined" in such a manner. Also Boolean Algebra doesn't have a "minus" symbol, only a "plus" symbol
(which, remember, really doesn't ADD). Likewise it doesn't have a "divide" symbol.
So in Boolean Algebra, you can only "combine" to form a larger set with the + operator,
or "consolidate" to form a leaner version of two sets with the * operator.
The "+" in Boolean Algebra can be called "OR", and the * can be called "AND".
So in Boolean Algebra, we will be ORing and ANDing instead of ADDing and MULTIPLYing.
The first postulate has two
parts:
If A and B are in the class K, then
A + B
is in the class K,
and likewise if A and B are in the class K, then A*B is in the class K.
The second postulate goes:
There is an element Z such that A + Z = A for every element A, and there is an element U such that A*U = A for every element A.
Postulate three goes like so:
A + B = B + A, and A*B = B*A.
Postulate four says:
A + B*C = (A + B) * (A + C),and A*(B + C) = A*B + A*C.
Postulate five says:
For every element A there is an element ~A such that A + ~A = U, and A*~A = Z.
[Note that "~" is pronounced "not"]
The sixth postulate states:
There are at least two distinct elements in the class K. The Z is called the "null class" and it turns out to be zero when using the binary numbers (zero and one), and the U is called the "universal class" and it turns out to be the number 1 when using binary numbers.
What do the Boolean Algebra postulates mean?
The first and second postulates defined above can apply to both Boolean Algebra and regular algebra.The first postulate in regular algebra means that whatever you do with two numbers, you will end up with another number that belongs to the set of all possible numbers. Well, in Boolean Algebra, when applied to binary numbers, there is only two numbers, 0 and 1, and if you are limited to only one digit each, then whatever operation you do on the two numbers, you will get one of the two numbers. So, for example, when you "OR" 1 + 0, you get 1. And when you "AND" 1*0 you get 0. In other words, the complete set you are allowed to work with in Boolean Algebra is only {0,1}
The second postulate when using binary numbers gives us that 1 + 0 = 1 and 0 + 0 = 0, in other words, ORing (adding in regular algebra) zero to anything (the class a) yields that same old anything (the class A, again, nothing changed). This makes sense in ordinary algebra. We can add zero to any number and get the same number.
The second postulate also shows
what happens when we AND the universal class ( binary 1) to class A, we
also get back class A. That is similar to when we multiply (in ordinary
algebra) any number with 1, we get that same old number.
Postulate three
is just like the commutative laws of addition and multiplication of our
everyday algebra. In other words, we get the same result no matter the
order of presentation.
Postulate four is where things
start to look different between the algebras. In regular algebra you can't do that.
The closest would be A*A + A*C + B*A + B*C = (A + B)*(A + C) which is quite
different from Boolean Algebra's A + B*C = (A + B)*(A + C).
What can we derive from the Boolean Algebra postulates?
From these postulates we can derive another set of basic postulate designed for switching circuits of the binary type. This means that we must go through the above postulates and apply them to the class that contains only two possible elements or states: 0, and 1.That means that the first postulate says:
A + B must be in K and A*B also. In binary numbers that means 0 + 0, 0 + 1, 1 + 0, and 1 + 1 must have answers in K. And the answers can only be either 0 or 1.
The second postulate
requires that one of the elements function as a "null element" or zero
and the other function
as a "universal element" or one. That gives us the rules: A + 0 =
A and A*1 = A. So we get four possible outcomes:
1 + 0 = 1,
0 + 0 = 0,
1*1 = 1,
0*1 = 0.
From postulate three, this must be true:
1 + 0 = 0 + 1,
1*0 = 0*1.
Postulate four may be
tested by selecting a set of values for A, B, and C, and
using the given postulate
formulas:
A + B*C = (A + B) * (A + C),
and
A*(B + C) = A*B + A*C.
Let us test it out for A = 0, B = 1, C = 1
result: 0 + 1*1 = (0
+ 1)*(0 + 1)
1 = 1
therefore postulate
four does not lie.
Postulate five says that
if you add [OR] the complement you get 1, and if you multiply [AND] by
the complement you get 0. Let us see if this is so.
Take one element and
OR its complement, and you should get 1.
0 + 1 = 1, it is so
for ORing.
Take one element and
AND its complement, and you should get 0.
0*1 = 0, it is so for
ANDing.
What I get out of postulate six is that you can have only 0 and 1, two distinct elements.
Okay, now we are going to rewrite
the above Boolean Postulates into a
more practical and explicit
form that allows us to use the binary
elements (ZERO and ONE), or
(FALSE and TRUE) or (OFF and ON) or
(MALE and FEMALE) or
(yin and yang) or whatever you like.
The set of basic
Boolean postulates
can be rewritten to more explicitly
show what is allowed with only the
the binary elements {0,1} as follows:
1a. If A = 1, then A = !0
1b. If A = 0, then A = !1
explanation: at any instant,
a variable will either be in the zero state or in the one state but not
both. The exclamation point (!) is effectively the same as the complement
symbol (~). Other ways of showing the operation of COMPLEMENTing or NEGATING
is with a BAR over the number or letter. But I can't easily do it here, so I will
usually use the ~ symbol in front of the thing to be complemented (or inverted).
2a. If A = 0, then ~A = ~0 =
1
2a. If A = 1, then ~A = ~1 =
0
In other words, the complement
of one state is equal to the other state.
3a. 0*0 = 0
3b. 1 + 1 = 1
4a. 1*1 = 1
4b. 0 + 0 = 0
5a. 1*0 = 0*1 = 0 5b.
0 + 1 = 1 + 0 = 1
The postulates can also be briefly
and graphically defined in a tabular fashion as follows:
YES function
A A
| 0 | 0 |
| 1 | 1 |
NOT function
A ~A
| 0 | 1 |
| 1 | 0 |
AND function
A B AB
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
OR function
A B A+B
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
The above tables are practically the same as TRUTH TABLES that are used to
define the functions of basic digital components. The 0 and the 1 can be
interchanged with FALSE and TRUE, or with LOW and HIGH.
From these basic postulates
of Boolean Algebra,
some useful relations are derived
and are considered theorems:
6a. A + 0= A
6b. A * 1= A
7a. A + 1= 1
7b. A*0= 0
8a. A + A= A
8b. A*A= A
9. ~(~A)= A
10a. A + ~A= 1
8b. A*~A= 0
11a. A + B= B + A
11b. A*B= B*A
12a. A + A*B= A
13. A*~B + B= A + B
14a. A + B + C = (A + B) + Z
= A + (B + C)
14b. A*B*C = (A*B)*C =
A*(B*C)
15. A*(B + C) = A*B + A*C
16. (A + D)*(B + C) = A*B +
A*C + D*B + D*C
17a. (A + B)*(~A + C)*(B
+ C) = (A + B)*(~A + C)
17b. (A * B)+(~A * C)+(B
* C) = (A * B)+(~A * C)
18a. ~(A
1
+ A
2
+...+A
n
)
= ~A
1
*~A
2
*...*~A
n
18b. ~(A
1
* A
2
*...*A
n
)
= ~A
1
+
~A
2
+...+
~A
n
What are some similarities and differences between Boolean Algebra and regular algebra?
Study of the theorems in Boolean
Algebra will show some interesting similarities and differences between
it and regular algebra. For example, in Boolean Algebra the symbol <
can be used to mean "is included in" which could be interpreted as "is
a member of". In regular algebra the < symbol means "is less than".
As you will see, when you come up with theorems using the "inclusion" operator
"<" you will find that they take a form that curiously resembles regular
algebra. But you will also notice that, for example, A < A in
regular algebra does not make sense. So in this case Boolean Algebra's
"<" is working more like a "<=", that is, is "less than OR equal
to".
[This "<" symbol seems similar in meaning
to the "
" symbol in
set theory which is pronounced as "is an element of". Perhaps the "
"
symbol was invented to not conflict its "is an element of" meaning with
the "less than" meaning already taken by the symbol "<" in regular algebra.
Further research is needed to see if there is some difference between "is
including in" (for <) and "is an element of" (for
).]
The Boolean theorems
derived from the first six "classical" postulates are
1) A < A
2) If A < A and B < C, then A < C
3) if A < B and B < A, then A = B
4) Z < A ( where Z is the element in Postulate two and it is proved to be the only element that will satisfy that Postulate)
5) A < U (where U is the element in Postulate two (the second part of it), also unique)
6) A < A + B; and if A < Y and B < Y, then A + B < Y.
7) A*B < A; and if X <
A and X < b, then X < A*B.
8) If X < A and X < ~A, then X = Z; and if A < Y and ~A < Y, then Y = U.
9) If X < ~B is false, then there is at least one element X, distinct from Z, such that X < A and X < B.
Remember that in Boolean Algebra,
the "<" symbol means "is included in" . But in regular algebra,
"<" means "is less than". Yet there are theorems above that resemble
and work well in our regular algebra of everyday counting numbers. For
example, it is interesting to note that in theorem (2), if A,B,C are real
numbers, and Z is zero, then that theorem is valid for our familiar arithmetic.
Also theorm (4) works for A as postive numbers. However theorem (1) does
not make sense in regular algebra. Also the second part of (6) does not
always work for everyday numbers.
