Chapter 3 Logical Formulas46
that look like the familiar ones for multiplication of numbers:
AANDB! BANDA commutativity ofAND (3.7)
.AANDB/ANDC! AAND.BANDC/ associativity ofAND (3.8)
TANDA! A identity forAND (3.9)
FANDA! F zero forAND (3.10)Three axioms that don’t directly correspond to number properties are
AANDA !A idempotence forAND (3.11)
AANDA !F contradiction forAND (3.12)
NOT.A/ !A double negation (3.13)
(3.14)It is associativity (3.8) that justifies writingAANDBANDC without specifying
whether it is parenthesized asAAND.BANDC/or.AANDB/ANDC. That’s
because both ways of inserting parentheses yield equivalent formulas.
There are a corresponding set of equivalences forORwhich we won’t bother to
list, except for theORrule corresponding to contradiction forAND:
AORA !T validity forOR (3.15)
(3.16)There is also a familiar rule connectingANDandOR:AAND.BORC/! .AANDB/OR.AANDC/ distributivity ofANDoverOR
(3.17)Finally, there areDeMorgan’s Lawswhich explain how to distributeNOT’s over
AND’s andOR’s:
NOT.AANDB/ !AORB DeMorgan forAND (3.18)
NOT.AORB/ !AANDB DeMorgan forOR (3.19)All these axioms can be verified easily with truth tables.
These axioms are all that’s needed to convert any formula to a disjunctive normal
form. We can illustrate how they work by applying them to turn the negation of
formula (3.4), namely,
NOT..AANDB/OR.AANDC//: (3.20)