Chapter 3 Logical Formulas44
the system designer is to come up with a system that follows all the specs. This
means that theANDof all the specs had better be satisfiable or the system will be
impossible (see Problem 3.8).
There is also a close relationship between validity and satisfiability, namely, a
statementPis valid iff its negationNOT.P/isnotsatisfiable.
3.4 The Algebra of Propositions
3.4.1 Propositions in Normal Form
Every propositional formula is equivalent to a “sum-of-products” ordisjunctive
form. More precisely, a disjunctive form is simply anORofAND-terms, where
eachAND-term is aANDof variables or negations of variables, for example,
.AANDB/OR.AANDC/: (3.3)
You can read a disjunctive form for any propositional formula directly from its
truth table. For example, the formula
AAND.BORC/ (3.4)
has truth table:
A B C AAND.BORC/
T T T T
T T F T
T F T T
T F F F
F T T F
F T F F
F F T F
F F F F
The formula (3.4) is true in the first row whenA,B, andCare all true, that is, where
AANDBANDCis true. It is also true in the second row whereAANDBANDC
is true, and in the third row whenAANDBANDCis true, and that’s all. So (3.4)
is true exactly when
.AANDBANDC/OR.AANDBANDC/OR.AANDBANDC/ (3.5)
is true. So (3.4) and (3.5) are equivalent.
