Mathematics for Computer Science

Chapter 3 Logical Formulas78

Exam Problems

Problem 3.32.

The following predicate logic formula is invalid:

8 x; 9 y:P.x;y/!9y; 8 x:P.x;y/

Which of the following are counter models for it?

1. The predicateP.x;y/D‘y
   xD 1 ’ where the domain of discourse isQ.


2. The predicateP.x;y/D‘y < x’ where the domain of discourse isR.


3. The predicateP.x;y/D‘y
   xD 2 ’ where the domain of discourse isR
   without 0.


4. The predicateP.x;y/D‘yxyDx’ where the domain of discourse is the
   set of all binary strings, including the empty string.

Problem 3.33.
Some students from a large class will be lined up left to right. There will be at least
two stduents in the line. Translate each of the following assertions into predicate
formulas with the set of students in the class as the domain of discourse. The only
predicates you may use are

 equality and,

 F.x;y/, meaning that “xis somewhere to the left ofyin the line.” For

example, in the line “CDA”, bothF.C;A/andF.C;D/are true.

Once you have defined a formula for a predicatePyou may use the abbreviation
“P” in further formulas.

(a)Studentxis in the line.

(b)Studentxis first in line.

(c)Studentxis immediately to the right of studenty.

(d)Studentxis second.