《Artificial Intelligence：A Modern Approach》教学资源（PPT课件，英文版）Chapter 8-First-Order Logic

First-Order Logic Chapter 8

First-Order Logic Chapter 8

Outline ·Vhy FOL? Syntax and semantics of FOL ·Using FOL ·Vumpus world in FOL Knowledge engineering in FOL

Outline • Why FOL? • Syntax and semantics of FOL • Using FOL • Wumpus world in FOL • Knowledge engineering in FOL

Pros and cons of propositional logic Propositional logic is declarative Propositional logic allows partial/disjunctive/negated information -(unlike most data structures and databases) Propositional logic is compositional: © -meaning of B1.1A P12 is derived from meaning of B1.1 and of P1.2 Meaning in propositional logic is context-independent -(unlike natural language,where meaning depends on context) Propositional logic has very limited expressive power

Pros and cons of propositional logic ☺ Propositional logic is declarative ☺ Propositional logic allows partial/disjunctive/negated information – (unlike most data structures and databases) – ☺ Propositional logic is compositional: ☺ – meaning of B1,1  P1,2 is derived from meaning of B1,1 and of P1,2 – ☺ Meaning in propositional logic is context-independent – (unlike natural language, where meaning depends on context) –  Propositional logic has very limited expressive power

First-order logic Whereas propositional logic assumes the world contains facts, first-order logic (like natural language) assumes the world contains ● -Objects:people,houses,numbers,colors, baseball games,wars,.. -Relations:red,round,prime,brother of, bigger than,part of,comes between,.. -Functions:father of,best friend,one more than nlue

First-order logic • Whereas propositional logic assumes the world contains facts, • first-order logic (like natural language) assumes the world contains • – Objects: people, houses, numbers, colors, baseball games, wars, … – – Relations: red, round, prime, brother of, bigger than, part of, comes between, … – Functions: father of, best friend, one more than, plus, …

Syntax of FOL:Basic elements ·Constants KingJohn,2,NUS,... ·Predicates Brother,>,.. 。Functions Sqrt,LeftLegof,... 。Variables X,y;a,b,... ·Connectives,→，入，V,→ ·Equality ·Quantifiers V,J

Syntax of FOL: Basic elements • Constants KingJohn, 2, NUS,... • Predicates Brother, >,... • Functions Sqrt, LeftLegOf,... • Variables x, y, a, b,... • Connectives , , , ,  • Equality = • Quantifiers , 

Atomic sentences Atomic sentence predicate (term,...,term) or term=term2 Term function (term,...,term) or constant or variable E.g.,Brother(KingJohn,RichardTheLionheart)> (Length(LeftLegOf(Richard)), Length(LeftLegOf(KingJohn)))

Atomic sentences Atomic sentence = predicate (term1 ,...,termn ) or term1 = term2 Term = function (term1 ,...,termn ) or constant or variable • E.g., Brother(KingJohn,RichardTheLionheart) > (Length(LeftLegOf(Richard)), Length(LeftLegOf(KingJohn)))

Complex sentences Complex sentences are made from atomic sentences using connectives S,S1ΛS2,S1VS2,S1→S2,S1台S2, E.g.Sibling(KingJohn,Richard) Sibling(Richard,KingJohn) >(1,2)V≤(1,2) >(1,2)Λ>(1,2)

Complex sentences • Complex sentences are made from atomic sentences using connectives • S, S1  S2 , S1  S2 , S1  S2 , S1  S2 , E.g. Sibling(KingJohn,Richard)  Sibling(Richard,KingJohn) >(1,2)  ≤ (1,2) >(1,2)   >(1,2)

Truth in first-order logic Sentences are true with respect to a model and an interpretation Model contains objects(domain elements)and relations among them Interpretation specifies referents for constant symbols → objects predicate symbols → relations function symbols functional relations An atomic sentence predicate(termj,...,tem)is true iff the objects referred to by term,...,termn are in the relation referred to by predicate

Truth in first-order logic • Sentences are true with respect to a model and an interpretation • Model contains objects (domain elements) and relations among them • • Interpretation specifies referents for constant symbols → objects predicate symbols → relations function symbols → functional relations • An atomic sentence predicate(term1 ,...,termn ) is true iff the objects referred to by term1 ,...,termn are in the relation referred to by predicate

Models for FOL:Example crown on head person brother person brother king left leg left leg

Models for FOL: Example

Universal quantification V Everyone at NUS is smart: Vx At(X,NUS)Smart(x) Vx P is true in a model m iff P is true with x being each possible object in the model Roughly speaking,equivalent to the conjunction of instantiations of P At(KingJohn,NUS)Smart(KingJohn) At(Richard,NUS)=Smart(Richard)

Universal quantification •  • Everyone at NUS is smart: x At(x,NUS)  Smart(x) • x P is true in a model m iff P is true with x being each possible object in the model • • Roughly speaking, equivalent to the conjunction of instantiations of P • At(KingJohn,NUS)  Smart(KingJohn)  At(Richard,NUS)  Smart(Richard)  At(NUS,NUS)  Smart(NUS)