CHAPTER 15
Boolean Algebra
15.1Introduction
Both sets and propositions satisfy similar laws, which are listed in Tables 1-1 and 4-1 (in Chapters 1 and 4,
respectively). These laws are used to define an abstract mathematical structure called aBoolean algebra, which
is named after the mathematician George Boole (1815–1864).
15.2Basic Definitions
LetBbe a nonempty set with two binary operations+and∗, a unary operation′, and two distinct elements
0 and 1. ThenBis called aBoolean algebraif the following axioms hold wherea,b,care any elements inB:
[B 1 ] Commutative laws:
(1a) a+b=b+a (1b) a∗b=b∗a
[B 2 ] Distributive laws:
(2a) a+(b∗c)=(a+b)∗(a+c)(2b) a∗(b+c)=(a∗b)+(a∗c)
[B 3 ] Identity laws:
(3a) a+ 0 =a (3b) a∗ 1 =a
[B 4 ] Complement laws:
(4a) a+a′=1(4b) a∗a′= 0
We will sometimes designate a Boolean algebra by〈B,+,∗,′, 0 , 1 〉when we want to emphasize its six parts.
We say 0 is thezeroelement, l, is theunitelement, anda′is thecomplementofa. We will usually drop the symbol
∗and use juxtaposition instead. Then (2b) is writtena(b+c)=ab+acwhich is the familiar algebraic identity
of rings and fields. However, (2a) becomesa+bc=(a+b)(a+c), which is certainly not a usual identity
in algebra.
The operations+,∗, and′are called sum, product, and complement, respectively. We adopt the usual
convention that, unless we are guided by parentheses,′has precedence over∗, and∗has precedence over+.
For example,
a+b∗cmeansa+(b∗c)and not(a+b)∗c; a∗b′meansa∗(b′)and not(a∗b)′Of course whena+b∗cis writtena+bcthen the meaning is clear.
EXAMPLE 15.1
(a) LetB={ 0 , 1 }, the set ofbits(binary digits), with the binary operations of+and∗and the unary operation′
defined by Fig. 15-1. ThenBis a Boolean algebra. (Note′simply changes the bit, i.e., 1′=0 and 0′=1.)
368Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use.