Propositional & Predicate Logic: Truth Tables, Validity, Quantifiers & Proofs

TAKEAWAYS:

• Propositional logic uses truth tables to evaluate compound statements with AND, OR, NOT, IMPLIES, and IFF.
• Predicate logic extends propositional logic with quantifiers (∀, ∃) and predicates to express statements about sets of objects.
• Logical equivalences (De Morgan’s, distributive laws) simplify complex statements into equivalent forms.
• Proof techniques like natural deduction and Fitch-style proofs systematically derive conclusions from premises.
• Real-world systems (e.g., WhatsApp’s message delivery logic, Ncell’s network routing) rely on these principles for reliability.
• Mastering truth tables and quantifier rules is critical for exam questions on validity, satisfiability, and logical forms.

Propositional Logic: Building Blocks of Reasoning

Propositional logic deals with propositions (statements that are either true or false) and logical connectives that combine them. Unlike natural language, it enforces strict rules for truth evaluation.

Key Connectives and Their Truth Tables

The five primary connectives are:

1. Negation (¬P): Inverts the truth value of P.
2. Conjunction (P ∧ Q): True only if both P and Q are true.
3. Disjunction (P ∨ Q): True if at least one of P or Q is true.
4. Implication (P → Q): False only when P is true and Q is false (read as "if P then Q").
5. Biconditional (P ↔ Q): True when P and Q have the same truth value.

Worked Example: Evaluating a Compound Statement Evaluate the truth value of (P → Q) ∧ (¬Q ∨ R) when:

• P is true, Q is false, and R is true. Solution:

1. Evaluate P → Q: Since P is true and Q is false, P → Q is false.
2. Evaluate ¬Q ∨ R: ¬Q is true (Q is false), so the whole expression is true.
3. Combine with ∧: false ∧ true is false.

Logical Equivalences: Simplifying Statements

Logical equivalences allow us to rewrite statements without changing their truth value. Key equivalences include:

1. De Morgan’s Laws

graph LR
    A["¬(P ∧ Q)"] -->|"De Morgan"| B["(¬P) ∨ (¬Q)"]
    C["¬(P ∨ Q)"] -->|"De Morgan"| D["(¬P) ∧ (¬Q)"]

Example: Simplify ¬(A ∨ B). Solution: By De Morgan’s, this becomes (¬A) ∧ (¬B).

2. Distributive Laws

graph LR
    E["P ∧ (Q ∨ R)"] -->|"Distribute ∧"| F["(P ∧ Q) ∨ (P ∧ R)"]
    G["P ∨ (Q ∧ R)"] -->|"Distribute ∨"| H["(P ∨ Q) ∧ (P ∨ R)"]

3. Implication Equivalences

• P → Q is equivalent to ¬P ∨ Q.
• P ↔ Q is equivalent to (P → Q) ∧ (Q → P).

Real-World Tie-In: WhatsApp Message Delivery WhatsApp’s "Read Receipts" feature can be modeled using implication:

• Let P = "Message is sent" and Q = "Read receipt is shown."
• The rule: "If the message is sent and the recipient is online, then show the read receipt." Formalized: (P ∧ Online) → Q. This uses implication to ensure receipts appear only under specific conditions.

Predicate Logic: Beyond Propositions

Predicate logic extends propositional logic by introducing predicates (properties of objects) and quantifiers (∀, ∃).

Components of Predicate Logic

1. Predicates: Functions that return true/false, e.g., Prime(x) (is x prime?).
2. Quantifiers:
   • Universal (∀): "For all x, P(x) holds."
   • Existential (∃): "There exists an x such that P(x) holds."
3. Domain: The set of objects the variables range over (e.g., natural numbers, students in a class).

Example: "All even numbers are divisible by 2." Formalized: ∀x (Even(x) → DivisibleBy2(x)).

Negating Quantifiers

graph LR
    A["¬(∀x P(x))"] -->|"Equivalent to"| B["∃x ¬P(x)"]
    C["¬(∃x P(x))"] -->|"Equivalent to"| D["∀x ¬P(x)"]

Worked Example: NEPSE Stock Market Logic NEPSE’s trading rule: "A stock can be bought only if its price is below ₹1000 or it is a blue-chip stock." Formalize:

• Let P(x) = "Stock x is below ₹1000."
• Let Q(x) = "Stock x is blue-chip."
• Rule: ∀x (Buyable(x) → (P(x) ∨ Q(x))).

Proof Techniques in Logic

1. Natural Deduction

A step-by-step method to derive conclusions from premises using inference rules. Example: Prove (P → Q) ∧ (Q → R) ⊢ P → R. Proof:

1. Assume P (assumption for implication).
2. From (P → Q) and P, derive Q (Modus Ponens).
3. From (Q → R) and Q, derive R (Modus Ponens).
4. Conclude P → R (discharge assumption).

2. Fitch-Style Proofs

A structured proof system with nested assumptions. Example: Prove ∀x (P(x) → Q(x)) ⊢ (∃x P(x)) → (∃x Q(x)).

graph TD
    A["1. ∀x (P(x) → Q(x))"] --> B["2. Assume ∃x P(x)"]
    B --> C["3. ∴ ∃y P(y) (rename)"]
    C --> D["4. Assume P(a) (∃ elimination)"]
    D --> E["5. From ∀x (P(x) → Q(x)), derive P(a) → Q(a)"]
    E --> F["6. From P(a) and P(a) → Q(a), derive Q(a)"]
    F --> G["7. ∴ ∃x Q(x) (∃ introduction)"]
    G --> H["8. Discharge assumption: (∃x P(x)) → (∃x Q(x))"]

Validity and Satisfiability

• Valid Argument: An argument where the conclusion must be true if the premises are true.
• Satisfiable: A statement that is true for at least one assignment of truth values.

Example: Check if (P → Q) ∧ (Q → R) ∧ ¬P ⊢ ¬R is valid. Solution:

1. Assume premises are true:
   • P is false (from ¬P).
   • P → Q is true (false implies anything is true).
   • Q → R must be true, but Q could be true or false.
2. If Q is true, then R must be true (from Q → R), but ¬R would be false. Contradiction.
3. If Q is false, R can be anything, but ¬R may or may not hold. Conclusion: The argument is not valid because ¬R does not necessarily follow.

In the Real World

1. Khalti’s Transaction Logic

   • Idea Used: Implication (P → Q).
   • How: "If the user verifies their identity (P) and enters correct credentials (Q), then process payment (R)." Formalized: (P ∧ Q) → R.
   • Why It Matters: Ensures payments only occur under verified conditions, reducing fraud.

2. Pathao’s Ride Allocation

   • Idea Used: Predicate logic with quantifiers.
   • How: "For every ride request x, if there exists a driver y within 500m (∃y Near(y, x)), then allocate the ride (Allocate(x))." Formalized: ∀x (Request(x) ∧ ∃y Near(y, x)) → Allocate(x).
   • Why It Matters: Efficiently matches riders to nearby drivers using existential quantifiers.

3. NTC’s Network Routing

   • Idea Used: Logical equivalences and implications.
   • How: "If a packet’s destination is unreachable (Unreachable(D)), then drop the packet (Drop(P))." Formalized: Unreachable(D) → Drop(P).
   • Why It Matters: Prevents infinite retries and optimizes network performance.

Exam Tip

1. Truth Tables: Always list all possible truth assignments (2ⁿ rows for n variables). Partial tables lose marks.
2. Predicate Logic: Clearly define your domain and variables. For example:
   • Bad: "∀x P(x)."
   • Good: "For all students x in BIT Level 2, P(x) holds."
3. Proofs: Structure is key. Use Fitch-style proofs for quantifiers and natural deduction for propositional logic. Label each step.
4. Equivalences: Memorize De Morgan’s and distributive laws. Exams often ask to simplify or negate statements.
5. Real-World Applications: Connect logic to systems like eSewa (implication for bill payments) or Daraz (quantifiers for inventory checks). Examiners love seeing these ties.
6. Common Pitfalls:
   • Confusing P → Q with P ↔ Q.
   • Misapplying quantifier negation (e.g., ¬∀x P(x) is not ∀x ¬P(x)).
   • Forgetting to discharge assumptions in proofs.

Visual Summary for Quick Revision:

mindmap
  root((Propositional & Predicate Logic))
    Connectives
      AND(∧)
      OR(∨)
      NOT(¬)
      IMPLIES(→)
      IFF(↔)
    Truth Tables
    Equivalences
      De Morgan
      Distributive
    Predicate Logic
      Quantifiers(∀, ∃)
      Domain
      Scope
    Proofs
      Natural Deduction
      Fitch-Style
    Real-World
      Khalti(P → Q)
      Pathao(∃y Near(y, x))
      NTC(Unreachable → Drop)