04 First-Order Logic

Question 1

From propositonal to first-order logic

Answer 1

Features of propositional logic:
+ Declarative
+ Compositional
+ “Possible-world” semantics
- Lacks expressiveness

First-order logic:
• Extends propositional logic
• Keeps good features
• Adds expressiveness

Question 2

First-order logic

Answer 2

First-order logic is based on “common sense” or linguistic concepts:
• Objects: people, houses, numbers, . . .
• Properties: tall, red, . . .
• Relations: brother, bigger than, . . .
• Functions : father of, roof of, . . .
• Variables : x, y, . . . (takes objects as values)

First-order logic is the most important and best understood logic in philosophy, mathematics, and AI

Question 3

Logical commitments

Answer 3

• Ontological commitment
– Ontology - in philosophy, the study of “what is”
– What are the underlying assumptions of the logic with respect to the nature of reality

• Epistemological commitment
– Epistemology - in philosophy, the study of “what can be known”
– What are the underlying assumptions of the logic with respect to the nature of what the agent can know

Question 4

FOL: Syntax

Answer 4

• *Constants, predicates, functions and terms**
• *Constant** symbols refer to specific objects in the world: John, 3, . . .

Predicate symbols refer to particular relations in the model: Brother, LargerThan, i.e. sets of objects that satisfy the relation

Function symbols refer to many-t-one object mappings: FatherOf

Term, a logical expression refers to an object in the model. Can be a Constant, a Variable, or a Function of other terms.

• *Atomic and complex sentences**
• *Atomic sentences** state basic facts.

Brother(Richard,John) Married(FatherOf(Richard),MotherOf(John))

Complex sentences is composed of atomic sentences by using logical connectives (same as for propositional logic)

Brother(Richard, John) ^ Brother (John, Richard) Older(John,30) ) ¬Younger(John, 30).

Quantifiers and equality
Quantifiers are used to express properties of classes of objects.
- Universal quantification: “For all …”
- Existential quantification: “There exists . . . “

Equality = Two terms refer to same object
Father(John) = Henry

Question 5

Kinship domain

Answer 5

The domain of family relationship
• Objects: Persons
• Unary predicates: Male, Female
• Binary predicates: Parent, Sibling, Brother, Sister, . . .
• Functions: Mother , Father

Question 6

TELLing and ASKing sentences

Answer 6

Question 7

First-order inference

Answer 7

• Reduce to propositional inference
• Generalized Modus Ponens
• Forward chaining
• Backward chaining
​• Resolution
• Require substitution and/or unification of terms

Question 8

Substitution and unification

Answer 8

Substitution is the replacement of variable(s) in a sentence with expressions SUBST(x/Richard,y/John,Brother(x,y)) = Brother(Richard,John)

Question 9

Reduce to propositional inference

Answer 9

Can reduce first-order sentence to propositional sentence by instantiation rules
• UI - Universal instantiation - Substitutes a constant in KB for a universally quantified variable
• EI - Existential instantiation - Substitutes a new constant for an existentially quantified variable

Apply UI and EI systematically to replace all sentences with quantifiers with variable-free sentences. Can use propositional inference rules to derive proofs, but it is an inefficient procedure.

Question 10

Generalized Modus Podens

Answer 10

Question 11

Completeness

Answer 11

First-order logic is complete. If a sentence is entailed by KB, then this can be proved (Gödel’s completeness theorem, 1930).

But generalized modus ponens is not complete.

However, first-order logic is semi-decidable. If the sentence is not entailed by the KB, this can not always be shown.

Extension of first-order logic with mathematical induction is incomplete. There are true statements that cannot be proved (Gödel’s incompleteness theorem, 1931).

Question 12

Forward chaining - FC

Answer 12

Start with sentences in KB, apply inference rules in forward direction, adding new sentences until goal found or no further inference can be made.

Production systems using FC
Main features
• Consists of rule base and working memory
• Uses rule matching and forward chaining to add facts to the working memory until a solution is found
• Rete networks are used to speed up matching

Applications
• Used in many expert systems, especially early ones • Design and configuration systems
• Real-time monitoring and alarming
• “Cognitive architectures” (SOAR)

Question 13

Backward chaining - BC

Answer 13

Start with goal sentence, search for rules that support goal, adding new sub-goals until match with KB facts or no further inference can be made.

Logic programming using BC
Main features
• Restricted form of first-order logic
• Mixes control information with declarative sentences
• Backward chaining search: Prove a goal

Prolog is the dominant logic programming language, and has been used for
• Expert systems
• Natural language systems
• Compilers
• Many others

Question 14

Resolution

Answer 14

Resolution
A complete inference procedure