Homework: Predicates and Quantifiers
Atiq Rahman
May 24, 2025
Instructions: Please answer the following questions based on the concepts presented in the lecture
slides. Be sure to define your domains and predicates clearly.
1. Propositional Functions
Let the predicate P(x) be the statement ”x2 > 10”, where the domain for x consists of all integers.
What are the truth values of the following propositions?
(a) P(2)
(b) P(4)
(c) P(-3)
(d) P(-4)
2. Universal and Existential Quantification
Let the domain for x be the set of all real numbers, R. Determine the truth value of the following
statements and provide a brief justification for your answer.
(a) ∀x(x2 ≥ x)
(b) ∃x(x2 = −1)
(c) ∀x(x + 1 > x)
(d) ∃x(x/2 = 2x)
3. Uniqueness Quantifier
Let the domain for x be the set of all integers, Z. What are the truth values of the following
statements? Explain why each is true or false.
(a) ∃!x(x2 = 1)
(b) ∃!x(x + 3 = 5)
4. Translating English into Logical Expressions
Let the domain consist of all students in your class. Define the following predicates:
• M(x): ”x is a math major.”
• CS(x): ”x is a computer science major.”
• T(x, y): ”x has taken course y.”
Translate the following English sentences into logical expressions using quantifiers.
(a) ”There is a math major in the class.”
(b) ”Every student in the class is a computer science major.”
(c) ”Every student in the class has taken Calculus I.”
(d) ”Some student in the class is both a math major and a computer science major.”
1
5. Negating Quantified Expressions
Using De Morgan’s Laws for quantifiers, find the negation of the following statements. Your final
answer must not have a negation symbol to the left of a quantifier.
(a) ∀x(x2 > 0)
(b) ∃x(x is even)
(c) ∀x(P (x) → Q(x))
6. Nested Quantifiers
Let the domain for variables x and y be the set of all integers, Z. Let P(x, y) be the statement
”x + y = 0”. Determine the truth value of each of the following quantifications and provide a
reason for your answer.
(a) ∀x∀yP (x, y)
(b) ∀x∃yP (x, y)
(c) ∃x∀yP (x, y)
(d) ∃x∃yP (x, y)
7. Order of Quantifiers
Explain the difference in meaning between the statements ∀x∃yP (x, y) and ∃y∀xP (x, y). Provide
your own example of a predicate P(x, y) and a domain where one of these statements is true and
the other is false.
8. Translating Nested Quantifiers
Let the domain for x and y be all people. Let F(x, y) be the predicate ”x is friends with y.”
Translate the following logical expression into a clear and natural English sentence:
∃x∀y(F (x, y) → ¬∃z((z ̸= x) ∧ F (y, z)))
9. Free and Bound Variables
For each logical expression below, identify all free and bound variables. Then, state whether the
expression is a proposition or a predicate (propositional function).
(a) ∀x(P (x, y) ∨ Q(x))
(b) ∃x(D(x) ∧ C(x))
(c) ∃xP (x) ∨ Q(x)
(d) ∀x∃y(R(x, y, z))
10. Quantifier Equivalence
As shown in the slides, (∃xP (x)) ∧ (∃xQ(x)) is not logically equivalent to ∃x(P (x) ∧ Q(x)). Provide
a domain and define predicates P(x) and Q(x) that serve as a counterexample to show this non-
equivalence. You must show that one statement is true while the other is false for your chosen
example.