3.4. The Algebra of Propositions 47
into disjunctive normal form.
We start by applying DeMorgan’s Law forORto (3.20) in order to move theNOT
deeper into the formula. This gives
NOT.AANDB/AND NOT.AANDC/:Now applying Demorgan’s Law forANDto the two innermostAND-terms, gives
.AORB/AND.AORC/: (3.21)At this pointNOTonly applies to variables, and we won’t need Demorgan’s Laws
any further.
Now we will repeatedly apply the distributivity ofANDoverORto turn (3.21)
into a disjunctive form. To start, we’lll distribute.AORB/overORto get
..AORB/ANDA/OR..AORB/ANDC/:Using distributivity over bothAND’s we get
..AANDA/OR.BANDA//OR..AANDC/OR.BANDC//:By the way, we’ve implicitly used commutativity (3.7) here to justify distributing
over anANDfrom the right. Now applying idempotence to remove the duplicate
occurrence ofAwe get
.AOR.BANDA//OR..AANDC/OR.BANDC//:Associativity now allows dropping the parentheses around the terms beingOR’d to
yield the following disjunctive form for (3.20):
AOR.BANDA/OR.AANDC/OR.BANDC/: (3.22)The last step is to turn each of theseAND-terms into a disjunctive normal form
with all three variablesA,B, andC. We’ll illustrate how to do this for the second
AND-term.BANDA/. This term needs to mentionCto be in normal form. To
introduceC, we use validity forORand identity forANDto conclude that
.BANDA/ !.BANDA/AND.CORC/:Now distributing.BANDA/over theORyields the disjunctive normal form.BANDAANDC/OR.BANDAANDC/: