3.6. Predicate Formulas 65
using addition, multiplication, and equality symbols, and nonnegative integercon-
stants 0 , 1 ,... ), but noexponentiation(likexy). For example, the predicate “n is
an even number” could be defined by either of the following formulas:
9 m: .2mDn/; 9 m: .mCmDn/:
(a)mis a divisor ofn.(b)nis a prime number.(c)nis a power of a prime.Problem 3.18.
Translate the following sentence into a predicate formula:
There is a student who has emailed exactly two other people in the
class, besides possibly herself.
The domain of discourse should be the set of students in the class; in addition,
the only predicates that you may use are
equality, and
E.x;y/, meaning that “xhas sent e-mail toy.”Exam Problems
Problem 3.19.
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 the implication above?- The predicateP.x;y/D‘yxD 1 ’ where the domain of discourse isQ.
- The predicateP.x;y/D‘y < x’ where the domain of discourse isR.
- The predicateP.x;y/ D‘yx D 2 ’ where the domain of discourse isR
without 0. - The predicateP.x;y/D‘yxyDx’ where the domain of discourse is the
set of all binary strings, including the empty string.