Mathematics for Computer Science

3.7. References 73

Problem 3.22.
Find a counter model showing the following is not valid.

Œ 9 x:P.x/AND 9 x:Q.x/çIMPLIES 9 x:ŒP.x/ANDQ.x/ç

(Just define your counter model. You do not need to verify that it is correct.)

Problem 3.23.
Which of the following arevalid?
(a) 9 x 9 y: P.x;y/IMPLIES 9 y 9 x: P.x;y/

(b) 8 x 9 y: Q.x;y/IMPLIES 9 y 8 x: Q.x;y/

(c) 9 x 8 y: R.x;y/IMPLIES 8 y 9 x: R.x;y/

(d) NOT. 9 x S.x// IFF 8 x NOT.S.x//

Class Problems

Problem 3.24.
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 broadcasts in logic notation into (English) statements.

(a)

NOT.D.Ben/ORD.David//IMPLIES.L.Albert;Ben/ANDL.Ben;Albert//

(b)

8 x..xDClaireAND NOT.L.x;Emily///OR.x¤ClaireANDL.x;Emily///AND

8 x..xDDavidANDL.x;Claire//OR.x¤DavidAND NOT.L.x;Claire////