First-Order Logic Overview

Limitations of Propositional Logic

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

First-Order Logic

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

Syntax of FOL

• 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.

Semantics of FOL

• 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.

Universal Quantification

• 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.

Existential Quantification

• 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.

Properties of Quantifiers

• 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)

Equality

• Term1 = Term2 is true in a model if both terms refer to the same object.

Using FOL: The Kinship Domain

• 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))

Why "First Order"?

• FOL allows quantification over variables.
• Higher-order logics permit quantification over functions and predicates.

Inference in FOL

• 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.

Reduction of FOL to PL

• 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.

Substitution

• Used to replace variables with ground terms.
  • SUBST({v/g},P): Replaces variable v with ground term g in predicate P.

Universal Instantiation (UI)

• Used to derive new sentences from universally quantified sentences.
• Allows us to conclude specific instances from general statements.

Explore the limitations of Propositional Logic and the fundamentals of First-Order Logic. Understand the key components including constants, variables, predicates, and quantifiers. This quiz covers the syntax and essential constructs of FOL to enhance your logical reasoning skills.