How To Read Predicate Logic


Predicate logic (also called first-order logic) extends propositional logic by allowing statements to include variables and quantifiers, making it more expressive. This allows us to formally represent statements like "All humans are mortal" or "Some birds cannot fly."

1.1 Differences Between Propositional and Predicate Logic

  • Propositional logic only deals with whole statements (ex: "P" is true or false).
  • Predicate logic breaks statements down into subjects and properties (ex: "Socrates is mortal" → M(Socrates)).

Key Features of Predicate Logic:

  1. Predicates: Represent properties or relations.
  2. Variables: Represent general objects.
  3. Quantifiers: Express universal or existential claims.

2.1 Predicates and Variables

A predicate is a function that expresses a property or relation. It applies to objects (variables or constants).

  • Example:
    • "x is a philosopher" → P(x)
    • "x is greater than y" → G(x, y)

2.2 Constants

A constant refers to a specific object in the domain.

  • Example:
    • "Socrates is mortal" → M(Socrates)
    • "Earth is a planet" → P(Earth)

2.3 Quantifiers

Quantifiers specify whether a statement applies to all or some objects.

  1. Universal Quantifier (∀x) – "For all x"

    • Example: "All humans are mortal"
      • Symbolic Form: ∀x (H(x) → M(x))
      • Meaning: If x is a human, then x is mortal.

  2. Existential Quantifier (∃x) – "There exists an x"

    • Example: "Some humans are philosophers"
      • Symbolic Form: ∃x (H(x) ∧ P(x))
      • Meaning: There exists at least one x such that x is both a human and a philosopher.

2.4 Logical Connectives in Predicate Logic

Predicate logic retains the logical operators from propositional logic:

  • ¬ (Negation): "It is not the case that..."
  • ∧ (Conjunction): "And"
  • ∨ (Disjunction): "Or"
  • → (Implication): "If...then"
  • ↔ (Biconditional): "If and only if"

English Statement Predicate Logic Representation
All cats are mammals. ∀x (C(x) → M(x))
Some dogs are friendly. ∃x (D(x) ∧ F(x))
No humans are immortal. ¬∃x (H(x) ∧ I(x)) or ∀x (H(x) → ¬I(x))
Every student loves logic. ∀x (S(x) → L(x))
Some numbers are even. ∃x (N(x) ∧ E(x))

Common Mistakes:

  1. Misplacing quantifiers: "Some people love all animals" is ∃x (P(x) ∧ ∀y (A(y) → L(x, y))), not ∀y (A(y) → ∃x (P(x) ∧ L(x, y))).
  2. Forgetting negations: "Not all humans are philosophers" means ¬∀x (H(x) → P(x)), which is equivalent to ∃x (H(x) ∧ ¬P(x)).

4.1 Negating Quantifiers

  • ¬∀x P(x) ≡ ∃x ¬P(x)
  • ¬∃x P(x) ≡ ∀x ¬P(x)

Example:

  • "Not all students like math" → ¬∀x (S(x) → M(x))
    • Equivalent to "Some students do not like math" → ∃x (S(x) ∧ ¬M(x)).

4.2 Implication Elimination

  • ∀x (P(x) → Q(x)) ≡ ∀x (¬P(x) ∨ Q(x))

4.3 Equivalence of Universal and Existential Statements

  • ∀x (P(x) → Q(x)) ≡ ¬∃x (P(x) ∧ ¬Q(x))
  • ∃x (P(x) → Q(x)) ≡ ∀x (¬P(x) ∨ Q(x))


5.1 Direct Proof

A direct proof starts from assumptions and derives the conclusion using logical steps.

Example: Prove that if all humans are mortal and Socrates is human, then Socrates is mortal.

  1. Given: ∀x (H(x) → M(x)) (All humans are mortal)
  2. Given: H(Socrates) (Socrates is human)
  3. Applying Universal Instantiation: H(Socrates) → M(Socrates)
  4. Modus Ponens: Since H(Socrates) is true, M(Socrates) follows.

5.2 Proof by Contradiction

Assume the negation of what you want to prove, derive a contradiction, and conclude the original statement must be true.

Example: Prove that "If all dogs bark, then there does not exist a silent dog."

  1. Assume ∀x (D(x) → B(x)) (All dogs bark).
  2. Assume ∃x (D(x) ∧ ¬B(x)) (There exists a silent dog).
  3. From (2), we have some d such that D(d) ∧ ¬B(d).
  4. From (1), applying Universal Instantiation: D(d) → B(d).
  5. Since D(d) is true, B(d) must be true.
  6. Contradiction: B(d) and ¬B(d) cannot both be true.
  7. Thus, the assumption (2) is false, proving ¬∃x (D(x) ∧ ¬B(x)).

5.3 Proof by Counterexample

To disprove ∀x P(x), find an x such that ¬P(x).

Example: Disprove "All prime numbers are even."

  • Counterexample: 3 is a prime number but not even.

Advanced Topics for Further Study

  • Second-Order Logic (Quantifying over predicates)
  • Modal Logic (Necessity and possibility)
  • Set Theory (Relations with logic)
  • Gödel’s Incompleteness Theorems (Limits of formal systems)


Popular Posts