Source: Homework 02, Foundations of Computer Science (Purdue)
Tags: predicate logic, quantifiers, universal quantifier, existential quantifier, quantifier distribution, negation of quantified statements, predicate translation, CS 18200, discrete math, logic expressions
Difficulty: Intermediate | Prerequisites: Basic propositional logic (AND, OR, NOT, implications), familiarity with truth tables.
Predicate logic extends propositional logic by letting you make statements about objects in a domain, not just fixed true/false propositions. Where propositional logic says "it is raining," predicate logic says "for every city x, if x is coastal, then it rains in x." This is the formal language behind database queries, program verification, and mathematical proof. You need solid propositional logic (truth tables, connectives, implications) before this material will click.
Predicates are functions that return true or false depending on their inputs. Quantifiers (∀ and ∃) let you say whether a predicate holds for all elements or at least one. Translating English into predicate logic, distributing quantifiers, and pushing negations inward are the three core skills tested here.
Predicate
A statement whose truth value depends on one or more variables. P(x) is not true or false on its own; it becomes true or false once you substitute a specific value for x. Think of it as a template for a proposition, with blanks to fill in.
Domain (or universe of discourse)
The set of all values that variables in your predicates can take. If the domain is "all homework questions," then x and y range over homework questions, nothing else. In simple terms, it is the boundary that tells you what your variables are allowed to be.
Universal quantifier (∀)
Read as "for all" or "for every." ∀x P(x) means P(x) is true for every single x in the domain. One counterexample is enough to make a universally quantified statement false.
Existential quantifier (∃)
Read as "there exists" or "for some." ∃x P(x) means there is at least one x in the domain for which P(x) is true. You only need one witness to make it true.
Bound variable
A variable that falls under the scope of a quantifier. In ∀x P(x), the variable x is bound by ∀.
Free variable
A variable not bound by any quantifier. A formula with free variables is not a proposition; it has no definite truth value until you either quantify or substitute.
The first skill is mapping natural-language sentences onto formal expressions. The approach:
Identify the domain (what are x and y ranging over?).
Identify the predicates and what they take as arguments.
Determine the quantifier structure: is the sentence about "all" things, or "some" things?
Watch for hidden implications: "Every A is B" typically translates to ∀x(A(x) → B(x)), not ∀x(A(x) ∧ B(x)).
Worked examples using the homework's predicates
The homework defines, for homework questions x and y:
E(x) = "x is easy"
C(x, y) = "x and y test the same concept"
W(x, y) = "x and y are written by the same person"
"Hard" simply means ¬E(x).
Example (a): "Easy questions are not written by the same person as hard questions."
This says: for any pair of questions x and y, if x is easy and y is hard, then x and y are not written by the same person.
∀x∀y((E(x) ∧ ¬E(y)) → ¬W(x, y))
The key move is recognising that "easy questions" and "hard questions" refer to two different variables, one easy and one not easy, and the claim is universal over all such pairs.
Example (b): "Every hard question tests the same concept as an easy question."
For every hard question, there exists some easy question that tests the same concept.
∀x(¬E(x) → ∃y(E(y) ∧ C(x, y)))
Notice the mixed quantifiers: the outer ∀ says "pick any hard question," and the inner ∃ says "there is at least one easy question paired with it."
Example (c): "Easy questions that test the same concept are written by the same person."
For any two easy questions that test the same concept, those two are written by the same person.
∀x∀y((E(x) ∧ E(y) ∧ C(x, y)) → W(x, y))
Quantifiers do not always distribute over connectives the way you might hope.
Existential quantifier over disjunction
∃x(P(x) ∨ Q(x)) is equivalent to ∃x P(x) ∨ ∃x Q(x).
If something in the domain satisfies P or Q, then either something satisfies P, or something satisfies Q (or both). This distribution works cleanly.
However, ∃x(P(x) ∨ ¬Q(x)) distributes to ∃x P(x) ∨ ∃x ¬Q(x), but you cannot push the quantifier past the negation further. The ∃x lands immediately before P(x) and immediately before ¬Q(x). That is as far as it goes.
Existential quantifier over implication: a trap
∃x(P(x) → Q(x)) is not equivalent to ∃x P(x) → ∃x Q(x).
This is a classic exam question. The left side says "there exists an x such that if P(x) then Q(x)." The right side says "if there exists an x with P(x), then there exists an x with Q(x)." These bind x differently: on the right, the two ∃x are independent, so the x satisfying P need not be the same x satisfying Q.
To see the gap concretely: let the domain be {1, 2}, P(1) = T, P(2) = F, Q(1) = F, Q(2) = T.
Left side: ∃x(P(x) → Q(x)). Try x = 2: P(2) → Q(2) = F → T = T. So the left side is true.
Right side: ∃x P(x) → ∃x Q(x). ∃x P(x) is true (x = 1). ∃x Q(x) is true (x = 2). So the right side is also true here.
Now flip Q(2) to F: P(1) = T, P(2) = F, Q(1) = F, Q(2) = F.
Left side: try x = 2: F → F = T. Still true.
Right side: ∃x P(x) = T, ∃x Q(x) = F. T → F = F. Now false.
The left can be true while the right is false, so they are not equivalent.
The rules for pushing negation inward through quantifiers:
¬∀x P(x) ≡ ∃x ¬P(x)
¬∃x P(x) ≡ ∀x ¬P(x)
Each quantifier flips to the other, and the negation moves one layer deeper. You then apply De Morgan's laws or implication identities to continue pushing negation to the predicates.
Worked example: negate ∃x∀y(P(x, y) ∨ Q(y))
Step 1 – Negate the outer ∃:
¬∃x∀y(P(x, y) ∨ Q(y)) ≡ ∀x ¬∀y(P(x, y) ∨ Q(y))
Rule used: ¬∃ becomes ∀¬.
Step 2 – Push negation past the inner ∀:
∀x ∃y ¬(P(x, y) ∨ Q(y))
Rule used: ¬∀ becomes ∃¬.
Step 3 – Apply De Morgan's law to the disjunction:
∀x ∃y (¬P(x, y) ∧ ¬Q(y))
Rule used: ¬(A ∨ B) ≡ ¬A ∧ ¬B.
The negation symbols now sit directly in front of the predicates. Each step is mechanical: flip the quantifier, move the ¬ inward, repeat until ¬ is adjacent to a predicate, then use De Morgan.
Quantifier negation rules (the two you must memorise):
¬∀x P(x) ≡ ∃x ¬P(x)
¬∃x P(x) ≡ ∀x ¬P(x)
De Morgan's laws for propositional connectives:
¬(A ∧ B) ≡ ¬A ∨ ¬B
¬(A ∨ B) ≡ ¬A ∧ ¬B
Implication rewrite:
P → Q ≡ ¬P ∨ Q
Universal vs existential with implication vs conjunction:
"Every A is B" = ∀x(A(x) → B(x))
"Some A is B" = ∃x(A(x) ∧ B(x))
Note the connective changes: universal uses →, existential uses ∧. Mixing these up is one of the most common errors.
Predicate logic is the foundation of SQL queries: SELECT * FROM users WHERE age > 18 is essentially ∃x(User(x) ∧ Age(x) > 18). Every database query you write is predicate logic in disguise.
Quantifier negation shows up whenever you negate a specification in software verification. "Not every input produces correct output" becomes "there exists an input that produces incorrect output," which is exactly how you think about finding bugs.
Students often write ∀x(A(x) ∧ B(x)) for "every A is B." The correct form uses →, not ∧. The conjunction version says everything in the domain is both A and B, which is far stronger than intended.
Thinking ∃x(P(x) → Q(x)) and ∃xP(x) → ∃xQ(x) are equivalent. They are not. The scope of x differs: in the first, one x satisfies the whole implication; in the second, different x's can satisfy P and Q independently.
Forgetting that "hard" is just ¬E(x), not a separate predicate. The homework gives you E(x) for "easy" and expects you to express "hard" as its negation.
Stopping a negation too early. Students push ¬ past quantifiers but forget to apply De Morgan's to the connectives inside. The negation must reach the predicates themselves.
⚠️ Translating English to predicate logic is nearly guaranteed on exams. Practise with varied sentence structures, especially ones mixing ∀ and ∃.
⚠️ The non-equivalence of ∃x(P(x) → Q(x)) and ∃xP(x) → ∃xQ(x) is a classic exam trap. Be ready to give a counterexample.
⚠️ Negation pushdown (flipping quantifiers and applying De Morgan's) appears both as a standalone problem and as a step inside proof questions.
True or false: ∀x(P(x) ∧ Q(x)) is equivalent to ∀xP(x) ∧ ∀xQ(x). True. Universal quantifiers distribute over conjunction.
True or false: ∃x(P(x) ∧ Q(x)) is equivalent to ∃xP(x) ∧ ∃xQ(x). False. The left requires one x satisfying both; the right allows different witnesses.
Fill in the blank: ¬∀x∃y R(x, y) ≡ ∃x ___. ∀y ¬R(x, y).
True or false: "Some cats are black" translates to ∀x(Cat(x) → Black(x)). False. It should be ∃x(Cat(x) ∧ Black(x)).
Q: Translate "Every student who studies passes the exam" into predicate logic, where S(x) = "x studies" and P(x) = "x passes the exam," with domain = all students.
A: ∀x(S(x) → P(x)).
Q: Negate the statement ∀x∃y(P(x) → Q(x, y)) so that negation symbols immediately precede predicates.
A: ∃x∀y(P(x) ∧ ¬Q(x, y)). Steps: ¬∀x becomes ∃x¬, then ¬∃y becomes ∀y¬, then ¬(P(x) → Q(x,y)) ≡ ¬(¬P(x) ∨ Q(x,y)) ≡ P(x) ∧ ¬Q(x,y).
Q: Are ∃x(P(x) → Q(x)) and ∃xP(x) → ∃xQ(x) logically equivalent? Justify your answer.
A: No. A counterexample: domain {1, 2}, P(1) = T, P(2) = F, Q(1) = F, Q(2) = F. Left side: x = 2 gives F → F = T, so the left is true. Right side: T → F = F, so the right is false.
Q: Write "No easy question tests the same concept as itself" in predicate logic using E(x) and C(x, y).
A: ∀x(E(x) → ¬C(x, x)). Equivalently, ¬∃x(E(x) ∧ C(x, x)).
Q: What is the negation of "there exists an x such that for all y, P(x, y) or Q(y)"?
A: ∀x∃y(¬P(x, y) ∧ ¬Q(y)).
This material connects directly to set theory (Chapter 2/3 in most discrete math texts), because set-builder notation {x | P(x)} is just predicate logic with curly brackets. It also underpins mathematical induction, since the inductive step is a universally quantified implication: ∀k(P(k) → P(k+1)).
If you go on to databases or formal methods courses, predicate logic is the language you will use daily, so comfort with translation and negation here pays forward significantly.
predicate logic, first-order logic, FOL, quantifiers, universal quantifier, for all, existential quantifier, there exists, quantifier distribution, negation of quantifiers, De Morgan's laws, bound variable, free variable, predicate translation, English to logic, CS 18200, discrete mathematics, Purdue, logic expressions, domain of discourse, universe of discourse