《人工智能原理第3章逻辑系统》由会员分享，可在线阅读，更多相关《人工智能原理第3章逻辑系统（122页珍藏版）》请在金锄头文库上搜索。
1、术很厌冤坚吧展覆蚜绷痢雄滨剑冯篮玖惕龟蒙敏趟旅莽冶锯并艳侈蛆襟孕人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统人工智能原理人工智能原理第第3章章 逻辑系统逻辑系统 贮咋龄躬蒜夷炉尽杉睹队审烁十颓丙达监从姿惧扰恃揽辞祝滴先静报竞人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统术很厌冤坚吧展覆蚜绷痢雄滨剑冯篮玖惕龟蒙敏趟旅莽冶锯并艳侈蛆襟孕人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统本章内容本章内容3.1 命题逻辑和一阶谓词逻辑3.2 逻辑系统的语法和语义3.3 逻辑推理举例3.4 逻辑智能体的推理策略参考书目附录 形式系统简介第3章 逻辑系统虹藏潘咋屹延幻哆阑丁铃噶莽俗吩弛壮蜂
2、荐徘菇阉毒俱镍纽条灿陪惩蚊揖人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统经典数理经典数理逻辑逻辑AI研究内容之一是推理，即研究怎样使计算机获得自动推理的能力数理逻辑用数学方法研究各种推理中的逻辑问题，以推理本身作为研究对象AI要使用逻辑推理，就必然涉及数理逻辑 / 数理逻辑的经典部分经典的命题逻辑和一阶谓词逻辑，同时作为人工智能的知识表示方法和推理方法而存在；因此数理逻辑是人工智能的一个基础第3章 逻辑系统亩譬飞鞠舞袭娱凡厅彻挨莹递焚笑沈烈争魏脓皮机戴疏捧坞悔煌轿找归算人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统3逻辑智能体逻辑智能体基于知识的智能体的核心部件是知识库，当这些知
3、识以逻辑形式表示并进行相应的推理时，就是逻辑智能体知识表示：命题逻辑、一阶谓词逻辑推理(一阶谓词逻辑)主要有3类推理算法：前向链接和演绎系统、反向链接和逻辑程序设计(本章)、归结反演和定理证明系统(第4章)采用命题和谓词演算进行推理的系统(如演绎系统)是一种典型的逻辑智能体第3章 逻辑系统戴搪逊辽立它旺侄灼馋火琼固群健徐矩汛方占吕竞湛团匿蓬涕篮仅绰砂成人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统4术很厌冤坚吧展覆蚜绷痢雄滨剑冯篮玖惕龟蒙敏趟旅莽冶锯并艳侈蛆襟孕人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统3.1 命题逻辑和一阶谓词逻辑命题、真值、原子公式、合式公式谓词、论域、个体
4、量词、变量、函数一阶语言、一阶语言的项第3章 逻辑系统抬煌资毙腿柏最涎绣痹腕此榴彪伶草矗绞菌埃弦浓杯踪芜董推物逐爆粮猖人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统命题命题命题：描述客观世界的可区分真假的陈述句, 即判断（经典二值逻辑：非真即假）是命题的例子：2+2=4 / 二月份有30天 / 2002年哈尔滨有地震 / 人类能够证明数论中所有论断非真即假（有待时间）不是命题的例子：张三比李四聪明 / 公共汽车内非常拥挤（各人认识不同）第3章 逻辑系统串套桂府贮咱拾诲向稽止隅瞩灌蠕喳缴寻统习拔率屏嫩头巍掠逐糊壤纫哦人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统6命题变量与真值命题变
5、量与真值命题变量（变元）：一个命题用符号表示，称为命题符号当命题符号代表任一个命题时，即为命题变量真值：真或假 一个命题或命题变量具有真值真值连接词（5个）：否定/合取/析取/蕴涵/等价第3章 逻辑系统鼻做于呀茁刀梧顶倔醇椿恢饺殴苍捣屹融代拉垛汲叁炊镭酸朔茬辞商藏股人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统7简单命题与复合命题简单命题与复合命题真值函数：真值联结词可以视为一元或二元映射(真值函数)，是从T,F到T,F，其余是T,F2到T,F的映射 / 其函数定义由真值表确定简单命题：一个被视为整体的、具有真或假的命题是简单命题；复合命题：使用联结词将简单命题联结起来的命题是复合命题第
6、3章 逻辑系统肤犬寸搬瞄聋镁遇投挖隆池分蛹纷式棍长特洪笋进妓微按汕牢植希衷义啮人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统8命题语言与原子公式命题语言与原子公式命题逻辑：研究复合命题之间的推导关系命题语言：是命题逻辑使用的形式语言，是符号的集合,用Lp表示 / 包括：命题符号、连接词、左右括号原子公式：命题语言中的一个表达式是原子公式，当且仅当它是一个命题符号 / 原子公式也称为文字(包括正文字和负文字)第3章 逻辑系统辊堪苍云慢雌知掷痪椅宜炮鸟娩见藏皿咒鳃厄始逛脆稀陆惰顽顷捐纱贝澄人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统9命题逻辑的合式公式命题逻辑的合式公式合式公式(we
7、ll-formed formula)，简称公式，记作wff：一个表达式是一个公式，当且仅当它能通过有限次地使用下述步骤生成：(1)原子公式是公式；(2)如果A是公式，则(A)是公式；(3)如果A、B均为公式，则A*B是公式，其中*表示中的任意一个 / 公式的形成规则 / 命题逻辑的主要研究对象是公式第3章 逻辑系统产悍将字倡痔惺钝扣张拄捻慢早鞘莆值聚不惠拱樟莆表玄贮钱翰撂瘟父拜人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统10谓词谓词从命题到一阶谓词：命题内部逻辑结构的分解 对判断的分解，把判断中的具体内容抽出，称为个体；剩下的判断即为谓词谓词可看作是从个体域或个体域的笛卡儿乘积到真值集
8、合T/F的映射典型的推理例子：(1)凡人皆有死；(2)苏格拉底是人；(3)苏格拉底有死。（三段论式）M(x)D(x), M(s) D(s)第3章 逻辑系统盼呢吃农郊奠职过诈肇秘禹詹汾涅窿祷些兹凸硫山资富搁阔忌耳肉婶均破人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统11论域与个体论域与个体论域和个体：在一阶逻辑中，被研究对象构成的非空集称为论域；论域中的每个元素称为个体论域例子：前面例子中的论域是“人” / 所有的有理数都是实数：其论域为有理数一阶逻辑还研究个体之间的关系（或个体的性质）及作用于个体的函数论域/个体/个体间关系/作用于个体函数 这4个成分构成了一阶逻辑的结构第3章 逻辑系统
9、爷枢警靶结帝兆形嘱跨趴虽叼没叙友桓吗杏鸳熙污挥埃影蕴祁乙馒叛叔滔人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统12谓词谓词谓词（关系）：一阶形式语言中用于指称论域中个体的性质或者个体之间关系的形式符号（大写字母表示）给定了论域，就确定了谓词的真假值一元谓词：个体的性质；二元谓词(多元谓词)：个体的关系个体的位置空位，具体化构成意义完整的语句空位的数目谓词的元数几元谓词第3章 逻辑系统杂冤刀汤洱姓癸灭诚骸屑义急抉贱刑告县吴业穷如眨埔弘翟乍僳顺宵荫俺人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统13量词与变量量词与变量变量(变元)：表示论域内的任意一个个体 / 常量(常元)，表示确定的
10、个体量词与变量：量词用来表示谓词的判断特性全称量词：对所有的x x P(x)存在量词：存在x x P(x)约束变量：、中x的变量，量词所管辖的公式如P(x)称为量词辖域自由变量：不在量词辖域内的变量为自由变量第3章 逻辑系统羡解袋噬准踪脓临烟儡丈痔盔倔着郡泛堰附怎孟路训啄您蚀泼黍汲入磷人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统14约束变量和自由变量约束变量和自由变量区别：自由变量可代入常量，约束变量不行，因为a P(a)无意义 ；约束变量可改名，自由变量不行带有全称变量x的命题表示为一阶公式时，其表示形式为 x(P(x)，带有存在变量x的命题则表示形式为x(P(x)例子：所有有理数都
11、是实数 x(P(x)R(x)，有些人身高超过2米x(M(x)G(x)上述使用方式不可改变，否则造成逻辑错误第3章 逻辑系统赠梁硅坑菩瞪咒劝拯茎筒态烫拙奏汇掺锦毋舵骗暑债历汞很榔彦箍崎围硼人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统15函数函数函数：表示个体之间的运算，可作用于一个或数个个体（用小写字母）给定一个或若干个体（对象），产生一个新的个体（对象）/ 函数的元数例子：x的父亲 father(张三)两数之和仍是一个数 add(e1, e2)第3章 逻辑系统溉咖夸糠熊觅鹏分播仇逻贿辟仕蹬滋琼刃卫蒲巍殃愿防怠啼肘坑典彪铲慈人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统16函数与谓
12、词的区别函数与谓词的区别谓词和函数的区别：谓词代表语句，结果是关系（具有真假值）；函数代表关系运算，结果是一个新个体例子：谓词SUM(e1, e2, e3) 说明e1、e2、e3之间的关系是e1与e2的和是e3 ，函数add(e1, e2)说明e1与e2相加的结果仍是一个数第3章 逻辑系统读轿滨衬丧傈霜匣瑞茄泄怒舶哉贼炬星秦帅媚髓贼抒兆啃荆恍况写馏仔妈人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统17一阶语言一阶语言(1)(1)一阶语言L：是一阶逻辑使用的形式语言，可以和任何结构（论域）没有联系，也可以与某个结构有联系与结构没有联系的一阶语言由8类符号组成：(1)无限序列的个体符号（个体
13、常量）(2)无限序列的谓词符号，有确定的元数n1有一个特殊的谓词符号称为相等符号（等式），记为=。 L可含或不含=，如果含有，即称为含=的一阶逻辑第3章 逻辑系统省颁横绣弥乘研坞览棘烁孽哩骏奸马郧吊何彩庚蛊萨疼址夸三推锚徊艰冷人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统18一阶语言一阶语言(2)(2)(3)无限序列的函数符号，有确定的元数m1(4)无限序列的自由变量：用u/v/w等表示自由变量(5)无限序列的约束变量：用x/y/z等表示约束变量(6)联结词：(7)量词： 、(8)标点：左右括号、逗号 ( ) ,第3章 逻辑系统肃泛拇仍敬笑拒昧咐肚趴录班咸少刊化俘培背造失死票桐兽喀姑阁柜
14、镰蚤人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统19一阶语言的项和公式一阶语言的项和公式L的项：一阶语言中的一个符号是项t，当且仅当它能通过有限次使用下述步骤生成：(1)个体常量、自由变量是项；(2)如果t1tn是项，且f是n元函数，则f(t1tn)是项L的原子公式：一阶语言中的一个表达式是一个原子公式，当且仅当它有如下2种形式：(1)F(t1tn)，F是n元谓词，t1tn是项；(2)=(t1,t2)或t1=t2， t1、t2是项第3章 逻辑系统垂湃框坯后遭矮幌捐厂跨拂叔慨敷邓蒲悸考供颂络播颗须性事搅槽洼屡团人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统20一阶语言的公式一阶语言
15、的公式(1)(1)L的公式：一阶语言中的一个表达式是一个公式，当且仅当它能通过有限次使用下述步骤生成：(1)原子公式是公式；(2)如果A是公式，则(A)是公式；(3)如果A、B均为公式，则A*B是公式，其中*表示中的任意一个(4)如果A(u)是公式，且x不在A(u)中出现，则x A(x)、x A(x)都是公式第3章 逻辑系统屯敌续川摹决凰役劲狡藏铣氟昏咆冉挺柏泽启随边灼槽维凰部蒋锁今衫砒人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统21一阶语言的公式一阶语言的公式(2)(2)一阶谓词公式的例子数学命题的表示：5只被1和5整除设Q(x,y)表示x被y整除，N(x)表示x是自然数 x(Q(5
16、,x)N(5)N(1)自然语言语句的表示：他不能在所有时刻欺骗所有人设F(x)表示“x是人”/G(x)“x是一个时刻”/H(x,y)“他能在y时刻欺骗x” x y (F(x)G(y) H(x,y) 或者 xy(H(x,y)F(x)G(y) 第3章 逻辑系统咖贩梁掏辽炭偏哥舆吧槐骨万育陪郝藩击喉废李败娶亲套贮将纱谚闹垮斟人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统22术很厌冤坚吧展覆蚜绷痢雄滨剑冯篮玖惕龟蒙敏趟旅莽冶锯并艳侈蛆襟孕人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统3.2 逻辑系统的语法和语义逻辑系统的语法逻辑系统的语义语法和语义之间的关系第3章 逻辑系统九铭牧厄獭纬饯谰
17、优瓣区遭貉醚泽怯略踢桑瓷幕厘手明龄攻辜朗秒挞逸竹人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统逻辑系统逻辑系统逻辑系统(亦称形式系统Formal System)由5个部分组成：符号表非空集合，即逻辑(形式)语言如一阶语言上全体符号的集合*的子集项和变量*的子集公式 | 公式和项的交集为空公式FORMULA上的子集公理AXIOM公式上的n元关系集合推理规则RULE、项TERM、FORMULA称为FS的组成部分 / AXIOM、RULE称为FS的推演部分第3章 逻辑系统仿刺鸭茅眯巴囤香壕蝴突癌篓澄悔瘁踊凉迎腿丑妙嘲钡朱沪蔓遵饯卒发象人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统24语法
18、和形式推演语法和形式推演逻辑系统除符号表以外的部分构成了逻辑系统的语法形式推演：定义了公式之间的形式可推演性关系，它涉及公式的语法结构，其正确性能够机械地证明用记号 表示形式可推演关系，读作“推出”用 A表示A是由形式可推演的（或形式可证明的），其中是前提，A是结论第3章 逻辑系统坷求队挟起芋喜谆斌南讥锅辉择谍恭弛凌前鄙桩泌搏疮扁途眉屏摧芹甥柏人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统25推演规则举例推演规则举例形式推演由形式推演规则定义，举例如下：自反A A (Ref)传递if A then A ()消去(反证律)if , A B & , AB then A()公式变换AB AB第
19、3章 逻辑系统羞纬廖性稽腻逝柔促驮斟隙诊限脸伍郁孩坡透滑厩菩祟赫皖缆雪佑嘿摊穿人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统26形式可推演性形式可推演性形式可推演性：在命题/一阶逻辑系统中，A是由可形式推演的(或形式可证明的)，记为A，当且仅当A能通过有限次应用相应逻辑的形式推演规则生成即A成立，当且仅当存在有限序列使得 1A1，2A2，nAn 中的每一项均由某个形式推导规则生成,且nAn 就是A即n=,An=A建立在上述形式推演规则基础上的形式推演系统称为自然推演(演绎)系统第3章 逻辑系统阮媳味恬雪寞欺页凌猩忽请波竖巧校吊追鉴宽最闷锨贤吓夫抵姐哈脆畦磺人工智能原理第3章逻辑系统人工智
20、能原理第3章逻辑系统27逻辑系统的语义逻辑系统的语义语义即对形式语言进行解释研究可推导性即形式推演()时不考虑作为前提和结论的命题的内容，只考虑命题真假并由此确定前提的真是否蕴涵结论的真，即前提和结论之间是否有可推导关系(语法)研究形式系统的语义时，对逻辑系统赋予研究对象的集合即论域；用论域中的个体对象、对象之上的运算(函数)、对象之间的关系(谓词)去解释逻辑系统中的符号，称作指称denote 指称语义学赋予形式系统的论域及解释称为形式系统的语义结构，简称结构(structure)第3章 逻辑系统晃斑哨倚尽僚帘稗疾冻锅幼坪袄袖狗迁唇揩驯泥漠爹沪姿九签堵壬陈怯剔人工智能原理第3章逻辑系统人工智能
21、原理第3章逻辑系统28命题逻辑的语义与可满足性命题逻辑的语义与可满足性研究命题逻辑的语义，即研究公式(公式集)的真假赋值问题真假赋值：真假赋值是以所有命题符号的集合为定义域、以真假值1,0为值域的函数。真假赋值v给公式A指派的值记作Av可满足性：是可满足的，当且仅当有真假赋值v，使得v=1。此时称v满足。第3章 逻辑系统未狭蹭翰浸首伶鳞柞纠今尚早它拔讫竹儿赘覆必雷择姿巨纺减苹量盎恶人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统29可满足性可满足性的可满足性蕴涵了中所有公式的可满足性，但反过来不成立。因为这要求同一个真假赋值满足所有的公式(并非所有可满足的公式使用同一个赋值)重言式和矛盾式
22、A是重言式(永真式)，当且仅当对于任意的真假赋值v，Av=1A是矛盾式(永假式)，当且仅当对于任意的真假赋值v，Av=0第3章 逻辑系统告验蒂佃椅喉久噬碟框蛮居舶担抄努昂割树诉咙主尝萄茵妈胃晒考厅陋叔人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统30真假判断与逻辑推论真假判断与逻辑推论一个命题公式是重言式或者是矛盾式或者两者都不是，需要进行判定。判定方法可通过构造真假值表方法或采用树形分支的方法来判定可推导关系：研究前提的真是否蕴涵结论的真，引入语义以后对公式进行真假赋值；如果对任意的真假赋值，都有上述关系，则说明前提和结论之间存在一种逻辑推论关系(或称逻辑蕴涵)第3章 逻辑系统棱茸疽楼
23、蜘疮啸忱酗籽戴县磐掘倪郭安朵至盟翱霜函逞珐貌慧涡寓濒顿呕人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统31命题逻辑的逻辑推论命题逻辑的逻辑推论逻辑推论：设、A分别是命题逻辑中的公式集合和公式,A是的逻辑推论，记为 A，当且仅当对于任意真假赋值v，v=1蕴涵Av=1。|=可读作“逻辑地蕴涵”，|=是前提和结论A之间的关系逻辑推论的证明要证明|=A时，即要证明对于任何真假赋值v，如果v=1则Av=1 (通常使用反证法)第3章 逻辑系统寻弟幽疚揭抨光计筐噬鼎善吝喧稼黄锨韩疤身挞议滁捍梯目斋搓逆反迫峰人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统32一阶语言的语义一阶语言的语义一阶语言的语
24、义：一阶语言的解释包括一个论域和一个函数函数把一阶语言中的个体符号映射到论域中的个体n元关系符号(即谓词)映射到论域上的n元关系m元函数符号映射到论域上的m元全函数以上组成了该论域中对一阶语言的解释第3章 逻辑系统巩组链盔格摊阁妓抠惯代箩煌呛喝航熏镍咨蜗鹤川利擒梨喧堆燃思柠泉孰人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统33一阶语言的赋值一阶语言的赋值赋值：一阶语言L的赋值v包括一个论域D和一个函数(记作v)L中所有个体符号a为定义域，其赋值v(a)或av 关系符号F的赋值v(F)或Fv 函数符号f的赋值v(f)或fv自由变量符号u的赋值v(u)或uv则有(1)av, uvD(2)Fv
25、Dn(3)fv: DmD第3章 逻辑系统瞧绩酒蛮谚烙雅焕愈乙冉道姆衡枕爷钥谩氏虎后登川良安策巩方糊片甸阿人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统34一阶逻辑的逻辑推论一阶逻辑的逻辑推论公式的真假值：一阶语言的公式在以D为论域的赋值之下，其真假值可以递归定义一阶逻辑的逻辑推论: 与命题逻辑相同，只是这里不使用真假赋值，而用赋值逻辑推论：设、A分别是一阶语言的公式集和公式，A是的逻辑推论，记作|=A，当且仅当对于任何赋值v，v=1蕴涵Av=1一阶逻辑的逻辑推论证明方法类似于命题逻辑，常用反证法。但对于否证逻辑推论，则需要构造赋值所需的论域。确定论域时，关键在于论域的大小第3章 逻辑系统
26、臃妊曰似损瑰跺干消绥痛蚤当袜寨倚要尿馒挎倪酌犹狄苇奖掣会捡垮拧靡人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统35逻辑系统的整体特征逻辑系统的整体特征在经典逻辑的形式系统中，形式推演是语法概念，逻辑推论是语义概念形式系统的整体特征：是在形式系统引入语义以后，研究对于任何一阶语言的公式集和公式A在何种赋值的条件下，其结果是否为真即研究形式推演与逻辑推论之间的关系赋值的条件：给定某个赋值可满足性给定任意赋值有效性第3章 逻辑系统昼学噶竹蛆龚敢舆驳躁锈累扬炮泡感诽喇圈既锻钳俺蚂揍司翅嘶蕉鼓忻践人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统36可靠性定理与完备性定理可靠性定理与完备性定理对
27、于任何一阶语言的公式集和公式A， A|=A表示：凡是形式可推演性所反映的前提和结论之间的关系，在非形式的推理中都是成立的，即形式可推演性对于反映非形式的推理是可靠的，此即可靠性定理(或者称合理性)|=A A表示：凡是在非形式推理中成立的前提和结论之间的关系，形式可推演性都是能够反映的，即形式可推演性在反映非形式推理时没有遗漏，此即完备性定理第3章 逻辑系统债些恶蔚轰廖浊隶鳞斗书剧竖撩搞咐级佐港舰撤氓协葫燕酿丈脖惜恋琅罢人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统37可满足性与有效性可满足性与有效性(1)(1)不加证明地给出有关定义和定理可满足性一阶逻辑公式集合是可满足的，当且仅当有(以
28、某个不空集为论域)赋值v，使得v=1 / 当v=1时，称v满足反过来，不可满足性就是对任意论域上的任意赋值都有v=0 第3章 逻辑系统玩予村炳韵攘锤熔跨深拄老萎信续褥掇阑尖烁蒜抠擦珐哨抓拖嘴脚胞赞洱人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统38可满足性与有效性可满足性与有效性(2)(2)有效性：一阶逻辑公式A是有效的，当且仅当对于(以任何不空集为论域)任何赋值v，Av=1 / 有效性也称为普遍有效性论域中的可满足性、有效性：(1)在D中是可满足的，当且仅当有以D为论域的赋值v，使得v=1(2)A在D中是有效的，当且仅当对于任何以D为论域的赋值v，Av=1第3章 逻辑系统律衙拐伎候祟呻
29、酌此缴上占犯逃胯钝陌幸桔迢昆摩倪笼蔑被魔铁脑伏议障人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统39可满足性与有效性可满足性与有效性(3)(3)(关于命题的)定理: (1)A是可满足的，当且仅当A是不有效的；(2)A是有效的，当且仅当A是不可满足的。(关于一阶的)定理: (1)A(u1,un)是可满足的，当且仅当x1. xn A(x1,xn)是可满足的(2)A(u1,un)是有效的，当且仅当x1. xn A(x1,xn)是有效的第3章 逻辑系统宇匪芽坚才岛庙燎咒未照策收主隋舰娜谈跺菇痪桌戒狙重按欲笨窝匣酒拙人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统40可靠性定理可靠性定理可靠性
30、定理1：设Form(L)，AForm(L)(也包括了命题语言Lp)(1)如果A，则|=A；(2)如果A，则|=A(即所有形式可推演的都是有效的)协调性(无矛盾性)： Form(L)是协调的，当且仅当不存在A Form(L)，使得A且 A可靠性定理2：设Form(L)，AForm(L)(1)如果是可满足的，则是协调的；(2)如果A是可满足的，则A是协调的。(12等价)第3章 逻辑系统铂艇巢憾绿咱沏贱甘知态凑科幂整睁歼欢只狸介褪踩违凤缠留腮安蒜速恍人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统41完备性定理完备性定理命题逻辑和一阶逻辑的完备性定理1:设 Form(L)，AForm(L)(含L
31、p)(1)如果是协调的，则是可满足的；(2)如果A是协调的，则A是可满足的。定理2:设 Form(L)，AForm(L)(1)如果|=A，则 A；(2)如果|=A，则 A(所有有效公式都是形式可证明公式)。如果对论域限定以后，可得更精确的陈述第3章 逻辑系统摹剪扩左氨晰酷铭墒陋印氯猜龟清虫枚驭打瑟耶怨催凭随补挡妊鹏学页郊人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统42术很厌冤坚吧展覆蚜绷痢雄滨剑冯篮玖惕龟蒙敏趟旅莽冶锯并艳侈蛆襟孕人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统3.3 逻辑推理举例 wumpus世界命题逻辑推理模式基于电路的智能体第3章 逻辑系统枢翠泊阮挪亩靛吵尊冷
32、棚穴储识掸恿砷斤钦安腋补串励鄂扰嫉祁绚趣拍送人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统w wumpusumpus世界世界(1)(1)Wumpus是一个早期电脑游戏中的怪物Agent感知：陷阱旁边有微风breeze怪兽旁边有恶臭stench金子闪闪发光glitter感觉墙的反弹陷阱和怪物的位置随机生成第3章 逻辑系统stenchBreezePitWumpus(Monster)BreezeStenchGoldPitBreezestenchBreezeAgentBreezePitBreeze槐敲栏壬曳呀沃贮孺卜滦鄙感滓铸氏瀑柱皮坯怀抹抗埠齿领际伴蛋吊亥卖人工智能原理第3章逻辑系统人工智能原
33、理第3章逻辑系统44w wumpusumpus世界世界(2)(2)Wumpus世界搜索图示感知用5元组表示感知wumpus, 感知微风, 感知金光, 感知墙, 感知wumpus被杀死A=AgentB=BreezeG=Glitter,GoldOK=safe squareP=PitS=StenchV=visitedW=wumpusN=None1,42,43,44,41,32,33,34,31,2 OK2,23,24,21,1 A OK2,1 OK3,14,1第3章 逻辑系统1,42,43,44,41,32,33,34,31,2OK2,2P?3,24,21,1VOK2,1 ABOK3,1P?4,1
34、(a) N,N,N,N,N(b) N,B,N,N,N橇桶牵乐府展做丙龄镁岂翻瞥信榆矢誊茫捧衰跪潜描媳床掠瓢芥顿瞧福首人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统45w wumpusumpus世界世界(3)(3)1,42,43,44,41,3W!2,33,34,31,2 ASOK2,2OK3,24,21,1VOK2,1 BVOK3,1P!4,1第3章 逻辑系统1,42,4P？3,44,41,3W!2,3 AB S G3,3P？4,31,2 S VOK2,2VOK3,24,21,1VOK2,1 BVOK3,1P!4,1A=AgentB=BreezeG=Glitter,GoldOK=safe
35、 squareP=PitS=StenchV=visitedW=wumpusN=None (c) S,N,N,N,N (d) S,B,G,N,N骡琶垄猎鄙翅骸身儡恒樊嗽荤银蓟殉贰天溉霜熙卯齿掳株自嘻览褒蹭缎硅人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统46w wumpusumpus世界中的命题和推理规则世界中的命题和推理规则只考虑陷阱的情况Pi,j=T i,j中有陷阱，记为Pi,jBi,j=T i,j中有微风，记为Bi,j规则如下：R1P1,1R2B1,1P1,2P2,1R3B2,1P1,1P2,2P3,1R4B1,1R5B2,1第3章 逻辑系统囚伙渠毡趾稍罗汇忠还炼饶戏君崭舒懦档椰服勺
36、碍颂那了配吕鹿树绷生人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统47命题逻辑推理模式命题逻辑推理模式分离规则与消去逻辑等价(双向蕴涵消去)第3章 逻辑系统广撒坠魔佯浇锐雇死铁畔贴旱汪弃仇踞窘拈赂用柔堪藤辈广舌厘总申袍聂人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统48w wumpusumpus世界的推理例子世界的推理例子用R1R5规则和推理模式证明：1,2和2,1中没有陷阱，即P1,2和P2,1证明：从R2开始R6(B1,1(P1,2P2,1)(P1,2P2,1)B1,1)R2双向蕴涵消去R7(P1,2P2,1)B1,1R6与消去R8B1,1(P1,2P2,1)逆否命题逻辑等价R
37、9(P1,2P2,1)R4/R8分离规则R10(结果) P1,2P2,1迪摩根定律第3章 逻辑系统挝狰螟征姨膊樱篇漠遗棠羔慧捡滇毯忆怎龟倡咕寻傻邀从荒维赌焊审醛喜人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统49基于电路的智能体基于电路的智能体基于电路的智能体的目的：把对现状的感知变为智能体的行动感知=input 判断/行动判断：尖叫怪兽wumpus将死亡行动：金光抓起金子/行动控制=寄存器第3章 逻辑系统grabglitterAlive延迟Scream 完及崔愉茬肚钮拨狭唾览逆朴牲档铆呸鲤俞姨收剑骤讯坟春颈吻蛔日磅秋人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统50w wumpu
38、sumpus世界中智能体的判断世界中智能体的判断(1)(1)位置判断：在L1,1分为3种情况：一直留在1,1，从1,2走到1,1，从2,1走到1,1使用位置寄存器/状态寄存器第3章 逻辑系统L1,2L2,1facing-leftfacing-downL1,1forwardbump孩芋傻订煤振巴坞饲显吹狭印瓶臣凌窒晰欲驱立惟棍快许亿触踏挂佰署按人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统51wumpuswumpus世界中智能体的判断世界中智能体的判断(2)(2)上述电路图表示为逻辑表达式第3章 逻辑系统前述电路的逻辑表达式判断wumpus是否活着发现金子后的行动但因为没有变量，不能表示更
39、一般的情况，如不同位置用同一个逻辑式巡有添枣徐传菱贷如墓溜慎湘搪贮截子亥濒待袁峡召怯坤磅界牺汽帖吃巷人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统52术很厌冤坚吧展覆蚜绷痢雄滨剑冯篮玖惕龟蒙敏趟旅莽冶锯并艳侈蛆襟孕人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统3.4 逻辑智能体的推理策略逻辑智能体构造Horn子句置换与合一前向链接算法 / 后向链接算法第3章 逻辑系统来完兼蜀回航谋编爸渤扔急岛否吉乞秸际唁氢才诬蔼越停凹畦刽灾丧祈疟人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统逻辑智能体的构造逻辑智能体的构造(1)(1)以一阶谓词演算为核心的逻辑系统是典型的逻辑智能体系统的基础
40、是一阶语言，由此构造知识库 / 一般构造知识库(知识工程)的过程包括：确定任务收集相关知识确定谓词、函数和常量词汇表第3章 逻辑系统长炉问谚辛虹炒计婿筹暑羌绕牡闭罐雄定菲鸥咏领振览巧胡葱晒卤琶咱透人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统54逻辑智能体逻辑智能体的构造的构造(2)(2)对领域(论域)的通用知识进行编码对特定问题实例的描述进行编码查询提交、推理、给出答案调试知识库如果采用一阶语言的特殊形式确定子句Horn子句，可获得高效推理第3章 逻辑系统墨疯滦杨函渡痪昭市囊仿框鹅诞翻肉给你昭昧砚顷狠油跌捧蚁景叹冗锯僧人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统55HornHo
41、rn子句子句Horn子句(Horn Clause)：是一类至多只有一个正文字的子句(子句=文字的析取式)例子: ABC (注意：这是一般公式ABC的变形)Horn子句称为确定子句, 其中正文字称为子句的头, 负文字构成子句的体第3章 逻辑系统泥铣尝尧踊臼撕湾丙帆献皇柜还帽韦角汪冕祈悦雁窝店枣驰叭岿苛指拓匿人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统56HornHorn子句的性质子句的性质只有一个正文字的约束具有重要意义:每个Horn子句实际上都是一个蕴涵式的变形, 实际知识库中常常使用这样易懂的形式 / 没有正文字的Horn子句可以写成结论为FALSE的蕴涵式Horn子句的推理可以使用
42、前向链接和后向链接算法用Horn子句判定蕴涵所需时间与数据库成线性关系最重要的是最后一个性质第3章 逻辑系统盘该隙漂北讼馅妊脏肮倾彦坡踪皂赚采轨烈唆九裔象咯台歪四起赏猩锅沟人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统57推理策略推理策略简要介绍2种推理算法简单的前向链接算法和简单的后向链接算法,结合一个例子说明算法的应用一阶推理规则一般化分离规则(Generalized Modus Ponens)对于原子语句pi, pi, q, 存在置换,使得(pi)= (pi), 对所有i都成立, 则第3章 逻辑系统睦春硼沽棵溉椭隋滔借伯宾办卯涂尘熏溉荔恭描管更疙傻哦归擅汲瑰将颧人工智能原理第3章逻
43、辑系统人工智能原理第3章逻辑系统58置换与合一置换与合一置换(或代换)：设x1xn是n个变量，且各不相同，t1tn是n个项(常量、变量、函数)，tixi，则有限序列t1/x1, t2/x2 tn/xn称为一个置换置换乘积(合成)：设和是2个置换，则先后作用于公式或项，称为置换乘积，用表示。通过相关的置换,使不同的一阶公式成为一样的，这个过程称为合一第3章 逻辑系统分亮侩称撰映旬锗瞩燥辰拎遗尔坦噬缔枚沥眺傲讨妹跋努铝扒吊磋漫全虽人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统59合一置换合一置换合一置换：设有一组谓词公式E1Ek和置换，使E1=E2=Ek,则称为合一置换，E1Ek称为可合一的
44、 / 合一置换也叫通代最一般合一置换(最广通代)：如果和都是公式组E1Ek的合一置换，且有置换存在，使得=，则称为公式组E1Ek的最一般合一置换，记为mgu (most general unification)第3章 逻辑系统霍期净碱够壕耘甩轻醚橡波蔑创裳棠蛋嚼控撩凿作美瞒某颠泉皇邢涤东峰人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统60置换与合一的例子置换与合一的例子有子句x King(x) Greedy(x) Evil(x)King(John)Greedy(John)则做置换 =x/John, 用一般化分离规则可得: q=Evil(John)第3章 逻辑系统启剁绷省宫颧药钱坎耸骏违遇
45、孽脉逢母磊躲影努料玫清札二黎叫船噎宴评人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统61合一结果合一结果对于合一UNIFY, 合一的结果是一个置换, 如:UNIFY(Know(John, x), Know(John, Jane) =x/JaneUNIFY(Know(John, x), Know(y, Mary) =x/Mary, y/John但是UNIFY(K(John, x), K(x, Jane)=FAIL, 原因是x不能同时选取2个值详细的合一算法将在第6章介绍第3章 逻辑系统滤辈射锅服彦求沸苦霖芯伶呢瘁其剪数长柬秧右盯乔挤汽腮栓辕本甩日咎人工智能原理第3章逻辑系统人工智能原理第3
46、章逻辑系统62用于逻辑推理的例子用于逻辑推理的例子问题描述: 美国法律规定：美国人(American)卖武器(weapon)给敌对国家(hostile)是犯罪的(criminal). 美国的敌国Nono有一些导弹(missile)，所有这些导弹是West上校卖给他们的，而West上校是一个美国人证明：West是犯罪的第3章 逻辑系统灶炮它总家怨珊妻疥资痛捐怎氓焰疥譬妻他铲拔缩药玉糯笑唯卿玛剃鸣颜人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统63问题用一阶子句表示问题用一阶子句表示(1)(1)用确定子句表示上述内容美国人卖武器给敌对国家是犯罪的American(x) Weapon(y) S
47、ell(x,y,z) Hostile(z) Criminal(x)1Nono有一些导弹x Own(Nono, x) Missile(x)消去其中的存在量词，引入新常量，得到2个原子公式(正文字)Own(Nono, M1) 4Missile(M1) 5第3章 逻辑系统塌糙席纷眼袒肚丢获蹿疵缸铲啊惦咐夺架解氯危揣据鬃蹲午羚嚼臀棚挡隶人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统64问题用一阶子句表示问题用一阶子句表示(2)(2)所有该国导弹都是West上校出售的Missile(y) Own(Nono, y)Sell(West, y, Nono) 2导弹是武器Missile(y) Weapon
48、(y)3其它陈述：美国人West American(West)6敌国 Nono Hostile(Nono)7上述描述放入知识库：13为确定子句(上述原始形式均可以化为原子的析取且只有一个正文字)， 47为正文字第3章 逻辑系统赢轩细礁晾企掷篙幅披悬要认箩夯烈锯饮赋陷耐丛钥窃讶火磅坯汇技陷桩人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统65前向链接算法的说明前向链接算法的说明(1)(1)前向链接算法的推理过程：从已知事实(知识库中的原子公式)开始，依次对知识库中的规则(以确定子句的形式出现)进行置换，检查规则前提部分的文字是否全部与知识库中的事实相匹配如果是匹配的，则把该条规则已经做过置换
49、的结论部分添加到知识库中，如果这个结论和查询(既需要推导出的结论)一致，则推理结束，获得证明第3章 逻辑系统番艘琐琢庭鹿奶皂败蜜蘸跋鸟孵汉搂涩隋缆盾故戒瓤羹音勿链渗床梆台乘人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统66前向链接算法的说明前向链接算法的说明(2)(2)重复上述过程，直到获得证明；或者再没有新的事实(推出的结论)加入，则此时推理以证明失败结束约束：要求每次加入知识库的结论都是全新的，而不是已知事实的重命名(即谓词相同只是变量名不同)第3章 逻辑系统滥刺骋钨酷雪涵干张颜疤尤烬玉钝鹤铅漱乓能邪剧怨糙猾予紧柄冕惮甚灵人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统67简单的
50、前向链接算法简单的前向链接算法Function FC(KB,) Return a substitution or FALSEInputs: KB , a set of first-order definite clauses / , the query = an atomlocal variables : new, the new rules inferred on each iterationrepeat until new is empty newfor each rule r (in the form of define clause) in KB do for each such th
51、at (p1pn)= (p1pn)get (q)=q if q is new (satisfied the constraint) then do add q to new UNIFY(q, ) If is not fail then return add new to KBreturn false 第3章 逻辑系统婴母路咙掉亮揖芳曾绎渍耐而氏有殷命审欣操捉汰虏昌牛筐袭督扭秤弃窜人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统68前向链接算法例子前向链接算法例子(1)(1)第3章 逻辑系统使用前向链接算法对前面的例子进行推理用知识库中的事实(即47)依次对知识库中的各个子句进行置换操作并用
52、推理规则获得新的文字第一次循环体执行：子句1前提部分未获满足(为什么？)子句2使用置换x/M1, 则可得Sell(West, M1, Nono)8子句3使用置换x/M1，则可得Weapon(M1)9虚尽晕蓬臼罐晓阁库抬戴眶窜酮踏院各鱼谢枫墩苍纽憎服栗客蛹退悼人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统69前向链接算法例子前向链接算法例子(2)(2)第3章 逻辑系统此时new中为89，为原知识库所未有，将它们添加到知识库中第二次循环体执行：再次循环时new首先清空子句1置换x/West, y/M1, z/Nono得到Criminal(West)10添加到new中，与查询进行合一测试，一致
53、则返回 / 算法结束拦拇么尤掖婉喘抹曰扦托光扁酿榔镑套捷悟掸竿蝇侗崖顶嘎记宾办逢苔巴人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统70前向链接生成的证明树前向链接生成的证明树第3章 逻辑系统Criminal(West)Weapon(M1)Sells(West,M1,Nono)Hostile(Nono)American(West)Missile(M1)Owns(Nono,M1)Enemy(Nono,America)瞧扰尾肋民课占硬食泵嫩仁拈鹊骄辕襟档添贯茅咀挟组硷芬卞整媳誉撇奖人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统71反向链接算法的说明反向链接算法的说明(1)(1)原始查询(
54、既要证明的结论)以目标列表的形式出现，开始时列表中只有一个元素列表的操作相当于栈，是一个递归过程(如下)即深度优先的搜索过程推理过程是从结论(子句的头)开始，找到匹配的头就扩展这个头所在的规则体；扩展部分又作为头继续扩展，直到全部原子均与事实相匹配比较：正向=事实结论/反向=结论事实第3章 逻辑系统辗郸哆灭至尤氦嚷享韵蹬蹿瞻烈远唇尾勺左赊搅柒乙替埔哥火痹狄叠耕藻人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统72反向链接算法的说明反向链接算法的说明(2)(2)算法的推理过程是：选取栈当中的第一个目标，在知识库中寻找子句的头(即结论部分)能与目标合一的每个子句每个这样的子句创建了一个递归调用
55、过程，在这个递归调用过程中子句的前提(子句的体)被加入到目标栈当中当栈中所有目标都得到匹配，则当前的证明分支是成功的注意：事实是指有头没有体的子句(正文字)第3章 逻辑系统疙狄序激堆泄全篷爷事份蔷派生肆景氯岳本沤捅胳顷货嚎赵哭恢疙茁姑卷人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统73反向链接算法的说明反向链接算法的说明(3)(3)在算法中answers作为存放置换的数据结构，返回一系列置换操作，这些操作说明了反向链接算法获取证明的过程在算法中包括了置换的合成(或者写为Compose(,)，其效果就是依次进行每个置换第3章 逻辑系统疙蚂涵兽惧痪痹崩毡萎询丙仟宽盯获眠纪壁贼拢墓植柞娩筷詹莽
56、蜗汞惋穆人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统74反向链接算法的说明反向链接算法的说明(4)(4)第一次应用算法，对于待证明的目标来说，本身就是一个正文字，此时要用这个文字中的常量对合适的规则(子句的头与该文字匹配)进行置换这个置换通过递归调用带入下一次置换，就得到了合成置换在本例中有：初始x/West 递归x/West, y/M1递归x/West, y/M1, z/Nono第3章 逻辑系统缔喜复杏嚷散岭丸靛嗣李戊盗吹急裁衅束转衰呐眨焙等扯剐漱靠育瘪迟干人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统75简单的反向链接算法简单的反向链接算法Function BC(KB, go
57、als, ) returns a set of substitutionsInputs: KB, goals=a list of conjuncts forming a query ( already applied), =the current substitution (initial=)local variables: answers=a set of substitutions (initial=)if goals is empty then return q=(FIRST(goals)(初始为空，递归以后不空)for each rule r (in the form of defin
58、e clause) in KB and =UNIFY(q, q) succeeds new_goal=p1, , pn as REST(goals) answers=BC(KB, new_goal, )answersreturn answers第3章 逻辑系统爸殷始伦腋亦用褒裔逐耽忱辛疥挂堡辅呆匠级旗仔晃辣蔼梭追摹醚簿肘娇人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统76反向链接算法例子反向链接算法例子(1)(1)反向链接算法推理过程目标Criminal(West)分解为公式1前提部分的4个文字，即American(West), Weapon(y), Sell(West, y, z),
59、Hostile(z)置换=x/WestAmerican(West)和事实相匹配需要递归匹配：Weapon(y), Sell(West, y, z), Hostile(z)Weapon(y)递归调用前=x/West，进入第一次递归产生Missile(M1)，此时置换y/M1匹配，递归返回复合=x/West, y/M1第3章 逻辑系统披藉辖纵疑悠雾钎遣戚逮尘示娜幸沛穷绷汤味撤辫储底羽陶游赣窑餐险伊人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统77反向链接算法例子反向链接算法例子(2)(2)再次递归调用Sell(West, M1, z)得到置换=z/Nono，递归返回复合置换x/West, y
60、/ M1, z/Nono在置换过程中每个变量只能置换一个常量作为约束，减少置换的不定性此时子目标全部匹配，再无新的子目标生成，返回置换集合结束第3章 逻辑系统还伐惦微鞭遥隅向糕旦罩祟袄薄拆嘱缎烷博患露垄得廉副善卢腻泼膘伍植人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统78反向链接生成的证明树反向链接生成的证明树第3章 逻辑系统Criminal(West)American(West)Weapon(y)Sells(West,M1,z)Hostile(Nono)Missile(y)Missile(M1)Owns(Nono ,M1)Enemy(Nono,Amerca)z/Nonoy/M1钢失骏抉
61、陡蛾哑吻裸峙澳宾氮镣陷聊李没臆窖睹牵斯替五叛耙甜盆战若惭人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统79正向链接和反向链接正向链接和反向链接前向链接算法特点：数据驱动 / 是可靠的和完备的后向链接算法特点：目标驱动 / 是可靠的但不是完备的(书中p220/p224)可以从“是否能找到问题的解”角度考虑不完备性后向链接算法根据目标来进行相关事实的匹配，对于大规模的知识库来说有助于减小搜索空间第3章 逻辑系统所夷啊檄里摄赤塑吁萧冈隶阿搞毕赔夯疾魔荡垦踪渺婶饲责拽篆念傀些出人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统80参考书目参考书目Stuart Russell / Peter N
62、orvig: AIMA 第7章 /第8章 /第9章陆汝钤 编著: 人工智能(上册) 第1章陆钟万，面向计算机科学的数理逻辑，科学出版社，1998年1月第1版朱梧木贾、肖奚安，数理逻辑引论，南京大学出版社，1995年5月第1版王元元，计算机科学中的逻辑学，科学出版社，1989年9月第1版第3章 逻辑系统促仗钡钙攫章筷鹃妆少换偶遵散也己瞥死喳宦跪呛坪舆谚挎赚诛厕卢浅挪人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统81术很厌冤坚吧展覆蚜绷痢雄滨剑冯篮玖惕龟蒙敏趟旅莽冶锯并艳侈蛆襟孕人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统附录 形式系统简介F1 形式系统和形式推演F2 形式系统的语义
63、F3 形式系统的整体特征第3章 逻辑系统基领拘殿呜拟祈懦烤避轻滩徊肃谁兰扩秸绢疟酣撑萍氢罕任菜劫父谋兴弟人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统术很厌冤坚吧展覆蚜绷痢雄滨剑冯篮玖惕龟蒙敏趟旅莽冶锯并艳侈蛆襟孕人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统F1 形式系统定义和形式推演第3章 逻辑系统政建奸坍秘殴市儒阮张康晓垛斯顺躬摧猖诞典瓜维初洗余缆津稿咐在呈陆人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统形式系统定义形式系统定义(1)(1)逻辑的形式系统的定义 一个形式系统Formal System由5个部分组成：(1)符号表，非空集合，即形式语言(如Lp和L)；(2)
64、上全体符号的集合*的一个子集TERM， 其 元 素 称 为 FS的 项 ； TERM有 子 集VARIABLE，其元素称为变量；(3)*的一个子集FORMULA，其元素称为FS的公式；FORMULA有子集ATOM，其元素称为原子公式；TERMFORMULA=；第3章 逻辑系统反禾漫颜像拘瓤取渠佬啮裹捂将济卷帐该艾富溅檀愁遵尚琼避春谆隋叔骨人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统84形式系统定义形式系统定义(2)(2)(4)FORMULA的一个子集AXIOM，其元素称为FS的公理；(5)FORMULA上的n元关系集合RULE，其元素称为FS的推理规则。其中、TERM、FORMULA称
65、为FS的组成部分，AXIOM、RULE称为FS的推演部分公理推演系统包括AXIOM，而自然推演系统只包括推理规则第3章 逻辑系统谜票锤资维短福御蜕庙显尉进垮料哨屑桃喉吓墨摈螺产胯状喝声细殉腋被人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统85对象语言和元语言对象语言和元语言(1)(1)对象语言和元语言：作为被研究对象的语言称为对象语言，用以研究对象语言的语言称为元语言例子：用汉语研究英语语法，则英语是对象语言，汉语是元语言数理逻辑中的形式系统各有其自身的形式语言如Lp和L，这些是被研究的对象，因而是对象语言；但为了研究这些形式系统，又必须使用某种语言，那么这种语言便是元语言第3章 逻辑系
66、统迷肾济束施监娘燕疑竭那酒赎廷重殴宠流鞍剩肠瓢代龙腊饺悦烯犯寡赊支人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统86对象语言和元语言对象语言和元语言(2)(2)如：“鸟正在飞翔”描述对象语言；“命题鸟正在飞翔真”对上句的评论元语言。形式系统的对象语言，其中的符号既是对客观对象的抽象，用于研究客观对象;同时又是一种符号客体，是被研究的对象第3章 逻辑系统皮晴厉蒜辖撬汛汇鹃软邯姐卓丸原渴诚权距盼密哨峡过忠厄碑刑唆围拂陷人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统87对象语言和元语言对象语言和元语言(3)(3)形式系统的元语言包括：对形式系统中组成成分的称谓项、公式、公理等逻辑术语如果
67、-那么、当且仅当、存在、所有等对形式系统性质（整体特征）的描述如一致性、完备性、可判定性等，该部分最重要元语言中使用的符号：自然语言（如汉语）和一些被引进的符号，如：、|= 等未经解释的形式语言可以没有含义，但元语言必须有其具体含义。第3章 逻辑系统原韭瘸踞弓节洛赞崇吓紫历十刻晕恢隐踢拄块吠甚写作撰稚蹬逝颓颂恤乡人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统88元理论元理论元理论是关于形式系统的理论，包括三部分内容：关于形式系统语法(syntax)的研究，不涉及具体意义的符号体系，研究符号串的推演，即形式推演；关于形式系统语义(semantics)的研究，研究形式系统在被作出各种解释时的
68、性质；关于形式系统语法和语义关系的研究，特别是形式系统的性质，如：合理性、完备性等。第3章 逻辑系统谚翁备舜浚感有堤等藐鸟撂季照个纸唆拨劣真灵勃钒枚淮寂俐过技典棘资人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统89形式推演形式推演形式推演：定义了公式之间的形式可推演性关系，它涉及公式的语法结构，其正确性能够机械地证明用记号 表示形式可推演关系，读作“推出”用 A表示A是由形式可推演的（或形式可证明的），其中是前提，A是结论记号不是形式语言中的符号， A也不是形式语言中的公式，而是元语言中的命题第3章 逻辑系统馋小璃摆面炬侠化秀弧侵逾骚童慷两县被疚洗枫赞尚服褒淤妖倚矮灸津父人工智能原理第3
69、章逻辑系统人工智能原理第3章逻辑系统90常用推演规则常用推演规则(1)(1)形式推演由形式推演的规则定义命题逻辑中有一些常用的推演规则(规则模式)肯定前提if A then A ()增加前提if A then , A (+)自反A A (Ref)传递if A then A ()第3章 逻辑系统讥执弧峡乍恤史伯渔登筋码陀悍灯涌眠截毗恕分书俘议驳秘添韵前描驼芬人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统91常用推演规则常用推演规则(2)(2)消去(反证律)if , A B & , AB then A(-)引入(归谬律) if , A B & , A B then A(+)消去if AB,
70、Athen B(-)引入if , A B then AB(+)第3章 逻辑系统肺傀蕴囚碑歌碘孺讼扶约柔宛芭镍很井氢邱邑哨胖前爵沛撤考弱意害麓揩人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统92常用推演规则常用推演规则(3)(3)消去if AB then A, B(-)引入if A, B then AB(+)消去if , A C & ,B C then ,AB C (-)引入if A then AB, BA(+)第3章 逻辑系统迂俊戴殿蓉患韦持毛验尧酣泥絮软登谷恕狭诬枪入袄碉揉坡抠厚骄檬撤疙人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统93常用推演规则常用推演规则(2)(2)消去if
71、 AB, A then Bif AB, B then A()引入if , A B & , B A then AB (+)通过连接词的增减或变形，实现公式的变换常用AB AB第3章 逻辑系统买部僵袭酱坟客膊琵圾归避讹送铱怕膘疆豁难由氨肋埋辜垣占轻讶缎揽孩人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统94形式可推演性形式可推演性(1)(1)(命题逻辑)形式可推演性：在命题逻辑中，A是由可形式推演的(或形式可证明的)，记为A，当且仅当A能通过有限次应用命题逻辑的形式推演规则生成即A成立，当且仅当存在有限序列使得 1A1，2A2，nAn 中的每一项均由某个形式推导规则生成,且nAn 就是A即n=
72、,An=A第3章 逻辑系统暑曝调凿藐膘悟赶卷棺郎犁馆捡绳凑丁呢打炭坎砂洪整高地瘁欠漓鞠去参人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统95形式可推演性形式可推演性(2)(2)用 A表示A不成立用A|-|B表示左右两边的公式可以互相推出，称其为语法等值公式或等值公式建立在上述形式推演规则基础上的形式推演系统称为自然推演(演绎)系统第3章 逻辑系统饰设聚啃初付戏锰塘数已峦篮方亩炭串瞄蛋茸慧贸寐帘荐细咯券鞍建哩膀人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统96形式可推演性形式可推演性(3)(3)命题逻辑中的形式推演规则都包括在一阶逻辑当中，但是其中出现的公式是一阶语言中的公式，另外增
73、加了关于量词的规则(一阶逻辑)形式可推演性：在一阶逻辑中，A是由可形式推演的(或形式可证明的)，记为A，当且仅当A能通过有限次应用一阶逻辑的形式推演规则生成形式推演的例子可以参考本章后面列出的3本关于逻辑的教科书第3章 逻辑系统敷催湾皆艇烁肮抓瑶渍撂眨牧望延党溶摆龟磷欠目磕佃芳故橙龄诈灯茁坛人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统97术很厌冤坚吧展覆蚜绷痢雄滨剑冯篮玖惕龟蒙敏趟旅莽冶锯并艳侈蛆襟孕人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统F2 形式系统的语义第3章 逻辑系统臼丁论峭舜遏罗曰酝劲悟畏量想寡申彼无完魏产十汤赫淋腾菜畔索黔鸯共人工智能原理第3章逻辑系统人工智能原
74、理第3章逻辑系统形式系统的语义形式系统的语义(1)(1)语义即对形式语言进行解释研究可推导性即形式推演()时不考虑作为前提和结论的命题的内容，只考虑命题真假并由此确定前提的真是否蕴涵结论的真，即前提和结论之间是否有可推导关系(语法)研究形式系统的语义时，对形式系统赋予研究对象的集合即论域；用论域中的个体对象、对象之上的运算(函数)、对象之间的关系(谓词)去解释形式系统中的符号，称作指称denote 指称语义学第3章 逻辑系统招膳鼓啸魄按遮僧伏嫌烩闯附石嗓谴目眶丸碾鲁俞康卫痢浮遣远可幅踢酪人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统99形式系统的语义形式系统的语义(2)(2)赋予形式系统
75、的论域及解释称为形式系统的语义结构，简称结构(structure)/ 结构及其在该结构下公式所取真值的规定，称为形式系统的指称语义(denotational semantics)第3章 逻辑系统许僳哥渴慢博腥旋趴誊沿壤蜡镁谱稠下邑寞粹辱期搭傈沙琅株硕嘎甫酣因人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统100命题逻辑的可满足性命题逻辑的可满足性研究命题逻辑的语义，即研究公式(公式集)的真假赋值问题真假赋值：真假赋值是以所有命题符号的集合为定义域，以真假值1,0为值域的函数。真假赋值v给公式A指派的值记作Av可满足性：是可满足的，当且仅当有真假赋值v，使得v=1。此时称v满足。第3章 逻辑
76、系统愿继诺履浮皑炳肛脱嗣垛隐瘦堪咋烈俞舔您寥亭氟乌反帝兼啃舜烤絮鸭廉人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统101可满足性可满足性的可满足性蕴涵了中所有公式的可满足性，但反过来不成立。因为这要求同一个真假赋值满足所有的公式(并非所有可满足的公式使用同一个赋值)重言式和矛盾式A是重言式(永真式)，当且仅当对于任意的真假赋值v，Av=1A是矛盾式(永假式)，当且仅当对于任意的真假赋值v，Av=0第3章 逻辑系统葡仿涣畴彻森啮攻卤翱外蹬淄鲁狄鞘去抗溜噪叛虱艺涛崇罗猾框眷娟郁烧人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统102真假判断与逻辑推论真假判断与逻辑推论一个命题公式是重言式
77、或者是矛盾式或者两者都不是，需要进行判定。判定方法可通过构造真假值表方法或采用树形分支的方法来判定可推导关系研究前提的真是否蕴涵结论的真，引入语义以后对公式进行真假赋值；如果对任意的真假赋值，都有上述关系，则说明前提和结论之间存在一种逻辑推论关系(或称逻辑蕴涵)。此时对关系陈述得也更精确第3章 逻辑系统瞬盘劈融旱隙炳纳旋雌厨断恃盂铆赞营箩胺肢碉喀桨心基尊细苗挨小楚惮人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统103命题逻辑的逻辑推论命题逻辑的逻辑推论逻辑推论：设、A分别是命题逻辑中的公式集合和公式,A是的逻辑推论，记为 A，当且仅当对于任意真假赋值v，v=1蕴涵Av=1。|=可读作“逻
78、辑地蕴涵”，|=是前提和结论A之间的关系,但不是命题语言中的符号，|=A是元语言中的命题第3章 逻辑系统棘均蓬乐炳悍奴段艘接担榆肉数历碑毯纬恤烟徘谊锥各铱颊寿坠瑰拣度胆人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统104逻辑推论的证明逻辑推论的证明逻辑推论的证明要证明|=A时，即要证明对于任何真假赋值v，如果v=1则Av=1但任意的真假赋值难于验证故使用反证法，假设|A，即存在一个真假赋值v，使得v=1且Av=0，由此而产生矛盾，即肯定了 |=A第3章 逻辑系统脂殴钧隧蓑版丢赡苗穿晌锚晃吱掐极宏序帖砌上译欠串躇厩鸡镣缮煮柏光人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统105一阶语
79、言的语义一阶语言的语义(1)(1)一阶语言的语义：一阶语言的解释包括一个论域和一个函数，函数把一阶语言中的个体符号、n元关系符号(即谓词)、m元函数符号分别映射到论域中的个体、论域上的n元关系和m元全函数，是在这个论域中对一阶语言的解释第3章 逻辑系统启屡婚市反廉肉磨眷佰肾写玖购搬应喊广武揖获釜然淫憎贸芹厕彻兵排南人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统106一阶语言的语义一阶语言的语义(2)(2)如果n元关系符号和m元函数中不含自由变量，其项为论域中的个体ai，则原子公式F(t1,tn)被解释为：a1,an有R关系；项f(t1,tn)被解释为论域中的个体f(a1,an)对于含有自
80、由变量的函数(项)和公式，则分别被解释为论域上的m元函数和n元命题函数，它们经过解释，再给其中的自由变量符号指派论域中的某些个体，就得到论域中个体作为其值、真或假的命题作为其真假值第3章 逻辑系统寂铀蚂晦蔗介算千媒京封萝匙妊所萧戒隙咳毛绅乎唤置墅露比价怨倔疯筑人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统107一阶语言的赋值一阶语言的赋值(1)(1)赋值：一阶语言L的赋值v包括一个论域和一个函数，记作v，以L中所有个体符号a、关系符号F、函数符号f和自由变量符号u构成的集合为定义域，且分别把v(a)、v(F)、v(f)、v(u)写作av、Fv、fv、uv，则有(1)av, uvD(2)F
81、vDn(3)fv: DmD第3章 逻辑系统运利彰帅蟹亮林倦雀义迷吟腊辑操阵雍纂誉两慌离做仿哉壶苑拿切畦苍暗人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统108一阶语言的赋值一阶语言的赋值(2)(2)项的值：在以D为论域的赋值v之下的项的值递归定义如下：(1)av, uvD(2)f(t1,tn)v=fv(t1v,tnv)对于一阶语言的项t，设v是以D为论域的赋值，则tvD第3章 逻辑系统贾炉埔咱性陋掸账柞瓜浸州诬鼓玲瑰坎们茫夏绍绰锨敢篇汐夹揖秋岿挥番人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统109一阶逻辑的逻辑推论一阶逻辑的逻辑推论公式的真假值：一阶语言的公式在以D为论域的赋值之
82、下，其真假值可以递归定义一阶逻辑的逻辑推论: 与命题逻辑相同，只是这里不使用真假赋值，而用赋值逻辑推论：设、A分别是一阶语言的公式集和公式，A是的逻辑推论，记作|=A，当且仅当对于任何赋值v，v=1蕴涵Av=1第3章 逻辑系统间帖且助恶忆于衣冷欣原荔及修娠倡窿抱斯眨殿仗石笼驻耪甜副伙扇叹祭人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统110逻辑推论的证明方法逻辑推论的证明方法一阶逻辑的逻辑推论证明方法类似于命题逻辑，常用反证法。但对于否证逻辑推论，则需要构造赋值所需的论域。确定论域时，关键在于论域的大小第3章 逻辑系统捂呼齐石想法符汞皖素加抠悟务妊碱馁迢诱啦九哮僧卓认唆射钡竭淬表殴人工智
83、能原理第3章逻辑系统人工智能原理第3章逻辑系统111术很厌冤坚吧展覆蚜绷痢雄滨剑冯篮玖惕龟蒙敏趟旅莽冶锯并艳侈蛆襟孕人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统F3 形式系统的整体特征第3章 逻辑系统悄癣痈怒泰疹岗弄驳沮校特院猪粉梁涛评梅瞬持育你户课糙淋驹矢蹿绘斋人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统形式系统的整体特征形式系统的整体特征在经典逻辑的形式系统中，形式推演是语法概念，逻辑推论是语义概念形式系统的整体特征：是在形式系统引入语义以后，研究对于任何一阶语言的公式集和公式A在何种赋值的条件下，其结果是否为真 / 研究形式推演与逻辑推论间的关系赋值的条件：给定某个赋值可
84、满足性给定任意赋值有效性第3章 逻辑系统媚曝壕罕老各退周由宫讶冯俏贫零墩岩潞瞧臣挂卯墨卖涛奄迫力逢瓣亭外人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统113可靠性定理与完备性定理可靠性定理与完备性定理对于任何一阶语言的公式集和公式A， A|=A表示：凡是形式可推演性所反映的前提和结论之间的关系，在非形式的推理中都是成立的，即形式可推演性对于反映非形式的推理是可靠的，此即可靠性定理(或者称合理性)|=A A表示：凡是在非形式推理中成立的前提和结论之间的关系，形式可推演性都是能够反映的，即形式可推演性在反映非形式推理时没有遗漏，此即完备性定理第3章 逻辑系统竭驳搬参晋咏栅惶班柠诱浊雌察拷懦详
85、酗备樱亮痕努窗迷围蔫嘘溯促裙触人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统114可满足性与有效性可满足性与有效性(1)(1)下面给出有关定义和定理，但均不加证明可满足性一阶逻辑公式集合是可满足的，当且仅当有(以某个不空集为论域)赋值v，使得v=1 / 当v=1时，称v满足反过来，不可满足性就是对任意论域上的任意赋值都有v=0 第3章 逻辑系统泪陌柑犁衔庞济狱祸硷盼耍证登导腊钩葛腮眨耽护购驴彤笺展镍巴副饥认人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统115可满足性与有效性可满足性与有效性(2)(2)有效性：一阶逻辑公式A是有效的，当且仅当对于(以任何不空集为论域)任何赋值v，Av
86、=1 / 有效性也称为普遍有效性论域中的可满足性、有效性：(1)在D中是可满足的，当且仅当有以D为论域的赋值v，使得v=1(2)A在D中是有效的，当且仅当对于任何以D为论域的赋值v，Av=1第3章 逻辑系统裁华单玖只萄篙嗅祁漱奏更思旬烷太筷竹琢枫消瓦啤兔恃认聚拿稻榴复瘸人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统116可满足性与有效性可满足性与有效性(3)(3)(关于命题的)定理: (1)A是可满足的，当且仅当A是不有效的；(2)A是有效的，当且仅当A是不可满足的。(关于一阶的)定理: (1)A(u1,un)是可满足的，当且仅当x1. xn A(x1,xn)是可满足的(2)A(u1,u
87、n)是有效的，当且仅当x1. xn A(x1,xn)是有效的第3章 逻辑系统瀑慈所坛生福终类仆碌兜伍贺剔站米皆雏咏隋星移牢雷隅绘推绷蚜订攻嚎人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统117可满足性与有效性可满足性与有效性(4)(4)定理: 设Form(L)，AForm(L)，和A不含相等符号，D和D1是论域，且|D|D1|，则 (1)如果在D中是可满足的，则在D1中是可满足的；(2)如果A在D1中是有效的，则在D中是有效的第3章 逻辑系统论巳绿瞎乡梨玖介翻尾拌漾溺从地描笛侦旋词证正准窒澳营花尖襄糟礁闯人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统118可靠性定理可靠性定理(1)
88、(1)可靠性定理1：设Form(L)，AForm(L)(也包括了命题语言Lp)(1)如果A，则|=A；(2)如果A，则|=A(即所有形式可推演的都是有效的)第3章 逻辑系统狠丘涝执翱更旭殖羡砰似搂父皑睬充甄吐态乘棱滁伊喻香珍塘鸟堆莎聂地人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统119可靠性定理可靠性定理(2)(2)协调性： Form(L)是协调的，当且仅当不存在A Form(L)，使得A且 A可靠性定理2：设Form(L)，AForm(L)(1)如果是可满足的，则是协调的；(2)如果A是可满足的，则A是协调的。上述2个定理是等价的，即用可满足性和协调性来陈述可靠性第3章 逻辑系统剐抱
89、蒂棉浓尽夹蛤开幻媚柏贵烦鸣找葡吐柬喜负奋淄七缄稳情答盟懈兰坟人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统120完备性定理完备性定理(1)(1)命题逻辑的完备性定理1：设 Form(Lp)，AForm(Lp)(1)如果是协调的，则是可满足的；(2)如果A是协调的，则A是可满足的。定理2：设 Form(Lp)，AForm(Lp)(1)如果|=A，则 A；(2)如果|=A，则 A(所有重言式都是形式可证明公式)第3章 逻辑系统殿领勿浦极档访如家逾堆针眶茵籽削迟茂茬犹复赐弱尸咬阵牢儡愚莉奏崎人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统121完备性定理完备性定理(2)(2)一阶逻辑的完备性定理1:设 Form(L)，AForm(L)(1)如果是协调的，则是可满足的；(2)如果A是协调的，则A是可满足的。定理2:设 Form(L)，AForm(L)(1)如果|=A，则 A；(2)如果|=A，则 A(所有有效公式都是形式可证明公式)。如果对论域限定以后，可得更精确的陈述第3章 逻辑系统降醋邮俗扇名浪段规左弱内佛呵迹孪衫灯熄骨柯哈咨故鸣筛梯妒萄骏泛嘿人工智能原理第3章逻辑系统人工智能原理第3章逻辑系统122
