Introduction to First Order Logic

Introduction to First Order Logic

• Propositional Logic can represent facts and has a sound inference procedure.
• Propositional logic is compositional; the meaning of combined statements are derived from its individual parts.
• Propositional logic is context-independent, unlike natural language.
• Propositional Logic has weaknesses:
  • Truth tables grow exponentially with the number of propositions.
  • Lacks expressive power, cannot generalize or express properties of individuals directly.

Propositional Logic Limitations

• Encoding "all men are mortals" in propositional logic requires listing the fact individually for each known man.
• The inability to express general-purpose knowledge succinctly is a limitation.
• Identifying individuals and expressing generalizations or patterns are difficult.
• Propositional logic struggles with properties of individuals or relations between them.

First Order Logic (FOL) as an expressive language

• FOL, or FOPC, is expressive enough to represent complex situations concisely.
• FOL adds relations, variables, and quantifiers.
  • "Every elephant is gray" represented as: ∀x (elephant(x) → gray(x)).
  • "There is a white alligator" represented as: ∃x (alligator(x) ∧ white(x)).
• Examples of statements FOL can represent:
  • All men are mortal: ∀x Man(x) ⇒ Mortal(x)
  • Everybody loves somebody: ∀x ∃y Loves(x, y)
  • Definition of "above": ∀x ∀y above(x,y) ⇔ (on(x,y) ∨ ∃z (on(x,z) ∧ above(z,y)))

FOL Assumptions and Capabilities

• FOL assumes the world contains objects, relations, and functions, unlike propositional logic which assumes only facts.
• Objects include people, houses, numbers, colors, etc.
• Relations can be unary (properties, e.g., red) or n-ary (relations between objects, e.g., brother of).
• Functions include Sqrt and Plus.
• FOL is capable of expressing:
  • Squares neighboring the Wumpus are smelly.
  • Squares neighboring a pit are breezy.
• Representation of "Socrates is a man":
  • Propositional logic uses a single proposition: MANSOCRATES.
  • First-order logic uses a predicate: Man(SOCRATES).

Logics Overview

• Propositional logic deals with facts.
• First-order logic deals with facts, objects, and relations.
• Temporal logic deals with facts, objects, relations, and times.
• Probability theory deals with facts with degrees of belief.
• Fuzzy logic deals with facts with a degree of truth.
• Propositional, First-order, and Temporal logics are true/false/unknown epistemologically
• Probability theory is a degree of belief between 0 and 1 epistemologically
• Fuzzy logic has interval values epistemologically.

First Order Logic Syntax - User Defined

• Constant symbols represent individuals in the world (e.g., Mary, 3).
• Function symbols map individuals to individuals (e.g., father-of(Mary) = John).
• Predicate/relation symbols map individuals to truth values (e.g., greater(5,3), green(apple)).

First Order Logic Syntax - System Defined

• Variable symbols (e.g., x, y).
• Connectives: ⇔, ∧, ∨, ⇒ (same as in Propositional Logic).
• Equality: =
• Quantifiers: Universal (∀) and Existential (∃).
• A well-formed formula (wff) is also known as a sentence.

FOL Example

• Sentences can be represented as:
• Brother(KingJohn, RichardTheLionHeart)
• (Length (LeftLegOf(RichardThe…) > (Length (LeftLegOf(KingJohn)
• Sibling(KingJohn, Richard…) → Sibling(Richard…, KingJohn)

Quantifiers

• Quantifiers express properties of collections of objects without enumerating them by name.
  • Universal ("for all"): ∀
  • Existential ("there exists"): ∃

Constant Symbols Details

• Each constant symbol names one object in the universe of discourse.
• Not all objects have symbol names.
• Some objects may have multiple symbol names.
• Constant symbols are usually denoted with an upper-case first letter.

Variables Details

• Represent objects or properties without explicitly naming the object.
• Usually in lower case.

Relation (Predicate) Symbols Details

• Represent a relation in a universe of discourse.
• The sentence Relation(Term1, Term2,…) is either TRUE or FALSE.
• Example: Wrote(Malek, Muata) is true if Malek wrote Muata.

Function Symbols Details

• Functions describe the binary relation of pairs of objects.
• Example: Father(Ali) refers to the father of Ali.

Properties of Quantifiers

• ∀ x ∀ y is the same as ∀ y ∀ x
• ∃ x ∃ y is the same as ∃ y ∃ x
• ∃ x ∀ y is not the same as ∀ y ∃ x
  • Existential then Universal example: ∃ x ∀ y Loves(x,y) - "There is a person who loves everyone in the world."
  • Universal then Existential example: ∀ y ∃ x Loves(x,y) - "Everyone in the world is loved by at least one person"
• Quantifier duality allows for the expression of each quantifier using the other.
  • ∀ x Likes(x,IceCream) ≡ ¬ ∃ x ¬Likes(x,IceCream)
  • ∃ x Likes(x,Broccoli) ≡ ¬ ∀ x ¬Likes(x,Broccoli)

Atomic Sentences

• An atomic sentence is a predicate (term1,...,termn) or term1 = term2.
• A term is a function (term1,...,termn), constant, or variable
• Example terms: Brother(Ali, Mohamed), Greater(Length(x), Length(y)).

Complex Sentences

• Complex sentences combine atomic sentences with connectives and quantifiers.
• Examples:
  • Sibling(Ali,Mohamed) ⇒ Sibling(Mohamed,Ali)
  • greater(1,2) ∨ less-or-equal(1,2)
  • ∀ x,y Sibling(x,y) ⇒ Sibling(y,x)

Logic and Set Theory

• Constant symbols, variables, and connectives are similar to propositional logic.
• Functions and predicates are distinct.
• Logic is based on set theory, including Sets, Relations, and Functions.

Sets

• Sets define a "Universe of Discourse."
• Objects are represented by Constant Symbols.
• Example: In a blocks world, the universe of discourse is {a,b,c,d,e}.

Relations

• A binary relation is a set of ordered pairs.
• Example: on = {<a,b>, <b,c>, <d,e>} represents the "on" relationships between blocks.
• On(A,B) is TRUE if <a,b> ∈ on.

Functions in Logic

• A function is a binary relation where no two distinct members share the same first element.
• If <x,y> ∈ F and <x,z> ∈ F, then y=z.
• If <x,y> ∈ F:
  • x is an argument of F
  • y is the value of F at x
  • y is the image of x under F
• F(x) designates the object y such that y = F(X)

Expressing functions with FOL

• Example: hat = {<c,b>, <b,a>,<e,d>}
• Then: hat (c) = b and hat(b) = a
• Possible FOL expressions for this example might resemble:
• On(A,B), On(B,C)
• On(D,E)
• On(A,Hat(C))

Syntax of First Order Logic (Formal)

• Sentence → Atomic Sentence | (sentence connective Sentence) | Quantifier variable,… Sentence | ¬ Sentence
• Atomic Sentence → Predicate (Term,…) | Term=Term
• Term → Function(Term,…) | Constant | variable
• Connective → ⇔ | ∧ | ∨ | ⇒ Quantifier → ∀ | ∃
• Constant → A | X₁
• Variable → a | x | s
• Predicate → Before | hascolor | ….
• Function → Mother | Leftleg |…

Inference in First Order Logic Methods

• Reducing first-order inference to propositional inference
• Unification
• Generalized Modus Ponens
• Resolution
• Forward chaining
• Backward chaining

FOL to PL Inference

• First-order inference can be done by converting KB to PL and using propositional inference.
• Universal quantifiers are converted by replacing variables with ground terms (Universal Elimination).
• Existential quantifiers are converted through Skolemization (Existential Elimination).

Substitution and Inference

• Given a sentence α and a binding list σ, Subst(σ, α) is the result of applying the substitution σ to α.
• Example: If σ = {x/Ali, y/Ahmad} and α = Likes(x,y), then Subst(σ, α) = Likes(Ali, Ahmad).

Universal Instantiation (UI)

• Every instantiation of a universally quantified sentence is entailed by it.
• For any variable v and ground term g: Subst({v/g}, α)

Existential Instantiation (EI)

• For any sentence α, variable v, and constant symbol k (not appearing elsewhere in KB): Subst({v/k}, α)
• e.g., ∃x Crown(x) ∧ OnHead(x,John) yields:
• Crown(C1) ∧ OnHead(C1,John), where C1 is a Skolem constant

Reduction to Propositional Inference Process

• Instantiate the universal sentence in all possible ways to propositionalize the KB.

Claims on Reduction to PL

• A ground sentence is entailed by a new KB if and only if entailed by the original KB.
• Every FOL KB can be propositionalized to preserve entailment.
• Propositionalize KB and query, then apply resolution and return result
• With function symbols, there are infinitely many ground terms

Inference with FOL Without Translating to PL

• Make inference rules work directly in FOL for efficiency.
• Substitute values directly to obtain results

Unification Details

• Find a substitution such that expressions match.
• Unify(α, β) = θ if Subst(θ, α) = Subst(θ, β)
• Returns a substitution list to translate logic to a single instance for evaluation

Generalized Modus Ponens (GMP) Details

• If Subst(θ, pi') = Subst(θ, pi) for all i, then infer Subst(θ, q) from p1', p2', ..., pn', and (p1 ∧ p2 ∧ ... ∧ pn ⇒ q).
• All variables are universally quantified.

Resolution

• General form including unifier and substitutions: Subst( θ, l₁ ∨ ··· ∨ li-1 ∨ li+1 ∨ ··· ∨ lk ∨ m₁ ∨ ··· ∨ mj-1 ∨ mj+1 ∨ ··· ∨ mn)
• Complete for FOL when applying to CNF(KB ∧ ¬α)

Forward Chaining

• When a new fact P is found:
• Check each rule to see if P unifies with a premise
• If the other premises are known, then add the conclusion to the KB and continue chaining.
• Data-driven, inferring properties and categories from percepts.

Backward Chaining

• Backward chaining starts with a hypothesis and works backwards, using the rules in the knowledge base until confirmed findings or facts are reached.

Semantic Networks

• A semantic network consists of entities and relations between the entities.
• Generally, it is represented as a graph.

Frames

• A frame is a data structure whose components are called slots.
• Slots have names and accommodate information of various kinds.
• Contains examples in the form of Frame: Bird, A_kind_of: animal etc