Difficulty: Intermediate | Prerequisites: Basic propositional logic (truth values, AND, OR, NOT, implication), understanding of sets.
Predicate logic extends propositional logic by adding variables, predicates, and quantifiers, which lets you express statements about collections of objects rather than just fixed true/false propositions. This is the language used to write formal specifications, database queries, and mathematical theorems precisely. Tautology identification (without truth tables) tests whether you can reason about logical structure itself. You should be comfortable with basic connectives and truth tables before tackling this material.
Translating English statements into predicate logic means choosing the right quantifiers (∀ for "all," ∃ for "some") and connecting predicates with the right logical connectives. Tautologies are propositions that are true under every possible assignment of truth values. You can identify them by structural reasoning rather than exhaustive truth tables.
Predicate
A function that takes one or more variables and returns true or false. For example, F(x) meaning "x is a freshman."
Think of it as a statement with a blank: "___ is a freshman" becomes true or false once you fill in a specific person.
Universal quantifier (∀)
The symbol ∀ means "for all" or "for every." The expression ∀x P(x) asserts that P(x) is true for every possible value of x in the domain.
In simple terms, every single element satisfies the condition, no exceptions.
Existential quantifier (∃)
The symbol ∃ means "there exists" or "for some." The expression ∃x P(x) asserts that at least one value of x makes P(x) true.
In simple terms, at least one element out there satisfies the condition.
Tautology
A compound proposition that is true for every possible combination of truth values of its component propositions.
Think of it as a formula that cannot possibly be false, regardless of what you plug in.
Contradiction
A compound proposition that is false for every possible combination of truth values.
In simple terms, the opposite of a tautology: it can never be true.
Implication (p → q)
A logical connective meaning "if p then q." It is false only when p is true and q is false. In all other cases, it is true.
The key insight students miss: an implication with a false premise is always true, regardless of the conclusion.
Given predicates: A(y) = "y is an advanced course," S(x) = "x is a sophomore," F(x) = "x is a freshman," T(x, y) = "x is taking y."
"There is an advanced course that every freshman is taking."
Translation: ∃y ∀x (A(y) ∧ (F(x) → T(x, y)))
Read it inside out: there exists some course y such that y is advanced AND for every student x, if x is a freshman then x is taking y.
The existential quantifier is outermost because one specific course must exist first, then every freshman must be taking that same course.
Note the implication after ∀x: "every freshman" means "for all x, if x is a freshman, then..." You do not use ∧ with ∀ when restricting a domain. That is a common error.
"No freshman is a sophomore."
Translation: ∀x (F(x) → ¬S(x))
"No freshman" means "for all x, if x is a freshman, then x is not a sophomore."
An equivalent form: ¬∃x (F(x) ∧ S(x)), meaning "there does not exist an x that is both a freshman and a sophomore."
"Some freshman is taking an advanced course."
Translation: ∃x ∃y (F(x) ∧ A(y) ∧ T(x, y))
"Some" signals the existential quantifier. There exists a student x who is a freshman, and there exists a course y that is advanced, and x is taking y.
Note the conjunction (∧) after ∃: "some freshman" means "there exists an x such that x is a freshman AND..." You use ∧ with ∃ when restricting a domain, not implication.
∀ pairs with → (implication) when restricting the domain: "All freshmen do X" = ∀x (F(x) → X).
∃ pairs with ∧ (conjunction) when restricting the domain: "Some freshman does X" = ∃x (F(x) ∧ X).
Mixing these up (∀ with ∧ or ∃ with →) is one of the most frequent mistakes on exams.
p ∧ ¬p: Not a tautology.
This is a contradiction. It asserts that p is simultaneously true and false. There is no assignment of p that makes this true.
p ∧ ¬q → q: Not a tautology.
To check, look for a counterexample. Set p = true and q = false. Then p ∧ ¬q = true ∧ true = true. The implication becomes true → false = false. One false case is enough to disqualify a tautology.
(p ∧ q) → (p ∧ q): Tautology.
The left and right sides of the implication are identical. An implication P → P is always true: if P is true, the implication holds; if P is false, the implication holds vacuously (a false premise makes any implication true).
Recognise structural patterns first: P → P is always a tautology. P ∧ ¬P is always a contradiction.
For non-obvious cases, try to find a counterexample (one assignment that makes the proposition false). If you can, it is not a tautology.
If you cannot find a counterexample after trying all critical assignments, it is a tautology. You should be able to articulate why in a sentence or two.
\exists y \forall x \big( A(y) \land (F(x) \to T(x,y)) \big)\forall x \big( F(x) \to \neg S(x) \big)\exists x \exists y \big( F(x) \land A(y) \land T(x,y) \big)Predicate logic is the backbone of SQL database queries (SELECT, WHERE clauses are essentially predicate logic), formal software verification, and type systems in programming languages. Tautology checking is related to SAT solving, which underpins everything from circuit verification to AI planning algorithms.
Students frequently pair ∀ with ∧ when restricting a domain. "All freshmen take CS 182" is ∀x (F(x) → T(x, CS182)), not ∀x (F(x) ∧ T(x, CS182)). The second version claims every person in the universe is both a freshman and takes CS 182.
Students frequently pair ∃ with → when restricting a domain. "Some freshman takes CS 182" is ∃x (F(x) ∧ T(x, CS182)), not ∃x (F(x) → T(x, CS182)). The second version is true if any non-freshman exists, which is almost certainly not what you mean.
Students sometimes assume that any proposition involving an implication is a tautology. An implication can be false (when the antecedent is true and the consequent is false).
Students confuse "contradiction" and "not a tautology." A proposition can be neither a tautology nor a contradiction. p ∧ ¬q → q is not a tautology, but it is not a contradiction either (it is true when q is true).
⚠️ Expect translation problems on the exam. Know the quantifier pairing rules cold: ∀ with →, ∃ with ∧.
⚠️ "Which of these are tautologies?" is a standard exam question. Practise reasoning structurally rather than building full truth tables.
⚠️ Watch for the order of quantifiers. ∃y ∀x and ∀x ∃y mean different things. The first says one y works for every x. The second says each x gets its own y.
⚠️ Be prepared to express "no" statements. "No X is Y" = ∀x (X(x) → ¬Y(x)) or equivalently ¬∃x (X(x) ∧ Y(x)).
True or false: ∀x (F(x) ∧ S(x)) means "all freshmen are sophomores." False. It means every entity is both a freshman and a sophomore. The correct translation uses →, not ∧.
True or false: p ∧ ¬p is a tautology. False. It is a contradiction.
Fill in the blank: An implication is false only when the antecedent is ___ and the consequent is ___. True; false.
True or false: ∃y ∀x means the same as ∀x ∃y. False. Quantifier order matters.
Fill in the blank: "Some freshman is a sophomore" translates to ∃x (F(x) ___ S(x)). ∧ (conjunction).
Q: Translate "There is an advanced course that every freshman is taking" into predicate logic.
A: ∃y ∀x (A(y) ∧ (F(x) → T(x, y))). One course exists (existential y, outermost), and for every student (universal x), if that student is a freshman, they take that course.
Q: Why does "no freshman is a sophomore" use an implication rather than a conjunction?
A: Because the statement applies to all entities (∀x), and when a universal quantifier restricts a domain, you use implication: "for all x, if x is a freshman, then x is not a sophomore."
Q: Is p ∧ ¬q → q a tautology? Justify without a truth table.
A: No. Counterexample: p = true, q = false. Then p ∧ ¬q = true, and the implication true → false is false.
Q: Why is (p ∧ q) → (p ∧ q) a tautology?
A: The antecedent and consequent are identical. P → P is always true: if P is true the implication holds; if P is false the implication is vacuously true.
Q: What is the difference between ∃y ∀x P(x, y) and ∀x ∃y P(x, y)?
A: The first says there is one specific y that works for every x. The second says for each x there is some y (possibly different for each x). The first is a stronger claim.
Predicate logic connects to set theory (quantifiers correspond to set operations: ∀ to subset, ∃ to non-empty intersection), database theory (SQL WHERE clauses are predicate expressions), and proof writing (every mathematical proof operates within predicate logic). Tautology identification connects to Boolean algebra and circuit design, where tautologies correspond to circuits that always output 1.
predicate logic, first-order logic, quantifiers, universal quantifier, existential quantifier, for all, there exists, tautology, contradiction, implication, logical connectives, propositional logic, truth values, domain of discourse, nested quantifiers, quantifier order, CS 182, Purdue, discrete mathematics, foundations of computer science, SAT solving, Boolean algebra