人工智能原理第3章非经典逻辑

人工智能原理第3章非经典逻辑本章内容3.1非经典逻辑简介3.2模态逻辑3.3知道逻辑和信念逻辑3.4多值逻辑3.5模糊逻辑参考书目第3章非经典逻辑3.1非经典逻辑简介不同逻辑的约定经典逻辑和非经典逻辑的区别广义模态逻辑第3章非经典逻辑4逻辑语言的约定•如前一章所示,逻辑作为一种知识表示,可称之为形式化的语言.不同的逻辑在表示客观世界时有各自的特点(约定)•若干逻辑语言的约定第3章非经典逻辑语言本体论约定(世界中存在的)认识论约定(智能体对事实的相信)命题逻辑一阶逻辑时序逻辑概率理论模糊逻辑事实事实、对象、关系事实、对象、关系、时间事实事实、真实度[0,1]真/假/未知(扩展)真/假/未知真/假/未知信度[0,1]已知区间值5经典逻辑与非经典逻辑的区别(1)•人工智能研究把逻辑作为重现智能的手段，其应用是广泛而深入的•经典逻辑（命题逻辑和一阶逻辑）在长期的实践中逐渐暴露出对许多应用领域力不从心，促使新的逻辑流派不断涌现•经典逻辑和非经典逻辑之间的主要区别：(1)演绎还是归纳？Bacon等倡导的归纳法打破了演绎方法的一统天下，归纳逻辑在AI中也有重要地位第3章非经典逻辑6经典逻辑与非经典逻辑的区别(2)(2)二值还是多值？经典的二值逻辑描述能力不足，是对客观世界的过分简单的抽象，提出多值和模糊逻辑(3)是否遵守传统数理逻辑运算法则？如排中律、否定之否定、狄摩根律甚至恒等律在一些非经典逻辑（多值逻辑）中不再成立(4)是否引进额外算子？经典逻辑只能回答绝对是非判断的问题，但面临“可能、必然、应该”等问题时就显得无能为力，需要引入额外的模态算子，即模态逻辑第3章非经典逻辑7经典逻辑与非经典逻辑的区别(3)(5)单调还是非单调？经典逻辑的信念是已知的事实（定理）是充分可信的，不会随着新事实的发现而使旧事实变假。所谓单调的。实际上这不符合客观认识规律，因为新的事实推翻旧的真理的情况时常发生。这是认识的非单调性•经典逻辑是演绎的、二值的、单调的，而不遵守其中的一个原则，就是非经典的•非经典逻辑缺少统一的理论体系，各种方法有较大的区别第3章非经典逻辑8非经典逻辑与模态逻辑•我们选择一些具有逻辑形式、采用经典逻辑语法框架的非经典逻辑加以介绍:•部分广义模态逻辑包括模态逻辑、知道逻辑、信念逻辑•多值逻辑•模糊逻辑•模态逻辑是在经典逻辑的框架下引入模态算子（也叫模态词），模态词的不同解释导致不同的模态逻辑第3章非经典逻辑9广义模态逻辑(1)•相对于“可能/必然”的解释，其他对模态词的不同解释，就得到了广义模态逻辑。•较老的有：•真理论模态逻辑关于“必然”的模态逻辑，模态算子的解释：“必然、可能”，标准的模态逻辑•认识论模态逻辑关于“知道”的模态逻辑，模态算子的解释：“知道、认可”，知道逻辑•道义论模态逻辑关于“应该”的模态逻辑，模态算子的解释：“应该、允许”，信念逻辑第3章非经典逻辑10广义模态逻辑(2)•较新的有：•经验论模态逻辑关于经验的模态逻辑，模态词：“一贯、偶然、经验地、有先例地”•时序逻辑关于时间次序(状态演变次序)的模态逻辑，模态词：“永远、将会、下个、直到”第3章非经典逻辑3.2模态逻辑模态逻辑的语法命题模态逻辑系统/T系统及其性质可能世界模态逻辑的语义/模态逻辑的模型标准模型及模型中关系第3章非经典逻辑12模态逻辑的提出•实际上，模态逻辑的历史和经典逻辑一样长，最先由Aristotle提出•波斯海战问题：明天波斯和雅典将发生海战•对于明天才知道真假的命题，经典逻辑无法回答是或否•1918年美国Lewis在研究实质蕴涵悖论时重新提出模态逻辑•根源：p→q经典定义：p→q等价于¬p∨q•Lewis提出用严格蕴涵来定义：p→q等价于“不可能(p∧¬q)”，引出了“可能”问题第3章非经典逻辑13模态逻辑的算子•模态逻辑的语法和系统•模态算子•必然算子：□A称为必然A•可能算子：◇A称为可能A•□﹁(A→B)表示A必然不能推出B；同样﹁◇(A→B)表示A不可能推出B第3章非经典逻辑14模态逻辑的合式公式•模态逻辑的合式公式：(1)任何一个一阶谓词演算（命题演算）的合式公式都是模态逻辑的合式公式；(2)若A是模态逻辑的合式公式，则□A是合式公式；(3)若A是模态逻辑的合式公式，则◇A是合式公式；(4)若A和B是模态逻辑的合式公式，﹁A，A∨B，A∧B，A→B，A≡B(←→)都是合式公式；(5)除此以外再无别的合式公式。第3章非经典逻辑15命题模态逻辑•命题模态逻辑系统•定义：一组称为公理的命题模态合式公式和一组推导规则取如下形式：•且该合式公式组在此推导规则下封闭，则这些公理和推导规则构成一个命题模态逻辑系统•命题模态逻辑系统包括T系统，也称NSK(正规系统)，以及Lewis引入的5个模态逻辑系统S1～S5第3章非经典逻辑AAAAn...2116T系统(1)•T系统的定义•T系统中逻辑运算定义：3个基本逻辑联结词(运算符)为﹁、∨、□，其他逻辑运算符为：(1)A→B定义为﹁A∨B(2)A∧B定义为﹁(﹁A∨﹁B)(3)A≡B定义为(A→B)∧(B→A)(4)◇A定义为﹁□﹁A第3章非经典逻辑17T系统(2)•引入严格蕴含符和严格等价符=，并规定：若A、B为合式公式，则AB也是合式公式；若A、B为合式公式，则A=B也是合式公式.即•(5)AB定义为□(A→B)(6)A=B定义为(AB)∧(BA)第3章非经典逻辑18T系统(3)•T系统的公理系统(与∨、□、→有关)(1)T1：(A∨A)→A(2)T2：A→A∨B(3)T3：A∨B→B∨A(4)T4：(A→B)→((C∨A)→(C∨B))(5)T5：□A→A(6)T6：□(A→B)→(□A→□B)(对于NSK系统来说，则加上所有永真式)第3章非经典逻辑19T系统(4)•T系统的推导规则(1)代入规则：若p是A中变量，A为合式公式，且能被T公理系统证明(记作├A)，B为任一合式公式，用B代入A中的p得到A’，则有├A’(2)分离规则：由├A→B和├A，得├B(3)必然规则：由├A得├□A(NSK中只把(2)列为推导规则，公理系统亦不同，但等价)第3章非经典逻辑20T系统(5)•T系统是最弱的命题模态系统，即T系统中成立的公理和推导规则，在其他命题模态系统中也成立•T系统的性质：(共17条)(1)A→◇A(2)(A=B)→(□A≡□B)(3)□(A∧B)≡(□A∧□B)(4)□(A≡B)≡(A=B)第3章非经典逻辑21T系统(6)(5)□A≡﹁◇﹁A(6)﹁◇(A∨B)≡(﹁◇A∧﹁◇B)(7)◇(A∨B)≡(◇A∨◇B)(8)(AB)→(◇A→◇B)(9)(□A∨□B)→□(A∨B)(10)◇(A∧B)→(◇A∧◇B)(11)(﹁AA)≡□A(12)(A﹁A)≡□﹁A第3章非经典逻辑22T系统(7)(13)((AB)∨(﹁AB))≡□B(14)((AB)∧(A﹁B))≡□﹁B(15)□A→(BA)(16)□﹁A→(AB)(17)□A→(◇B→◇(A∧B))第3章非经典逻辑23例子：性质的证明(1)•选证其中2条作为练习•例1(1)之证明：A→◇A•证明过程(1)□﹁A→﹁A(公理T5及代入规则)(2)﹁□﹁A∨﹁A(定义)(3)﹁A∨﹁□﹁A(公理T3)(4)A→◇A(定义及◇定义)第3章非经典逻辑24•例2(9)之证明(□A∨□B)→□(A∨B)(1)├□A∨□B(前提)(2)□A→A(公理T5)(3)□B→B(公理T5)(4)A→A∨B(公理T2)(5)B→A∨B(公理T2及T3)(6)├□A→A∨B(由(2)、(4))(7)├□B→A∨B(由(3)、(5))(8)├A∨B(推导公理(A→C,B→C,A∨B)→C)(9)├□(A∨B)(必然规则)第3章非经典逻辑例子：性质的证明(2)25可能世界和模态逻辑语义•可能世界和模态逻辑的语义•可能世界：模态逻辑的基本思想是在经典逻辑当中引入可能和必然2个模态算子•Leibnitz给出了最初的可能世界的适当解释：世界不只一个，除了现实世界以外，还有许多可能世界；其命题的真假取决于在哪个世界中对它进行考察,即真假(真理)标准随可能世界而转移•在给定的可能世界上定义模态逻辑的语义第3章非经典逻辑26模态逻辑的模型定义•模态命题逻辑的语义：取决于它的模型•模态逻辑的模型：三元组M=(W，R，V)称为模态逻辑的一个模型，其中W是可能世界的非空集合，V是对W中各个可能世界的真值指派(赋值映射：对每个合式公式证明其在每个可能世界中的真假值)，R是附加于此模型之上的其他关系，可以为空第3章非经典逻辑27模态逻辑的真值指派•对可能世界的真值指派应满足以下条件：(1)TRUE在所有可能世界中为真；(2)FALSE在所有可能世界中为假；(3)A在可能世界中为真，当且仅当﹁A可能世界中为假；(4)A∨B、A∧B、A→B、A≡B在可能世界中为真的定义同普通逻辑的定义。•注意：□、◇在何时为真随着模型的真值指派而定第3章非经典逻辑28两种模态逻辑模型•公式A在模型M的可能世界中为真，记作|=MA，(M可省略)；如果在所有可能世界中为真，则记作|=MA。•存在多种不同的语义模型•Leibnitz模型•标准模型第3章非经典逻辑29Leibnitz模型(1)•Leibnitz模型的定义：如果规定(1)|=M□A当且仅当|=MA(所有可能世界)；(2)|=M◇A当且仅当W，使得|=MA，M=(W,V,R)(可以简记为M)，则此模型称为Leibnitz模型。•在Leibnitz模型中，下列若干公式成立(性质，一个定理)：•第1组：□A→A◇A≡□◇A第3章非经典逻辑30Leibnitz模型(2)•第2组：□A≡﹁◇﹁A◇A≡﹁□﹁A◇﹁A≡﹁□A□﹁A≡﹁◇A•第2组公式在模态逻辑的所有模型中均成立，而其余两组未必•第3组：(□A∨□B)→□(A∨B)(□A∧□B)≡□(A∧B)◇(A∧B)→(◇A∧◇B)(◇A∨◇B)≡◇(A∨B)□(A→B)→(□A→□B)第3章非经典逻辑31Leibnitz模型性质的证明(1)•下面给出对第1组公式的证明，其他两组可依此类推•第1组公式：□A→A，◇A≡□◇A•证明：•对于第1个公式，该式左边表示对所有可能世界，皆有|=A成立，右边表示对于一个未显式说明的可能世界，|=A成立，故可从左边推到右边。第3章非经典逻辑32Leibnitz模型性质的证明(2)•对于第2个公式，左边表示存在一个可能世界，有|=A成立；右边表示对于所有皆有|=M◇A。根据定义，其含义为，使|=MA成立；因为与无关，所以“对于所有”可去掉。因为都是表示存在一个可能世界，所以用或符号都没有关系。因此，左右表示是相同的(P→P)，即知从左可推到右。•反过来，利用性质1，可证从右到左。☆第3章非经典逻辑33标准模型(1)•标准模型的定义:•若R定义了模型M=(W,R,V)中W×W上的一个二元关系，且定义模态算子为：(1)|=M□A当且仅当对每个使RW成立的有|=MβA成立；(2)|=M◇A当且仅当W满足关系R，有|=MβA成立则M称为标准模型第3章非经典逻辑34标准模型(2)•这里R理解为可达到关系，即:•□A为真，当且仅当从目前所在的可能世界出发，在能够到达的一切可能世界中，A皆为真；•◇A为真，当且仅当从目前所在的可能世界出发，能够到达某个可能世界，在此中A为真。第3章非经典逻辑35标准模型(3)•注意：此处未对R限定任何条件，因此在Leibnitz模型中成立的公式(定理)，此处不成立。•例如当R不具备自反性质时，□A→A不成立•例子:A表示享福，R父子关系，□A表示子孙享福，由于αRα不成立，所以本人未必A(即子孙享福未必本人享福)第3章非经典逻辑36标准模型(4)•[定理](1)|=M◇A≡|=M﹁□﹁A(2)|=M□A≡|=M﹁◇﹁A•证明：(1)|=M◇A等价于存在，R，使|=MA；等价于并非对于