Mathematics for Computer Science

(Frankie) #1

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)
Free download pdf