7.3 First-Order Validity, Semantic Tableaux & Prenex Normal Form

Back to Discrete Mathematics Notes

📚Module 07: First-Order Predicate LogicTopic 7.3: First-Order Validity, Semantic Tableaux & Prenex Normal Form⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: Compiling High-Level Code to Assembly

Think of advanced first-order logic like compiler parsing and intermediate code generation:

1. First-Order Validity (Universal Truth across All Universes): In propositional logic, a tautology is true across a finite table of $2^n$ rows. In predicate logic, a valid formula must be true across every conceivable universe—whether the universe has 1 element, 5 elements, or an infinite continuum of numbers!
2. Prenex Normal Form (Hoisting Quantifiers): Just as JavaScript hoists variable declarations var x, y to the top of a function scope, Prenex Normal Form (PNF) pulls all quantifiers ($\forall, \exists$) out to the very front of the formula ($Q_1 x_1 Q_2 x_2 \dots$), leaving a clean, flat, quantifier-free logic circuit (the Matrix) behind.
3. The 4 Quantifier Inference Rules:
   • Universal Instantiation (UI): If a law applies to all citizens, it applies to Bob.
   • Universal Generalization (UG): If you proved a theorem for an arbitrary generic triangle without special assumptions, it holds for all triangles!
   • Existential Instantiation (EI): If a crime witness exists, name them "Witness X" (a fresh name not already used in court).
   • Existential Generalization (EG): If Bob solved the bug, then someone solved the bug!

💻 Bridging to Computer Science: SMT Solvers, Skolemization & Undecidability

In computer systems:

• Skolemization in SMT Solvers (Z3, CVC5): Before automated theorem provers can check first-order assertions, they convert formulas to PNF and replace existential variables with Skolem functions.
• Gödel vs Church-Turing: Gödel proved that first-order logic is Complete (every valid formula can be proven in finite steps). But Alonzo Church and Alan Turing proved it is Undecidable—no algorithm can exist that halts and decides whether an arbitrary first-order formula is valid (Entscheidungsproblem)!

📑Table of Contents

• 🏛️ Interpretations, Validity & Satisfiability
• 📐 The Master 10-Case Quantifier Distribution Matrix
  • Master 10-Case Quantifier Distribution Reference Table
• 🪟 Null Quantification Laws (Variable x Free of A)
• 📦 Prenex Normal Form (PNF) Conversion
• ⚙️ The Four Quantifier Rules of Inference
• 📝 Step-by-Step Worked Examples
  • Example 1: Converting a First-Order Formula to Prenex Normal Form
  • Example 2: Formal Deductive Proof in First-Order Logic
  • Example 3: Disproving an Invalid Quantifier Implication
• 🎯 Exam & Interview Pitfall Check

---

🏛️ Interpretations, Validity & Satisfiability

In propositional logic, an evaluation is simply an assignment of True or False to atomic letters. In First-Order Logic (FOL), an evaluation requires an entire mathematical universe called an Interpretation.

📖Definition 7.4: Interpretation & First-Order Modeldefinition

An Interpretation $\mathcal{I} = (D, \sigma)$ for a first-order language consists of:

1. A non-empty set $D$ called the Domain (or Universe).
2. An assignment $\sigma$ that maps:
   • Each constant symbol $c$ to a concrete element in $D$.
   • Each $k$-ary function symbol $f$ to a mapping $f^{\mathcal{I}}: D^k \to D$.
   • Each $k$-ary predicate symbol $P$ to a relation $P^{\mathcal{I}} \subseteq D^k$.

Classifications:

• Valid (Universal Tautology): A formula $\phi$ is valid if it evaluates to True in every possible interpretation $\mathcal{I}$ over every possible domain $D$.
• Satisfiable: A formula $\phi$ is satisfiable if there exists at least one interpretation $\mathcal{I}$ under which $\phi$ evaluates to True.
• Unsatisfiable (Contradiction): A formula $\phi$ is unsatisfiable if it evaluates to False in every interpretation.

---

📐 The Master 10-Case Quantifier Distribution Matrix

A classic question in competitive examinations (GATE) tests whether quantifiers distribute across $\lor$, $\land$, and $\to$:

📐Theorem 7.3: Quantifier Distributivity & Equivalencestheorem

1. Full Equivalences ($\equiv$):
   • Universal over Conjunction: $\forall x (P(x) \land Q(x)) \equiv (\forall x P(x)) \land (\forall x Q(x))$.
   • Existential over Disjunction: $\exists x (P(x) \lor Q(x)) \equiv (\exists x P(x)) \lor (\exists x Q(x))$.
2. One-Way Semi-Distributive Implications ($\implies$):
   • Existential over Conjunction is one-way: $\exists x (P(x) \land Q(x)) \implies (\exists x P(x)) \land (\exists x Q(x))$.
   • Universal over Disjunction is one-way: $(\forall x P(x)) \lor (\forall x Q(x)) \implies \forall x (P(x) \lor Q(x))$.
   • Universal over Implication is one-way: $\forall x (P(x) \to Q(x)) \implies (\forall x P(x) \to \forall x Q(x))$.

Master 10-Case Quantifier Distribution Reference Table

Index	Premise Form	Consequent Form	Validity Status	Mathematical Justification / Counterexample Valuation
1	$\exists x \big( P(x) \lor Q(x) \big)$	$\big( \exists x P(x) \big) \lor \big( \exists x Q(x) \big)$	Valid ($\equiv$)	Full Distributivity: Witness for $P$ or $Q$ suffices for both sides
2	$\big( \exists x P(x) \big) \lor \big( \exists x Q(x) \big)$	$\exists x \big( P(x) \lor Q(x) \big)$	Valid ($\equiv$)	Converse of Case 1 is strictly valid
3	$\exists x \big( P(x) \land Q(x) \big)$	$\big( \exists x P(x) \big) \land \big( \exists x Q(x) \big)$	Valid ($\implies$)	If single element satisfies both, separate witnesses trivially exist
4	$\big( \exists x P(x) \big) \land \big( \exists x Q(x) \big)$	$\exists x \big( P(x) \land Q(x) \big)$	INVALID	Counterexample: Over $\mathbb{Z}$, $P(x)$ = even, $Q(x)$ = odd (Separate witnesses exist, but no number is both!)
5	$\big( \forall x P(x) \big) \lor \big( \forall x Q(x) \big)$	$\forall x \big( P(x) \lor Q(x) \big)$	Valid ($\implies$)	If all are $P$ (or all are $Q$), then every element is $P \lor Q$
6	$\forall x \big( P(x) \lor Q(x) \big)$	$\big( \forall x P(x) \big) \lor \big( \forall x Q(x) \big)$	INVALID	Counterexample: Over $\mathbb{Z}$, every integer is even or odd, but not all are even nor all odd!
7	$\forall x \big( P(x) \land Q(x) \big)$	$\big( \forall x P(x) \big) \land \big( \forall x Q(x) \big)$	Valid ($\equiv$)	Full Distributivity: Conjunction holds for all iff each holds for all
8	$\big( \forall x P(x) \big) \land \big( \forall x Q(x) \big)$	$\forall x \big( P(x) \land Q(x) \big)$	Valid ($\equiv$)	Converse of Case 7 is strictly valid
9	$\forall x \big( P(x) \to Q(x) \big)$	$\big( \forall x P(x) \big) \to \big( \forall x Q(x) \big)$	Valid ($\implies$)	If $P(x) \to Q(x)$ holds everywhere, then all $P$ forces all $Q$
10	$\big( \forall x P(x) \big) \to \big( \forall x Q(x) \big)$	$\forall x \big( P(x) \to Q(x) \big)$	INVALID	Counterexample: Let $\forall x P(x)$ be False (antecedent vacuously True), but $P(a) = T, Q(a) = F$ for some element

---

🪟 Null Quantification Laws (Variable x Free of A)

⚡Law 7.3: Null Quantification & Quantifier Hoistinglaw

Let $A$ be a formula in which variable $x$ does NOT occur as a free variable:

1. Conjunction & Disjunction (Zero Quantifier Shift): $$\forall x \big( P(x) \land A \big) \equiv \big( \forall x P(x) \big) \land A$$ $$\forall x \big( P(x) \lor A \big) \equiv \big( \forall x P(x) \big) \lor A$$ $$\exists x \big( P(x) \land A \big) \equiv \big( \exists x P(x) \big) \land A$$ $$\exists x \big( P(x) \lor A \big) \equiv \big( \exists x P(x) \big) \lor A$$
2. Implication with Quantifier in Consequent (No Flip): $$\forall x \big( A \to P(x) \big) \equiv A \to \big( \forall x P(x) \big)$$ $$\exists x \big( A \to P(x) \big) \equiv A \to \big( \exists x P(x) \big)$$
3. Implication with Quantifier in Antecedent (QUANTIFIER FLIPS!): $$\forall x \big( P(x) \to A \big) \equiv \big( \exists x P(x) \big) \to A \quad (\forall \text{ flips to } \exists!)$$ $$\exists x \big( P(x) \to A \big) \equiv \big( \forall x P(x) \big) \to A \quad (\exists \text{ flips to } \forall!)$$

Algebraic Proof of the Antecedent Flip:

$$P(x) \to A \equiv \neg P(x) \lor A$$$$\forall x \big( P(x) \to A \big) \equiv \forall x \big( \neg P(x) \lor A \big) \equiv \big( \forall x \neg P(x) \big) \lor A$$

By Quantifier De Morgan: $\forall x \neg P(x) \equiv \neg \big( \exists x P(x) \big)$:

$$\neg \big( \exists x P(x) \big) \lor A \equiv \big( \exists x P(x) \big) \to A$$

---

📦 Prenex Normal Form (PNF) Conversion

📖Definition 7.5: Prenex Normal Form (PNF)definition

A first-order formula is in Prenex Normal Form (PNF) if it is structured as:

$$Q_1 x_1 \, Q_2 x_2 \, \dots \, Q_k x_k \, M(x_1, x_2, \dots, x_k)$$

where:

1. Each $Q_i \in \{\forall, \exists\}$ is a quantifier (the Prefix).
2. $M$ is a completely quantifier-free propositional logic formula (the Matrix).

The 4-Step Prenex Normal Form (PNF) Conversion Algorithm

Standardized procedure to hoist all quantifiers to the leftmost prefix

Step 1

Eliminate Conditionals & Biconditionals

✂️

Replace a → b with ¬a ∨ b and a ↔ b with (¬a ∨ b) ∧ (¬b ∨ a).

↓Pure {¬, ∧, ∨} Connectives

Step 2

Push Negations Inward (NNF)

📥

Apply De Morgan's laws: ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x).

↓Negation Sits Only at Atomic Predicates

Step 3

Standardize Variables Apart (Alpha-Conversion)

🏷️

Rename dummy variables so every quantifier binds a unique variable name (e.g., ∀x P(x) ∨ ∀x Q(x) ⟹ ∀x P(x) ∨ ∀y Q(y)).

↓Zero Variable Clashes

Step 4

Hoist Quantifiers to the Prefix

🚀

Apply Null Quantification laws to pull all quantifiers to the left of the expression.

---

⚙️ The Four Quantifier Rules of Inference

To extend propositional natural deduction to First-Order Logic, we introduce four formal quantifier rules:

The 4 Quantifier Inference Rules

Formal derivation rules bridging quantified formulas and individual instances

⬇️

Universal Instantiation (UI)

∀x P(x) ⊢ P(c)

• From ∀x P(x), deduce P(c) for ANY arbitrary element or constant c in the domain.
• Zero restrictions: if a property holds for all elements, it holds for c.
• Example: 'All humans are mortal' ⟹ 'Socrates is mortal'.

⬆️

Universal Generalization (UG)

P(c) ⊢ ∀x P(x)

• From P(c), deduce ∀x P(x), provided c is an ARBITRARY, generic element.
• Restriction: c must NOT appear in any prior un-discharged premises or hypotheses!
• Standard method of mathematical proof: 'Let c be an arbitrary integer...'.

🔓

Existential Instantiation (EI)

∃x P(x) ⊢ P(c)

• From ∃x P(x), deduce P(c) for a BRAND NEW constant symbol c.
• Strict Restriction: c must be a FRESH constant that has NEVER appeared anywhere earlier in the proof!
• Intuition: Name the unknown witness c; do not assume c is someone already known.

🔒

Existential Generalization (EG)

P(c) ⊢ ∃x P(x)

• From P(c) for a known specific element c, deduce ∃x P(x).
• Zero restrictions: if c has the property, then at least one such element exists.
• Example: '7 is prime' ⟹ 'There exists a prime number'.

---

📝 Step-by-Step Worked Examples

Example 1: Converting a First-Order Formula to Prenex Normal Form

Problem Statement: Convert the formula $\phi = \forall x P(x) \to \exists y Q(y)$ into Prenex Normal Form (PNF).

Step-by-Step Solution:

1. Step 1: Eliminate the implication ($\to$)

   • Apply $A \to B \equiv \neg A \lor B$: $$\phi = \neg \big( \forall x P(x) \big) \lor \exists y Q(y)$$

2. Step 2: Push negations inward using Quantifier De Morgan

   • Negate $\forall x P(x)$: $$\neg \big( \forall x P(x) \big) \equiv \exists x \, \neg P(x)$$
   • The expression becomes: $$\phi = \exists x \, \neg P(x) \lor \exists y Q(y)$$

3. Step 3: Standardize variables apart

   • The quantified variables are $x$ and $y$. They are already distinct! No renaming needed.

4. Step 4: Hoist quantifiers using Null Quantification

   • Variable $y$ does not appear in $\neg P(x)$, and variable $x$ does not appear in $Q(y)$.
   • Hoist $\exists x$: $$\exists x \big( \neg P(x) \lor \exists y Q(y) \big)$$
   • Hoist $\exists y$: $$\exists x \exists y \big( \neg P(x) \lor Q(y) \big)$$
   • Prefix: $\exists x \exists y$. Matrix: $(\neg P(x) \lor Q(y))$.

Key Takeaway: An implication with $\forall$ in the antecedent converts into an existential prefix ($\exists$) in PNF due to the negation of the antecedent!

---

Example 2: Formal Deductive Proof in First-Order Logic

Problem Statement: Prove the classic syllogism using first-order inference rules:

1. "All men are mortal": $\forall x (M(x) \to D(x))$
2. "Socrates is a man": $M(s)$
3. Prove: "Socrates is mortal": $D(s)$

Step-by-Step Solution:

Step	Formal Expression	Rule of Inference Applied
1	$\forall x (M(x) \to D(x))$	Premise 1
2	$M(s)$	Premise 2
3	$M(s) \to D(s)$	Universal Instantiation (UI) on Step 1 with $c = s$
4	$D(s)$	Modus Ponens on Steps 2 and 3

The conclusion $D(s)$ is derived cleanly in 4 formal steps.

---

Example 3: Disproving an Invalid Quantifier Implication

Problem Statement: Prove that $(\forall x P(x) \to \forall x Q(x)) \implies \forall x (P(x) \to Q(x))$ is INVALID by constructing a formal interpretation counterexample.

Step-by-Step Solution:

1. Choose Domain: Let $D = \{1, 2\}$.
2. Assign Predicates:
   • Let $P(1) = \mathbf{T}$ and $P(2) = \mathbf{F}$.
   • Let $Q(1) = \mathbf{F}$ and $Q(2) = \mathbf{T}$.
3. Evaluate the Antecedent: $(\forall x P(x)) \to (\forall x Q(x))$:
   • $\forall x P(x) \equiv P(1) \land P(2) \equiv T \land F = F$.
   • Since the hypothesis $\forall x P(x)$ is False, the antecedent $(\forall x P(x)) \to (\forall x Q(x))$ is vacuously True ($F \to \dots \equiv T$)!
4. Evaluate the Consequent: $\forall x (P(x) \to Q(x))$:
   • For $x = 1$: $P(1) \to Q(1) \equiv T \to F = F$ (False!).
   • Thus, $\forall x (P(x) \to Q(x))$ is False!
5. Conclusion:
   • Under this interpretation, $\text{Antecedent} = T$ while $\text{Consequent} = F$.
   • Therefore, the implication is INVALID!

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: Is First-Order Logic decidable? Key Focus Points: No! By Church's Theorem and Turing's Undecidability Theorem (1936), First-Order Logic is semi-decidable (recursively enumerable), but NOT decidable. If a formula is valid, a resolution refutation will eventually find a proof in finite time. But if a formula is invalid, an automated prover may loop forever without halting!

Question 2: Why does Existential Instantiation (EI) require a fresh, unused constant symbol? Key Focus Points: If $\exists x P(x)$ is known, using an existing constant (say, $c$) assumes that the witness is an already-known entity. For example, if you know "Someone committed the robbery" ($\exists x R(x)$) and you instantiate it with "Alice" without evidence, you have falsely accused Alice! A fresh symbol (e.g., $w_{\text{fresh}}$) guarantees that no prior assumptions pollute the witness.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Forgetting that $\forall x (P(x) \to A) \equiv (\exists x P(x)) \to A$ Why it fails: When pulling a quantifier out of the antecedent of an implication, students often leave it as $\forall$. Because $P(x) \to A \equiv \neg P(x) \lor A$, the negation flips $\forall$ to $\exists$! Pulling quantifiers across the left side of $\to$ ALWAYS inverts the quantifier!

Trap 2: Renaming variables carelessly during PNF conversion Why it fails: In $(\forall x P(x)) \lor (\exists x Q(x))$, hoisting without renaming produces $\forall x \exists x (P(x) \lor Q(x))$, where the inner $\exists x$ illegally shadows the outer $\forall x$. You must always standardize variables apart first: $(\forall x P(x)) \lor (\exists y Q(y)) \equiv \forall x \exists y (P(x) \lor Q(y))$.

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic7.2 Nested Quantifiers, Negation De Morgan Laws & English TranslationNext Topic →8.1 Counting Principles, Permutations, Combinations & Stars and Bars