Page 74 - Discrete Mathematics and Its Applications

1.4 Predicates and Quantifiers 53

Exercises

1. Let P(x) denote the statement “x ≤ 4.” What are these 10. Let C(x) be the statement “x has a cat,” let D(x) be the
truth values? statement “x has a dog,” and let F(x) be the statement “x
a) P(0) b) P(4) c) P(6) has a ferret.” Express each of these statements in terms of
C(x), D(x), F(x), quantifiers, and logical connectives.
2. Let P(x) be the statement “the word x contains the
letter a.” What are these truth values? Let the domain consist of all students in your class.
a) A student in your class has a cat, a dog, and a ferret.
a) P(orange) b) P(lemon)
c) P(true) d) P(false) b) All students in your class have a cat, a dog, or a ferret.
3. Let Q(x, y) denote the statement “x is the capital of y.” c) Some student in your class has a cat and a ferret, but
What are these truth values? not a dog.
a) Q(Denver, Colorado) d) No student in your class has a cat, a dog, and a ferret.
b) Q(Detroit, Michigan) e) For each of the three animals, cats, dogs, and ferrets,
c) Q(Massachusetts, Boston) there is a student in your class who has this animal as
d) Q(New York, New York) a pet.
2
4. Statethevalueofx afterthestatementifP(x)thenx := 1 11. Let P(x) be the statement “x = x .” If the domain con-
is executed, where P(x) is the statement “x> 1,” if the sists of the integers, what are these truth values?
value of x when this statement is reached is a) P(0) b) P(1) c) P(2)
a) x = 0. b) x = 1. d) P(−1) e) ∃xP(x) f) ∀xP(x)
c) x = 2. 12. Let Q(x) be the statement “x + 1 > 2x.” If the domain
5. Let P(x) be the statement “x spends more than five hours consists of all integers, what are these truth values?
every weekday in class,” where the domain for x consists a) Q(0) b) Q(−1) c) Q(1)
of all students. Express each of these quantifications in d) ∃xQ(x) e) ∀xQ(x) f) ∃x¬Q(x)
English.
g) ∀x¬Q(x)
a) ∃xP (x) b) ∀xP(x)
13. Determine the truth value of each of these statements if
c) ∃x ¬P(x) d) ∀x ¬P(x)
the domain consists of all integers.
6. Let N(x) be the statement “x has visited North Dakota,” a) ∀n(n + 1 >n) b) ∃n(2n = 3n)
where the domain consists of the students in your school.
Express each of these quantifications in English. c) ∃n(n =−n) d) ∀n(3n ≤ 4n)
14. Determine the truth value of each of these statements if
a) ∃xN(x) b) ∀xN(x) c) ¬PxN(x)
the domain consists of all real numbers.
d) ∃x¬N(x) e) ¬HxN(x) f) ∀x¬N(x) 3 4 2
a) ∃x(x =−1) b) ∃x(x <x )
7. Translate these statements into English, where C(x) is “x 2 2
is a comedian” and F(x) is “x is funny” and the domain c) ∀x((−x) = x ) d) ∀x(2x> x)
consists of all people. 15. Determine the truth value of each of these statements if
a) ∀x(C(x) → F(x)) b) ∀x(C(x) ∧ F(x)) the domain for all variables consists of all integers.
2
2
c) ∃x(C(x) → F(x)) d) ∃x(C(x) ∧ F(x)) a) ∀n(n ≥ 0) b) ∃n(n = 2)
2
2
8. Translate these statements into English, where R(x) is “x c) ∀n(n ≥ n) d) ∃n(n < 0)
is a rabbit” and H(x) is “x hops” and the domain consists 16. Determine the truth value of each of these statements if
of all animals. thedomainofeachvariableconsistsofallrealnumbers.
2
2
a) ∀x(R(x) → H(x)) b) ∀x(R(x) ∧ H(x)) a) ∃x(x = 2) b) ∃x(x =−1)
2
c) ∃x(R(x) → H(x)) d) ∃x(R(x) ∧ H(x)) c) ∀x(x + 2 ≥ 1) d) ∀x(x = x)
2
9. Let P(x) be the statement “x can speak Russian” and let 17. Suppose that the domain of the propositional function
Q(x) be the statement “x knows the computer language P(x) consists of the integers 0, 1, 2, 3, and 4. Write out
C++.” Express each of these sentences in terms of P(x), each of these propositions using disjunctions, conjunc-
Q(x), quantifiers, and logical connectives. The domain tions, and negations.
for quantifiers consists of all students at your school.
a) ∃xP(x) b) ∀xP(x) c) ∃x¬P(x)
a) There is a student at your school who can speak Rus-
d) ∀x¬P(x) e) ¬PxP(x) f) ¬HxP(x)
sian and who knows C++.
18. Suppose that the domain of the propositional function
b) There is a student at your school who can speak Rus- P(x) consists of the integers −2, −1, 0, 1, and 2. Write
sian but who doesn’t know C++.
out each of these propositions using disjunctions, con-
c) Every student at your school either can speak Russian
junctions, and negations.
or knows C++.
a) ∃xP(x) b) ∀xP(x) c) ∃x¬P(x)
d) No student at your school can speak Russian or knows
C++. d) ∀x¬P(x) e) ¬PxP(x) f) ¬HxP(x)