3.7. References 71
(a)Explain why theANDof the four constraining formulas above along with a
fifth formula consisting of just the variableOwill be satisfiable iff (3.27) is satisfi-
able.
(b)Explain why each constraining formula will be equivalent to a 3CF formula
with at most 24 occurrences of variables.
(c)Using the ideas illustrated in the previous parts, explain how to constructC.F/
for an arbitrary propositional formula,F.
Problem 3.18.
It doesn’t matter whether we formulate the SAT problem (Section 3.5 in terms of
propositional formulas or digital circuits. Here’s why:
Letf be a Boolean function ofkvariables. That is,f W fT;Fgk! fT;Fg.
WhenP is a propositional formula that has, among its variables, propositional
variables labelledX 1 ;:::;Xk. For any truth valuesb 1 ;:::;bk2fT;Fg, we let let
P.b 1 ;:::;bk/be the result of substitutingbifor all occurrences ofXiinP, for
1 ik.
IfPfis a formula such thatPf.b 1 ;:::;bk/is satisfiable exactly whenf.b 1 ;:::;bk/D
T, we’ll say thatPfSAT-representsf.
Suppose there is a digital circuit using two-input, one-output binary gates (like
the circuits for binary addition in Problems 3.5 and 3.6) that hasnwires and com-
putes the functionf. Explain how to construct a formulaPfof sizecnthat SAT-
representsffor some small constantc. (LettingcD 6 will work).
Conclude that the SAT problem for digital circuits—that is, determining if there
is some set of input values that will lead a circuit to give output 1—is no more
difficult than the SAT problem for propositional formulas.
Hint:Introduce a new variable for each wire. The idea is similar to the one used
in Problem 3.17 to show that satisfiablity of 3CNF propositional formmulas is just
as hard as for arbitrary formulas.
Problems for Section 3.6
Practice Problems
Problem 3.19.
For each of the following propositions:
- 8 x 9 y: 2x yD 0