1. Let N(x) be "x has visited North Dakota." Let U = students at CSUB.
Express each of these quantifications in English.
a) ∀x N(x)
b) ~(∃x N(x))
2. P(x): x has a cat. Q(x): x has a dog. R(x): x has a ferret. The universe
of discourse is all students in class. Write in predicate logic:
a) Some student in your class has a dog, a cat, and a ferret.
b) Everyone in your class has a dog, a cat, or a ferret.
3. Determine the truth value of these statements if the universe of discourse
is all rational numbers; i.e., can the statement be satisfied?
a) ∃x(x^3 = -1)
b) ∃x(x^4 < x^2)
4. Assume the universe of discourse of P(x) consists of x in {1,2,3}. Rewrite
these propositions with disjunctions or conjunctions (remove quantifiers).
a) ∃xP(x)
b) ∀xP(x)
5. Express the negation of these propositions using quantifiers and then in
English. The universe is all drivers and P(x) is x obeys the speed limit.
a) Some drivers do not obey the speed limit.
b) All Swedish movies are serious. The universe is all Swedish movies. The
predicate P(x) means movie x is serious.
6. Which of these is an accurate translation of a system specification where
the predicate P(x,y) is "x is in state y" and the universe of x and y is
all systems and all possible states, respectively:
∃xP(x,open) | ∃xP(x,diagnostic)
A. Some system is in an open state or some system is in a diagnostic state.
B. There is some system that is either open or is in a diagnostic state.
C. Both are accurate
7. Remove quantifiers and express the meaning in logic. Assume U = {a,b,c}
a) ∀x(P(x) ^ Q(x))
b) ∀xP(x) ^ ∀xQ(x)
c) ∀x(P(x) v Q(x))
d) ∀xP(x) v ∀xQ(x)
8. Using your answer to (c) and (d) above, show why ∀x(P(x) v Q(x)) and
∀xP(x) v ∀xQ(x) are not logically equivalent.
9. Show why ∃x(P(x)^Q(x)) and ∃xP(x) ^ ∃xQ(x) are not equivalent.
10. An expression is in conjunctive normal form (CNF) if E is a conjunction of
clauses, where each clause is a disjunction of literals and where the not
operator is only present as part of a literal.
Example of a valid CNF: (p v q) ^ (~q ) ^ (r v ~s) ^ (r v q v t)
Convert each of the following into CNF.
Hint: distribute OR over AND.
a. (p ^ q) v r
b. ~(p v q) v r
c. (p ^ q) v (r ^ s)
d. (a ^ b v ~c) ^ ( d v ~e ) v f // AND takes precedence over OR
Predicate Logic with Nested Quantifiers
11. If the universe of discourse for x and y is the set S = {1,2,3},
P(x,y) establishes relationships between 2-tuples in the set S x S:
{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)}
Rewrite these propositions by removing quantifers and using ∨ and ∧.
a) ∃x P(x,3)
b) ∀y P(1,y)
c) If ∀x ∀y P(x,y) is true, how many elements are there for which P(x,y) is true?
12. Let P(x,y) be the statement "student x has taken class y," where the
universe of discourse for x is all students at CSUB and for y is all CS
courses at CSUB. Express each of these quantifications in English.
a) ∃x ∃y P(x,y)
b) ∃x ∀y P(x,y)
c) ∀x ∃y P(x,y)
13. Translate the following into English. The universe of discourse is all
integers. State whether the statement is valid (always true), satisfiable
(true for at least one assignment of values), or not satisfiable (never
true). Recall that an expression is valid if it is a tautology.
a) ∃x ∀y (x + y = y)
b) ∀y∃x(x + y = y)
c) ∀y∀x(x + y = y)
14. Let F(x,y) be "x fools y" and U = all people in class. The location of the
variable determines its relationship to the predicate - not whether it is x
or y. F(x,y) is "x fools y" and F(y,x) is "y fools x". Express in logic:
a) Everybody can fool Fred.
b) Evelyn can fool everybody.
c) Everybody can fool somebody.
d) No one can fool everybody.
e) Everyone can be fooled by somebody.
f) No one can fool both Fred and Jerry.
g) Nancy can fool at least two people.
h) Nancy can fool exactly two people.
i) Nancy can fool no more than two people.
j) No one can fool himself or herself.
15. Let Q(x,y) be "x + y = x - y." If the universe of discourse x and y is the
set of integers, what are the truth values for the following predicates?
a) ∃xQ(x,2)
b) ∃y∀xQ(x,y)
16. Rewrite each statement to move the negations next to the predicates.
a) ~(∃y ∃xP(x,y))
b) ~(∀x ∃y P(x,y))
17. AIRLINE PROBLEM. Express each sentence in predicate logic, assuming
p is in P, where P = {all passengers at LAX}
f is in F, where F = {all flights at LAX}
a is in A, where A = {all airlines at LAX}
T(p,f): passenger p takes flight f.
O(a,f): airline a offers flight f.
a) "Some passenger has taken all flights offered by some airline."
b) "Some passenger has taken some flight on all airlines."
c) "There is some flight that all passengers have taken."
d) "There is some airline that all passengers have flown on."
Inference Rules
Give the name of the syllogism used in these arguments and state whether the
argument is valid or invalid.
18. If an animal is a bird then it has wings. Pooh doesn't have wings so Pooh
is not a bird.
19. Roos live in Austrialia and roos are marsupials. Roos are marsupials.
20. If Linda is an excellent swimmer then she can work as a lifeguard. Linda is
an excellent swimmer. I conclude she can work as a lifeguard.
21. If x^2 is irrational, then x is irrational. Since x is irrational, we
conclude that x^2 must be irrational.
22. If x^2 is irrational, then x is irrational. Since x^2 is not irrational,
we conclude that x must be not be irrational either.
23. You could win a dollar. Therefore, you could win a dollar or you could
win a million dollars.
24. The ball is orange or it is blue. The ball is red or it is not orange.
Therefore, the ball is blue or red.
25. If the sky is falling then Chicken Little is sane. If the moon is made of
cheese then the cow jumps over it. The sky is falling or the moon is made
of cheese. Therefore, Chicken Little is sane or the cow jumps over the moon.
26. This question refers to this argument:
"If it does not rain or it is not foggy then the sailing race will be
held and the lifesaving demo will go on. If the sailing race is held then
the trophy will be awarded. The trophy was not awarded. Therefore,
it rained and it is foggy." Assume:
r: It rains
f: It is foggy
s: Sailing Race will be held
d: Demo will go on
t: Trophy will be awarded
a) Express premise #1 in propositional logic.
b) Express premise #2 in propositional logic.
c) Express premise #3 in propositional logic.
d) Express the entire argument and the conclusion in propositional logic.
27. Apply inference rules and equivalences to show whether the argument above
is valid or not. (Valid means true premises lead to a true conclusion.)
28. The premises and conclusion in an argument might be expressed as statements
from predicate calculus. If so, you must convert the quantified statement
into a proposition to apply the inference rules. You then convert the
quantified statement back into a logical statement. See the inference rules
for quantifiers here. Assume:
"Everyone enrolled in CSUB has lived in a dormitory. Mia has never lived
in a dormitory. Therefore, Mia is not enrolled in CSUB."
Let the universe of discourse U be {all people in Bakersfield}. Let P(x)
mean x is enrolled at CSUB and Q(x) mean x lives in a dormitory.
Express the argument using predicate logic then provide a proof to show
whether the argument is valid or invalid.
29. Given the argument:
"All convertible cars are fun to drive. Pooh's car is not a convertible,
therefore Pooh's car is not fun to drive."
Let the universe of discourse U be all cars. Let the predicates be
P(x): x is a convertible and
Q(x): x is fun to drive
a) Express the argument using predicate logic.
b) Use logical equivalences to determine if the argument is valid or invalid.
30. Use logical equivalences to determine if the argument below is valid.
"Out of all theatre on Broadway, Pooh likes all the musicals. Pooh likes
Wit, therefore Wit is a musical." Assume:
PoohLikes(x): "Pooh likes x"
Musical(x): "x is musical."
U={all performances on Broadway}
a) First express the argument in predicate logic
b) Apply logical equivalences to show the argument as valid or invalid.
31. In this argument the Universe of Discourse is all cartoon characters.
"Someone is shorter than Mickey. Donald is shorter than someone. It follows
that Donald is shorter than Mickey." What is wrong with the argument,
expressed below in predicate form?
Shorter(x,y) be "x is shorter than y."
P1. Ex Shorter(x,Mickey)
P2. Ex Shorter(Donald,x)
------------------------
∴ Shorter(Donald,Mickey)
32. If you don't believe you will fall off the roof then you won't fall off.
Therefore, if you think you are going to fall off the roof then you will.
a) express the argument in propositional logic
b) State whether the argument is valid. If invalid, name the fallacy.
33. This argument is from the Death Scene in Princess Bride. Re-write Premise 1
using "If" and "then". Then state whether Vinzinni's argument is valid. If
invalid, name the fallacy.
P1. Only a fool would reach for the goblet put before him.
P2. I am not a fool.
---------------------
: I will not reach for the goblet put before me.