Chapter 3 Logical Formulas54
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.13):
AOR.BANDA/OR.AANDC/OR.BANDC/: (3.15)
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/:Doing the same thing to the otherAND-terms in (3.15) finally gives a disjunctive
normal form for (3.5):
.AANDBANDC/OR.AANDBANDC/OR
.AANDBANDC/OR.AANDBANDC/OR
.BANDAANDC/OR.BANDAANDC/OR
.AANDCANDB/OR.AANDCANDB/OR
.BANDCANDA/OR.BANDCANDA/:Using commutativity to sort the term andOR-idempotence to remove duplicates,
finally yields a unique sorted DNF:
.AANDBANDC/OR
.AANDBANDC/OR
.AANDBANDC/OR
.AANDBANDC/OR
.AANDBANDC/:
This example illustrates a strategy for applying these equivalences to convert any
formula into disjunctive normal form, and conversion to conjunctive normal form
works similarly, which explains: