First-Order Logic Overview

Created by

@BlitheAloe

Study Notes

Propositional Logic is limited in representing complex statements like "All humans are mortal" or "Some people can run a marathon".

Assumes the world contains objects, relationships between objects, and functions.

Contains:
- Constants: Represent specific entities (e.g., John, Sally, 2).
- Variables: Represent unspecified entities (e.g., x, y, a, b).
- Predicates: Represent relationships between objects (e.g., Person(John), Siblings(John, Sally), IsOdd(2)).
- Functions: Represent operations on entities (e.g., MotherOf(John), Sqrt(x)).
- Connectives: Similar to propositional logic (e.g., ¬, ∧, ∨, ⇒, ⇔).
- Equality: Represents equivalence (e.g., =).
- Quantifiers: Represent scope of statements (e.g., ∀, ∃).
Terms are built from constants, variables, and functions.
Atomic sentences are created using predicates and terms.
Complex sentences are constructed from atomic sentences using connectives and quantifiers.

Truth of sentences is determined by models and interpretations.
Models include objects and relations among them.
Interpretations map:
- Constant symbols to objects.
- Predicate symbols to relations.
- Function symbols to functional relations.
An atomic sentence is considered true if the objects referred to by its terms are in the relationship defined by the predicate.

Represented by ∀x P(x)
Example: "Everyone at UNC is smart" can be expressed as ∀x At(x,UNC) ⇒ Smart(x).
∀x P(x) is true in a model if P(x) is true for every object in the model's domain.

Represented by ∃x P(x)
Example: "Someone at UNC is smart" can be expressed as ∃x At(x,UNC) ∧ Smart(x).
∃x P(x) is true in a model if P(x) is true for at least one object in the model's domain.

Order matters:
- ∀x ∀y is equivalent to ∀y∀x
- ∃x ∃y is equivalent to ∃y∃x
- ∃x ∀y is not equivalent to ∀y∃x
Quantifier duality: Each quantifier can be expressed using the other with negation.
- ∀x Likes(x,IceCream) is equivalent to ¬∃x ¬Likes(x,IceCream)
- ∃x Likes(x,Broccoli) is equivalent to ¬∀x ¬Likes(x,Broccoli)

FOL can be used to represent family relationships. For example:
- Brothers are siblings: ∀x,y Brother(x,y) ⇒ Sibling(x,y)
- Sibling is symmetric: ∀x,y Sibling(x,y) ⇔ Sibling(y,x)
- One's mother is one's female parent: ∀m,c (Mother(c) = m) ⇔ (Female(m) ∧ Parent(m,c))

All rules of inference from propositional logic apply to FOL.
FOL sentences can be reduced to propositional logic sentences by instantiating variables and removing quantifiers.

Universal quantification is handled by instantiating the sentence for each object in the domain.
Existential quantification is handled by introducing a new constant that doesn't appear in the knowledge base.