Predicate logic extends propositional logic by introducing predicates (functions that return true or false depending on their input) and quantifiers ("for all" and "there exists"). This lets you make statements about entire collections of objects rather than just fixed true/false propositions. You will translate English claims into quantified expressions, choose the right quantifiers based on the domain, evaluate argument validity using quantified statements, and write basic proofs.
Difficulty: Introductory to Intermediate
Prerequisites: Propositional logic (connectives, truth tables, implication, contrapositive). Read the propositional logic study notes first if any of those terms are unfamiliar.
Predicate logic is the second major topic in CS 182, following directly from propositional logic. Where propositional logic handles fixed statements ("it is sunny"), predicate logic lets you reason about objects and their properties ("for every prime number greater than 3, it is congruent to 1 or 5 mod 6"). This is the language used in mathematical proofs, formal specifications, and database queries. Nearly every proof you write for the rest of the course will use quantifiers, so fluency here is non-negotiable.
Predicate
A function that takes one or more variables and returns true or false. P(x) = "x is a prime number" is a predicate; it becomes a proposition only once you supply a specific value for x.
Think of it as a statement with a blank: fill in the blank and you get true or false.
Domain (universe of discourse, U)
The set of all possible values that a variable can take. The meaning of a quantified statement changes depending on the domain.
In simple terms, the domain is the pool of things you are talking about. "All x" means all x in the domain, not all x in existence.
Universal quantifier (∀, "for all")
∀x P(x) means P(x) is true for every x in the domain.
Think of it as: check every single element in the domain; if P holds for all of them, the statement is true.
Existential quantifier (∃, "there exists")
∃x P(x) means there is at least one x in the domain for which P(x) is true.
Think of it as: you only need to find one example.
Bound variable
A variable that appears within the scope of a quantifier. In ∀x P(x), x is bound.
Free variable
A variable that is not bound by any quantifier. An expression with free variables is not a proposition until those variables are given values or quantified.
Nested quantifiers
Multiple quantifiers applied in sequence. ∀x ∃y F(x, y) means "for every x, there is some y such that F(x, y)." The order matters: ∀x ∃y is not the same as ∃y ∀x (unless the domain is trivial).
Negation of quantifiers
¬(∀x P(x)) ≡ ∃x ¬P(x) and ¬(∃x P(x)) ≡ ∀x ¬P(x). To negate a quantified statement, flip the quantifier and negate the predicate.
In simple terms, "not everything is P" means "something is not P," and "nothing is P" means "for all x, x is not P."
Valid argument
An argument where the conclusion necessarily follows from the premises in every possible interpretation. Contrast with a sound argument, which is valid and has true premises.
Proof by contradiction
Assume the negation of what you want to prove, then derive a logical contradiction. The contradiction shows the assumption was false, so the original statement must be true.
Proof by contrapositive
To prove p → q, instead prove ¬q → ¬p. They are logically equivalent.
The domain changes everything. The same English sentence requires different logical expressions depending on what U (the domain) contains.
Example statement: "All prime numbers greater than 3 are equal to a multiple of 6, plus 1 or minus 1."
Let P(x) = "x is prime," Q(x) = "x > 3," R(x) = "x % 6 = 1 or x % 6 = 5."
U = all primes greater than 3: Every element already satisfies P(x) and Q(x), so the statement is simply ∀x R(x). No extra conditions needed.
U = all prime numbers: Elements satisfy P(x) automatically, but not all are greater than 3. So: ∀x (Q(x) → R(x)). "For every prime x, if x is greater than 3, then R(x)."
U = all positive integers: Elements need not be prime or greater than 3. So: ∀x ((P(x) ∧ Q(x)) → R(x)). "For every positive integer x, if x is prime and greater than 3, then R(x)."
The pattern: the narrower the domain, the fewer conditions you need in the antecedent.
A quantified statement of the form ∀x (P(x) → R(x)) tells you that R(x) holds whenever P(x) does. It does not tell you the converse.
Valid use: "31 % 6 ≠ 1 and 31 % 6 ≠ 5" (i.e., ¬R(31)), so by contrapositive of Statement 1, either 31 is not prime or 31 is not greater than 3. Since 31 > 3, it would follow that 31 is not prime. (In reality 31 % 6 = 1, so this hypothetical does not arise, but the reasoning pattern is valid.)
Invalid use (converse error): "31 % 6 = 1, therefore 31 is prime." This affirms the consequent. R(x) being true does not mean P(x) ∧ Q(x) is true. Many non-primes also satisfy R(x) (e.g., 25 % 6 = 1, but 25 is not prime).
Valid use (contrapositive): "52 % 6 ≠ 1 and 52 % 6 ≠ 5" means ¬R(52). Given the statement ∀x ((P(x) ∧ Q(x)) → R(x)), the contrapositive gives ¬R(52) → ¬(P(52) ∧ Q(52)). Since 52 > 3 (Q(52) is true), we conclude ¬P(52): 52 is not prime. This is a valid argument.
Let P(x) = "x is blue," Q(x) = "x is a kangaroo," R(x) = "x can leap tall buildings in a single bound," S(x) = "x wears a cape." Domain = all animals.
"No kangaroos are blue": ∀x (Q(x) → ¬P(x)), or equivalently ¬∃x (Q(x) ∧ P(x)).
"Some kangaroos wear capes": ∃x (Q(x) ∧ S(x)).
"All animals that wear capes can leap tall buildings": ∀x (S(x) → R(x)).
"Blue kangaroos do not wear capes": ∀x ((P(x) ∧ Q(x)) → ¬S(x)).
Argument (i): If "some kangaroos wear capes" and "all cape-wearers can leap tall buildings," then "some kangaroos can leap tall buildings."
∃x (Q(x) ∧ S(x)) gives us a specific animal, call it a, with Q(a) ∧ S(a).
∀x (S(x) → R(x)) applied to a gives S(a) → R(a). Since S(a) is true, R(a) is true.
So Q(a) ∧ R(a) is true, meaning ∃x (Q(x) ∧ R(x)). Valid.
Argument (ii): If "no kangaroos are blue," "all cape-wearers can leap," and "blue kangaroos do not wear capes," then "blue kangaroos cannot leap."
"No kangaroos are blue" means there are no blue kangaroos at all.
So the conclusion "blue kangaroos cannot leap" is vacuously true (there is nothing to contradict it), but the argument does not actually prove the conclusion through the premises about capes and leaping. The conclusion holds trivially because the subject class is empty.
Technically valid (the conclusion is true whenever the premises are), but worth noting the reasoning is vacuous.
Let F(x, y) = "x manages y." Domain = employees at a company.
"Marlene manages Kevin": F(Marlene, Kevin).
"Kevin doesn't manage anyone": ¬∃y F(Kevin, y), equivalently ∀y ¬F(Kevin, y).
"Lena manages everyone": ∀y F(Lena, y).
"Everyone is managed by someone": ∀x ∃y F(y, x). For every employee x, there exists some employee y who manages x.
"No one manages himself or herself": ∀x ¬F(x, x).
Note the quantifier order in "everyone is managed by someone": the ∀ comes first (for each person, find a manager), which allows different managers for different people. If you wrote ∃y ∀x F(y, x), that would mean one single person manages everyone.
Example: Prove that if m and n are integers and mn is even, then m is even or n is even.
Assume the opposite: mn is even, but m is odd and n is odd.
If m is odd, then m = 2a + 1 for some integer a.
If n is odd, then n = 2b + 1 for some integer b.
Then mn = (2a + 1)(2b + 1) = 4ab + 2a + 2b + 1 = 2(2ab + a + b) + 1.
This is odd, contradicting the premise that mn is even.
Therefore the assumption is false: at least one of m or n must be even.
Predicate logic is the formal language behind SQL queries (SELECT * FROM employees WHERE department = 'Engineering' is essentially ∃x with a predicate). It is also the basis of Prolog and other logic programming languages, formal software verification (proving that code meets its specification), and the mathematical foundations of type systems in programming languages.
Students often think ∀x ∃y and ∃y ∀x mean the same thing. They do not. The first says "for each x, you can find a y (possibly different for each x)." The second says "there is a single y that works for every x." The second is strictly stronger.
Students forget to adjust the logical expression when the domain changes. "All primes greater than 3 satisfy R" needs no P(x) guard when U is already restricted to primes greater than 3, but it needs the full (P(x) ∧ Q(x)) → R(x) when U is all positive integers.
Students confuse "no X is Y" with "some X is not Y." "No kangaroos are blue" is ∀x (Q(x) → ¬P(x)), which is much stronger than ∃x (Q(x) ∧ ¬P(x)), "some kangaroo is not blue."
Students assume that a vacuously true conclusion means the argument is invalid. If the premises make the subject class empty, the conclusion holds trivially, and the argument is technically valid.
⚠️ Domain sensitivity: expect a question where the same English statement must be translated under two or three different domains. Know how the expression changes.
⚠️ Quantifier order: if the exam gives ∀x ∃y vs. ∃y ∀x, you must explain why they differ.
⚠️ Affirming the consequent with quantifiers: a classic exam trap. ∀x (P(x) → R(x)) and R(a) do not let you conclude P(a).
⚠️ Proof by contradiction: expect at least one question requiring you to assume the negation and derive a contradiction, especially involving parity (even/odd) arguments.
True or False: ¬(∀x P(x)) is equivalent to ∀x ¬P(x).
Fill in the blank: "Some kangaroos wear capes" in predicate logic is ∃x (Q(x) ____ S(x)).
True or False: ∀x ∃y F(x, y) and ∃y ∀x F(x, y) are logically equivalent.
Fill in the blank: To prove p → q by contrapositive, you prove ____ → ____.
True or False: If ∀x (P(x) → R(x)) is true and R(a) is true, then P(a) must be true.
Answers: 1. False (it is ∃x ¬P(x)). 2. ∧ (conjunction, not implication). 3. False (quantifier order matters). 4. ¬q → ¬p. 5. False (affirming the consequent).
Q: Let P(x) = "x is a student" and Q(x) = "x has submitted the homework." Domain = all people. Write "Every student has submitted the homework" in predicate logic.
A: ∀x (P(x) → Q(x)).
Q: Using the same predicates, write "Some student has not submitted the homework."
A: ∃x (P(x) ∧ ¬Q(x)). Note the conjunction, not implication, with ∃.
Q: Let F(x, y) = "x manages y." Write "Everyone is managed by someone" and explain why it differs from "Someone manages everyone."
A: "Everyone is managed by someone" = ∀x ∃y F(y, x). "Someone manages everyone" = ∃y ∀x F(y, x). The first allows a different manager per person; the second requires a single person who manages all.
Q: Prove by contradiction that if n is an integer and n² is odd, then n is odd.
A: Assume n² is odd but n is even. Then n = 2k for some integer k. So n² = 4k² = 2(2k²), which is even. This contradicts the premise that n² is odd. Therefore n must be odd.
Q: Given ∀x ((P(x) ∧ Q(x)) → R(x)), and you know R(7) is false, what can you conclude about 7?
A: By the contrapositive, ¬R(7) → ¬(P(7) ∧ Q(7)), which means ¬P(7) ∨ ¬Q(7). So either 7 does not satisfy P, or 7 does not satisfy Q (or both).
Predicate logic is the gateway to mathematical proof techniques covered in the rest of CS 182: induction, strong induction, and structural induction all rely on quantified statements. It also connects to set theory (set-builder notation is predicate logic in disguise: {x | P(x)} = the set of all x satisfying predicate P). In later computer science courses, predicate logic appears in formal methods, database theory, and automated theorem proving.
predicate logic, first-order logic, FOL, quantifiers, universal quantifier, existential quantifier, for all, there exists, domain, universe of discourse, bound variable, free variable, nested quantifiers, negating quantifiers, predicate, argument validity, proof by contradiction, proof by contrapositive, vacuous truth, affirming the consequent, converse error, CS 182, foundations of computer science, discrete math, Purdue CS 182