赵才荣 E-mail：zhaocairong@tongji.edu.cn 同济大学，电子与信息工程学院，智信馆410室 《人工智能原理》课程 第八章 一阶逻辑 一阶逻辑 赵才荣 E-mail：zhaocairong@tongji.edu.cn 同济大学，电子与信息工程学院，智信馆410室 理性的Agent是人工智能方法的核心 通过对Agent从感知外部环境，到实施行动，并最后对外部环境施加影响的全过程，把AI中相互分离的主要领域，如问题求解，知识与推理，合乎逻辑 的行动，不确定知识与推理，学习以及通信、感知与行动等统一在智能Agent这一框架下，形成了一个相互联系的整体。

Outline Why FOL? Syntax and semantics of FOL Using FOL Wumpus world in FOL Knowledge engineering in FOL 1.弄清楚置换与合一的概念 2.掌握求取最一般合一置换的方法 3.掌握Skolem标准式和子句集的求取方法 上海市精品课程 人工智能原理

Limitations of propositional logic So far we studied propositional logic Some English statements are hard to model in propositional logic: “If your roommate is wet because of rain, your roommate must not be carrying any umbrella” Pathetic attempt at modeling this: RoommateWetBecauseOfRain => (NOT(RoommateCarryingUmbrella0) AND NOT(RoommateCarryingUmbrella1) AND NOT(RoommateCarryingUmbrella2) AND …) 命题逻辑的局限性： 命题逻辑足以阐述逻辑和基于知识的agent的基本概念。但是命题逻辑是一种表达能力很弱的语言，无法以简洁的方式表示复杂的环境的知识。 上海市精品课程 人工智能原理

Problems with propositional logic Whereas propositional logic assumes the world consists of facts No notion of objects No notion of relations among objects RoommateCarryingUmbrella0 is instructive to us, suggesting there is an object we call Roommate, there is an object we call Umbrella0, there is a relationship Carrying between these two objects Formally, none of this meaning is there Might as well have replaced RoommateCarryingUmbrella0 by P 命题逻辑中存在的问题：基于语句和可能世界（事实构成）的真值关系。没有对象和关系的概念。 命题逻辑是一种描述性语言。 自然语言的特点：最明显的元素，对象和对象之间的关系（属性），函数。 采用命题逻辑的基础上，（即一种描述式的、上下文无关且无歧义性的合成语义）借用自然语言的表达思想 同时避开它的缺点，构造一种更具有表达能力的逻辑，即一阶逻辑。 一阶逻辑语言是围绕对象和关系建立起来的。 命题逻辑和一阶逻辑之间最根本的区别在于每种语言所给出的本体论约定。命题逻辑假定世界中的事实要么成立要么不成立。 一阶逻辑假定对象之间的关系或者成立或者不成立。 上海市精品课程 人工智能原理

Elements of first-order logic Objects: can give these names such as Umbrella0, Person0, John, Earth, wheel, door, body … Relations: Carrying(., .), IsAnUmbrella(.) Carrying(Person0, Umbrella0), IsUmbrella(Umbrella0) Relations with one object = unary relations = properties such as red, round, prime, Functions: Roommate(.), ColorOf(.) Roommate(Person0), ColorOf(car) Equality: Roommate(Person0) = Person1 一阶逻辑的组成元素 对象(个体)：具体或者抽象（名词或者代词组成） 关系（属性）：可以是(unary)一元关系或者n元关系。即谓词：刻画个体词的性质或者个体词之间关系的词。谓词，分为常项和变项 函数： 等价：？？ 量词：表示数量的词 上海市精品课程 人工智能原理

Semantics there is a correspondence between functions, which return values predicates, which are true or false Function: father_of(Mary) = Bill Predicate: father_of(Mary, Bill) Functions are relations with single value for each object 语义： 模型中的对象可能以多种方式相互关联。 形式化地说，关系只是相互关联的对象的元组集合。 一阶逻辑的基本句法元素是表示对象，关系和函数的符号。 这些符号分三类：表示对象的常量符号；表示关系的谓词符号；表示函数的函词。 一阶逻辑的模型包括对象集及其解释，解释将常量符号映射到对象、谓词符号映射到对象之间的关系、函词映射到对象上的函数。 上海市精品课程 人工智能原理

Syntax of FOL: Basic elements Constants KingJohn, 2, NUS,... Predicates Brother, >, Person(John)... Functions Sqrt, LeftLegOf,... Variables x, y, a, b,... Connectives , , , ,  Equality = Quantifiers ,  归纳起来，一阶逻辑的语法包括以下基本部分 常量： 谓词： 函数： 变量： 连接词： 等价： 量词： 上海市精品课程 人工智能原理

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 and quantifiers S, S1  S2, S1  S2, S1  S2, S1  S2, E.g. Sibling(KingJohn,Richard)  Sibling(Richard,KingJohn) 复合语句：由逻辑连接词构成的语句。 上海市精品课程 人工智能原理

Syntax of FOL Syntax of Propositional Logic 语法： 上海市精品课程 人工智能原理

Semantics of FOL 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 包含五个对象：Richard the lionheart; the evil King John; Richard 和 John的左腿；一个王冠 （crown） 两个二元关系：Brother , On head; 三个一元关系：(用对象上的标注表示)；属性：person,king,crown 以及一个一元函数：Leftleg 【1189-1199 在位的英格兰国王Richard;他的弟弟the evil King John从1199到1215年统治英格兰】 上海市精品课程 人工智能原理

Universal quantification <variables> <sentence> x P(x) Everyone at NUS is smart: Why not x At(x,UNC)  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)  ... 有了允许对象存在的逻辑，那么很自然地想要表达全部对象集合的属性。 一个逻辑有两个标准量词：全称量词，存在量词 全称量词：如果在根据给定解释构成的所有可能扩展解释为真，则给定解释下的给定模型为真。 读为：“对于所有的……” 变量，按照惯例，变量用小写字母表示 没有变量的项称为基项 上海市精品课程 人工智能原理

A common mistake to avoid Typically,  is the main connective with  Common mistake: using  as the main connective with : x At(x,NUS)  Smart(x) means “Everyone is at NUS and everyone is smart” 蕴涵是在使用全称量词时的自然连接词 ??常范错误：用合取词替代蕴涵词！ 通过真值表可以直观的发现，这样不对。 上海市精品课程 人工智能原理

Existential quantification <variables> <sentence> x P(x) Someone at NUS is smart: Why not x At(x,UNC)  Smart(x)? x P is true in a model m iff P is true with x being some possible object in the model Roughly speaking, equivalent to the disjunction of instantiations of P At(KingJohn,NUS)  Smart(KingJohn)  At(Richard,NUS)  Smart(Richard)  At(NUS,NUS)  Smart(NUS)  ... 存在量词，读为“存在x，使得……” 存在量词表示至少存在一个对象x,使得P为真。 上海市精品课程 人工智能原理

Another common mistake to avoid Typically,  is the main connective with  Common mistake: using  as the main connective with : x At(x,NUS)  Smart(x) is true if there is anyone who is not at NUS! 合取是使用存在量词时的自然连接词。 （蕴涵通常会使陈述过弱） 到此结束：转练习 上海市精品课程 人工智能原理

Properties of quantifiers x y is the same as y x x y is the same as y x x y is not the same as y x x y Loves(x,y) “There is a person who loves everyone in the world y x Loves(x,y) “Everyone in the world is loved by at least one person Quantifier duality: each can be expressed using the other x Likes(x,IceCream) x Likes(x,IceCream) x Likes(x,Broccoli) x Likes(x,Broccoli) 嵌套量词：采用多个量词可以表示更复杂的语句。 x y Loves(x,y)：存在某人爱每个人。 y x Loves(x,y)：对每个人，都会存在爱此人的人。 由此看出量词的顺序很重要。 全称量词和存在量词之间的关联：两者通过否定词紧密相关。 全称量词是论域上所有对象的合取式，而存在量词时析取式，所以他们遵循摩根定律。 x Likes(x,IceCream) ，每个人都喜欢冰激凌；x Likes(x,IceCream)，没有人不喜欢冰激凌 x Likes(x,Broccoli) 有人喜欢西兰花； x Likes(x,Broccoli)，不是每人都不喜欢西兰花 用于量化语句的摩根定律 上海市精品课程 人工智能原理

Equality term1 = term2 is true under a given interpretation if and only if term1 and term2 refer to the same object E.g., definition of Sibling in terms of Parent: x,y Sibling(x,y)  [(x = y)  m,f  (m = f)  Parent(m,x)  Parent(f,x)  Parent(m,y)  Parent(f,y)] 等词：一阶逻辑使用等词来声明两个项指代同一个对象。 到此结束：转练习 上海市精品课程 人工智能原理

Using FOL Brothers are siblings One's mother is one's female parent x,y Brother(x,y)  Sibling(x,y) One's mother is one's female parent m,c Mother(c) = m  (Female(m)  Parent(m,c)) “Sibling” is symmetric x,y Sibling(x,y)  Sibling(y,x) 8.3 运用一阶逻辑 亲属关系论域： 上海市精品课程 人工智能原理

Using FOL The set domain: s Set(s)  (s = {} )  (x,s2 Set(s2)  s = {x|s2}) x,s {x|s} = {} x,s x  s  s = {x|s} x,s x  s  [ y,s2 (s = {y|s2}  (x = y  x  s2))] s1,s2 s1  s2  (x x  s1  x  s2) s1,s2 (s1 = s2)  (s1  s2  s2  s1) x,s1,s2 x  (s1  s2)  (x  s1  x  s2) x,s1,s2 x  (s1  s2)  (x  s1  x  s2) 数，集合，表 {} ,空集；一元谓词Set判断对象是否为集合；二元谓词x  s （x是集合s中的一个元素）； s1  s2 ,集合s1是集合s2的子集；s1  s2，两个集合的交，s1  s2，两个集合的并；x|s，把元素x添加到集合s而产生的集合。 ？？？ 可能的公理集如下： .集合是空集或通过将一些元素添加到集合中而构成； .集合中没有任何元素，即，空集无法再分解为更小的集合和元素 .将已经存在于集合中的元素添加到该集合中，该集合无任何变化 .集合的元素是哪些被添加到集合中的元素 .一个集合是另一个集合的子集，当且仅当第一个集合的所有元素都是第二个集合的元素 .两个集合相等当且仅当他们互为子集 .一个对象属于两个集合的交集，当且仅当它同时是这两个集合的元素 .一个对象属于两个集合的并集，当且仅当它是其中任一集合的元素。 上海市精品课程 人工智能原理

Why “First order”? FOL permits quantification over variables Higher order logics permit quantification over functions and predicates: P,x [P(x)  P(x)] x,y (x=y)  [P (P(x)P(y))] 一阶逻辑：允许量化陈述的公式 一阶逻辑是区别于高阶逻辑的数理逻辑，它不允许量化性质 上海市精品课程 人工智能原理

Knowledge base for the wumpus world Perception t,s,b Percept([s,b,Glitter],t)  Glitter(t) Reflex t Glitter(t)  BestAction(Grab,t) 一阶逻辑运用于wumpus 世界 感知： 反射： 上海市精品课程 人工智能原理

Deducing hidden properties x,y,a,b Adjacent([x,y],[a,b])  [a,b]  {[x+1,y], [x-1,y],[x,y+1],[x,y-1]} Properties of squares: s,t At(Agent,s,t)  Breeze(t)  Breezy(s) Squares are breezy near a pit: Diagnostic rule---infer cause from effect s Breezy(s)  \Exi{r} Adjacent(r,s)  Pit(r)$ Causal rule---infer effect from cause r Pit(r)  [s Adjacent(r,s)  Breezy(s)$ ] 任何两个方格相邻可以定义为： 上海市精品课程 人工智能原理

Knowledge engineering in FOL Debug the knowledge base 8.4 一阶逻辑的知识工程 确定任务 搜集相关知识 确定词汇表，包括谓词、函词和常量 对领域通用知识编码 对特定问题实例描述编码 把查询提交给推理过程并获取答案 知识库调试 上海市精品课程 人工智能原理

The electronic circuits domain One-bit full adder 一位全加器电路 上海市精品课程 人工智能原理

The electronic circuits domain Identify the task Does the circuit actually add properly? (circuit verification) Assemble the relevant knowledge Composed of wires and gates; Types of gates (AND, OR, XOR, NOT) Irrelevant: size, shape, color, cost of gates Decide on a vocabulary Alternatives: Type(X1) = XOR Type(X1, XOR) XOR(X1) 上海市精品课程 人工智能原理

The electronic circuits domain Encode general knowledge of the domain t1,t2 Connected(t1, t2)  Signal(t1) = Signal(t2) g Type(g) = NOT  Signal(Out(1,g)) ≠ Signal(In(1,g)) 上海市精品课程 人工智能原理

The electronic circuits domain Encode the specific problem instance Type(X1) = XOR Type(X2) = XOR Type(A1) = AND Type(A2) = AND Type(O1) = OR Connected(Out(1,X1),In(1,X2)) Connected(In(1,C1),In(1,X1)) Connected(Out(1,X1),In(2,A2)) Connected(In(1,C1),In(1,A1)) Connected(Out(1,A2),In(1,O1)) Connected(In(2,C1),In(2,X1)) Connected(Out(1,A1),In(2,O1)) Connected(In(2,C1),In(2,A1)) Connected(Out(1,X2),Out(1,C1)) Connected(In(3,C1),In(2,X2)) Connected(Out(1,O1),Out(2,C1)) Connected(In(3,C1),In(1,A2)) 上海市精品课程 人工智能原理

The electronic circuits domain Pose queries to the inference procedure What are the possible sets of values of all the terminals for the adder circuit? i1,i2,i3,o1,o2 Signal(In(1,C_1)) = i1  Signal(In(2,C1)) = i2  Signal(In(3,C1)) = i3  Signal(Out(1,C1)) = o1  Signal(Out(2,C1)) = o2 Debug the knowledge base May have omitted assertions like 1 ≠ 0 上海市精品课程 人工智能原理

Summary First-order logic: objects and relations are semantic primitives syntax: constants, functions, predicates, equality, quantifiers Increased expressive power: sufficient to define wumpus world 上海市精品课程 人工智能原理

Thank you