Mathematics for Computer Science

Chapter 3 Logical Formulas70

Homework Problems

Problem 3.16.
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.17.
A 3-conjunctive form (3CF) formula is a conjunctive form formula in which each
OR-term is anORof 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 for each operator that
occurs inF. For example, ifFwas

..PXORQ/XORR/OR.PANDS/ (3.27)

we might use new variablesX 1 ,X 2 ,O, andAcorresponding to the operator oc-
currences as follows:

..P„ƒ‚...XOR

X 1

Q/„ƒ‚...XOR

X 2

R/„ƒ‚...OR

O

.P„ƒ‚...AND

A

S/:

Next we write a formula that constrains each new variable to have the same truth
value as the subformula determined by its corresponding operator. For the example
above, these constraining formulas would be

X 1 IFF.PXORQ/;

X 2 IFF.X 1 XORR/;

AIFF.PANDS/;

OIFF.X 2 ORA/