7.1 Predicates, Quantifiers (∀, ∃) & Domain of Discourse Formalisms

Back to Discrete Mathematics Notes

📚Module 07: First-Order Predicate LogicTopic 7.1: Predicates, Quantifiers (∀, ∃) & Domain of Discourse⏱️5 min read

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

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: Function Signatures & Database SQL Queries

Think of propositional logic vs predicate logic like hardcoded booleans vs parameterized functions:

1. Propositional Logic (Hardcoded Flag): "The CPU is overheating." It is a static, rigid boolean flag (boolean isOverheating = true;). It cannot talk about which CPU core or how many cores are overheating!
2. Predicate Logic (Parameterized Function): isOverheating(core_id). The statement contains a parameter ($x$). Its truth value changes depending on what you feed into it: isOverheating(0) might be True, while isOverheating(1) might be False!
3. Quantifiers (SQL Aggregates):
   • Universal Quantifier ($\forall x$): SELECT ALL. "Every single core is overheating." (A single cool core destroys the claim).
   • Existential Quantifier ($\exists x$): SELECT ANY. "At least one core is overheating." (A single overheating core proves the claim).
4. Domain of Discourse (The Table): The set of all permissible values for $x$. Saying "everyone is asleep" means something very different in your household versus the entire planet Earth!

💻 Bridging to Computer Science: SQL WHERE, Invariants & Formal Verification

In computer systems:

• Relational Databases (SQL): ALL and ANY in SQL clauses directly translate $\forall$ and $\exists$: SELECT * FROM Users WHERE age >= ALL (SELECT age FROM Minors);
• Loop Invariants & Hoare Logic: Formal verification of algorithms uses predicates like $\text{Sorted}(A, 0, i)$ to prove that loops maintain correctness at every iteration.
• Static Analysis & Type Guards: Compilers use predicates like x is NonNullable<T> to narrow types inside control flow blocks.

📑Table of Contents

• 🔍 Why Propositional Logic Fails: The Need for Predicates
• 🌐 The Two Fundamental Quantifiers: ∀ and ∃
• 🔢 Finite Domain Expansions
• 🔒 Variable Binding, Scope & Free Variables
• 📝 Step-by-Step Worked Examples
  • Example 1: Evaluating Quantified Statements Across Different Domains
  • Example 2: Expressing Uniqueness Formally
• 🎯 Exam & Interview Pitfall Check

---

🔍 Why Propositional Logic Fails: The Need for Predicates

📐Observation 7.1: The Expressive Boundary of Propositional Logicobservation

Consider the classic deductive argument:

• Premise 1 ($P_1$): "Every Indian likes cricket."
• Premise 2 ($P_2$): "Sunny is an Indian."
• Conclusion ($Q$): "Sunny likes cricket."

In propositional logic, each statement must be assigned a completely distinct atomic proposition letter:

$$P_1 \equiv A, \quad P_2 \equiv B, \quad Q \equiv C$$

Testing validity yields $(A \land B) \to C$, which is a Contingency (Invalid)! Propositional logic treats statements as indivisible black boxes, completely blind to:

1. The Subject (an individual entity like "Sunny").
2. The Predicate (a property or relation like "is an Indian" or "likes cricket").
3. The Quantity (generalizations like "All", "Every", or "Some").

To extract internal semantic relationships and deduce that $Q$ follows inevitably from $P_1$ and $P_2$, we must upgrade to First-Order Predicate Logic (FOL).

📖Definition 7.1: Predicate, Subject & Domain of Discoursedefinition

1. Subject: The object or entity being described (e.g., "$1$", "$x$", "Sunny").
2. Predicate: The property, attribute, or relation asserted about the subject (e.g., "is a natural number", "likes cricket").
   • Denoted: $P(x)$, $Q(x, y)$, $R(x_1, \dots, x_n)$.
   • $P$ is the predicate symbol; $x$ is the subject variable.
3. Domain of Discourse (Universe $U$): The non-empty set of all permissible values that the variable $x$ may assume.
   • Example: Let $U$ be the set of all people.
   • Predicate $C(x)$: "$x$ likes cricket".
   • $C(\text{Sunny})$ is now a valid proposition with a definite truth value!
4. Truth Set: The subset of elements in domain $U$ for which $P(x)$ evaluates to True: $$T_P = \{ x \in U \mid P(x) \text{ is True} \} \subseteq U$$

The Anatomy of First-Order Predicate Statements

Key components distinguishing open formulas from closed propositions

⚙️

Open Formula (Predicate)

Free Variable

• Expression contains at least one unbound (free) variable x.
• Cannot be assigned a truth value until x is specified.
• Example: P(x): 'x > 5' is neither True nor False by itself.

🔒

Closed Formula (Proposition)

Bound Variable

• Every variable is bound either by substitution or by a quantifier.
• Possesses an absolute, well-defined truth value.
• Example: P(8): '8 > 5' is True; ∀x P(x) is False over ℝ.

🌐

Domain of Discourse (U)

Evaluation Context

• Defines the universe of eligible values (e.g., ℤ, ℝ, Strings, Students).
• Changing the domain can instantly flip the truth value of a statement!
• Example: '∃x (x² = 2)' is False over ℚ, but True over ℝ.

---

🌐 The Two Fundamental Quantifiers: ∀ and ∃

Universal Quantifier (∀) vs Existential Quantifier (∃)

The fundamental dual quantifiers of first-order mathematical logic

Universal (∀)

Universal Quantifier: ∀x P(x)

🌐

Dominant Architecture / DomainExhaustive Global Truth

• •English: 'For all x', 'For every x', 'For each x', 'All'.
• •True Condition: P(x) is True for EVERY element x in the domain U.
• •False Condition: There exists AT LEAST ONE counterexample c ∈ U such that P(c) is False.
• •Finite Domain Expansion: P(a₁) ∧ P(a₂) ∧ ... ∧ P(aₙ) (Generalized Conjunction).

"One single counterexample shatters the entire statement."

Existential (∃)

Existential Quantifier: ∃x P(x)

🔍

Dominant Architecture / DomainAt-Least-One Witness

• •English: 'There exists an x', 'For some x', 'There is at least one x'.
• •True Condition: There exists AT LEAST ONE witness c ∈ U such that P(c) is True.
• •False Condition: P(x) is False for EVERY element x in the domain U.
• •Finite Domain Expansion: P(a₁) ∨ P(a₂) ∨ ... ∨ P(aₙ) (Generalized Disjunction).

"A single valid witness proves the entire claim."

📐Rule 7.1: The Golden Connective Pairing Rulesrule

In first-order logic translations:

1. Universal Quantifiers ($\forall$) Pair with Implication ($\to$): $$\text{"All } A \text{ are } B\text{"} \iff \forall x \big( A(x) \to B(x) \big)$$
   • Why NEVER $\land$? Writing $\forall x (A(x) \land B(x))$ asserts that every single object in the universe is an $A$ and a $B$! For example, "All students are smart" with $\land$ implies the Sun, the Moon, and your laptop are all students!
2. Existential Quantifiers ($\exists$) Pair with Conjunction ($\land$): $$\text{"Some } A \text{ are } B\text{"} \iff \exists x \big( A(x) \land B(x) \big)$$
   • Why NEVER $\to$? Writing $\exists x (A(x) \to B(x))$ is vacuously True if there exists any object that is not an $A$ ($F \to \dots \equiv T$)! For example, "Some students are smart" with $\to$ is proven True by a coffee mug, because a mug is not a student!

📖Definition 7.2: Uniqueness Quantifier (∃!)definition

The Uniqueness Quantifier, denoted:

$$\exists! x \, P(x) \quad \text{or} \quad \exists_1 x \, P(x)$$

states: "There exists one and only one $x$ such that $P(x)$ is True."

First-Order Formal Expansion: $\exists! x \, P(x)$ asserts both existence and uniqueness:

$$\exists! x \, P(x) \equiv \exists x \Big( P(x) \land \forall y \big( P(y) \to y = x \big) \Big)$$

---

🔢 Finite Domain Expansions

When the domain of discourse $U$ is a finite set $\{a_1, a_2, \dots, a_n\}$, quantifiers reduce directly to propositional logic:

📐Theorem 7.1: Finite Expansion Equivalencestheorem

Let $U = \{a_1, a_2, \dots, a_n\}$ be a finite universe:

1. Universal Expansion (Generalized Conjunction): $$\forall x \, P(x) \equiv P(a_1) \land P(a_2) \land \dots \land P(a_n)$$
2. Existential Expansion (Generalized Disjunction): $$\exists x \, P(x) \equiv P(a_1) \lor P(a_2) \lor \dots \lor P(a_n)$$

Direct Consequence: In finite domains, searching for a counterexample for $\forall$ is searching for a False operand in a giant AND, while searching for a witness for $\exists$ is searching for a True operand in a giant OR!

---

🔒 Variable Binding, Scope & Free Variables

📖Definition 7.3: Scope of a Quantifier & Variable Bindingdefinition

1. Scope: The sub-formula over which the quantifier has binding authority. In $\forall x (P(x) \land Q(x))$, the scope of $\forall x$ is $(P(x) \land Q(x))$.
2. Bound Variable: An occurrence of variable $x$ is bound if it falls within the scope of a quantifier $\forall x$ or $\exists x$.
3. Free Variable: An occurrence of variable $x$ is free if it is not bound by any quantifier.

Example: In the formula:

$$\big(\forall x \, P(x, y)\big) \lor Q(x)$$

• The variable $x$ in $P(x, y)$ is bound by $\forall x$.
• The variable $y$ in $P(x, y)$ is free.
• The variable $x$ in $Q(x)$ is outside the parentheses, so it is free!
• Because free variables exist, the entire formula is a predicate, not a proposition.

---

📝 Step-by-Step Worked Examples

Example 1: Evaluating Quantified Statements Across Different Domains

Problem Statement: Determine the truth value of each statement under two different domains:

• Domain 1: $\mathbb{Z}$ (All integers)
• Domain 2: $\mathbb{R}$ (All real numbers)

1. Statement A: $\forall x (x^2 \ge 0)$
2. Statement B: $\forall x (x^2 > 0)$
3. Statement C: $\exists x (x^2 = 2)$
4. Statement D: $\forall x (x \lt x + 1)$

Step-by-Step Solution:

1. Analysis of Statement A: $\forall x (x^2 \ge 0)$

   • Domain $\mathbb{Z}$: For every integer, its square is non-negative ($0^2 = 0 \ge 0$; $(-3)^2 = 9 \ge 0$). True.
   • Domain $\mathbb{R}$: The square of every real number is non-negative. True.

2. Analysis of Statement B: $\forall x (x^2 > 0)$

   • Counterexample Test: Does there exist any element with $x^2 \le 0$?
   • Setting $x = 0$ gives $0^2 = 0$, which is NOT strictly greater than $0$.
   • Since $x = 0$ is a valid counterexample in both $\mathbb{Z}$ and $\mathbb{R}$, Statement B is False in both domains.

3. Analysis of Statement C: $\exists x (x^2 = 2)$

   • Domain $\mathbb{Z}$: The solutions to $x^2 = 2$ are $x = \pm \sqrt{2}$. Neither $\sqrt{2}$ nor $-\sqrt{2}$ is an integer ($\sqrt{2} \notin \mathbb{Z}$). Thus, no integer satisfies the condition. False in $\mathbb{Z}$.
   • Domain $\mathbb{R}$: Since $\sqrt{2} \in \mathbb{R}$, $x = \sqrt{2}$ is a valid witness. True in $\mathbb{R}$!

4. Analysis of Statement D: $\forall x (x \lt x + 1)$

   • Subtracting $x$ from both sides gives $0 \lt 1$, which is unconditionally true for all real numbers and integers.
   • Statement D is True in both domains.

Key Takeaway: Always inspect the domain of discourse: statement C is False over integers but True over real numbers.

---

Example 2: Expressing Uniqueness Formally

Problem Statement: Let $E(x)$ be the predicate "$x$ is an even prime number" over the domain of positive integers $\mathbb{Z}^+$.

1. Evaluate $\exists! x \, E(x)$.
2. Write the formal expansion of this statement in standard first-order logic.

Step-by-Step Solution:

1. Step 1: Truth Value Analysis

   • Positive prime numbers are $\{2, 3, 5, 7, 11, \dots\}$.
   • The only even prime number is $2$.
   • Any prime $> 2$ is divisible by $2$ and therefore composite.
   • Since $2$ is the unique even prime, the statement $\exists! x \, E(x)$ is True!

2. Step 2: Formal First-Order Expansion

   • We must assert two sub-formulas:
     1. Existence: There exists an even prime: $\exists x E(x)$.
     2. Uniqueness: If any number $y$ is an even prime, it must be identical to $x$: $\forall y (E(y) \to y = x)$.
   • Combining both with conjunction: $$\exists x \Big( E(x) \land \forall y \big( E(y) \to y = x \big) \Big)$$
   • Alternative equivalent formulation (asserting no second distinct witness exists): $$\exists x E(x) \land \neg \exists x \exists y \big( E(x) \land E(y) \land x \neq y \big)$$

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: Is the statement $\forall x P(x)$ automatically True if the domain of discourse $U$ is the empty set ($\emptyset$)? Key Focus Points: Yes! In formal logic, this is a vacuous truth. If the domain is empty, there are no elements to test, which means it is impossible to find a counterexample! Therefore, $\forall x P(x)$ is vacuously True. Conversely, $\exists x P(x)$ over an empty domain is always False because no witness exists!

Question 2: Can a formula have the same variable symbol appear both as a bound variable and as a free variable? Key Focus Points: Yes! For example, in $(\forall x P(x)) \lor Q(x)$, the first occurrence of $x$ is bound by $\forall x$, while the second occurrence in $Q(x)$ is free. To avoid confusion, best practice in computer science (variable renaming / alpha conversion) renames the bound variable: $(\forall z P(z)) \lor Q(x)$.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Dropping the domain when evaluating truth values Why it fails: "$\forall x (x > 0)$" has NO intrinsic truth value until the domain is stated! If $U = \mathbb{N} = \{1, 2, 3, \dots\}$, it is True. If $U = \mathbb{Z} = \{\dots, -1, 0, 1, \dots\}$, it is False. Never evaluate a quantified formula without first identifying its domain of discourse!

Trap 2: Assuming $\exists x P(x)$ implies $P(x)$ is true for most elements Why it fails: The existential quantifier $\exists$ requires only AT LEAST ONE witness. Even if an event occurs only once in a quadrillion cases ($10^{15}$ failures and 1 success), $\exists x P(x)$ is 100% True!

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic6.3 Rules of Inference, Validity Proofs & Resolution RefutationNext Topic →7.2 Nested Quantifiers, Negation De Morgan Laws & English Translation