FOL

First Order Logic (FOL) Overview

  • Language & Commitments:

    • Ontological Commitment: What exists in the world.

    • Epistemological Commitment: What an agent believes about facts.

  • Types of Logic:

    • Propositional Logic: Handles facts with truth values: true/false/unknown.

    • First-Order Logic: Includes facts, objects, and relations with truth values: true/false/unknown.

    • Temporal Logic: Extends FOL to include times.

    • Probability Theory: Quantifies degree of belief (range [0, 1]).

    • Fuzzy Logic: Works with facts having degrees of truth (range [0, 1]).

Structure of First Order Logic

  • Model Elements:

    • Contains five objects.

    • Two binary relations and three unary relations.

    • One unary function (e.g., left-leg).

FOL Sentences

  • Basic Constructs:

    • Sentence Types:

      • Atomic Sentence: Predicate form (e.g., Predicate or Predicate(Term)).

      • Complex Sentence: Can be composed of other sentences using logical operators (¬, ∧, ∨, ⇒, ⇔) and quantifiers.

FOL Terms

  • Components:

    • Function: e.g., Function(Term).

    • Constant: Specific entities (e.g., John, X1).

    • Variable: Symbolic representation (e.g., x, a).

  • Predicate Examples: True, False, After, Loves.

  • Operator Precedence:

    • High to Low: ¬, =, ∧, ∨, ⇒, ⇔.

Specific Sentence Examples

  • Atomic Sentences:

    • Representation: LeftLeg(John) refers to "King John's left leg".

    • Complex relationships: Married(Father(Richard), Mother(John)).

  • Implications and Existential Quantifiers:

    • Example: ∃ x Crown(x) ∧ OnHead(x, John) implies existence of a crown on John’s head.

Nested Quantifiers

  • Example Structure:

    • Brother(x,y) ⇒ Sibling(x,y) indicates relationships.

    • Quantifier order matters and can affect interpretation (e.g., ∀ x ∃ y Loves(x,y): everyone loves someone).

Logical Equivalences

  • Rewrite Rules:

    • Negation relationships (e.g., ∀x P ≡ ¬∃x ¬P).

    • Property relationships (e.g., ¬(P ∨ Q) ≡ ¬P ∧ ¬Q).

Friendship and Kinship in FOL

  • Social Relations:

    • Definitions (e.g., one’s mother is the female parent).

    • Relations: Sibling(x,y) ⇔ (x ≠ y) ∧ Parent(p,x) ∧ Parent(p,y).

Wumpus World Model

  • Perception and Actions:

    • Percept example: Percept([Stench, Breeze, Glitter], 5).

    • Actions represented by: Turn(Right), Forward, Shoot.

  • Inference Rules:

    • Agent's deductions based on percepts to infer state of the environment.

Knowledge Engineering Process

  1. Identify the task.

  2. Assemble relevant knowledge.

  3. Decide on vocabulary of predicates, functions, and constants.

  4. Encode general knowledge about the domain.

  5. Describe specific problem instances.

  6. Pose queries to the inference procedure.

  7. Debug the knowledge base.

Rule-Based Inference

  • Unit Resolution: Takes clauses to produce new clauses based on literals.

  • Resolution Algorithm: Includes steps for simplifying knowledge base into conjunctive normal form (CNF).

Example Cases in FOL

  • Barber Paradox: Exploration of self-reference in predicates (e.g., Barber(x)).

  • Social Dynamics: Example about politicians and their relationships with the public.

Inference Rules for Quantifiers

  • Universal Instantiation:

    • Allows the derivation of sentences by substituting constant terms for variables.

  • Existential Instantiation:

    • Replaces variables with new constants that do not appear elsewhere in the knowledge base.