7: First-Order Logic in Depth
First-Order Logic (FOL) extends propositional logic to enable more expressive and nuanced knowledge representation. It introduces quantifiers, predicates, and variables, allowing agents to model relationships and reason about objects in the world.
7.1 Syntax and Semantics of FOL
7.1.1 Basic Elements of FOL
Constants: Represent specific objects in the domain. Example: John,Mary,42John, Mary, 42John,Mary,42.
Variables: Represent arbitrary objects in the domain. Example: x,y,zx, y, zx,y,z.
Predicates: Represent properties or relationships between objects. Example: Loves(John,Mary)Loves(John, Mary)Loves(John,Mary) indicates John loves Mary.
Functions: Map objects to other objects. Example: Father(John)Father(John)Father(John) represents John’s father.
Logical Connectives:
AND (∧\wedge∧), OR (∨\vee∨), NOT (¬\neg¬), IMPLIES (→\rightarrow→), EQUIVALENT (↔\leftrightarrow↔).
Quantifiers:
Universal (∀\forall∀): Applies to all objects. Example: “All humans are mortal”: ∀x Human(x)→Mortal(x)\forall x \, Human(x) \rightarrow Mortal(x)∀xHuman(x)→Mortal(x).
Existential (∃\exists∃): Applies to at least one object. Example: “There exists a human who is a doctor”: ∃x Human(x)∧Doctor(x)\exists x \, Human(x) \wedge Doctor(x)∃xHuman(x)∧Doctor(x).
7.1.2 Semantics
The semantics of FOL define how sentences correspond to truth in a specific domain:
Interpretation: Assigns meaning to constants, predicates, and functions.
Domain: The set of all possible objects FOL can refer to.
Model: A specific interpretation where all sentences are true.
7.2 Translating Natural Language into FOL
Representing real-world knowledge in FOL involves translating natural language statements into logical expressions.
Examples:
Statement: "All cats are mammals." FOL: ∀x Cat(x)→Mammal(x)\forall x \, Cat(x) \rightarrow Mammal(x)∀xCat(x)→Mammal(x).
Statement: "Some students are enrolled in the AI course." FOL: ∃x Student(x)∧EnrolledIn(x,AI)\exists x \, Student(x) \wedge EnrolledIn(x, AI)∃xStudent(x)∧EnrolledIn(x,AI).
Statement: "If it is raining, the ground is wet." FOL: Raining→WetGroundRaining \rightarrow WetGroundRaining→WetGround.
7.3 Inference in FOL
Inference in FOL allows agents to derive new knowledge from existing facts using valid rules of reasoning.
7.3.1 Methods of Inference
Universal Instantiation: Derive specific facts from universal statements. Example: From ∀x Human(x)→Mortal(x)\forall x \, Human(x) \rightarrow Mortal(x)∀xHuman(x)→Mortal(x), infer Human(John)→Mortal(John)Human(John) \rightarrow Mortal(John)Human(John)→Mortal(John).
Existential Instantiation: Replace an existentially quantified variable with a specific constant. Example: From ∃x Loves(x,Mary)\exists x \, Loves(x, Mary)∃xLoves(x,Mary), infer Loves(John,Mary)Loves(John, Mary)Loves(John,Mary) (assuming John is chosen).
Resolution: A powerful method for automated reasoning, combining facts to deduce new conclusions.
7.4 Knowledge Representation with FOL
7.4.1 Representing Objects and Relationships
Objects: Represented as constants or variables.
Relationships: Represented as predicates.
Example:
Objects: John,Mary,AIJohn, Mary, AIJohn,Mary,AI.
Relationships: Teaches(John,AI),Enrolled(Mary,AI)Teaches(John, AI), Enrolled(Mary, AI)Teaches(John,AI),Enrolled(Mary,AI).
7.4.2 Representing General Knowledge
FOL is used to encode general knowledge about the world:
Hierarchies: Example: "All dogs are animals." ∀x Dog(x)→Animal(x)\forall x \, Dog(x) \rightarrow Animal(x)∀xDog(x)→Animal(x).
Causality: Example: "If it rains, the ground will be wet." Raining→WetGroundRaining \rightarrow WetGroundRaining→WetGround.
Rules and Exceptions: Example: "Birds can fly, except penguins." ∀x Bird(x)∧¬Penguin(x)→CanFly(x)\forall x \, Bird(x) \wedge \neg Penguin(x) \rightarrow CanFly(x)∀xBird(x)∧¬Penguin(x)→CanFly(x).
7.5 Applications of FOL
7.5.1 Expert Systems
FOL is used in expert systems to encode domain-specific knowledge for decision-making, such as medical diagnosis.
7.5.2 Natural Language Processing (NLP)
FOL underpins semantic analysis in NLP, helping machines understand the meaning of text.
7.5.3 Planning and Robotics
Robots use FOL to plan actions by reasoning about objects and their relationships in the environment.
7.6 Summary
In this chapter, we explored:
The syntax and semantics of First-Order Logic.
Translating natural language into FOL expressions.
Inference techniques in FOL for deriving new knowledge.
Applications of FOL in real-world AI systems.
Last updated