Quantification Theory: Predicates, Quantifiers & Logical Forms

TAKEAWAYS:

• Quantifiers (∀, ∃) bind variables to express universal ("all") or existential ("some") statements in logic.
• Predicates (P(x), Q(y)) define properties of objects, enabling precise logical expressions.
• Quantified statements can be negated using De Morgan’s laws: ¬∀x P(x) ≡ ∃x ¬P(x).
• Scope rules determine which variables are bound by quantifiers (e.g., ∀x ∃y P(x,y) ≠ ∃y ∀x P(x,y)).
• Nested quantifiers require careful evaluation of truth tables or substitution methods.
• Real-world applications include database queries (SQL WHERE clauses), AI rule engines, and formal verification of algorithms.

1. Introduction to Quantification Theory

Quantification theory extends propositional logic by allowing statements about collections of objects (e.g., "All students passed," "Some books are expensive"). It uses:

• Quantifiers: ∀ (universal: "for all"), ∃ (existential: "there exists").
• Predicates: Functions like P(x) ("x is a student") that return true/false for inputs.

Why it matters: Without quantification, logic can only handle simple statements (e.g., "The sky is blue"). Quantification lets us reason about groups, like:

• ∀x (Student(x) → Passed(x)): "All students passed."
• ∃y (Book(y) ∧ Expensive(y)): "Some book is expensive."

2. Predicates and Their Role

A predicate is a statement containing a variable that becomes true/false when the variable is replaced with a specific value. Example:

• P(x): "x is a prime number."
  • P(5) = true, P(4) = false.

Visualizing predicates:

classDiagram
    class Predicate {
        +P(x): Boolean
        +Variables: x, y, z...
        +Domain: Set of possible values (e.g., integers, students)
    }
    Predicate --> "evaluates to" TruthValue : true/false
    Predicate --> "depends on" Variable : x, y, z

Real-world analogy:

• eSewa’s "Order Status" predicate: Status(order_id) = "Delivered" is a predicate where order_id is the variable. Quantified: ∀x (Order(x) → ∃y (Delivery(y) ∧ Linked(x,y))): "Every order is linked to a delivery."

3. Universal Quantifier (∀)

Definition: ∀x P(x) means "For all x in the domain, P(x) is true." Example:

• ∀x (Human(x) → Mortal(x)): "All humans are mortal."
• Domain: {Socrates, Einstein, You}.

Truth table for ∀x P(x):

Key rule: ∀x P(x) is false only if at least one P(x) is false.

4. Existential Quantifier (∃)

Definition: ∃x P(x) means "There exists an x in the domain such that P(x) is true." Example:

• ∃x (Book(x) ∧ Price(x) > 1000): "Some book costs more than Rs. 1000."
• Domain: {Harry Potter, Logic Book, Cookbook}.

Truth table for ∃x P(x):

Key rule: ∃x P(x) is true if at least one P(x) is true.

5. Negation of Quantified Statements

Use De Morgan’s laws to negate quantified statements:

1. ¬∀x P(x) ≡ ∃x ¬P(x)
   • "Not all students passed" ≡ "Some student did not pass."
2. ¬∃x P(x) ≡ ∀x ¬P(x)
   • "No student passed" ≡ "All students failed."

Example with Daraz orders:

• Original: ∀x (Order(x) → Delivered(x)): "All orders are delivered."
• Negation: ∃x (Order(x) ∧ ¬Delivered(x)): "Some order is not delivered."

6. Scope of Quantifiers

The scope of a quantifier determines which variables it binds. Order matters! Example:

• ∀x ∃y Loves(x, y): "Every person loves someone."
  • For each x, there exists a y (could be different for each x).
• ∃y ∀x Loves(x, y): "Someone is loved by everyone."
  • There exists a y loved by all x (e.g., a celebrity).

Real-world tie-in:

• Pathao’s driver assignment:
  • ∀r ∃d (Request(r) → Assigned(d, r)): "Every request gets some driver."
  • ∃d ∀r (Driver(d) → Assigned(d, r)): "Some driver gets all requests" (unlikely!).

7. Nested Quantifiers and Evaluation

Nested quantifiers require substitution or truth tables. Steps:

1. Identify the innermost quantifier and its scope.
2. Replace variables with domain elements systematically.

Example: Evaluate ∀x ∃y (Friend(x, y) ∧ Smart(y)) for domain {A, B}:

• For x = A: Is there a y such that Friend(A,y) ∧ Smart(y)?
  • If y = B works, then ∃y holds for A.
• Repeat for x = B.
• If both hold, ∀x holds.

Visualization:

flowchart TD
    A["∀x ∃y P(x,y)"] --> B["For each x in domain"]
    B --> C["Check if ∃y P(x,y) is true"]
    C --> D["Test all y in domain for P(x,y)"]
    D -->|"P(x,y) true for some y"| E["∃y P(x,y) = true"]
    D -->|"P(x,y) false for all y"| F["∃y P(x,y) = false"]
    E --> G["Move to next x"]
    F --> H["∀x ∃y P(x,y) = false"]

8. Quantifiers in Real-World Systems

In the real world

1. Khalti’s Transaction System:

   • Idea: Existential quantifier for transactions.
   • How: ∃t (Transaction(t) ∧ Status(t) = "Completed" ∧ Amount(t) > 1000): "Some transaction over Rs. 1000 is completed."
   • Use: Fraud detection flags transactions where ∀t (Transaction(t) → ¬Verified(t)): "All transactions are unverified."

2. Ncell’s Network Coverage:

   • Idea: Universal quantifier for service areas.
   • How: ∀l (Location(l) → Covered(l)): "All locations have network coverage."
   • Negation: ∃l (Location(l) ∧ ¬Covered(l)): "Some location has no coverage" (used to identify dead zones).

3. NEPSE Stock Market:

   • Idea: Nested quantifiers for trading rules.
   • How: ∀s (Stock(s) → ∃t (Trade(t) ∧ Stock(t) = s ∧ Price(t) > 500)): "Every stock has a trade above Rs. 500."
   • Use: Identifies illiquid stocks where ∃s (Stock(s) ∧ ¬∃t (Trade(t) ∧ Price(t) > 100)).

9. Quantifiers in Programming and Databases

SQL Queries as Quantified Logic

SQL uses quantifiers implicitly:

• SELECT * FROM Students WHERE Passed = TRUE ≡ ∀x (Student(x) → Passed(x)) if filtered.
• SELECT * FROM Orders WHERE Status = 'Pending' ≡ ∃x (Order(x) ∧ Status(x) = "Pending").

Example: Find all courses with no enrolled students (∀s (Course(s) → ∃e (Enrollment(e) ∧ Course(e) = s)) is false):

SELECT CourseID
FROM Courses c
WHERE NOT EXISTS (
    SELECT 1 FROM Enrollments e WHERE e.CourseID = c.CourseID
);

10. Common Pitfalls and Misconceptions

Example of failure:

• ∀x ∃y Loves(x, y): "Everyone loves someone."
• ∃y ∀x Loves(x, y): "Someone is loved by everyone."
  • The first allows different y for each x; the second requires a single y loved by all.

11. Practical Worked Example: Bank Loan Approval

Scenario: A bank approves loans if:

1. The applicant has a stable income.
2. The loan amount is ≤ 50% of the applicant’s annual income.

Formalize:

• Let Applicant(x), StableIncome(x), Loan(x, amount), Approved(x).
• Rules:
  1. ∀x (Loan(x, amount) → (StableIncome(x) ∧ (amount ≤ 0.5 × AnnualIncome(x))))
  2. ∀x (Loan(x, amount) ∧ StableIncome(x) ∧ (amount ≤ 0.5 × AnnualIncome(x)) → Approved(x))

Negation for fraud detection:

• ∃x (Loan(x, amount) ∧ Approved(x) ∧ ¬(StableIncome(x) ∨ (amount ≤ 0.5 × AnnualIncome(x)))): "Some approved loan violates rules."

Real data:

Evaluation:

• For A: 400,000 ≤ 0.5 × 1,000,000 → Approved.
• For B: StableIncome(B) = false → Rejected (matches ∃x condition above).

12. Exam Tip

How this unit is tested:

1. Translation: Convert natural language to quantified logic (30% weight).
   • Example: "No student failed" → ∀x (Student(x) → Passed(x)).
2. Truth evaluation: Given a domain, evaluate ∀/∃ statements (25%).
   • Example: For domain {1, 2, 3}, evaluate ∀x (x > 0 ∧ x < 4).
3. Negation: Apply De Morgan’s laws to quantified statements (20%).
   • Example: Negate ∃x (Prime(x) ∧ x > 10).
4. Scope analysis: Identify errors in quantifier order (15%).
   • Example: Why ∀x ∃y Friend(x,y) ≠ ∃y ∀x Friend(x,y)?
5. Real-world application: Relate to databases, AI, or algorithms (10%).
   • Example: How would you use ∀/∃ in SQL to find unassigned tasks?

Common exam mistakes:

• Ignoring domain restrictions (e.g., assuming x is a human when it’s a number).
• Misapplying negation (e.g., ¬∀x P(x) ≡ ∀x ¬P(x) is wrong).
• Skipping truth tables for nested quantifiers.

Pro tip:

• For translation, underline the quantifier words ("all," "some," "none") first.
• For evaluation, list all domain elements and check systematically.
• For negation, rewrite step-by-step using De Morgan’s laws.