ic
Section 8.1 Boolean Algebra Structure
625
For x an element of a Boolean algebra B, the element x′ is called the complement of x (picking up the terminology from set theory). The complement of x
satisfies
x + x′ = 1
and
x # x′ = 0
Indeed, x′ is the unique element with these two properties. To prove it, suppose x 1
is an element of B with these same properties,
x + x 1 = 1
and
x # x 1 = 0
Then
x 1 = x 1 # 1
(4b)
= x 1 # (x + x′)
(x + x′ = 1)
= (x 1 # x) + (x 1 # x′)
(3b)
= (x # x 1 ) + (x′ # x 1 )
(1b)
= 0 + (x′ # x 1 )
(x # x 1 = 0)
= (x # x′) + (x′ # x 1 )
(x # x′ = 0)
= (x′ # x) + (x′ # x 1 )
(1b)
= x′ # (x + x 1 )
(3b)
= x′ # 1
(x + x 1 = 1)
= x′
(4b)
Thus x 1 = x′, and x′ is unique. (Uniqueness in the context of propositional logic
means that the truth table is unique, but there can be many different wffs associated with any particular truth table.)
The following theorem summarizes our observations.
ReminDeR
To prove that something
is unique, assume that
there are two of them and
prove that they must be
the same.
use a distributive property, although it’s not clear at this point how the z is going
to disappear.
x′ # y + x′ # y # z = x′ # y # 1 + x′ # y # z
(4b)
= x′ # y # (1 + z)
(3b)
= x′ # y # (z + 1)
(1a)
= x′ # y # (1)
(universal bound—and that’s
how z disappears)
= x′ # y
(4b)
ReminDeR
If it walks like a duck and
it quacks like a duck, it
must be a duck.
If it has the two properties
of the complement, then
by uniqueness it must be
the complement.
tHeoRem on the UniqUeness of CoMPLeMents
For any x in a Boolean algebra, if an element x 1 exists such that
x + x 1 = 1
and
x # x 1 = 0
then x 1 = x′.