Page 75 - Discrete Mathematics and Its Applications

54 1 / The Foundations: Logic and Proofs

19. Suppose that the domain of the propositional function e) Everyone is your friend and is perfect.
P(x) consists of the integers 1, 2, 3, 4, and 5. Express f) Not everybody is your friend or someone is not per-
these statements without using quantifiers, instead using fect.
only negations, disjunctions, and conjunctions. 26. Translate each of these statements into logical expres-
a) ∃xP(x) b) ∀xP(x) sions in three different ways by varying the domain and
c) ¬PxP(x) d) ¬HxP(x) by using predicates with one and with two variables.
e) ∀x((x = 3) → P(x)) ∨∃x¬P(x)
a) Someone in your school has visited Uzbekistan.
20. Suppose that the domain of the propositional function
b) Everyone in your class has studied calculus and C++.
P(x) consists of −5, −3, −1, 1, 3, and 5. Express these
c) No one in your school owns both a bicycle and a mo-
statements without using quantifiers, instead using only torcycle.
negations, disjunctions, and conjunctions.
d) There is a person in your school who is not happy.
a) ∃xP(x) b) ∀xP(x)
c) ∀x((x = 1) → P(x)) e) Everyone in your school was born in the twentieth
d) ∃x((x ≥ 0) ∧ P(x)) century.
e) ∃x(¬P(x)) ∧∀x((x < 0) → P(x)) 27. Translate each of these statements into logical expres-
sions in three different ways by varying the domain and
21. For each of these statements find a domain for which the
statement is true and a domain for which the statement is by using predicates with one and with two variables.
false. a) A student in your school has lived in Vietnam.
a) Everyone is studying discrete mathematics. b) There is a student in your school who cannot speak
b) Everyone is older than 21 years. Hindi.
c) Every two people have the same mother. c) A student in your school knows Java, Prolog, and
d) No two different people have the same grandmother. C++.
22. For each of these statements find a domain for which the d) Everyone in your class enjoys Thai food.
statement is true and a domain for which the statement is e) Someone in your class does not play hockey.
false. 28. Translate each of these statements into logical expres-
a) Everyone speaks Hindi. sions using predicates, quantifiers, and logical connec-
b) There is someone older than 21 years. tives.
c) Every two people have the same first name. a) Something is not in the correct place.
d) Someone knows more than two other people.
b) All tools are in the correct place and are in excellent
23. Translate in two ways each of these statements into logi- condition.
cal expressions using predicates, quantifiers, and logical c) Everything is in the correct place and in excellent con-
connectives. First, let the domain consist of the students dition.
in your class and second, let it consist of all people.
d) Nothing is in the correct place and is in excellent con-
a) Someone in your class can speak Hindi. dition.
b) Everyone in your class is friendly. e) One of your tools is not in the correct place, but it is
c) There is a person in your class who was not born in in excellent condition.
California.
d) A student in your class has been in a movie. 29. Express each of these statements using logical operators,
e) No student in your class has taken a course in logic predicates, and quantifiers.
programming. a) Some propositions are tautologies.
24. Translate in two ways each of these statements into logi- b) The negation of a contradiction is a tautology.
cal expressions using predicates, quantifiers, and logical c) The disjunction of two contingencies can be a tautol-
connectives. First, let the domain consist of the students ogy.
in your class and second, let it consist of all people. d) The conjunction of two tautologies is a tautology.
a) Everyone in your class has a cellular phone. 30. Suppose the domain of the propositional function P(x, y)
b) Somebody in your class has seen a foreign movie. consists of pairs x and y, where x is 1, 2, or 3 and y is
c) There is a person in your class who cannot swim. 1, 2, or 3. Write out these propositions using disjunctions
d) All students in your class can solve quadratic equa- and conjunctions.
tions. a) ∃x P(x, 3) b) ∀yP(1,y)
e) Some student in your class does not want to be rich.
c) ∃y¬P(2,y) d) ∀x ¬P(x, 2)
25. Translate each of these statements into logical expres- 31. Suppose that the domain of Q(x,y,z) consists of triples
sions using predicates, quantifiers, and logical connec- x, y, z, where x = 0, 1, or 2, y = 0 or1,and z = 0or 1.
tives.
Write out these propositions using disjunctions and con-
a) No one is perfect. junctions.
b) Not everyone is perfect.
c) All your friends are perfect. a) ∀yQ(0,y, 0) b) ∃xQ(x, 1, 1)
d) At least one of your friends is perfect. c) ∃z¬Q(0, 0,z) d) ∃x¬Q(x, 0, 1)