Mathematics for Computer Science

(Frankie) #1

Chapter 3 Logical Formulas62


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


..P„ƒ‚...XOR
X 1

Q/„ƒ‚...XOR
X 2

R/„ƒ‚...OR
O

.P„ƒ‚...AND
A

S/:


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


X 1 IFF.PXORQ/;
X 2 IFF.X 1 XORR/;
AIFF.PANDS/;
OIFFX 2 XORA:

(a)Explain why theANDof the above four constraining formulas will be satisfi-
able iff (3.32) is satisfiable.


(b)Explain why any 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.


Problems for Section 3.6


Class Problems


Problem 3.13.
A media tycoon has an idea for an all-news television network called LNN: The
Logic News Network. Each segment will begin with a definition of the domain of
discourse and a few predicates. The day’s happenings can then be communicated
concisely in logic notation. For example, a broadcast might begin as follows:


THIS IS LNN. The domain of discourse is

fAlbert;Ben;Claire;David;Emilyg:

LetD.x/be a predicate that is true ifxis deceitful. LetL.x;y/
be a predicate that is true ifxlikesy. LetG.x;y/be a predicate that
is true ifxgave gifts toy.

Translate the following broadcasted logic notation into (English) statements.
Free download pdf