Page 1040 - The Mechatronics Handbook

36.9 Boolean Algebra

Boolean algebra provides a means to analyze and design binary systems and is based on the seven
postulates given in Table 36.14. All other Boolean relationships are derived from these seven postulates.
Expressed in graphical form, called Venn diagrams, the postulates appear more natural and logical. This
benefit results from the two-dimensional pictorial representation freeing the expressions from the one-
dimensional constraints imposed by lineal language format.
The OR and AND operations are normally designated by the arithmetic operator symbols + and ◊
and referred to as sum and product operators in basic digital logic literature. However, in digital systems
that perform arithmetic operations this notation is ambiguous and the symbols for OR and L for AND
eliminates the ambiguity between arithmetic and boolean operators. Understanding the conceptual
meaning of these boolean operations is probably best provided by set theory, which uses the union
operator for OR and the intersection operator for AND. An element in a set that is the union of
sets is a member of one set OR another of the sets in the union. An element in a set that is the intersection
of sets is a member of one set AND a member of the other set in the intersection.
A set of theorems derived from the postulates facilitates further developments. The theorms are
summarized in Table 36.15. Use of the postulates is illustrated by the proof of a theorem in Fig. 36.2.

TABLE 36.14 Boolean Postulates
Forms
Postulate Name Meaning (a) (b)
1 Definition ∃ a set {K } = {a, b,. . .} OR AND
of two or more elements +
and two binary operators V
{K} = {a,b,a + b,a· b,. . .}
2 Substitution expression = expression 2
1
Law If one replaced by the other
does not alter the value
3 Identity ∃ identity elements a + 0 = a a 1 = a
Element for each operator
4 Commutativity For every a and b in K a + b = b + a a b = ba
5 Associativity For every a, b, and c in K a + (b + c) = (a + b) + c a · (b · c) = (a · b) · c
6 Distributivity For every a, b, and c in K a + (b · c) = (a + b) · (a + c) a · (b + c) = (a · b) + (a · c)
-
-
7 Complement For every a in K a + a = 1 aa = 0
∃ a complement in K
TABLE 36.15 Boolean Theorems

Forms
Theorem (a) (b)
8 Idempotency a + a = a a ◊ a = a
9 Complement a + 1 = 1 a ◊ 0 = 0
Theorem
10 Absorption a + ab = a a(a + b) = a
a
11 Extra Element a + b = a + b a(a + b) = ab
Elimination
a
a
12 De Morgan’s Theorem a + b = ◊ b ab = + b
a
a
13 Concensus ab + c + bc = ab + c (a + b)(a + c)(b + c) = (a + b)(a + c)
14 Complement ab + a = a (a + b)(a + b) = a
b
Theorem 2
b
15 Concensus 2 ab + ac = ab + ac (a + b)(a + + c) = (a + b)(a + c)
b
a
a
16 Concensus 3 ab + c = (a + c)(a + b) (a + b)(a + c) = ac + b
©2002 CRC Press LLC