Section 4.1 Sets
235
Once we have proved the set identities in this list, we can use them to prove
other set identities. Just as the tautological equivalences of propositional logic
represent recipes or patterns for transforming wffs, the set identities represent
patterns for transforming set expressions. And, as with tautologies, the set identity
can be applied only when the set expression exactly matches the pattern.
The dual for each set identity in our list also appears in the list. The dual is
obtained by interchanging c and d and interchanging S and [. The dual of the
identity in Example 20 is
[A d (B c C  )] c ([A′ d (B c C  )] c (B c C  )′) = S
which we could prove true by replacing each basic set identity used in the proof of
Example 20 with its dual. Because this method always works, any time we have
proved a set identity by using the basic identities, we have also proved its dual.
example 20
We can use the basic set identities to prove
[A c (B d C  )] d ([A′ c (B d C  )] d (B d C  )′) = [
for A, B, and C any subsets of S. In the following proof, the number to the right is
that of the basic set identity used to validate each step. The first step uses identity
2b because the expression
[A c (B d C  )] d ([A′ c (B d C  )] d (B d C  )′)
matches the right side of 2b, A d (B d C  ) where A is [A c (B d C  )], B is
[A′ c (B d C  )], and C is (B d C  )′
[A c (B d C  )] d ([A′ c (B d C  )] d (B d C  )′)
= ([A c (B d C  )] d [A′ c (B d C  )]) d (B d C  )′
(2b)
= ([(B d C  ) c A] d [(B d C  ) c A′]) d (B d C  )′
(la twice)
= [(B d C  ) c (A d A′)] d (B d C  )′
(3a)
= [(B d C  ) c [] d (B d C  )′
(5b)
= (B d C  ) d (B d C  )′
(4a)
= [
(5b)
ReminDeR
You must match the
pattern of a set identity in
order to use it. In the set
identities, A, B, and C can
represent any sets.
PraCtiCe 19
a. Using the basic set identities, establish the set identity
[C d (A c B)] c [(A c B) d C′] = A c B
(A, B, and C are any subsets of S.)
b. State the dual identity that you now know is true.
■