Questions: Introduction to Predicate Logic (First-Order Logic)

Question 1

In propositional logic, you represent 'Socrates is mortal' as atom P and 'Plato is mortal' as atom Q. Why can you NOT use propositional logic to prove 'Socrates is mortal' from 'All humans are mortal' and 'Socrates is human'?

• A. You can — just define P = 'Socrates is mortal' and derive it from other atoms using modus ponens
• B. Propositional logic can't represent the universal claim 'All humans are mortal' — it would need a separate atom for every individual human, with no formal connection between them
• C. Propositional logic is too slow to evaluate syllogisms with more than two premises
• D. The argument is invalid, so neither logic system can prove it

Answer: (B)

This is the core limitation predicate logic was designed to fix. In propositional logic, 'All humans are mortal' would require an infinite set of independent atoms (P₁ = 'Alice is mortal', P₂ = 'Bob is mortal', ...) with no formal link between them and 'x is human'. There is no way to express quantification over a domain. Predicate logic introduces ∀x Human(x) → Mortal(x), which formally connects the universal claim to any specific individual via instantiation.

Question 2

A student argues: 'Predicate logic is just propositional logic with better notation — they're equally powerful, predicate logic is just more convenient.' What is the strongest objection to this claim?

• A. Predicate logic uses more symbols, which makes it harder to read
• B. Predicate logic is fundamentally more expressive: it can quantify over infinite domains and express relations, neither of which propositional logic can do
• C. Predicate logic can only be used in mathematics, while propositional logic is general-purpose
• D. Propositional logic handles temporal reasoning better than predicate logic does

Answer: (B)

The difference is not aesthetic — it's a difference in expressive power that has concrete computational consequences. Propositional logic is decidable (truth tables determine validity for any formula). Predicate logic is undecidable: Church and Turing proved in 1936 that no algorithm can determine whether an arbitrary first-order formula is valid. This is not a limitation of current technology; it's a fundamental theorem. The extra expressiveness (universal and existential quantification over infinite domains) comes with this unavoidable computational cost.

Question 3

The statement ∀x Human(x) → Mortal(x) is a valid formula in predicate logic that could not be expressed as a single formula in propositional logic.

• T. True
• F. False

Answer: True

This formula uses a universal quantifier ranging over a domain of objects — a feature predicate logic adds that propositional logic lacks entirely. In propositional logic, you can only have atomic propositions and truth-functional connectives. There is no mechanism to say 'for all objects x in the domain.' Predicate logic's ability to express universal and existential claims about entire domains is precisely what makes it strictly more expressive.

Question 4

Because predicate logic is undecidable, it is very difficult to prove any theorem in first-order logic — most proofs should be carried out informally.

• T. True
• F. False

Answer: False

Undecidability means there is no algorithm that correctly decides validity for *all* first-order formulas. It does not mean proofs are impossible. For specific formulas, proofs can often be constructed (and verified mechanically). Proof assistants like Coq and Lean verify first-order proofs formally. Undecidability only means you can't write a program that halts on all inputs with a correct yes/no answer — you can still enumerate and check valid proofs, you just can't guarantee finding them for every formula.

Question 5

What is the key structural difference between propositional and predicate logic, and why does that difference make predicate logic undecidable when propositional logic is decidable?

Model answer: Propositional logic has finitely many atomic propositions, so a formula with n distinct atoms has exactly 2^n truth assignments to check — truth tables always terminate. Predicate logic introduces quantifiers over potentially infinite domains, meaning there is no finite procedure to check all possible interpretations. A formula like ∃x P(x) could be true in one domain and false in another, and verifying it requires reasoning about all possible domain structures.

The undecidability of predicate logic (the Entscheidungsproblem) is one of the foundational results in mathematical logic and theoretical computer science. Church proved it using lambda calculus; Turing proved it using Turing machines — and these proofs were among the first results that defined the limits of what algorithms can compute. Propositional logic avoids this because the domain of truth values is just {T, F} — finite and fixed.