ic
Section 8.1 Boolean Algebra Structure
623
Although ordinary arithmetic of integers has many of the properties of a Boolean algebra, the idempotent property should convince you that arithmetic is not a
Boolean algebra. The property x + x = x does not hold for ordinary numbers and
ordinary addition unless x is zero.
In the proof of Example 4, we used property 5a to replace 1 with x + x′. The
properties of Boolean algebra are equalities, and either side of an equal sign can
be replaced with the other side. The Boolean algebra properties (rules) are like the
equivalence rules in logic; to apply the rule, your situation must match exactly the
pattern of the rule. For example, it is legal to replace
( y # z) + x
with
x + ( y # z)
using property 1a, because ( y # z) + x matches the right side of 1a where y is the
Boolean algebra element y # z, and x + ( y # z) matches the left side of 1a under the
same interpretation of y. We cannot say
x + ( y # z) = (x # y) + (x # z)
using either property 3a or 3b because we have mixed up the two properties. And,
strictly speaking, we cannot replace
( y # z) + x
with
( y + x) # (z + x)
and claim that we are using property 3a because in property 3a the addition is to
the left of the multiplication. We must reason as follows:
( y # z) + x = x + ( y # z)
(1a)
= (x + y) # (x + z)
(3a)
= ( y + x) # (z + x)
(1a twice)
However, we will sometimes make implicit use of the associative property and
write
x + y + z
with no parentheses.
Each property in the definition of a Boolean algebra has its dual as part of
the definition, where the dual is obtained by interchanging + and # , and 1 and
0. For example, x + 0 = x and x # 1 = x are duals of each other. Therefore, every
time a new property P about Boolean algebras is proved, each step in that proof can
be replaced by the dual of that step. The result is a proof of the dual of P. Thus, once
we have proved P, we know that the dual of P also holds. It’s a two-for-one deal!
ReminDeR
A Boolean algebra
property may be applied
only when your expression exactly matches the
pattern of one side of the
property.
Section 8.1 Boolean Algebra Structure
623
Although ordinary arithmetic of integers has many of the properties of a Boolean algebra, the idempotent property should convince you that arithmetic is not a
Boolean algebra. The property x + x = x does not hold for ordinary numbers and
ordinary addition unless x is zero.
In the proof of Example 4, we used property 5a to replace 1 with x + x′. The
properties of Boolean algebra are equalities, and either side of an equal sign can
be replaced with the other side. The Boolean algebra properties (rules) are like the
equivalence rules in logic; to apply the rule, your situation must match exactly the
pattern of the rule. For example, it is legal to replace
( y # z) + x
with
x + ( y # z)
using property 1a, because ( y # z) + x matches the right side of 1a where y is the
Boolean algebra element y # z, and x + ( y # z) matches the left side of 1a under the
same interpretation of y. We cannot say
x + ( y # z) = (x # y) + (x # z)
using either property 3a or 3b because we have mixed up the two properties. And,
strictly speaking, we cannot replace
( y # z) + x
with
( y + x) # (z + x)
and claim that we are using property 3a because in property 3a the addition is to
the left of the multiplication. We must reason as follows:
( y # z) + x = x + ( y # z)
(1a)
= (x + y) # (x + z)
(3a)
= ( y + x) # (z + x)
(1a twice)
However, we will sometimes make implicit use of the associative property and
write
x + y + z
with no parentheses.
Each property in the definition of a Boolean algebra has its dual as part of
the definition, where the dual is obtained by interchanging + and # , and 1 and
0. For example, x + 0 = x and x # 1 = x are duals of each other. Therefore, every
time a new property P about Boolean algebras is proved, each step in that proof can
be replaced by the dual of that step. The result is a proof of the dual of P. Thus, once
we have proved P, we know that the dual of P also holds. It’s a two-for-one deal!
ReminDeR
A Boolean algebra
property may be applied
only when your expression exactly matches the
pattern of one side of the
property.