3.6. Predicate Formulas 61
(a)Write formulas using onlyAND,OR,NOTthat are equivalent to each ofAIFFB
andAXORB. Conclude that every propositional formula is equivalent to anAND-
OR-NOTformula.
(b)Explain why you don’t even needOR.(c)Explain how to get by with the single operatorNANDwhereANANDBis
equivalent by definition toNOT.AANDB/.
Class Problems
Problem 3.10.
Explain how to find a conjunctive form for a propositional formula directly from a
disjunctive form for its complement.
Homework Problems
Problem 3.11.
Use the equivalence axioms of Section 3.4.2 to convert the following formula to
disjunctive form:
AXORBXORC:Problems for Section 3.5
Homework Problems
Problem 3.12.
A 3-conjunctive form (3CF) formula is a conjunctive form formula in which each
OR-term is aORof at most 3 variables or negations of variables. Although it may be
hard to tell if a propositional formula,F, is satisfiable, it is always easy to construct
a formula,C.F/, that is
in 3-conjunctive form, has at most 24 times as many occurrences of variables asF, and is satisfiable iffFis satisfiable.To constructC.F/, introduce a different new variables, one for each operator that
occurs inF. For example, ifFwas
..PXORQ/XORR/OR.PANDS/ (3.32)