Predicate Logic

First-Order Predicate Logic (FOPL), also called First-Order Logic (FOL), extends Propositional Logic by introducing quantifiers, predicates, and variables.

Thank you for reading this post, don't forget to subscribe!

• Unlike propositional logic, which deals only with true or false statements, FOPL allows reasoning about objects, their properties, and relationships.

1.) Syntax of FOPL:

The syntax of Predicate Logic defines the rules for constructing valid logical expressions using:

• Constants: Represent specific objects (e.g., Socrates, Earth, 5).
• Variables: Represent generalized objects (e.g., x, y, z).
• Predicates: Represent relationships between objects (e.g., Loves(John, Mary) means “John loves Mary”).
• Functions: Map objects to other objects (e.g., Father(John) → Robert).
• Logical Connectives: Similar to propositional logic: AND (∧), OR (∨), NOT (¬), IMPLIES (→), IFF (↔).
• Quantifiers: Express statements about all or some objects.

Example:

“All humans are mortal.”

• Formal representation:
  • ∀x(Human(x)→Mortal(x))
  • (“For all x, if x is a human, then x is mortal.”)

“Some animals are carnivores.”

• Formal representation:
  • ∃x(Animal(x)∧Carnivore(x))
  • (“There exists an x such that x is an animal and x is a carnivore.”)

2.) Semantics of FOPL:

The semantics of predicate logic define how logical expressions are interpreted in terms of objects, domains, and relationships.

Components:

• Domain (D): The set of objects under consideration (e.g., the set of all living beings).
• Interpretation (I): Assigns meaning to predicates and functions.
• Truth Values: Sentences in FOPL are evaluated as true or false based on the domain and interpretation.

Example:
If the domain is all humans, and the predicate Mortal(x) means “x is mortal”, then:

• ∀x (Human(x) → Mortal(x)) is true, since all known humans are mortal.

3.) Quantification in FOPL:

Quantifiers define the scope of a logical statement by specifying whether it applies to all or some objects.

Types of Quantifiers:

1.) Universal Quantifier (∀): Specifies that a statement is true for all elements in the domain.

Example:

• ∀x(Bird(x)→CanFly(x))
• (“All birds can fly.”)

2.) Existential Quantifier (∃): Specifies that a statement is true for at least one element in the domain.

Example:

• ∃x(Mammal(x)∧LaysEggs(x))
• (“There exists a mammal that lays eggs.”)
• Valid Example: The platypus fits this description.

4.) Inference in FOPL:

Inference in predicate logic involves deriving new knowledge from existing facts using logical rules.

Existential and Universal Instantiation:

1. Universal Instantiation (UI):

• From a general statement, we derive a specific case.
• Example:
  • Given: ∀x (Human(x) → Mortal(x))
  • Infer: Human(Socrates) → Mortal(Socrates)
  • (“If all humans are mortal, then Socrates is mortal.”)

2. Existential Instantiation (EI):

• From “there exists an x,” we introduce a new constant to represent it.
• Example:
  • Given: ∃x (Mammal(x) ∧ LaysEggs(x))
  • Infer: Mammal(Platypus) ∧ LaysEggs(Platypus)

Unification and Lifting:

1.) Unification: A process of making logical expressions identical by substituting variables.

• Example:
  • Given: Parent(x, y), Parent(John, Mary)
  • Unification: x=John,y=Mary

2.) Lifting: Applying unification in generalized cases in inference.

Inference Using Resolution:

Resolution is a rule of inference that allows us to infer new knowledge by eliminating contradictions.

Example:

• Given Statements:
  • ∀x (Bird(x) → CanFly(x))
  • Bird(Penguin)

• Flawed Deduction:
  • Infer: CanFly(Penguin) ❌ (Incorrect because penguins cannot fly)

• Correction:
  • Add exceptional cases:
    • ∀x (Bird(x) ∧ ¬Penguin(x) → CanFly(x))
    • (“All birds except penguins can fly.”)

Thus, resolution helps refine knowledge and avoid incorrect conclusions.

5.) Example of a Full Inference Chain:

Premises:

• All humans are mortal → ∀x (Human(x) → Mortal(x))
• Socrates is human → Human(Socrates)

Apply Universal Instantiation:

• Mortal(Socrates) (From ∀x (Human(x) → Mortal(x)))

Conclusion:

• Socrates is mortal. ✅

This shows how predicate logic can be used to prove statements through inference.