First-Order Logic and Inference in FOL 吉建民 USTC jianminOustc.edu.cn 2022年4月11日 4口◆4⊙t1三1=，￥9QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . First-Order Logic and Inference in FOL 吉建民 USTC jianmin@ustc.edu.cn 2022 年 4 月 11 日
Used Materials Disclaimer:本课件采用了S.Russell and P.Norvig's Artificial Intelligence-A modern approach slides,徐林莉老师课件和其他网 络课程课件，也采用了GitHub中开源代码，以及部分网络博客 内容 口卡4三4色进分QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Used Materials Disclaimer: 本课件采用了 S. Russell and P. Norvig’s Artificial Intelligence –A modern approach slides, 徐林莉老师课件和其他网 络课程课件，也采用了 GitHub 中开源代码，以及部分网络博客 内容
Last chapter Logical agents apply inference to a knowledge base to derive new information and make decisions Basic concepts of logic: ~syntax(语法)：formal structure of sentences =semantics (语义：truth of sentences wrt.models entailment (蕴涵)：necessary truth of one sentence given another inference (推理)：deriving sentences from other sentences soundness (可靠性)：derivations produce only entailed sentences completeness (完备性)：derivations can produce all entailed sentences Forward,backward chaining are linear-time,complete for Horn clauses Resolution is complete for propositional logic Propositional logic lacks expressive power 口◆461三1，是90C
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Last chapter ▶ Logical agents apply inference to a knowledge base to derive new information and make decisions ▶ Basic concepts of logic: ▶ syntaxffffffff(语法): formal structure of sentences ▶ semanticsffffffff(语义): truth of sentences wrt. models ▶ entailmentffffffff(蕴涵): necessary truth of one sentence given another ▶ inferenceffffffff(推理): deriving sentences from other sentences ▶ soundnessffffffffff(可靠性): derivations produce only entailed sentences ▶ completenessffffffffff(完备性): derivations can produce all entailed sentences ▶ Forward, backward chaining are linear-time, complete for Horn clauses ▶ Resolution is complete for propositional logic ▶ Propositional logic lacks expressive power
Table of Contents First-Order Logic Why FOL? Syntax and semantics of FOL Using FOL Knowledge engineering in FOL Inference in FOL Reducing first-order inference to propositional inference Unification(合一 Generalized Modus Ponens(一般化分离规则) Forward and backward chaining Resolution 口卡回t·三4色，是分Q0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table of Contents First-Order Logic Why FOL? Syntax and semantics of FOL Using FOL Knowledge engineering in FOL Inference in FOL Reducing first-order inference to propositional inference Unification (合一) Generalized Modus Ponens（一般化分离规则） Forward and backward chaining Resolution
Pros 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 A 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 口◆4日1三1，是90C
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Pros 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
Cons of propositional logic Propositional logic has very limited expressive power unlike natural language E.g.,cannot say "pits cause breezes in adjacent squares" except by writing one sentence for each square B1,1台(P1,2VP2,1) 口卡4三4色进分QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cons of propositional logic ▶ Propositional logic has very limited expressive power ▶ unlike natural language ▶ E.g., cannot say “pits cause breezes in adjacent squares” except by writing one sentence for each square B1,1 ⇔ (P1,2 ∨ P2,1)
Cons of propositional logic All students know arithmetic. AlicelsStudent-AliceKnowsArithmetic BoblsStudent-BobKnowsArithmetic 44 Propositional logic is very clunky.What's missing? Objects and relations:propositions (e.g., AliceKnowsArithmetic)have more internal structure (alice, Knows,arithmetic) Quantifiers and variables:all is a quantifier which applies to each person,don't want to enumerate them all... 4口◆4⊙t1三1=，￥9QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cons of propositional logic ▶ All students know arithmetic. ▶ AliceIsStudent → AliceKnowsArithmetic ▶ BobIsStudent → BobKnowsArithmetic ... ▶ Propositional logic is very clunky. What’s missing? ▶ Objects and relations: propositions (e.g., AliceKnowsArithmetic) have more internal structure (alice, Knows, arithmetic) ▶ Quantifiers and variables: all is a quantifier which applies to each person, don’t want to enumerate them all
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, 谓词用来描述个体（可以独立存在的事物）之间的关系或属性 口卡回+·三色是分Q
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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, … 谓词用来描述个体（可以独立存在的事物）之间的关系或属性
Logics in general 本体论约定 认识论约定 语言 (世界中存在的) (智能体对事实 所相信的内容) 命题逻辑 Propositional logic 事实 真/假/未知 一阶逻辑 First-order logic 事实、对象、关系 真/假/未知 时序逻辑 Temporal logic 事实、对象、关系、时间 真/假/未知 概率逻辑 Probability logic 事实 信度∈[0,1] 4口404三·1=，生9QG
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Logics in general 语言 本体论约定 （世界中存在的） 认识论约定 （智能体对事实 所相信的内容） 命题逻辑 Propositional logic 事实 真/假/未知 一阶逻辑 First-order logic 事实、对象、关系 真/假/未知 时序逻辑 Temporal logic 事实、对象、关系、时间 真/假/未知 概率逻辑 Probability logic 事实 信度 ∈[0,1]
一阶逻辑的模型：Example crown M on head person brother person brother king left leg left leg 口·三，4色，进分Q0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 一阶逻辑的模型: Example
