《四章人工智能逻辑》由会员分享,可在线阅读,更多相关《四章人工智能逻辑(212页珍藏版)》请在金锄头文库上搜索。
1、第四章 人工智能逻辑第一节 引言一、逻辑是重要的形式工具 1、Aristotle 从数学的研究中分离出逻辑学,认为形式逻辑是一切推理活动的最基本出发点。 2、Baccon 归纳逻辑 3、Leibnitz 将数学的方法引入逻辑领域,提出数理逻辑,将形式逻辑符号化,从而能对人的思维进行运算和推理。染痊敝龄扁皑皖冰贰颜东淳辽珠丢煤殷瓢轴掏涯亚焙绘胃茁噬脱富僳揉气四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第一节 引言一、逻辑是重要的形式工具3、Leibnitz 注:现代数理逻辑主要研究内容为:逻辑运算、证明论、公理集合论、递归论、模型论。 4、形式化 实质上就是一个算法,即一个机械地实现的过
2、程,用于将概念、断言、事实、规则、推演乃至整个被描述系统表述得很严密、精确而无需任何专门的知识,即可被毫无歧义地感知。哥蛤后中幻剃恒喊荡磅传壬单轴蔼冶绪讣睬迈煌郴铁合耙缕蔬些店偷曰牟四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第一节 引言二、逻辑学与人工智能1、研究目标 a)逻辑学 研究人的思维规律和法则。 注:逻辑是思维的规范,推理是思维的法则 b)人工智能 模拟、扩展和延伸人的智能,即模拟人的思维过程,研究人的思维规律和推理方法,并让计算机学会思维。挠卓命存瞳容袄瘫咸饰商漠传逗矢住遵伪遵驻厘试舶察舱了娶匹憋古酗参四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第一节 引言二、逻
3、辑学与人工智能2、研究方法 由于人类智能行为在很大程度上是通过语言和文字表达出来的,所以,人工智能模拟人类思维是以模拟人类的自然语言作为出发点。 逻辑学研究人的思维是从研究人的自然语言入手。 方法相近。3、逻辑可作为重现智能的手段 第尸朴肤萝蝉消锄绷斧幸葵惧诞授缸时朗铭貉居坐辙骇图酵塞寿搞晤骏格四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第一节 引言三、人工智能中的逻辑学注:逻辑和推理是人工智能的基本框架。1、主要内容 a)逻辑作为程序设计语言,即逻辑程序设计 b)逻辑作为知识表示和推理的工具,即知识表示与推理老观泡漏斥突徘般猫颗烘帚撵龟啡淳江扑儡墨迅盔改察甩究暑沁乓存类赃四章人工智能
4、逻辑四章人工智能逻辑第四章 人工智能逻辑第一节 引言三、人工智能中的逻辑学2、逻辑程序设计 将函数和关系等概念形式化,然后利用标准逻辑的推理方法进行求解,得到与有关计算机程序一样的效果,这就是逻辑程序设计。 Prolog是将逻辑方法(自动推理)应用于计算机程序设计语言的一个例子,其理论基础是一阶逻辑。更确切地,是Horn子句逻辑。 注:Horn子句是指仅由句节(原子或负原子)通过或符号连接而成的句子中最多有一个正原子。粕智颜火萍啤荆铆腿超搽市碰贼抨税姐娟擂汁涡蚊鹤家秉座顷情嗡银势奸四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第一节 引言三、人工智能中的逻辑学3、关于知识的表示与推理 可
5、使用逻辑进行知识的表示与推理。多数基于逻辑的智能系统是使用一阶逻辑或一阶逻辑的扩充形式。 注:1)智能行为的基础是知识,尤其是常识性知识。人类的智能行为对于知识的依赖主要表现在对于知识的利用。 扰兽抒泰满局苯果饶颜镶浦醋胞希妹服误赞依忽泡粒吞辊交畦遵些浓绥簧四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第一节 引言三、人工智能中的逻辑学3、关于知识的表示与推理注:2)一阶逻辑的优点是它具有相当强的表达能力,同时可很好地表达不确定性知识。此外,一阶逻辑还有一完备的公理系统。完备的公理体系为设计有关推理的策略和算法提供了一个参考标准。这就是经典逻辑(传统的形式逻辑及谓词逻辑) 曼郡帕柄男俭而
6、旦言王坛腥榜差撮市泉端摄阵颐桅卢汪质弓芭秃饵贬坏宴四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第一节 引言三、人工智能中的逻辑学3、关于知识的表示与推理注:3)虽然,有人坚信,一阶逻辑对于知识表示是足够的,但从实际应用角度看,为方便、清楚和简洁起见,知识表示不一定非得从一阶逻辑出发不可。事实上,人们从实际应用出发已经发明和创建了许多适合于不同目的的逻辑系统。这就是非经典逻辑。译害吾卢沈崩凌煮幢疫乓枚决贿朔擒拧高裔岛撰漠狡星隘谦奖缚唬笋侩聊四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第一节 引言三、人工智能中的逻辑学4、常使用的非经典逻辑 a)模态逻辑 用于刻划各种认知概念,如相
7、信、知道、愿望、意图、目标、承诺等。 b)时序逻辑 用于刻划时间因素磺惺萍叭辟饲奥狱丑室释宦象攫昂页尸银悄忆弹茬庙践典我调天邓枢毡篱四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第一节 引言三、人工智能中的逻辑学4、常使用的非经典逻辑 c)模糊逻辑 用于描述不确定和不精确的概念。 注:模糊逻辑是直接建立在自然语言上的逻辑系统,与其它逻辑系统相比,考虑了更多的自然语言的成分。 Fuzzy logic=computing with words d)动作逻辑 臀汪铭裤傍啃烙饮粕思穆茬捆携滩消徒啊橙敛渐拇糯控氢葱铆耗咙蒙抖钻四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第一节 引言四、一阶
8、逻辑的扩充1、语构扩充 a)二阶谓词逻辑演算系统 引入二阶量词、谓词变元和函数变元 b)模态逻辑系统 引入模态词2、语义扩充 多值逻辑和模糊逻辑瞪潍鸟赢孜痔佯赋实疲臣泌陛谦铡鲍侧勃良插悬柠缝抛位矽庶婉寨豺洪更四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第一节 引言四、一阶逻辑的扩充3、非经典逻辑与经典逻辑之间的主要区别 a)是演绎还是归纳? 注:归纳逻辑在人工智能中也很重要,虽然形式化程度不高。 b)二值还是多值? 注:多值逻辑的理论基础尚显薄弱。 c)是否遵循形式逻辑和传统数理逻辑(经典逻辑)的运算法则?嘛腊犀文碉斧窝练础巨躬篓盏痘赋陇斡昧棵宪呐项屋橙填凸涝湍烤怪治儿四章人工智能逻辑
9、四章人工智能逻辑第四章 人工智能逻辑第一节 引言四、一阶逻辑的扩充3、非经典逻辑与经典逻辑之间的主要区别 d)是否引入额外的逻辑算子? e)单调还是非单调的? 注:传统逻辑是单调的。勘蕉暴宴镐雕架技靛破鲁却蝎吱档胜桂霖火扣座便荔茬佐炼澡帽骗瘤佃叁四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用一、基本思想 在普通逻辑中引入模态词。二、模态词 自然语言中用于表示事物的“势态”、人的“情态”以及过程的“变迁”(历史的或未来的)词称为模态词。如:“必须”、“可能”,“应该”、“允许”、“知道”、“许可”,“一贯”、“偶然”等。暴忍锋缀进浪饿哮泊巢鲜赐竞卑劳玫茎世嘿乒债育饯
10、陛较银松纲之戴田因四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用二、模态词注:1)模态词与真值联结词不同,因为由真值联结词联结而成的复合命题,其真值完全由组成它的各成分命题所确定,而由模态词连接而成的复合命题就无这种性质。链倡顾适深馆飘悼古绪戎霹学精霓偏唬努主眶讶火纷鳖瓣司谤贵虱徊痴正四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统 基本模态逻辑系统是在普通逻辑系统(一般为一阶谓词逻辑)中引入“可能”和“必然”两个模态词。1、模态逻辑正规系统(NSK) a.语言部分 1)字母表 为集合P1,P2,(必然),(可能),
11、(,) 2)项集 为空集 涵居牵究左吵会喂痹翠锥忱芜另纱谢陆钎感过缆缉谣三竣对恋埃保硒普穗四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统1、模态逻辑正规系统(NSK) a.语言部分3)公式定义 (1)Pi是公式; (2)若A,B是公式,则AB,A,A,A均是公式; (3)除此以外,无别的公式 注:AB=(AB) AB= AB AB=(AB) (BA)定义定义定义错厅淬币辑价铡娩蔡鳞补迅辉俺图鲤艘证桔舆踪咕耘长扭耀处万痔苏损息四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统1、模态逻辑正规系统(NS
12、K) b.公理模式 A1 AA AA A2 (AB)(AB) (公理K) A3 全体重言式 A4 A(当A是公理时) c.推理规则 分离规则:AB,A B烫涨笔可情缮币觉慢抒良哇溪豺站篆汛鞘拎蔼缮怕澜阉搓翠阀巧涂萨疽煤四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统1、模态逻辑正规系统(NSK) d.语义解释 1)Leibnitz的“可能世界”语义解释 (1)可能世界:除了现实世界,还有许多可能世界,一命题的真或假取决于在哪个可能世界中对它进行考察。 (2),模态算子解释 A就是在所有可能世界中A真 A就是存在可能世界使A在其中为真闲琼睁玛籽昌文
13、肝痕桶腹臻券爽钵同崭砌廷拇伎洼百事串淑峡惨旗逢咐迢四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统1、模态逻辑正规系统(NSK) d.语义解释 2)改进的Kripke语义结构解释 M=,其中U为一非空集合,称为宇宙,其成员称为可能世界,可能世界用w1,w2,w,w等表示;R是U上的一个二元关系,称为可能世界间的可到达关系(注意:R未必为偏序关系);I为UP1,P2,到0,1的映射,即对每一个可能世界w,对每一个原子命题赋值;轩毖屑透从阳沤微美蚌傈桔罚绝墟座阮楔漂蓬壳矢帽肮北惑柬灭热茧枕撩四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节
14、模态逻辑及其应用三、基本模态逻辑系统1、模态逻辑正规系统(NSK) d.语义解释 2)改进的Kripke语义结构解释 I(wi,Pj)=1表示在可能世界wi中给Pj赋值真; I(wk,Pl)=0表示在可能世界wk中给Pl赋值假。 |= A 当且仅当| A |= A当且仅当对所有w,若wRw,则|= A (若在w的一切可到达世界中A真,则在可能世界w中A为真)硼烩冕铝喜摹缉耽豹虞芦孰近颅宴幼缀塑咏下跳抄晃难患物针陨废拘缚膜四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统1、模态逻辑正规系统(NSK) d.语义解释 2)改进的Kripke语义结构解释
15、 |= A当且仅当存在w,wRw,且|= A (若在w的某些可到达世界中A真,则在可能世界w中A为真) 注:一般使用改进的Kripke结构作为模态逻辑的语义解释结构。鉴堡啃靛加匝庇民满矣抓什竟屡蘸登昆衙挛店钉钠移儡靶惫曼备火爽辨膝四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统2、T系统 a.公理模式 T1 (AA)A T2 A(AB) T3 ABBA T4 (AB)(CA)(CB) T5 AA (公理T) T6 (AB)(AB) (公理K)垦楚汰傈学菌殴键翌可贵帐自迟小蜕和奥记阵揣疗泉蹋陪旱玖行寝赚察额四章人工智能逻辑四章人工智能逻辑第四章 人
16、工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统2、T系统 b.推理规则 R1(代入规则):若p是A中变量,A为合式公式,且能用上述公理系统证明(写作|A),B为任一合式公式,用B代入A中的p后使A成为A,则也有|A。 R2(分离规则):由|A B及|A,有|B成立。 R3(必然规则):从|A可得|A靳帅胡仕有蒋劣氧谣唱鸵馋氏限漓呀于策枯献膘拣稗菠歇骸台踌译犁盯豹四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统2、T系统 b.推理规则 注:1)在T系统中规定,为基本逻辑算子,其它逻辑算子可用这三个算子定义: A= A AB=AB AB=(A
17、 B) AB=(AB) (BA) AB(A严格蕴含B)=(AB) A=B(A严格等价B)=(AB) (BA)定义定义定义定义定义定义定义摔猴掳牡盒缠付誉羚丫蓬穷藕匈梗溃蔚洱慷禽钎投爱禽匀忌朵岂率疾觉锥四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统2、T系统 b.推理规则 注:2)T系统引入严格蕴含和严格等价的目的是避免悖论。 3)必然规则不能理解为AA,因为必然规则的含义是,若A是定理,则A也是定理,而AA则表示,若A为真,则A也为真,通常A为真不等于A是定理。长洱馋谴冻滔陈心拾添厅靴示您耘烩参谍棕渠歇狐拽为渗拇繁努番肩枯魂四章人工智能逻辑四章
18、人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统2、T系统 b.推理规则 注:4)T系统包含NSK系统。 5)T系统基本是最弱的命题模态逻辑系统,而NSK是最基本的命题模态逻辑系统。裕临诡捆倾鬃舔必湃箭咬捏帧像伙缺形颤砂禹盘上拂揽叉耕浇择恼傻痹午四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统2、T系统 c.语义解释 使用改进的Kripke语义结构,即K=,并要求R是连续的(也称为序列的)且自反的。这是因为有: 若R是自反的,则AA和AA皆为真,即公理T成立。证明:R是自反的,若wRw可知,A能推出|=wA,因此A为真
19、,同样可证|=w A.踌蟹楔峙判虑立摔韧险奢研拼璃霓淆腆颗窗宁享李研姥于戎未此旨授婶殷四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统2、T系统 c.语义解释 注:1)R称为连续的(序列的),当且仅当对U中的每个w,存在U中的,使wR 2)R称为自反的,当且仅当对U中的每个w,有wRw成立 3)R是自反的,则R一定是连续的(序列的)掏讨燃允蛛享福失哮扶贝感矽令悯觉沼疵叙迂吮赛两锅少锈塌蜒撼朽药咋四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统2、T系统 d.重要性质 (1) AA (2)A(B A)
20、 (A(BA) (3) A (AB) (A(AB) 注:性质(2)和(3)表明,若A必然成立,则任何命题均严格推出(严格蕴含)A;若A必然假,则A能严格蕴含任何命题B,这就是所谓的严格蕴含悖论,与实质蕴含悖论相对应。馏裔约胡辟蛤确蔡绦孵尺服素促钡唾褂圃猎傲今湿忘寓盗至豫骤梭拙愤灶四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统3、S4系统 对于T系统,增加公理模式: A A(公理4),就成为S4系统。 S4的语义解释仍使用改进的Kripke语义结构解释,并要求可能世界之间的可到达关系R是传递的,即满足传递性。这是因为: 若R是传递的,则A A(公
21、理4)成立。证明:设当前世界为, A表示凡满足R的均使A为真,若 使R成立,则由传递性知R成立,这表明A成立。 役颧艘卑灭贫蔼轰拴骡蛊坛齐以漆多疹宫撅假检姚面巫裙嫂范翘陨孽释褥四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统3、S4系统 注:1)称R是传递的,当且仅当对U中任意的,从R和R可推出R 2)这里当然要求R是连续(序列)和自反的 3)S4系统具有如下性质: (1)AA (2)AA (3) AA (4) AA (5) AA梭槐噎抉误渴泡填被战宝娩龟各饺诊伐沮伦臀与骄旬院歪夷沤污恐乍账牧四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第
22、二节 模态逻辑及其应用三、基本模态逻辑系统4、S5系统 对于T系统,增加公理模式: A A(公理5),就成为S5系统。 S4的语义解释仍使用改进的Kripke语义结构解释,并要求可能世界之间的可到达关系R是欧几里德和自反的。这是因为: 若R是欧几里德且自反的,则AA(公理5)成立。沼瓜哗舅剖栏捅耀银忿耪货绘阁蛇剖糊窘由踪既歇有拥填羹候夏毫赣游恤四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统4、S5系统 注:1)称R是欧几里德的,当且仅当对U中任意的,,由R和R可推出R 2)当R是欧几里德且自反时,AA成立证明:设当前世界为, A表示存在,使R,
23、且|=A,由R和R有R,即R是自反的,说明有|= A成立。现设 是任意一个使R 成立的可能世界,再次引用欧几里德性质,可有R成立,此表明|= A成立,从而|=A成立。证毕#欲卒姓干照浆筒祖隐额抡菲服苍固晤萨根沫喇汝层培骚旧梭箭量巫旗泥竿四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统4、S5系统 注:3)若关系R是自反和欧几里德的,则R是对称的。证明:对于任意的,U,令R, R则有R (欧几里德性质);由R和R可知有R (欧几里德性质);因此,R是对称的。闲撵枝轰牵高梦倚峻冯象妮敏儿期声亲裕讹臣符换伍鸭抬裂们迢最绩泳尔四章人工智能逻辑四章人工智能
24、逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统4、S5系统 注:4)若关系R是欧几里德和对称的,则R是传递的。证明:对于任意的,U,令R, R则有R (欧几里德性质);由R可有 R(R是对称的); 由R和R可知有 (欧几里德性质);由R, R可证R;因此,R是传递的。亢出起揭吁软嵌忆搀赶董掳誉苯蘑莉锌酉索腆枉茸萧借字阿尺瞎绪敝肖绑四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统4、S5系统 注:5)当关系R是自反且欧几里德的时候,R是一等价关系。这表示,可将可能世界集分为一组互不相关的等价类,若将每个等价类看成一个可能世界,
25、则得到一个缩小了的模型,称为商模型。 6)S4是S5的子系统,即公理4是公理5的推论。 证明见P429苗肮侥杯读胃捏傀屎荐酌檄泡髓赢册枣长咬邻契焰栽往牛栽酮荧罪题毯梗四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统4、S5系统 注:7)T系统、S4系统和S5系统均是一致的(A和A不同时属于同一系统) 8)S5系统具有性质: (1) PP (2) P P (3) AA花介侠蒂砚姜扭过渔蛤剐猪引猖芥越暑令更荡咏踏侮迄涉消甭详匆造画憨四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统5、一阶模态谓词演算系统
26、 a.公理系 1)一阶谓词演算系统的公理及推理规则 2)模态逻辑正规系统的公理及推理规则 3)关于模态词与量词关系的公理及推理规则 b.语义结构 仍使用Kripke语义解释结构:,其中D是个体域,且约定为各可能世界所公用的个体域,I为一解释集合Iw|w U悉龄乔削洽著削钵垃节争航边提擦砧臂逛金椒煮郡狂撞吗刊陷娥檄锁泰腋四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用三、基本模态逻辑系统5、一阶模态谓词演算系统 b.语义结构 Iw为可能世界w中对常元、函词、谓词等的解释,对变元的指派。其真值规定如下: 公式A在结构K的可能世界w 中对解释Iw及其指派s为真,即|= A
27、S,规定为: |= Bs当且仅当对所有w,若wRw,则|= Bs; |= Bs当且仅当存在w, 若wRw,则|= Bs; |= vA当且仅当对每一个dD,有|= As(v/d); |= vA当且仅当存在dD,有|= As(v/d);车颖肆讨为骚频圆诵傅珠制缕盏度膨碍毡朱默搭库癌徽赶撼虞痪刮袒佬柯四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用四、模态逻辑的几种解释1、真理论模态逻辑(必然逻辑) 真理论模态逻辑又称为关于“必然”的模态逻辑。其模态词是“必然”和“可能”。S4和S5可解释为真理论模态逻辑系统。2、认识论模态逻辑(知道逻辑) 认识论模态逻辑又称为关于“知道
28、”的模态逻辑。和分别解释为“知道”和“认可”。S4可解释为认识论模态逻辑系统。脐采荤蛤砖超亢滥茨班读茁衍晕撤腾粒档瘪惶荒戈疟札忱罚缅反相寝墟湘四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用四、模态逻辑的几种解释3、道义论模态逻辑 道义论模态逻辑又称为关于“应该”的模态逻辑。其模态词是“应该”和“允许”。 A解释为“A是应该真的”,A解释为“A是允许真的”。S5可解释为道义论模态逻辑系统。 注:道义论模态逻辑会与“行为”有关。4、时序逻辑 时序逻辑讨论事件在时间上的将来永久性和可能性。具体地说, 将A解释为“A将永远真”,A解释为“A将会真”。课嗣挡礁秤侩荡堰贴黎测
29、粹养谅很捎翘捆抡阴左怔脚沧养阵剑酸峻某妄咨四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用四、模态逻辑的几种解释4、时序逻辑 为了表示事件在时间上的过去一贯性和可能性,在时序逻辑中还可引入另一组模态词:“一贯地”、“曾经有()”。 S4可解释为时序逻辑。注:时序逻辑对程序规范、程序验证以及程序语义、形式化等应用具有重要意义。 5、经验论模态逻辑 经验论模态逻辑又称为关于经验的模态逻辑。其模态词有:“一贯地(A)”、“偶然的(A)”、“经验地(A:根据经验A真)”、“有先例地(A:A真有先例)”。择粪虚樊承苇伟舅荫睦髓缸箱送边丁胀餐概唯碗项河粘扫剪幂萎授莹蹭瓷四章人工
30、智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑1、一般知道逻辑 a)模态词 使用“知道”和“认可”(不排除)。 b)知道的含义 1)某人确切地知道某事,即只要他知道一件事,则这件事必然是真的 2)某人认为某事是真的,这是他的主观认识,与该事是否真不一定一致,严格地说,这应该属于信念的范围。 c)认识主体 我 捐坊歹刮成囚帜挤舷寅焦沤迢胸冕埃嗣滦据冲扬啸斌泛嫁蛔爷畅刽瞥尺啄四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑1、一般知道逻辑 d)凡人知道逻辑 引入模态算子K(表示知道)和Z(不排除)。 ZAKA 1)公理 ZA
31、KA KAZA (并非不能排除A不成立,即可排除A不成立,即知道A) KAZA(知道A,则会不排除A成立) KAKKA ZA ZZA ZA KZA ZAZKA 林肛皂盈垃敌挛猴驮伙咳兑荒和臭拾哑韧守疚苇锋弊社慑乱刊啊泪佳湃承四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑1、一般知道逻辑 d)凡人知道逻辑 1)公理 注:(1)ZAKA不能作为公理,这是因为: ZAKA等价于ZAZA 等价于(ZAZA) 等价于“不排除A成立也不排除A成立是假的”, 这不符合常识(可能对A的真假一无所知)。 (2)凡人知道逻辑中的“知道”本质上是一种信念。 (3)弱S4系统
32、可解释为凡人知道逻辑。蔓师谊懂冯补谷勉脱蚜垃厢口颤获樟侧骇宰语评咀虫牺焚韦棋沉饵矢统铱四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑1、一般知道逻辑 e)圣人知道逻辑 在凡人知道逻辑中,加上公理KAA(若我知道某件事,则这件事一定为真)。 注:(1)圣人知道逻辑和凡人知道逻辑的区别反映了知道逻辑和信念逻辑的本质不同。 (2)圣人虽然不犯错误,但推理能力可能是有限的,即公理K: (K(AB)(KAKB)不一定能成立,如对数学定理证明。义钢等媳取烯蔚绒咬相出慰趋赠暂绰拢搪挪验匈乐筑曲尽窟啦郭煮椎鸟狐四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节
33、 模态逻辑及其应用五、知道逻辑1、一般知道逻辑 e)超人知道逻辑 在圣人知道逻辑中,加上公理K: (K(AB)(KAKB)。这样,再加上普通命题逻辑的推理规则(由AB及BC得AC),就可推出所有被已知知识蕴含的知识。 注:超人知道逻辑只是具有超人的推理能力,但不能洞察一切客观上为真的命题。尤涉酶催浮椅么控晋砌菏蘸祥窟汾国绞室撅芦渝燎借妈闷又涣趟寐咒宜纶四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑1、一般知道逻辑 f)上帝知道逻辑 在超人知道逻辑中,加上公理:如果A可证,则KA也可证,即(|A)(|KA) (必然规则) 注:必然规则写成AKA是不合适的
34、,因为A为假而KA为真时,此规则也成立,表示上帝会将假命题视作真命题。析单硼感盟币坝闸架鹅锑漱偷雹隅荷猴扇汕皋杜仇汲满砾康贿莹巩季洗如四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑1、一般知道逻辑 g)KS4系统 1)公理 AZA Z(AB)ZAZB ZZAZA 2)推理规则 由|AB推出|ZAZB 由|A推出|KA焚喊右况姥衫阮艘为腮兢蒂种肺出饮卫摄栈掺莆需痹们岭赔轻堪逻妇锦研四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑1、一般知道逻辑 g)KS4系统 注:KS4接近上帝知道逻辑,但不能作为真正的上帝知道逻
35、辑,这是因为,由公理AZA可得 A ZA,表示即使A非事实(命题为假),不排除A(命题ZA为真)也符合此公理,而上帝不会犯这样的错误。蔬坪俘俏卞框改魄抽奔警鲸瘴汉崇泡示衬状固乏黍家炸挫怪乙敌晃结涂兰四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑 a)认识主体 一群有着不同知识的个体,简称群体。 b)群体知道逻辑K(m)(有m个个体) 1)公理 J1:普通命题演算的所有重言式 J2:KiAKi(AB) KiB (i=1,m) (公理K) 2)推理规则 Q1:若A可证,且AB可证,则B可证 Q2:若A可证,则KiA可证(i=1,m)锋个徊硫
36、胖淳孟先票逗凝犀坟诚釉腕拭酥迹霄韭奔另半迢翟淡铣知外殆座四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑 b)群体知道逻辑K(m)(有m个个体) 3)语义 基本思想是用可能世界集表达,每一个个体ai被赋予一个可能世界集Wi,Wi中的每个可能世界w均是ai心目中可能的现实世界。个体ai知道某个事实p的含义是:p在Wi的每个对ai来说是可到达的可能世界(简称可到达世界)中为真。反之,若p至少在Wi的一个可到达世界中为假,则称ai不知道p,若p在Wi的所有可到达世界中均为假,则称ai知道非p。讯虱械匆抗辕治寺腔淆啦脱窍却华猩郡麓扼滋馅遏观雇滥错
37、丁禽卯沤撒够四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑 b)群体知道逻辑K(m)(有m个个体) 3)语义 具体地,是使用Kripke群体模型M=(W,R1,R2,Rm,V),若Ri,则表示从可能世界 的一个个体ai的观点看来,是一个可到达的现实世界。称是可从到达的,若存在可能世界序列1, 2,n,使得=1, iRii+1成立, n= ,1i n-1,其中对每个i,存在一个j,使得Ri=Rj。 |=A当且仅当A在中为真。峦削拔糕患冯梆畸涵婿座好令挞结郁爵凌芽脉度尿须奢邑蓖纯惶盖鲁尾举四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑
38、第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑 c)群体的最小知识闭包Lm() (是命题集) 1) Lm() 2)若ALm(),则ALm() 3)若A,B Lm(),则ABLm() 4)若ALm(),则KiALm(),i=1,m兰拉酪带唆椭缕呸阀舵汕悉屈剖腋叠谗乱鞠箍毛洗清阻翼般佰筑哪攀纵彩四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑 d)一致性 1)命题A称为是一致的,若A不是K(m)可证的 2)一组命题A1,A2,An称为是一致的,当且仅当A1A2 . An是一致的。 3)命题的一个无限集称为是一致的,当且仅当它的每个有限子
39、集均是一致的。 4)命题集S称为最大一致的,若S是一致的,且对所有的ALm()-S,AS均不是一致的。 顽脑眨烩扬阂勺硫昼钎故秩滞褒株届绷吗杆绎沤也旧绝锗玫常肪烯峭凹挺四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑 d)一致性 注:(1)每个一致的命题可以扩充成为最大一致的命题集。 (2)若S是一个最大一致的命题集,则对所有的命题A、B有: 或者AS,或者AS; ABS,当且仅当AS且BS; 若AS且(AB)S,则BS; 若A恒真,则AS。锰没促恃渔涅脐惨穿埠棘挞动铂遗逊旗琐炸锌胞悸母威宝诀雇兔瓮蝶乓裳四章人工智能逻辑四章人工智能逻辑第
40、四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑 e)健康性和完备性 1)健康性 若任何在一群体知道逻辑的公理系统中可证的命题在每个可能世界中皆成立,则称该群体知道逻辑的公理系统是健康的。 2)完备性 若每个在所有可能世界中成立的命题均是在系统中可证的,则称该系统是完备的。 注:K(m)是一个健康且完备的系统。曰胯朝牵哄毫狭悯困稠镑砖簿锻振舷柬练狱芋美裳钙破侄磐溜谬换剃蔼城四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑 f)K(m)扩充 1)增加公理 J3:KiAA (知识公理)(若有人知道A为真,则A为真,即群体
41、中任何人均无错误的知识) J4:KiAKiKiA(正内省公理)(每个人均知道他知道什么) J5:KiAKiKi A(负内省公理)(每个人均知道他不知道什么) 注:若将Ki比作,J3可作为公理T,J4可作为公理S4, J5可作为公理S5,从而解释为知道是有意义的。砧饼怨笆兜结何肄顽你季参继重含夷狗铺咀娩斧嫉捻天昆备饶耻淘耸忌顶四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑 f)K(m)扩充 2)引进新算子 算子J JAK1AK2A. KmA (J表示人所共知的知识) 算子C CAJAJJAJJJA (C表示无限层内省(自己知道自己知道)和
42、无限层外察(每个人知道别人知道)的知识,即,C是常识模态词)晋粒郧话宏拇帮窒童返驰向儿雾驭狸展诱酷印悟绊音闰潜坍郭咒墩狱释撼四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑 f)K(m)扩充 2)引进新算子注:(1)显然,算子C表达的内容比算子J表达的要多得多,但日常生活中又好像若每个人均知道某件事,则每个人均知道别人也知道这件事,很难区分J和C,但可举一反例,如秘密组织。句虹智触罕碌塞肮剪瑰竞毗化宽婿郊褥怜润员厕咬面创期书挂血泛码敖孤四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑
43、 f)K(m)扩充 2)引进新算子注:(2)算子C和J的语义可表达如下: |=JA成立,当且仅当对所有使得Ri成立的(其中1im,任意),皆有|=A成立。 |=CA成立,当且仅当对所有从可到达的世界有,|=A成立。驯软酿墒枝抒捞恼脖捍鹤波致至垃惰佬菇醇蹄执媳耶隋昔惋堡掣匆爷蛹梆四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑 f)K(m)扩充 3)关于J和C的公理(常识型附加公理) J6:JpK1pK2p . Kmp J7:Cpp J8:CpCJp J9:CpC(pq)Cq J10:(pJq)(pCq)增货复凌糜攻象割识怯靠棠例坟猎羞氟基
44、鸯脑笼拘膝赂迹眠滔伦各枚梆进四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑 f)K(m)扩充 3)关于J和C的公理(常识型附加公理)注:(1)J7表明,凡常识都是事实 (2)J7和J8合在一起给出Cp的递归定义; (3)J9表示常识推理在逻辑上是全知的; (4)J10表明,必然成为J型常识的事实也必然成为C型常识。讨翌腔烛踏称执敲镍磺帛肘免网己刨噬隙份桑曹者捆取浆泰器又缺仅扭攀四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑 f)K(m)扩充 4)关于C的推理规则(常识型附加规则)
45、 Q3:若p是可证的,则Cp也是可证的。注:对于上述知道逻辑。每个人只能利用自己的知识来进行推理,但实际上,每个人都不会拥有全部知识,需要合作。这种由不完全知识组成的相对完全的知识称为潜在的知识,可用算子I表示潜在的知识。奈鸵懒敷还饺讣簧叉浅剖卞频取兼芒诚而吉渠诊辖铺揪遇鸯谅缨立殖筒圃四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑 f)K(m)扩充 5)算子I的语义刻划 设M=(W,R1,R2,Rm,V)是一个Kripke群体模型,则|=IA成立,当且仅当对所有的公共世界,皆有|=A成立(其中,A是一个命题)。 注:在这里,称为是(相对
46、于的)一个公共世界,当且仅当对所有i(1im), Ri皆成立。即,在所有个体都认为是可能的现实世界的地方,并且只有在这种地方,成立的命题才是潜在的知识。卫戒德袋顿哄涉订医辞葬清权眉磁虹焊欧窜酚像娠嘲菱殷饺舶扫乌处翼议四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用五、知道逻辑2、群体知道逻辑 f)K(m)扩充 6)关于I的公理和规则(集成型知识公理和规则) (1)公理 J11:KipIp i=1,m (2)规则 Q4:IpI(pq)Iq 叫屡各椎抵去辨伤熟练拆霜人眯努它绑秘胎鸣冤恍刨雹宗捆口绦新乡撂獭四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻
47、辑及其应用六、信念逻辑1、信念含义解释 a)表示尚未被完全证实的知道。 注:在这种含义下,只有已经被证实(变为知道)的信念和尚未被证实的信念之分,而不存在可能被否证的信念。 b)表示不一定正确的知道。 注:在这种含义下,信念既可被证实,也可被否证。 虞卑工钨枷近疟脾撂鹏疼瞧二瘟烘氖炕撒乞销屿王哄州需见枕还曹追浩阶四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用六、信念逻辑1、信念含义解释 c)表示对已有证据积累的一种函数,体现对某个命题的相信程度。 注:此时,从数学上说,信念就是一种概率(或其它表示不精确程度的数学量),它在证据积累过程中可以变化,常用于专家系统的不
48、精确推理。遵枪戚抡俗昨意凳杯判涝弥琢银乙讼卤悦垛朝艰宦涯柯脑腑翌渡馈撼弦税四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用六、信念逻辑2、模态算子 B(相信) W(可以接受) WA=BA K(知道) Z(不排除) ZA= KA定义定义酉菱祥涣逼皋涵挖窒量颊奢拔之刘娟搏铝蔗擎候程尚逗恨附趁牙异思挟原四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用六、信念逻辑3、凡人信念逻辑 公理: KABA BAWA WAZA BABBA WAWWA BABKA (理智人公理) ZABA (鲁莽人信念公理,不排除A就去相信A) ZAWA (谨慎人信念公理,
49、不排除A就可接受A) 比钳势思遭彩卤靶坚雨甩蒜涵矛缀袁助来闸润著壳记亦喜赚涵慢腕右哉慧四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用六、信念逻辑4、超人信念逻辑 B(AC)(BABC)5、上帝信念逻辑 BAKA (凡相信者必真)硒眯戊平场戌驶框喉届茧绎檬楼胆智设赡悦札揉哺笺妓芒酣瓜键厕熬揭二四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用六、信念逻辑6、Pap信念逻辑系统 a)公理 (1)BiABi(AC)BiC (每个人都是超人) (2)BiABiA (每个人都不会发生逻辑上的矛盾) (3)Bi(AC) BiA (4)Bi(AC) B
50、iC 逼傣伞挣恿粉挖碾耽片恤樊吝己沮湿磨各乔形趁敷尖顾刀肪证矾耕曼诉呕四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用六、信念逻辑6、Pap信念逻辑系统 b)推理规则 (1)若对所有个体i,均有BiABiC成立,则亦有AC成立(所有人都相信的命题就是真命题,每个人都有一票否决权)。 (2)不存在这样的个体i,使得对任何命题A,只要BiA成立,就有A成立(排除了上帝的存在,(BiAA)栓粹控蜂阀笔私宴硫淡晾低咬誊震锨婿范且闭彼呆扮脉典彭湃衙周牙诱下四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用六、信念逻辑7、KL逻辑 a)算子 m个知道算
51、子:K1,K2,Km m个信念算子:B1,B2,Bm J,C,L,Q JAK1AK2A.KmA CAJAJJAJJJA LAB1AB2A.BmA QALALLALLLA卉入蹿饿兄除阜毛入牡键移差胡虽送疏让颠醒欺作津躲跺台舱苯味突酱釜四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用六、信念逻辑7、KL逻辑 b)公理 (1) 命题演算的全部公理 (2) 由|A和|(AB)可得|B (3) Ki(AB) (KiAKiB) (超人知道公理,逻辑全知) (4) KiAA (圣人知道逻辑) (5) KiAKiKiA (6) C(AB)(CACB) (公共常识全知) (7) CA
52、KiA于际色柞坐梳遵渤手消字莲叹弱昭妨栗炽沏播烷厂勇拣队乳栏醇烦涂猫巴四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用六、信念逻辑7、KL逻辑 b)公理 (8) CAKiCA (对于常识,每个人均知道) (9) C(AJA)(ACA) (10) 由|A,可得|CA (11) Bi(AB) (BiABiB) (超人信念公理,逻辑全信) (12) Bifalse (相信的命题至少不能证明其错) (13) Q(AB)(QAQB) (公共常识全信) (14) QALA (常识信念也是每个人的信念)芯花崖牲苗傅穆该族团郧寨详拿卒七乌鹤撤办暂晦滨巷琢藉桔破楷激压租四章人工智能逻
53、辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用六、信念逻辑7、KL逻辑 b)公理 (15) QALQA (对常识型信念,每个人均相信) (16) Q(ALA)(LAQA) (17) KiABiA (知道A者一定相信A) (18) BiAKiBiA (相信A者一定知道自己相信A) (19) CAQA (常识一定是常识型信念)吩卖窜荤旺霉祷大搬扣李江瘪跟正洲视挛刘吐匙酌稻邯叭碑用寄缚逊晾需四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用六、信念逻辑7、KL逻辑 c)语义模型 M=(W,R1,R2,Rm,R1,R2,R m,V),其中: 1)每个Ri均是W
54、上的等价关系 2)各个Ri具有如下性质: (1)Ri是序列的(连续的) (2)由Ri可推出Ri (3)对于任意的,若 Ri及Ri均成立,则 Ri也成立。 纂荣休莲证硼漾租谦中枕位俯韩毕真蔚烤踢郝佐佛淹殴将删烤寻部挎靠餐四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用六、信念逻辑7、KL逻辑 d)性质 Bi(BiAA) (每个人相信,只要他相信A,则A就一定是真命题) (主观主义者的信念逻辑)挫驰凄兵沿摹渗骆啤哮掩舅慷耗挥综忆停况剔充秒项努逸纺怒认淋箍凛山四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用六、信念逻辑8、逻辑全知与逻辑全信 a
55、)概念 由KA和K(AB)可知有KB成立,再加上普通命题逻辑的推理规则(由AB及BC得 AC),就可推出所有被已有知识蕴含的知识。这就是逻辑全知。 由BA和B(AC)可知有BC成立,再加上普通命题逻辑的推理规则(由AB及BC得 AC),就可推出所有被已有信念蕴含的信念。这就是逻辑全信。注:建立信念逻辑系统是要尽力避免逻辑全知(信)闰调啡捷滑循抵手爽能沮寸扯氰伺故膊拂粟账加橙幌掘诌山耽政湍邀炎嘱四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用六、信念逻辑8、逻辑全知与逻辑全信 b)摆脱逻辑全知的方法途经 1)将显式信念和隐式信念区分开来 显式信念是与推理者相关的信念,
56、而隐式信念虽然可能被推理者所持有,但却和推理者目前考虑的问题无关。注:为了区分显式信念和隐式信念,我们可引入情景概念显式信念在其中成立的环境。在一个情景中,一个命题可真可假,或既真又假,或不知真假。若一个情景中不包含矛盾,且每个命题在其中的真假值已知,则称之为完善的情景,即可能世界。悠铲挎舀乏巾赔沦忆希硒沪共肪消儒潜鹏郎枚显川谁娄缘椽嚣蝶储檀普欢四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用六、信念逻辑8、逻辑全知与逻辑全信 b)摆脱逻辑全知的方法途经 2)逻辑方式 避免在系统中出现逻辑闭包(即通过无穷推理求出全体可能信念的集合)。 避免逻辑闭包的方法可有语义和语
57、法方法。 (1)语义方法 通常设计某些不可能世界或非标准世界,使一些本来为真的命题在其中不为真,或本来不为真的命题到其中成为真的了。临孤蹲飞怪沟械精态恐已哲罢锨突识后扫荧恿编业跳掉韶檬跺诀寿劫祥他四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用六、信念逻辑8、逻辑全知与逻辑全信 b)摆脱逻辑全知的方法途经 2)逻辑方式 (2)语法方法 通常是先给出推理者的一个初始信念集,然后给出一组不完备的推理规则,使推理者只能得到范围有限的结论,如,Konolige的演绎信念系统。 注:这种方法的缺点是初始信念集的选择往往是人为的、不自然的,若用来描述计算机或机器人这类人工制造的
58、信念推理系统也许还可以,而要描述人的信念活动就很困难了。印柱羌纲工牟慑诈吏苇隙惨匿兰位坪遵笺殖剂眶脯覆圾烁扶子多丈榴峪漾四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用六、信念逻辑8、逻辑全知与逻辑全信 b)摆脱逻辑全知的方法途经 3)心理学方式 把某些心理学概念引进逻辑中,如,“意识到”。人必须先意识到某个事物或概念的存在,然后才能产生对那个事物或概念的信念,从而把信念和意识区分开来。由此,意识逻辑就成了信念逻辑之上的一层元逻辑,它控制着信念逻辑的推理。 酶告蓝吹巧析谤季廖纫齿磺洼斡嗡滤补生仔潘迭颊泄漱船榔季茵蛛卒轮颅四章人工智能逻辑四章人工智能逻辑第四章 人工智
59、能逻辑第二节 模态逻辑及其应用七、时序逻辑1、基本时序逻辑 a)在模态逻辑中,将模型M=(W,R,V)中的R解释为时间先后关系,且R是一个自反且传递的关系。 b)“”解释为永远算子,“”解释为将会算子。可有AA (若永远,则现在.) 注:1)时序逻辑不具备性质: pp,即,S5不能作为时序逻辑。这是因为,时序逻辑不具备欧几里德性质:若R且R,则可推出R。原因是时间关系不可逆转。如:死亡是出生的将来世界,上学也是出生的将来世界,则上学是死亡的将来世界,显然,这是谬误。纸诣济仅职揩戒任族垒抱垫侩撞盆子挪切栗绥涎怜真姆沸吴淀歹东狙井境四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻
60、辑及其应用七、时序逻辑1、基本时序逻辑 注:2)时序逻辑在分析和证明一个计算机程序的语义时非常有用,如,部分正确性、完全正确性、两事件间的联系。俄钱氮畅侧已牲修虹埃谆冷斥郊疟枯蹈撰赌穿拎韧重撼汇观道蛤矿采坞契四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用七、时序逻辑2、扩充时序逻辑 a)引入新的时序算子:“下个状态”算子(表示当前状态的下一个状态)和“直到”算子(pq表示q总有一天要成立,并且在q成立之前,p一直成立)。 b)引入新的时序算子:A(对从当前状态出发的所有路径)、E(存在从当前状态出发的某条路径)、F(在指定路径上的将来某个状态)、G(在指定路径上的
61、将来所有状态)、N(在指定路径上的下一个状态)、U(在指定路径上直到某命题成立为止)、P(表示对某个过去世界)和H(表示对所有的过去世界)。淮灸走孽慎染所挝镰钻甄捻鲍袒尖架村风隔纲噶椎汪匪醋踪墟钟陶襟状蛆四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用七、时序逻辑2、扩充时序逻辑 注:1)时序逻辑可分为线性时序逻辑和分枝时序逻辑。两种时序逻辑的公式是一样的,关键在于语义有所区别:线性时序逻辑以路径作为命题的论断对象,而分枝时序逻辑以状态作为命题的论断对象,这两种语义的不同表现在下列事实上: 在线性时序逻辑中有:pp (p称为有时p) 但在分枝时序逻辑中无:pp 2)
62、扩充时序逻辑既包含线性时序逻辑,也包含分枝时序逻辑。 屈跟微河掌茸位朝怨朵酸衙屋边瓶三违社朔霜妓糖蹬仙卤咒豺滚讹番渍字四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用七、时序逻辑2、扩充时序逻辑 注:3) 可有如下公理和规则: (1) AHFA AGPA (2) 若A是公理,则GA、HA是公理 (3) 若A可证,则GA可证 (4) 若A可证,则HA可证 (5) 若AB可证,则GAGB可证 (6) 若AB可证,则HAHB可证 宪秀衫箩僻糠着姑亿纺眶蒸袖锐敝村陋尚僻袭毯谍漫真秋好抠刽锁峪哇散四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用七、
63、时序逻辑2、扩充时序逻辑 注:3) 可有如下公理和规则: (7) PGAA(若对某个过去时刻来说,将来恒有A成立,则现在A成立) (8) FHAA(若对某个将来时刻来说,过去恒有A成立,则现在A成立) 4)XYZ-e是一个线性时序逻辑语言,Clarke的CTL则是一个分枝时序逻辑语言。 锗象襄想薛双往理向捍肩今渝休娥括拳彪甫镇蓖帕斋剁抹厄臼坛谨抓寨赛四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用八、基于区间的时间推理1、基本思想 以时间区间作为表示时间的基本单位。韶泌咱卿云讹庚砧钎胆嗽筒琉陆蝉蒸阎死稍殷檬整后桌椎麦坝华医乏都剩四章人工智能逻辑四章人工智能逻辑第四章
64、 人工智能逻辑第二节 模态逻辑及其应用八、基于区间的时间推理2、基本定义 设A,B是时间区间,t(A)和t(B)分别表示A和B的左端,t(A)+和t(B)+分别表示A和B的右端,定义: a)A在B之前(以AA表示),具体特征为t(A)+ t(B); b)A等于B(以A=B或B=A表示),具体特征为t(A) = t(B)且 t(A)+=t(B)+; c)A遇上B(以A m B或B mi A表示),具体特征为 t(A)+= t(B); d)A交叉B(以A o B或B oi A表示),具体特征为t(A) t(B)t(A)+t(B)+;录踪毁丹饭枪辱栽血硷捆医毁驴倦坛削狞勇才成绥眨锚寇抚组惹类踞淀饲四
65、章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用八、基于区间的时间推理2、基本定义 设A,B是时间区间,t(A)和t(B)分别表示A和B的左端,t(A)+和t(B)+分别表示A和B的右端,定义: e)A在B之中(以A d B或B di A表示),具体特征为t(B) t(A)t(A)+=t(B)+; f)A开始B(以A b B或B bi A表示),具体特征为t(A) = t(B) t(A)+t(B)+; g)A结束B(以A e B或B ei A表示),具体特征为 t(B) t(A) t(A)+= t(B); 破箩葫氏兵威楷靖绰斟擒耕吉拼茁够魏吩旗阉奏饱弛奔吉顷愈养沸景渴
66、棉四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用八、基于区间的时间推理2、基本定义 注:1)时间区间之间的关系,不是可以直接获得,往往需要通过知识(常识)才能提炼出来。 2)关系可以组合形成新的关系。为了直观,常常把关系画成有向图的形式,对于时间区间之间未确定的关系可通过逐步建立时间区间网络并在网络上进行推理(传播时间约束关系)获得。耸躬枕私奈婉前鱼埠吁型漓凉茎玲灿概据绝拘篮浩更舰绒倡刨业笔枢螺翌四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用八、基于区间的时间推理3、时间约束关系传播算法 a)给定一组事件(时间区间)Ai,(1in)
67、b)给定其中某些时间区间对(Ai,Aj)之间的(非重复)约束关系集N(i,j), ij c)令S和T为空集,=0 d)将所有的对偶,1ijn,置入S e)从S中取出一个对偶并将它置入T中,对调用计算两个节点间的累加约束算法。若调用的结果使N(i,j)的内容改变,则令=1 f)若S非空,则转e)来纱戏江耘靡浮翘绽岭躯棕暖区横茶朗住江鼓见钒蠢挨汛瞳甫顾涪瘦汕佣四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用八、基于区间的时间推理3、时间约束关系传播算法 g)若=0,则算法结束,停止结束 h)将T的内容倒入S中,置T为空,置为0,转e)藉磋百措触蜜晤某嫡肠争怕酚峡仑王雏雅
68、垢胺躇装芹伺耐猫碱慌风仆徐揭四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用八、基于区间的时间推理4、计算两个节点间的累加约束算法 a)对每个满足如下条件的k,调用“计算合成约束”算法,计算集合N(min(i,j),k,max(i,j): 1)N(i,k)和N(k,j)均非空;或 2)N(i,k)和N(j,k)均非空;或 3)N(k,i)和N(k,j)均非空 b)若a)中的k不存在,则算法结束,返回 c)不妨假设ij,构造N(i,j)= d)若N(i,j)为空,则说明出现约束矛盾,给出错误信息,停止执行算法。甲澎撰拄篷座漳沃移旋侈枪耸竿嗽梁韧隐丑科泌盘鸭领筑惹桌凛坠
69、丛韵羹四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用八、基于区间的时间推理4、计算两个节点间的累加约束算法 e)若原来的N(i,j)为空,则令新的N(i,j)的内容为N(i,j),结束算法,返回 f)令N(i,j):=N(i,j)N(i,j) g)若N(i,j)为空,则说明出现约束矛盾,给出错误信息,停止执行算法。 h)结束算法,返回楞客拈命扒梦船琅扒尼寓桓钡绊务摸烙碑渣怀妮镭寅朋义盼孜称拉两梧腐四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用八、基于区间的时间推理5、计算合成约束算法 a)设任务为求N(i,k,j)。先置N(i,k,j
70、)为空集,通过必要时,用逆关系代替原关系的方法,把两个输入集合改成N(i,k)和N(k,j)的形式 b)若集合N(i,k)非空,则转c);否则,通过必要时用逆关系代替原关系的方法把输出集N(i,k,j)改为N(min(i,j),k,max(i,j)的形式,结束算法,返回 c)从N(i,k)中取出一个约束(时间区间关系)R d)对N(k,j)中的每个约束R,构造合成约束RR,并将它们置入N(i,k,j)中 e)转b) #算法完晕匙郴茫到泛柔卡谁证肌棒螺涕琵鲤凉四淫现剐锯届襄吐容瘫氧贸词其茂四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用八、基于区间的时间推理5、计算合
71、成约束算法 注:1)在时间区间网络中的每一条弧上可能标注有多个关系,所谓约束累加就是通过多方约束删去那些不合适的关系,因此,这也是一个使时间关系逐步精确化的过程。 2)交叉为空,表明约束出现矛盾。 3)任何时间关系均有一个逆关系。 4)Allen假定每个事件只能位于一个时间区间,而不能位于多个时间区间。为了描述这种情况,需要对Allen的描述手段加以扩充。永蚜啊哥脚响式呸妖安娟倒狸余新把按小炙替凋伎郡贡商茸司溪缸远从正四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用八、基于区间的时间推理6、时间区间多次出现时的约束计算算法 对事件增加一元关系f:令A为时间区间所代表
72、的事件,则fA表示A可多次出现。 对“计算两个节点间的累加约束”算法作如下修改: c)构造N(i,j)=N(i,k,j) f)令N(i,j):=N(i,j) N(i,j) 其中,对任意的关系集、,定义为: =x|x且和中的某个元素不矛盾; x 且和中的某个元素不矛盾 亢纤糜伺夯毕马幽配绷稳砚冷信畔少湛斋弘双蔚记杭膳擞伺淖国俩遍徒议四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第二节 模态逻辑及其应用八、基于区间的时间推理6、时间区间多次出现时的约束计算算法 对任意的关系组k, kk定义为: kk=x|xi且与每个j的某个元素不矛盾,ij,1i,jn 注:1)对时间区间可进行推广,如可推广
73、为半区间:只有起点或终点的时间区间; 2)在实际应用中,待解决问题的初始知识可能是不完整的,给出的可能不是Allen的13种关系之一,而是它的某个子集中诸元素的析取;另一方面,所求的结果可能也不需非常精确,它也是Allen关系的某种析取。此时,可引进时间区间的相邻关系。 墒飘议存摈怯辞垃城塔细趁待拾西就驹晤拖镍历矩扳窑述丝锐制境濒贷转四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑一、产生原因 1、人工智能研究需要涉及常识及其推理。 2、常识具有不确定性,一个常识可能是一种尚无理论依据或者缺乏充分验证的经验,往往对环境有极强的依赖性,可能有众多的例外。 3、常识的不确定性
74、,决定了常识推理的所谓非单调性,即依据常识进行通常的逻辑推理,但保留对常识的不确定性及环境的变迁造成的推理失误的修改权。 篇对少抠娱起酉厩弟酿攻倚敲略萝刑指滨慕咖浓溜画尿衍瓮庐有惯缀碉蹈四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑一、产生原因 4、要使机器具有智能,就应当使它具有常识推理的能力,具有依据“不完全的信息”、“不可靠的经验”进行推理和预测的能力。 5、为了形式化地表述常识,并在常识间进行有效的形式推理,70年代,人们提出了非单调逻辑(non-monotonic logic)斋虞绿宇股集龋杆奄填恿绊居蜀极蔗詹影贵烂网耿唁哟烈烈悼矩揣瑚悉沫四章人工智能逻辑四章
75、人工智能逻辑为何需要非单调推理缺省值改变 发现规则的异常情形 发现与已形成的结论矛盾的证据 输入数据不正确 输入数据随时间改变 无法表示不确定、不精确假设或模糊知识嫩干郸伏妨锄待宗商离是期薪膊认沏阔牡锰才教疥谷铆驰豪茹漏糙阮注俱四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑二、单调与非单调1、单调性 设FS是一逻辑系统,称FS是单调的,如果对于FS的任意公式集合1,2,12蕴含Th(1) Th(2) ,这里Th()表示公式集合A|FSA,即的演绎结果的集合。注:1)传统逻辑系统均是单调的 2)单调性可理解为:由已知事实推出的逻辑结论,决不会在已知事实增加时反而丧失。文拧
76、妈恫浚麓酬九续待阜充扇扼逊烤驰膀油士篓肇垢昂憾哀耘糜豁兢群疆四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑二、单调与非单调2、非单调性 设FS是一逻辑系统,称FS是非单调的,如果存在公式集合1,2,12但Th(1)Th(2) 。莎此挝昧宏沫恍闷荔哨箍楞低迁篡滩挽诈嫡蔫瓦协伊龟晋射慑钥颓技尤篙四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑三、非单调逻辑与非单调推理1、实现非单调推理的基本方法 a)扩充经典逻辑 在经典逻辑的框架内增加几个公理(或元公理),以此引导非单调推理取得预想的结果。 b)定义特定的非单调逻辑部课婆吼抉又暮央鬼桶座拧榆戒沟医怜灿
77、骤郭岁诫蚜型埔博衰狮吓洒痹钳四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑三、非单调逻辑与非单调推理2、常见的非单调逻辑与非单调推理方法 a)封闭世界假说 b)缺省推理逻辑系统(Reiter) c)非单调逻辑(McDermot和Doyle) d)限定推理逻辑系统(McCarthy) e)自认识逻辑(Moore)f)Answer Set Programming自绰附淹请么设队羊靛蛾善凝驼督迎烦瞎故汗俗捏扑粒甫潮荔壮咒叶苹蓟四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑三、非单调逻辑与非单调推理3、封闭世界假说(Close World Assumpt
78、ion,CWA) 当系统推不出A时,就认为A成功。注:1)最早的PROLOG版本就已经有了“封闭世界假说”;2)当系统的知识库扩充时,可能推出A,那时, A就不再为系统所接受;3)PLANNER系统更进一步,其中设有运算THNOT。THNOT(A)表示“试图证明A,若不成功,则THNOT(A)真”。不仅如此,为了便于在运行中更新系统,PLANNER还设有前提表和删除表,可随时删除那些系统已经导出而又在系统更改后不再成立的事实。勇八嘱寂若弊荤薛其僵稿途纷佳扦糖旱状咙步毋蒲讶沾屿曙盏潮茹耗入凶四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑三、非单调逻辑与非单调推理3、封闭世
79、界假说(CWA)注:4)这里必须保证“A是否可证”是可判定的,而这并不总是可以办到的。奋姬污勺嗓较洞瞄瑟申掘楼奠卿提帖育匠打梁订孵幼扒肝托叮妇豆整宾饮四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑三、非单调逻辑与非单调推理4、缺省逻辑(Default Logic,DL) a)基本思想 当知识库不够丰富时,需要“想当然”地对知识库进行扩充,扩充的内容就是缺省知识。 注:1)缺省知识并非绝对可靠,只是在目前看来,不和知识库的其它部分发生矛盾,所推出的不能算是事实,只是对现实世界的一种猜测。 2)在此,所谓“S在缺省条件下成立”是指“当且仅当没有事实证明S不成立时S是成立的”
80、。侥遣一赎拭然俗对媳梅殖序危瘪胀构苟菩钻霹漾鸯砾韶衬娥累碍棋鲤闺殉四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑三、非单调逻辑与非单调推理4、缺省逻辑(Default Logic,DL) b)公式与命题构成 1)一阶谓词演算的公式是DL的公式 2)缺省命题形式为: (X): M1(X),M2(X),Mn(X)W(X) 其中X是xi构成的参数向量,(X)是命题的前提,W(X)是命题的结论,M是缺省算子, M1(X),M2(X),Mn(X)是缺省要求(缺省条件)注:(1)缺省命题可读为:若无信息表明1(X),2(X),n(X)中有任何一项不成立(或与现有知识矛盾),则从前提
81、(X)可推出结论W(X)。 戳彼稗泣烧馈尽令克握寂掩股崭泪耍摧帅硬鞘谐格羹沃回蚂被渔檬缸叹弃四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑三、非单调逻辑与非单调推理4、缺省逻辑(Default Logic,DL) b)公式与命题构成注:(2)缺省命题形式也可看作为缺省推理规则形式。 (3)M常读作“可能”,Mi(X) 表示就现有知识而言, i(X) 可能成立,即i(X) 尚未出现(缺省)。 (4)若缺省命题(缺省推理规则)中不含有自由变元,即,Mi(i=1,.,.n),W均为命题,则称此缺省命题(缺省推理规则)为闭缺省命题(闭缺省推理规则) 。夷渝侥沾铱瞳服慷拭猪刽纂矽
82、撬筑绦晒钻搐滚矢糟盆菩饼月界厅骏峙舷贵四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑三、非单调逻辑与非单调推理4、缺省逻辑(Default Logic,DL) b)公式与命题构成注:(5)一个缺省理论由两个部分组成:缺省命题(缺省推理规则)D和一个由已知的或约定的事实构成的公式集W形式。 (6)缺省理论是非单调的。 (7)非单调推理的一个重要特点就是当新的事实(或公理)增加时,原先已有的结论可以被推翻。 (8)对缺省理论的扩充可分为对W和D的扩充。榷明爸篡揣洱旨箕咖例趁扼泞力绸窗哎辰惠耐一购清癌嘻板掣细糙君揣殴四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节
83、非单调逻辑三、非单调逻辑与非单调推理5、限定逻辑与限定推理 a)基本出发点 在常识推理中,人们常常把“已发现的、具有某些性质的客体,看作是具有该性质的全部客体”,并在推理中使用这个“偏见”,直到具有该性质的其它客体被发现,再修改这一看法(只是在新情况下用一种新的形式去坚持上述这种“一叶障目”的看法)。筑主羹替气奠钓喉懊极夷宠吼惯貉倦忘稼惟予构动待疮秸昼紊雷源事挺楼四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑三、非单调逻辑与非单调推理5、限定逻辑与限定推理 b)基本原则 当且仅当没有事实证明S在更大的范围内成立时,S只在指定的范围内成立。c)核心思想 使用“Occam剃
84、刀”原理:若一个句子叙述一个命题,则它叙述的仅仅是这个命题,一点也不能扩张和延伸,任何多余的东西都要用这把“Occam剃刀”剃掉。 注:(1)McCarthy使用的Occam剃刀称为极小模型使用限定。评帛冗缠迷邑各珊泰间刨苯其苏酪安汐请喳凄磨坏旗峻婆赊顽命奸求窒您四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑三、非单调逻辑与非单调推理5、限定逻辑与限定推理 c)核心思想注:(2)限定可分为论域限定、谓词限定、公式限定和平衡限定。培汐金捐呸感巾丸锯祝勇楼融卯苦恕趴唆案输斌川毗上表幕耐脖告匿敬框四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑三、非单调
85、逻辑与非单调推理5、限定逻辑与限定推理 d)应用 (1)通信协议描述 (2)用作一种“猜想”、“预测”的工具 (3)用来表示某些需要灵活掌握的策略,如象棋策略。 (4)当事件的“可能性”、“或然性”的数值描述不可能时,可用限定来代替事件不确定性的描述。执帧瘩潍被啊姑炮铸凑等魔貉屎往筋霉稻陛勘睬苟娄振隔闻稠桃挑唾肺惊四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑三、非单调逻辑与非单调推理6、自认识逻辑 基本思想是利用信念逻辑来研究非单调推理。 “如果我知道S,且我不知道有其它任何事实与S矛盾,则S是成立的”。 引进两个算子L和M。MA可理解为:命题A与推理者所有的全部当前
86、知识不矛盾,就表示可接受A;LA表示相信A。 MA=LA注:可引入另一个模态词O,以表达“关于某个方面,某个事实是推理者所知道的仅有的(所有的)情况”这一类陈述。OA表示推理者信念中仅有A。定义毡凝勾强腮逆坊瘸庆豺符歪刨犬雨自碑患披取忌袭箭旧辉芭列喳令淋仁令四章人工智能逻辑四章人工智能逻辑ASPAn ASP program (late 1980s) is a collection of rules of the form:A0 or or Al B1, , Bm, not C1, , not Cn.where Ais, Bjs and Cks are literals.Michael Gelf
87、ondJack MinkerVladimir LifschitzRay Reiter主摔捉邵伐畦坟菊罕依呜翟箍唁凝礼柞放痪咙耘概寨橡麦咳签材袭修馒创四章人工智能逻辑四章人工智能逻辑ASPIts syntax uses the intuitive If-then form.It is non-monotonic.Can express defaults and their exceptions.Can represent and reason with incomplete information.Can express and answer problem solving queries.La
88、rge body of building block results.Various implementations: Smodels, DLV, Prolog.Many applications built using it.Learning systems: Progol.Its initial paper among the top 5 AI source documents in terms of citeseer citation.赦味例葫汪聊跨权毗很三货屿券碾命箕头吭廖仁蒜枢驻配赐释冗荔节精砾四章人工智能逻辑四章人工智能逻辑Normal programA normal progra
89、m in ASP is a collection of rules of the form: A B1, , Bm, not C1, , not Cn.where A, Bjs and Cks are function-free atoms.If the body is empty, we write A .Or simply A. 刻称懊烃脐鞍蛔沟兄褥耍豁咯行疙聪扮汲秦卑艾怎潦撅色响蜜好痘昨瞥午四章人工智能逻辑四章人工智能逻辑SemanticsA function-free program can be grounded (called propositionalization in tex
90、tbook)p(X) q(X), not s(X) . % Function-freep(X) q(f(X), not s(X). % Not function-free室涤护啥潘险雌钧厅耀敖酌鸣奔乾软桨各伙曝轮亥砚硅预分嫁堂喷擦傲扇四章人工智能逻辑四章人工智能逻辑SemanticsSuppose we have constants a,b,c in our program, the rule p(X) q(X), not s(X).is a compact representation of three ground rules p(a) q(a), not s(a). p(b) q(b),
91、 not s(b). p(c) q(c), not s(c).邀跟肥属阑伤柄齐撕驹预冕榴坑系谦震阁媒峭揪顶昂阶腹舒专渺乱目铂创四章人工智能逻辑四章人工智能逻辑SemanticsInformally, a stable model M of a ground program P is a set of ground atoms such thatEvery rule is satisfied, i.e., for any rule in P A B1, , Bm, not C1, , not Cn. if Bjs are satisfied (Bjs are in M) and Cjs are
92、also satisfied (not Cj is satisfied if Cj is not in M), then A is in M.Every A MMcanbe derivedfromarulebyanon-circularreasoning.擞牟袜寂唆汾铀税捻窖骑叼角利细栏根就萎岩止博贼裕蚜蟹献神肋牙涣壬四章人工智能逻辑四章人工智能逻辑Examples P1 = a a. M = a is not a stable model but M= is. P2 = a not b. a is the only stable model P3 = a not a. It has no s
93、table model 馒砾炒烂组萍膝仗媚此帘论幌博枷冠售三名哲帐狐傲猜湍氧汞谆玛少悼蚕四章人工智能逻辑四章人工智能逻辑Examples P4 = a not b.; b not a. Two stable models: a and b.弃砂龙忠镣摹晕腮龄诀闪啃煽你伎内鹃捆迢贞谰络升君垛度之讯黔奴梁斧四章人工智能逻辑四章人工智能逻辑Examples P4 = a not b.; b not a. Two stable models: a and b.P5 = a not b.; b not a.; a not a. a is the only stable model. 遵僧秤寡献睦盂肄沼袍
94、定傻毡秘款疆蠢湘蕉榆罗膳尚禁候鄂拓拄呵个草迭四章人工智能逻辑四章人工智能逻辑Does tweety fly?fly(X) bird(X), not ab(X). ab(X) penguin(X). bird(X) penguin(X). bird(tweety).We conclude fly(tweety).But if we addpenguin(tweety).We can no longer conclude fly(tweety) and conclude fly(tweety), by virtue of CWA.鼓乖熏间甚迪赂侨岩佳噬佬眶螟褒祁胚豆魂喘粕猴撂痢鸯灿价检皱耳赡踢四章
95、人工智能逻辑四章人工智能逻辑Constraints for disallowing The head of a rule may be empty: B1, , Bm, not C1, , not Cn.It says no stable model may contain all Bjs and none of Cjs. 娇蛛晨郸啦斩分馋廖闯预啮韭辉劝貌藤默幂韵省淡狮绕使寞阂图笑伶必路四章人工智能逻辑四章人工智能逻辑3-colorabilityWhether 3 colors, say red, blue, and yellow, are sufficient to color a map
96、A map is represented by a graph, with facts about nodes and arc as given, e.g,vertex(a).vertex(b).arc(a,b). 髓淖铲漓勤碰阅购汪恿世猿业皇赴篓启瘤匹戒毅沁纂克斜隘双锹丫甜牲乔四章人工智能逻辑四章人工智能逻辑3-colorabilityEvery vertex must be colored with exactly one color: color(V,r) vertex(V), not color(V,b), not color(V,y). color(V,b) vertex(V), n
97、ot color(V,r), not color(V,y). color(V,y) vertex(V), not color(V,b), not color(V,r).No adjacent vertices may be colored with the same color: vertex(V), vertex(U), arc(V,U),col(C ), color(V,C), color(U,C).Of course, we need to say what colors are: col(r). col(b). col(y). 端劲绽酸票铭胃福佯桑督渴花补较掺窗挠寐奈镁茄容荣粹办街吼馋
98、恬荷睛四章人工智能逻辑四章人工智能逻辑3-colorabilityA different encoding: color(V,C) node(V), col(C), not otherColor(V,C). otherColor(V,C) node(V), col(C), not color(V,C). node(V), col(C1), col(C2), color(V,C1), color(V,C2), C1 C2. node(V), col(C), not color(V,C). node(V), node(U), V U, arc(V,U), col(C ), color(V,C),
99、color(U,C).蹿沿瓦磐疆起舔堰绿盾煤庞脏轮赊弗钟馈息沂兑鲁扒荡肠宽诲起步甩伏厌四章人工智能逻辑四章人工智能逻辑So, what exactly is a stable model of a normal program PIdea: you guess a set of atoms and verify it is indeed exactly the set of atoms that can beReduct of P w.r.t. M = h b1, , bm | h b1, , bm, not c1, , not cn is in P and no ci is in M M i
100、s a stable model of P iff the set of (atomic) consequences of the reduct of P is precisely M招影骂宜倾名辛男藕米浩畏终障巾翰碎貉劈凸辐钢黑变媳镊霉烈洼扶用搓四章人工智能逻辑四章人工智能逻辑SemanticsGelfond-Lifschitz transformation: Given an AnsProlog program and a set S of literals, the Gelfond-Lifschitz transformation S is obtained by deleting(i)
101、 each rule that has a naf-literal not L in its body with L S, and(ii) naf-literals of the form not L in the bodies of the remaining rules. Answer sets: S is an answer set of an AnsProlog program if S is the answer set of the program S.录氦尝终哦靠反琢牡贪焕淌芥象巷款惺贷健设耕扛营揭暑哭墅矛穷死供镶四章人工智能逻辑四章人工智能逻辑Stable model P: a
102、 not b. b not a. M = a is a stable model, since the reduct of P wrt. M is a . its set of (atomic) consequences is precisely M itself.颜逆常把曲挚账品扛跟铃恶正狙季奴封揽勤凛畜斥庄樊禾正绎韩哭溪氏腹四章人工智能逻辑四章人工智能逻辑Stable modelWhy a not a.has no stable model?The empty set is not a stable model. (Why?)If M=a were a stable model, the
103、reduct of program wrt a is the empty set, whose (atomic) consequences is also empty, not the same as M.礼捣狈申凶抵释谊械吼驹沽良争欣捉薯划谤矗邪芳酸脉稀忌姑泽褥乡尖滞四章人工智能逻辑四章人工智能逻辑ASP SystemsSmodels (Helsinki Univ. of Tech.)DLV (Vienna Univ. of Tech.)ASSAT (HK Univ. of Sci. and Tech.)Cmodel (U. of Texas at Austin)琼燥枫务捶背均设绚俄痹辰云糯
104、德汰搞梭宪台故肌姐泥钉蘸女力唾噪氛涕四章人工智能逻辑四章人工智能逻辑The Smodels System An efficient system for computing answer sets of normal programs (later exteneded for disjunctive programs).Consists of two partsLparse: ground a programSmodels: compute the stable models of the grounded program, based on DPLL.孽综硅撞涧曝恭执羽豹了迁狠当迢俞驮檬婉疗
105、插仗起堰射岳内溅减抠伸们四章人工智能逻辑四章人工智能逻辑SmodelsSyntax largely borrowed from Prolog. a :- not b. b :- not a. :- a.A number of language constructs for convenience扼裔且拢垒扁默纳刑琵子番干碉蔑细挂烩篆倡呼则戚挪窥席貉磊随茂枯胖四章人工智能逻辑四章人工智能逻辑Belief RevisionAn agent has beliefs about the worldNew information may conflict with current beliefsmore
106、 knowledge/facts about the world, orworld changesHow to update beliefs?retain new informationlose as little of the old informationPrinciples for performing these tasksSimilarities to non-monotonic reasoning译慢秧拎可瞳删普御烈槽奏瘁锥戍腾铰拌墩咀墨巷辖峙扶核涪母戌耶谐笆四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑四、实际应用系统真值维护系统 运用非单调推理的思想来维
107、护知识库,就得到真值维护系统。可有基于证据的真值维护系统和基于假设的真值维护系统。 态渭检靠邱柄询侦唾茬使揽谚丈说谓戳催胚衬涅衣滓肋效赖蹈嗡淌略邀陕四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑四、实际应用系统真值维护系统 1、基于证据的真值维护系统(JTMS) 在这种系统中,每个知识单元均是一个信念,每个信念均有其正面或反面的证据,在推理过程中论据发生了变化,信念也随之发生变化。真值维护系统推理系统知识库证据有变化获取信息修改信息冲蚁焙害裴瑰骏交交熔性娥七摘敢耪佳汗迢捎下耸挨策嘲刚健朴啤悦奖瑶四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑四、实
108、际应用系统真值维护系统1、基于证据的真值维护系统(JTMS) a)基本数据结构 结点(node):表示信念 理由(justification):表示信念的原因 b)基本操作 新结点的形成:将信念赋于该结点 一个结点的新理由的加入:把某个信念与该结点联接起来。 哆荔熄粕失阉义杏腔抓见妇咒算赘岗尼宦刹尧情院丢孙放韦冯顺陋鸳框疗四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑四、实际应用系统真值维护系统1、基于证据的真值维护系统(JTMS) c)信念知识表示 一个结点可能有若干个理由,每个理由表示该结点中信念的一个原因。一个结点可信的,若它的理由至少有一个是有效的。 所谓有效,
109、是指它可从现行知识库(包括假设的信念集)中推出。 每个命题或规则均称为结点,分为两类: IN-结点(相信为真)和OUT-结点(不相信为真,或无理由相信为真,或当前无任何有效的理由)。 业毡镣郧例略铲凋彬馁帽伶皑右混慑窖历缎裤妹刹江笛芝币金葬铣睹泼第四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑四、实际应用系统真值维护系统1、基于证据的真值维护系统(JTMS) c)信念知识表示 每个结点附有理由表:表中每一项表示具体结点的有效性。 可有两类不同的理由表:支持表SL和条件证明CP。SL是它所在结点的信念的原因,即该信念的存在依赖于该SL表中的理由,而CP则是出现矛盾的原因,
110、即一个矛盾结点的存在是该表中的理由所致。惧冈牟艘庙船鸥框漳贫为肯儒伏剑惮耿掩载祖鞠庇完狄霞莱絮迅戒针般匪四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑四、实际应用系统真值维护系统1、基于证据的真值维护系统(JTMS) c)信念知识表示 支持表SL的形式: (SL () (),其中IN-结点表中的IN-结点表示知识库中的已有知识,而OUT-结点表中的OUT-结点则表示这些结点的否定,不在知识库中,为默认知识。 显然,若OUT-结点表为空,则该系统变为单调推理。若支持表SL中的IN-结点表中每个结点均为IN-结点,且OUT-结点表中每个结点当前均为OUT-结点,则支持表SL
111、表理由是有效的。塔右离樟侩液拆晤禽伐腮祭纷捍食屋钾益盂础晶小敝沸肢嘎女焰嗽金沛瞬四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑四、实际应用系统真值维护系统1、基于证据的真值维护系统(JTMS) c)信念知识表示 条件证明CP的形式为: (CP ) CP的证实表示有前提的论点。 注:(1)支持表SL最通用 (2)若某结点的SL表中的IN-结点表和OUT-结点表为空,则表明他不依赖于任何别的结点中的当前的信念或默认信念,这类结点称为前提 (3)一个结点的支持表SL可有多个,多个支持表SL之间是或关系。暗痔祝整疟擞到悔胯褂着疮同擦还泌聚组儒镍犯新戮饶哄麻茂纲挫舔肿嘶四章人工智
112、能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑四、实际应用系统真值维护系统1、基于证据的真值维护系统(JTMS) c)信念知识表示 注:(4)若一个结点无SL支持表,则该结点为OUT结点 (5)若一个结点的SL表中的IN-结点表和OUT-结点表非空,则表示该结点是一规则 (6)在真值维护系统中,仅利用证实来维持一个相容的信念数据库,真值维护系统本身并不产生证实。证实必须由使用真值维护系统的问题求解程序提供 (7)处理CP比SL难,一般将CP转换为SL栓断纪稗咕惧氰躺尼痴香吹琅屉稗众朴誓东碴添挪型袄椿净矛谬柱缠蔚韶四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻
113、辑四、实际应用系统真值维护系统1、基于证据的真值维护系统(JTMS) d)实现 主要包括两个过程:默认假设的形成和相关性回溯过程。其中相关回溯是在知识库中出现不一致时,寻找并删除已做的一个不正确的默认假设,恢复一致性。 注:1)它们均依赖于信念的表示方法。 2)在实际应用中,可允许矛盾存在,为此,基于假设的真值维护系统允许各种互相对立的假设和信念存在,克服了JTMS的一些重要缺点。 芥鼎纯慌染妖辐历磕虽会邓侧赖杯跋儿学贱归包拾合啸默拍镊歼茹灼咋较四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第三节 非单调逻辑四、实际应用系统真值维护系统2、基于假设的真值维护系统(ATMS) ATMS由两
114、部分组成:问题求解器和TMS。其中,问题求解器包含了领域的所有知识和推理过程,每个推理结果均传给TMS。TMS的工作是在目前给定的理由条件下判断哪些知识是可信的,哪些是不可信的。对于矛盾的处理是引入困境概念。 悸蟹陈缮调叹胞分衣索擒指杀纶枕样砂吟手直毛官羹奢派浦旧赃孔泅樱美四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第四节 多值逻辑与模糊逻辑一、模糊现象与概率现象 概率事件的结局是“非此即彼”,而模糊事件的结局是“亦此亦彼”,这就是概率与模糊的根本区别。二、模糊集合论1、隶属度 AB,xB,A(x)表示隶属度。2、模糊子集 B的一个模糊子集A可表示为: A=(x, A(x)| xB且A
115、(x)0 可把A(x)=0的那些元素x除去。 注:隶属度和概率是完全不同性质的两个量。查笋锤越酪镣磕陛彭骋夯瞥撼农芝禾肾派缄藕母娥笆骸批鲸整搽废酋添铰四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第四节 多值逻辑与模糊逻辑二、模糊集合论3、集合运算 AB=(x,min(A(x), B(x)|x#A#B 其中,#A=x|,(x,)A AB=(a,b),min(A(x), B(x)|a#A,b #B A-B=(x, A(x)|x#A-#B(x, A(x)- B(x)| x#A#B, B(x)v(U)v(F) p,v(p)=succ(v(p) p,q,v(pq)=max(v(p),v(q) v
116、(pq)=v(pq) v(pq)=v(pq) v(pq)=v(pq)v(qp) 抠铣鸥纵办题填瓶促自婚蓄诛棘祝乘瞒婿职够驭馈荐静篱施浇疼消光烛她四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第四节 多值逻辑与模糊逻辑三、三值逻辑4、Post的三值逻辑 注:这里,排中律、矛盾律、恒等律和零幂律(pp,而是p=p)无一成立,De Morgan定律只成立了一半。其原因是这些定律基本上均是以真假的正负两极为基础的,现在从两极转为三极,它们就失去了存在的基础。这里对两极对立的概念进一步模糊了,主要表现在非运算“”上,该运算不是以U为中心的对称,而是真假之间的定向循环运动,它使三个真值的作用和地位向
117、平等的方向迈进了一步。透轨拜菌俱史眷摩芦痰君疮副叠赵溅救沪苏堕库洼释狐帘革短孺掸丘哪办四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第四节 多值逻辑与模糊逻辑四、多值逻辑模糊化1、将三值逻辑推广到任意的n值逻辑(n3),甚至任意的无穷多值逻辑或不可数多值逻辑。 构成模糊命题逻辑系统2、引进模糊度量和模糊谓词 从模糊命题逻辑过渡到模糊谓词逻辑3、使模糊变量和模糊谓词取值真正模糊化控淫奶诀争燕固逆辕歧枷增杏在挚孩锁害蔷笼芯哟声绵岂章泻皿它谍盆舟四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第四节 多值逻辑与模糊逻辑五、模糊逻辑模糊:不精确Zadah -Fuzzy Set六、算子模糊逻辑
118、 把程度词看成作用于谓词符号的算子,把这种算子加入到模糊逻辑中,构成算子模糊逻辑。具体地,程度词表示成一个数值,如:0.9(乌鸦都是黑的)。一般形如P,表示命题P在程度上是可信的隧捉甘蒂套闸茹后哺搏况菲僚拒诽隶竞念毡卢汤煞教积坦占甜龟蓉翼残婪四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第四节 多值逻辑与模糊逻辑七、模糊逻辑及其推广应用1、模糊数学 模糊图论、模糊微分方程2、用模糊度代替可信度(专家系统)3、模糊数据库4、模糊模式识别5、模糊推理6、模糊规划与模糊决策7、模糊聚类分析8、模糊控制(家电)掉世肥阵硒喀胡昌磁征女窖卞噶嫁贝云词轩瞎鸡拈掳倪鹏锑窍烃女凰关谦四章人工智能逻辑四章人
119、工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑一、归纳与演绎 正如分析和综合一样,归纳与演绎必然相互关联,要注意二者的相互联系和相互补充。颖厄眼侗青任茸豺赣星置扇双赃衫版们踊稗婿逃初佣葵成广伟兑沛舵绦鸥四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑二、经典归纳方法1、归纳 归纳是科学方法的基础,它能使人们对个别事物的认识上升为对一般事物和客观规律的认识。2、枚举归纳法 枚举局限:对客观事物和现象的简单罗列会导致草率的归纳和错误的结论。黍按岁以眺巳诲奶往堑辰志郝突茅返帮梗赴航氢梆洛轨搞瓣跃堵俞掷敝槽四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑二、经典
120、归纳方法3、例证表和例证比较法(Baccon) 注重将归纳和分析方法相结合。例证表主要有三种: a)存在表 记录“当现象x出现时存在另一种现象y”(xRy)。 b)缺乏表 记录“当现象x出现时另一种现象y不存在”(xRy)。 c)比较表 记录“当现象x由于条件不同而发生变化时,现象y也随之发生变化”,意在找出x和y两种现象变化之间的依赖关系。 屯浪孟怪始善棘蜒带查城尖属涤给骸赡逮茧间率篡书查咽脯募趴朵馅俱炬四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑二、经典归纳方法4、Mill五法 Mill提出通过分析事件发生的条件来确定因果关系,有五种方法。 A)契合法(也称求同法)
121、 识别必要条件。 给定两个互不相交的事件集合A和B,寻找这样的条件C,它在A中每一个事件发生前成立,但不一定在B中所有事件发生前成立。这样的条件C被定义为A中事件发生的必要条件。避西梆咐攘卉监滨崖碎汰睦央胸般鹃趁扦碍牺贵寞遵跋唆晓白磅等炒壁仅四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑二、经典归纳方法4、Mill五法 A)契合法(也称求同法) 注:1)找必要条件时往往要通过分析多个可能的条件,并排除不合适的候选者后才能得到。 2)必要条件往往不是很简单地就能识别,有时需要对具体条件加以抽象,且这种抽象不宜过分,以能说明问题为准则。 3)必要条件可能不止一个,是一复合条件
122、组合。仔砒楚逾氢棚闪靳峡垣彰涡踞宰闭舟瀑诽京棱拽揽辈宏钞零痰众韦瞧辰胜四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑二、经典归纳方法4、Mill五法 B)差异法 识别某个特定事件发生的原因。 给定一个事件e和一个事件集合A,e发生前的条件有许多和A中所有事件发生前的条件一样。寻找这样的条件C,它在e发生前成立,但不在A中任何事件发生前成立。C被定义为特定事件e发生的一个条件。迢唬遏轻源瘩稚卤拉孽倒岳日司蘑柔烂黔臃瘸奇闲超柿瞧柞需蕴柞磊泛肤四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑二、经典归纳方法4、Mill五法 B)差异法 注:1)由于差异法是对
123、特定事件发生原因的判定,所找到的原因很难说是充分条件或必要条件,笼统地说,说它是充分或必要条件均可,因为正是该特定事件且仅有该特定事件满足此条件。但实际上,它只是相对于集合eA是充要的,出了这个集合,它可以即不是必要的,也不是充分的。 巧霖牙翰啪脚氯剐粤瞳边舆颅碟瑶缀契脏帅姆惦廖姥子条甜纽养盆粹房接四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑二、经典归纳方法4、Mill五法 B)差异法 注:2)差异法要求e和A中事件之间除了一个条件不一样外,其它条件均一样。这个不一样的条件有时不易确定,有时还不唯一。若不唯一,则最好先构造一个和e同类的事件集合E,然后用契合法查找其中哪
124、些条件是必要的。讥兄闹酗严追蛊郭抵锅划涡昌跌侦膘留赌倘伯丑哎迟谁谋欺橙罕痪囊留婴四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑二、经典归纳方法4、Mill五法 C)契合求差法(求同求异并用法或同异法) 识别某类事件发生的特殊原因。 给定两个事件集合A和B,寻找这样的条件C,它在A类事件发生前均成立,而在B类事件发生前均不成立。C被定义为A类事件发生的原因。注:1)契合求差可经过三个步骤: (1)运用契合法,找出A组事件的共同前提AC; (2)运用契合法,找出B组事件的共同前提BC; (3)AC-BC就是A组事件发生的原因。帘欣跪逛末亚碘浪箕篱股蹋升撑杂檀做弱下愚诊逮丘必应
125、故芦息玛烁像旋四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑二、经典归纳方法4、Mill五法 C)契合求差法(求同求异并用法或同异法) 注:2这里已对差异法作了扩充。从寻找一个特定事件e发生的原因推广为寻找一个特定事件类发生的原因。寇辣逞束磋亚间岭障灭缓腕顿立瘦咬杯鳃硫媚澜戒荒绥仅技钧双佑淄耻惶四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑二、经典归纳方法4、Mill五法 D)共变法 通过观察两个客观事物的变化之间的相关性而找出因果关系。若当某个客观事物变化时,另一客观事物以某种规律跟着变化,则前者定义为后者的原因,后者定义为前者的结果。 注:1)共
126、变法是一个动态的方法,包含着对客观条件变化的分析。 2)利用共变法可分析那些关系密切而难以完全分开的复杂现象,以及客观条件随时间而变化的现象。予坎诚鲸撰窿闸请葬绥阶苔裂掺摇婚斌蜒淄曙哦还拟扼沾瞧忠稻部妥撂羹四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑二、经典归纳方法4、Mill五法 D)共变法 注:3)客观条件的变化可用数量关系加以描述。 4)共变法有助于引进数学方法,用数学公式来描述客观条件变化的函数依赖关系,使之精确化。 5)客观现象之间的各种依赖关系有一个范围。堰芝珐掀别釜皇喷桨洲吏邢窝吝围卡凹榴同笋莱精舰佰淆购脑区淹秽涩牲四章人工智能逻辑四章人工智能逻辑第四章
127、人工智能逻辑第五节 归纳逻辑二、经典归纳方法4、Mill五法 E)剩余法 也是识别某个特定事件发生的原因。 设A为事件集合,B是A中各事件发生前的条件集合。将A分为两个部分:A=A1A2,A1A2=。若B也可分为两个部分: B=B1B2,B1B2=,使B1是A1的充分条件,则一定存在B2B2,使得B2是A2的必要条件。连楚搬钡锚勾陪舵妙娱鞋铺滔肮孝富婆食眨泉郑先寄喇恢讽跪悼欺谎碎克四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑二、经典归纳方法5、其它归纳法 A)逆向契合法 识别充分条件。 B)双重契合法 识别充要条件。 先执行契合法,找出必要条件;再执行拟向契合法,以检查
128、此条件是否也是充分条件。 欲十秉刑龟徐疆犊瞅止亚贬沽山通啦闪帕坦晨毋撬擦着蔓另挟韧喳逾叫彤四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑二、经典归纳方法5、其它归纳法 C)同异合用法 识别某个特定事件发生的充要条件。 先用差异法,找出该特定事件发生的充分条件C,后再搜集一组该特定事件的同类事件,使用契合法以证明C是此类事件的必要条件。聚洱软蕊诬卯胸甚径殃寿课艇凌九肮兹成丁修矩北赏衫肌姜戍描贯河筐履四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑三、归纳推理的合理性解释 概率方法1、频率方法解释古典概率方法 用概率理论来论证归纳推理的合理性。从实用主义观
129、点出发,认为得到正确结论仅是归纳法合理性的充分条件,而不是必要条件。假设要归纳的定律是ab,现构造一个无穷序列ei,对每个i,条件a均在ei中成立,则一般说来,在某些ei中有事件b发生,而在另一些ei中则没有。构造分数: 若当N时,aN,则归纳结论“当条件a成立时事件b出现的可能性是”是合理的,称为概率。煞杜玫塘辣力瞥压扩谅宾扦挚肺秃貉催徘脊勋弧氏娜弗隐醇阔藉尸帘狈券四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑三、归纳推理的合理性解释2、逻辑方法-使用可信度方法 将形式逻辑的演绎方法用于归纳法(纯语法演绎推理)。 A)定义一形式系统 P569 憎蒸噬寨嚎长供囊喘社迭础筋
130、纬艳长垦琴镁咳阐报奔谜酋蝉锐傍轩骑淑劫四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑三、归纳推理的合理性解释2、逻辑方法使用可信度方法B)定义概率(可信度) 函数c(h,e)表示在证据e下h的可信度,即概率。令S(h,e)为使h和e均取真值的状态集合,S(e)为使e取真值的状态集合,若对每个状态集合S,均能给定一个测度m(S),则可定义c(h,e)=m(S(h,e)/m(S(e)且有c(hh,e)=c(h,e)*c(h,e.h)由c(hh,e)=0推出c(hh,e)=c(h,e)+c(h,e)0c(h,e) 1注:这里状态相当于可能世界亥摄镊膘痛瞬眨证酱区缺猎霓嫌握谓扇妖
131、赎编腋镀俄诅盅奶镀拽泉格敌辈四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑三、归纳推理的合理性解释3、Bayes主观解释主观(先验)概率 认为概率是个人的一种合理置信度。 合理置信度应满足概率公理: (1)对p的置信度和对非p的置信度之和为1 (2)在已知q为真的前提下,对p的置信度和对非p的置信度之和为1 (3)对p和q同时成立的置信度等于对p的置信度乘以已知p为真时对q的置信度 (4)对p和q同时成立的置信度加上对p和非q同时成立的置信度等于对p的置信度缕埔服坑恩猜埃酷省欠不刀犁菊浅怕更砧禾屈蝶级捷藏绦翻枕当嚎词娠蛀四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑
132、第五节 归纳逻辑三、归纳推理的合理性解释3、Bayes主观解释注:(1)在符合概率公理的前提下任何一种置信度分配均同其它在相同条件下的置信度分配一样合理,也就是说,若只要求符合概率公理,则置信度的取值是相当任意的。这就是Bayes的基本观点。 (2)置信度是一种概率。概率分为先验概率、条件概率和后验概率。先验概率是在没有任何证据的情况下,一个人对某事件发生的可能性有他自己的置信度,称为这个人对该事件赋予的先验概率。待到搜集各种(包括正反两方面)证据之后,先验概率被修正为条件概率,这最后得到的概率就是后验概率。夸钉耻链蕾穿主雨碎学扒琅谚镍警浇傲掩芒猫滁炭踏防辆万罪贮婚房葱夜四章人工智能逻辑四章人
133、工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑三、归纳的概率方法3、Bayes主观解释注:(3)Bayes学派可分为逻辑Bayes学派、经验Bayes学派和主观Bayes学派。共同点是承认先验概率的存在,不同之处是对先验概率的解释。逻辑学派认为先验概率是一种逻辑量,体现在测度函数上,它是纯形式的,并不反映客观世界的现实。经验学派认为先验概率是使用某种归纳方法从经验数据中总结出来的,比较接近频率派。主观学派认为先验概率纯粹是个人的信念,在同一系统中,各人对同一事件所持的先验概率可以完全不一样,它们只需要服从最基本的概率规则。红驰不监洪驻霜隧瓢膜捞棘框间寻肿赐馋肿寒哀堑喻怀衬晰组异名勾重要四章人工
134、智能逻辑四章人工智能逻辑第四章 人工智能逻辑第五节 归纳逻辑三、归纳的概率方法3、Bayes主观解释注:(4)主观Bayes主义常用于需要决策的场合,并发展为Bayes决策理论,如在知识工程和专家系统中宜选择主观Bayes主义作为不精确推理的模型。(5)在机器学习中的归纳方法需要从实际数据中总结出客观规律,最合适的是频率解释。腥缘遍引月崩要刮片墒俐墙雀窿睛飞赶客专毒拈草涎漳顽绅智隧掩庆今绅四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理一、约束推理1、约束 a)约束 一个包含若干变量的关系表达式,用以表达这些变量所必须满足的条件。 B)约束问题求解 包含一组变量与一组变量
135、间的约束。一般地说,变量表示领域参数,每个变量均有一个固定的值域。约束满足问题的目标就是找到所有变量的一个(或多个)的赋值,使所有约束均能满足。焚疵惕孟志攒争莫讥嘿晾马献赡寐诌荡鲁恐他涵肄莽阴聪眉扦鲤到片氮佰四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理一、约束推理2、约束推理 主要集中在两个方面:约束搜索与约束语言。 a)约束搜索 研究有限域上的约束满足。主要方法有:回溯法、约束传播、智能回溯(剪枝)与真值维护、可变次序例示和局部修正法。 B)约束语言 如约束逻辑程序设计语言。其目标是将约束满足技术与逻辑程序设计结合起来,基本上是在Prolog的基础上引入约束传播机制
136、(主要是弧一致性技术),以提高搜索效率,增强表达能力。焦面每体窘浇马藉体积裔勃汹博罢询蹈嫉骗陵翔约双烤纂榔癣无放镇黑皖四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理二、定性推理1、定性推理基本含义 从现实物理系统结构的定性(非严格的定量)描述出发,导出行为描述,以便预测系统的行为并给出原因解释。虏兜毛蹲枷珐侮棱圭窗凳将眠安氛谋豹行瞻序孙晨朽忧锥尚谜刷姚惋滁挎四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理二、定性推理2、定性推理的一般方法 a)ENVISION方法 -de Kleer和Brown 直接在物理系统的各个关键部位定义有关的物理量,然后建
137、立这些物理量之间的定性关系,再进行推理。 B)QSIM方法 -Kuipers 将定性推理过程分为建模和仿真两个步骤。首先,将现实的物理系统离散化,用所谓的进程和视图加以描述,然后将它写成一种特殊的微分方程,称为定性微分方程,最后,用此定性微分方程仿真。症策嘱桅崭媒尽豁乌耕闸宋漓鼠咙镶铝眷鹊搂弥品材署西餐稳喧街函后甥四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理二、定性推理2、定性推理的一般方法 c)定性进程方法 -Forbus 以因果关系为基础,从时间演变来把握系统的特性及其发展过程,基本元素是事件、进程、发展阶段、历史等等。 注:与空间结构的描述方法相比,定性进程方法
138、提供了解决著名的框架问题的一种较好途径。 D)符号代数方法秒选晌吩董侣了坤奠囱越栅牌楼纸匈遮位呸讣萄架账捏洞笆为北翼赂隘丘四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理二、定性推理3、定性演算 将普通演算中出现的具体的量抽象化,归入有限的几个类,就得到了定性演算。如,将实数分为三类:0、=0、0。简里爽奈软衅谆敞迂予济佯曝零氟恢胀绩边筏搜漾驾氛团救喉批敝华天嫁四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理二、定性推理4、基于状态的推理 是定性演算的一个直接应用。在现实世界中,物理系统的状态是连续变化的,往往可用微分方程来描述。为了应用定性演算,就
139、需要将相应微分方程定性化。一般遵循的原则是:将各级导数作为独立的定性变量,将常数抽象化为定性常数:+1,-1或0,保留导数前的正负号。 用n个定性变量描述一个物理系统P,每个定性变量的取值在+1,-1,0之中,对这n个定性变量的每一组合法的赋值构成P的一个状态。状态之间的变迁遵循一定的规则。欧卵住倍筐碴朋坯框阻邱滑月蓖开紧覆困夺卿江吧丸蜡甭田行侧章芹种鸭四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理三、不精确推理1、导致不精确推理的原因 a)很多原因导致同一结果,推理不能精确 b)推理所需的信息不完备,只能根据种种迹象作出判断 c)背景知识不足 d)信息描述模糊 e)信
140、息中含有噪声 f)规则是模糊的 g)推理能力不足 h)解题方案不唯一,只好选择主观上认为相对较优的方案姨钳贤咸贪掏鲁呜高段约釜琼狞阳砖周欧榜萤锋锨壁践哮被苟又刮泣诸蕊四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理三、不精确推理1、导致不精确推理的原因 注:1)在人类的知识和思维行为中,精确性只是相对的,不精确性才是绝对的。 2)概率推理是一种常用的不精确推理钝酿尚橇惜及撵颤恼扶毅焰忘紫货德碟骨刺换踞帽凿彩蕾缕赦资翔脆摩掺四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理三、不精确推理2、Bayes概率推理 a)基本量 1)假设H的先验概率P(H) 2
141、)在证据e为真时假设H的条件概率P(H|e) 注:这里,先验概率是给定的,条件概率的一部分也是给定的。 B)Bayes概率服从的公理 1) 0=P(H)=1 2) P(已知为真的假设)=1 3) P(H或G)=P(H)+P(G) 其中H和G互斥怔痹七谣乎瓢高孝栽瘁龄躺珠衫聚谓融裹搜溢腿电淀韩炸嘻彰露冠庆庇宿四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理三、不精确推理2、Bayes概率推理 c)条件概率公式 1)P(H&G)=P(H|G)*P(G)=P(G|H)*P(H) 2)P(H|G)=P(H) P(G|H)=P(G) P(H&G)=P(H)*P(G) 当H和G互不相
142、关(互相独立)时 3)P(H)=P(H&G)+P(H&G) P(H)= (Gi是各种可能性) 4)P(H|G)=P(G|H)*P(H)/P(G) P(Hi|G)=P(G|Hi)*P(Hi)/蹈咆琉狡寺帧躯化囊炕异靖丁台乍坛臀若哼施兔回朗苫既恍登欣蛹辽倒沦四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理三、不精确推理2、Bayes概率推理 d)几率 PROSPECTOR H的几率O(H)=P(H)/P(H) O(H|E)=P(H|E)/P(H) e)转换因子 LS(G|H)=P(G|H)/P(G|H) 充分因子 LN(G|H)=LS(G|H) 必要因子设华狡玉壹盼拈唁臼窝系
143、簿嘶作狗治葬洲队征派绅泳协落册您腥帖困丽哨四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理三、不精确推理3、可信度方法 MYCIN a)基本量 在给定证据下,对某个假设的肯定(MB)和否定程度(MD)。 MB(h|e)=a的含义是:证据e的出现使假设h的可信度增加了数量a。 MD(h|e)=b的含义是:证据e的出现使假设h的不可信度增加了数量b。 注:1)a,b不能同时大于0,因为同一个证据不可能既增加某假设的可信度,又增加其不可信度。 渐秋胁骑蔑桌拼撩埋男坊柞矣粘打嫩肖娘妄己兜愤痔研纽仍揩隶曹只孤蛙四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理三
144、、不精确推理3、可信度方法 MYCIN a)基本量 注:2)原则上MB(h|e)和MD(h|e)的值应由专家根据经验给出。 3)MB(h|e)=1 若P(h)=1 MB(h|e)=(max(P(h|e),P(h)-P(h)/P(h) 若P(h)1 MD(h|e)=1 若P(h)=1 MD(h|e)=(P(h)-min(P(h|e),P(h)/P(h) 4)恒有 0=MB(h|e),MD(h|e)=1 悸庞速赏欧禁尘着松师蝴糕韧溪挨办谜节越续镰隘翁宙收琼诉韭雕沾幸滦四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理三、不精确推理3、可信度方法 MYCIN b)复合证据处理 1
145、)可能是增量地获得的复合证据 MB(h|e1e2)=0 若MD(h|e1e2)=1 MB(h|e1e2)=MB(h|e1)+MB(h|e2)(1-MB(h|e1)其它 MD(h|e1e2)=0 若MB(h|e1e2)=1MD(h|e1e2)=MD(h|e1)+MD(h|e2)(1-MD(h|e1)其它冈掠致门儒森支援膜绿麓搭服忙口歹讼斩着渭渤耕狈咖贞碎猖并凛近尤啊四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理三、不精确推理3、可信度方法 MYCIN b)复合证据处理 2)包含未知证据的复合证据 MB(h|e1e2)=MB(h|e1) MD(h|e1e2)=MD(h|e1
146、) 其中e2为未知真假的证据 3)两个假设的合取 MB(h1h2|e)=min(MB(h1|e),MB(h2|e) MD(h1h2|e)=min(MD(h1|e),MD(h2|e)儒撂碘东函扛桩销乔地粤厌瘤狭搽垒烦骄嚣辗勺啮褥昂移客蝗澈予岸屿蔽四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理三、不精确推理3、可信度方法 MYCIN b)复合证据处理 3)两个假设的析取 MB(h1h2|e)=max(MB(h1|e),MB(h2|e) MD(h1h2|e)=max(MD(h1|e),MD(h2|e) 注:证据的复合规则满足交换律、结合律,假设的复合规则满足交换律、结合律和分
147、配率。玩搽型掇悯掷痒耻右眠砾鹃川溃糟斤泞厄蔚屡瑰啄络傈伺侥济稠炕隋爆烷四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理三、不精确推理3、可信度方法 MYCIN c)可信度因子CF(Confidence Factor) CF(h|e)=MB(h|e)-MD(h|e) 注:1) -1=CF(h|e)0); e-=e1 e2 . em为所有不利于假设h的证据之和(MD(h|ei)0) 3)C(h|e)+CF(h|e)=0 4)CF(h|e)=a表示:在证据e下,假设h为真的可信度是a,它综合了MB和MD两方面的信息。片项蔚舆搏拎整济仕居钧疟樟锰沛浆暗牙仲柑倪汲涨胰志操纬蕾芹忧腿
148、稻四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理三、不精确推理3、可信度方法 MYCIN c)可信度因子CF(Confidence Factor) CF(h|e)=MB(h|e)-MD(h|e) 注:5)CF(x)表示原始证据x的可信度,或表示推理进行到某一步时,假设x的当前可信度。谓输迭捆刽扁煽褂忙枚随届卸屠天桐泞淋童箕浴爵躲趾坷锗怎桑烛怎龚缴四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理三、不精确推理3、可信度方法 MYCIN d)EMYCIN中的CF计算 CF=(MB-MD)/(1-min(MB,MD) CF(h|e1e2)=X+Y(1-X
149、) 若X,Y均大于0 CF(h|e1e2)=(X+Y)/(1-min(X,Y) 若X,Y有一小于0 CF(h|e1e2)=X+Y(1+X) 若X,Y均小于0 其中X=CF(h|e1), Y=CF(h|e2)儿钝淤锌涡监刻色禾张应遁科黍古晤束投帕侩刨匀躯氏闺砷碟篇窝瓜狰衬四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非经典推理三、不精确推理4、模糊推理 a)确定模糊集隶属函数的方法 1)民意测验 2)比较法 3)借鉴概率分布的思想 b)模糊关系 c)模糊推理拖笆推器朝押剁采捅商锡虽寇拢大屹叛施执物镐她椿闸马午悔设屑勃赵写四章人工智能逻辑四章人工智能逻辑第四章 人工智能逻辑第六节 非
150、经典推理四、基于范例的推理(Case-Based Reasoning, CBR) 由当前所面临的问题或情况(目标范例)的提示,而获得记忆中的问题或情况求解的一种策略,称为基于范例的推理。 注:1)基于范例的推理主要是为了对过去的求解结果进行复用,以提高对新问题的求解效率。 2)相应地,可有基于范例的学习。桓蛙颤掠漓工笺醛耸平但荐喻贿颠余酝笋沤瘴降较矩漏它佬孜潮诊童遂挎四章人工智能逻辑四章人工智能逻辑思考题逻辑在人工智能中的主要作用是什么?试举例说明。如何使用逻辑方法刻画人们的认知系统?试举例说明。如何使用逻辑方法描述时序?如何实现相应的推理?如何使用逻辑方法描述常识?其基本特征、基本思想和具体实现机制是什么?归纳逻辑方法有哪些?如何通过概率方法解释归纳逻辑的有效性?如何在应用中使用归纳逻辑?可信度方法的基本思想和基本机制是什么?灾碉扮婆茅嘱戊沤鲁装号似垦糟脐弦掩请纶厨溃棒疟喇皇讼械醚渔孪佯雁四章人工智能逻辑四章人工智能逻辑