624
Boolean Algebra and Computer Logic
More properties of Boolean algebras appear in the exercises at the end of
this section. The most important of these properties are double negation and De
Morgan’s laws:
(x′)′ = x
(double negation—Exercise 7)
(x + y)′ = x′ # y′ (x # y)′ = x′ + y′
(De Morgan’s laws—Exercise 8)
Table 8.1 suggests hints that may help when trying to prove a Boolean algebra
property of the form
some expression = some other expression
example 5
The dual of the idempotent property (Example 4), x # x = x, is true in any Boolean
algebra.
■
PraCtiCe 2
a. What does the idempotent property of Example 4 become in the context of propositional logic?
b. What does it become in the context of set theory?
■
PraCtiCe 3
a. Prove that the universal bound property x + 1 = 1 holds in any Boolean algebra. Give a
reason for each step.
b. What is the dual property?
Once a property about Boolean algebra is proved, we can use it to prove new
properties.
table 8.1
Hints for proving boolean algebra equalities
Usually the best approach is to start with the more complicated expression and try to show that it reduces to the
simpler expression.
Think of adding some form of 0 (like x # x′) or multiplying by some form of 1 (like x + x′).
Remember property 3a, the distributive property of addition over multiplication—it is easy to forget because it
doesn’t look like arithmetic.
Remember the idempotent property x + x = x and its dual x # x = x.
Remember the universal bound property x + 1 = 1 and its dual x # 0 = 0.
example 6
Prove that x′ # y = x′ # y + x′ # y # z in any Boolean algebra.
Following the suggestion in Table 8.1, we start with the more complicated
expression, x′ # y + x′ # y # z. There is a “common factor” of x′ # y, so we should
Boolean Algebra and Computer Logic
More properties of Boolean algebras appear in the exercises at the end of
this section. The most important of these properties are double negation and De
Morgan’s laws:
(x′)′ = x
(double negation—Exercise 7)
(x + y)′ = x′ # y′ (x # y)′ = x′ + y′
(De Morgan’s laws—Exercise 8)
Table 8.1 suggests hints that may help when trying to prove a Boolean algebra
property of the form
some expression = some other expression
example 5
The dual of the idempotent property (Example 4), x # x = x, is true in any Boolean
algebra.
■
PraCtiCe 2
a. What does the idempotent property of Example 4 become in the context of propositional logic?
b. What does it become in the context of set theory?
■
PraCtiCe 3
a. Prove that the universal bound property x + 1 = 1 holds in any Boolean algebra. Give a
reason for each step.
b. What is the dual property?
Once a property about Boolean algebra is proved, we can use it to prove new
properties.
table 8.1
Hints for proving boolean algebra equalities
Usually the best approach is to start with the more complicated expression and try to show that it reduces to the
simpler expression.
Think of adding some form of 0 (like x # x′) or multiplying by some form of 1 (like x + x′).
Remember property 3a, the distributive property of addition over multiplication—it is easy to forget because it
doesn’t look like arithmetic.
Remember the idempotent property x + x = x and its dual x # x = x.
Remember the universal bound property x + 1 = 1 and its dual x # 0 = 0.
example 6
Prove that x′ # y = x′ # y + x′ # y # z in any Boolean algebra.
Following the suggestion in Table 8.1, we start with the more complicated
expression, x′ # y + x′ # y # z. There is a “common factor” of x′ # y, so we should