Mathematics for Computer Science

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.