高级人工智能逻辑、推理与知识课件.ppt

高级人工智能逻辑、推理与知识,2022/11/30,1/113,2022/11/30,2/117,命题逻辑一阶逻辑(一阶谓词演算）其他逻辑系统约束推理定性推理基于范例的推理知识及其表示,命题逻辑,什么是逻辑？简单地说，逻辑就是人们用以处理问题而抽象的一种思维规则或计算方法。 命题逻辑的关系表达直观、生动而简洁，它是一阶逻辑发展的前导和基础。把命题逻辑加以简单的形式化，就能扩展应用于一阶逻辑推理中。,2022/11/30,3/117,命题逻辑,1. 命题和个体 设有如下符号命名的语句： X：爱因斯坦是一位伟人。 Y：海水是甜的。 W：3+4=9 上述X、Y、Z都是陈述性语句，分别具有肯定(True)或否定(False)意义的真值，我们把它们都称之为命题。其中，诸如“爱因斯坦”，“海水”，数字“3”、“4”等，它们是命题中的行为中心对象，又称为个体。,2022/11/30,4/117,命题逻辑,定义3.1 命题(Proposition)，即具有真(T)假(F)意义的陈述性语句。,2022/11/30,5/117,注意： 命题一定是陈述性语句；如上述X、Y、W等。 例如，下面句子是陈述性语句吗？ 请勿吸烟。 昨晚你看足球联赛了吗？ 西湖好美呵！ 命题既可用自然语言(包括中、外文)形式表示，也可用大写的英文字符或字符串来命名。 命题反映了人脑进行思维的一种判断，可见命题表达自身就含有智能特性。,命题逻辑,2022/11/30,6/117,（1）个体是命题中的中心对象，通常由名词构成。个体可以是具体的人物、物体、一组数字、地名等，也可以是某个抽象的概念。例如，机器人、海棠花、理想、快乐、智能等均可作为个体。 （2）个体的取值范围称为个体域。个体域可以是有限的，也可以是无限的。,定义3.2 所谓个体，是指可以独立存在的某个事物。,命题逻辑,2. 谓词及变元,2022/11/30,7/117,为了对许多具有进步影响人物都使用形同X命题方式赞扬之，可使用一种类同数学函数的形式语言用含有变量字符或字符串的谓词来定义：表达为英文字符串形式： GIANT(x).其被赋予的汉语解释是： x是一位伟人。 把 GIANT(x)称为谓词（Predicate），其中GIANT ( )是谓词名；括号中的参量x叫做谓词的变元，又称之为项(item)。,GIANT( ),谓词名,谓词变元,命题逻辑,2022/11/30,8/117,这种由定义的谓词名、变元，共同构成了具有陈述性表达的形式化语句，称为谓词。一个谓词可以有n（其中n=0,1,2, ）个变元，并称之为n元谓词。 在谓词中，谓词名表达了语句中除主语个体之外的其余部分，常采用自然语言的谓语动作词根来表达；谓词的变元可在相应个体域集合中取值任意一个元素。,命题逻辑,2022/11/30,9/117,例3.1 假如定义英文字符串“OCITY(x) ” 设其含意为：x是一座历史名城。,解：这里x可以取值“西安” 真值为T；x取值“深圳” 真值为F。若取值“北京”则为T、“华盛顿”T、“野玫瑰”F、 “机器人” 为F等。 由上例可见，当使用特定的个体常量取代了谓词中的变元，该谓词就转换成为一个命题；反之，如果把命题中有独立结构的个体常量替换成变元参量，则又可把命题转换成为一个具有谓词结构的表达式了。,命题逻辑,3. 谓词的元和谓词的阶,2022/11/30,10/117,定义3.3 谓词中包含个体或变元的数目，称为谓词的元或谓词的目。例3.2 比较下列谓词或谓词形式的命题： LIKE(john，mary)； ROBOT(john)； ROBOT(mary)； ADDQ(x，y，z)。试解释具体含义，并指出它们各是几元谓词。解：上述谓词意即“机器人约翰喜欢玛丽”；和都只有一个个体，称为一元谓词；相应则称为二元谓词；表示为表达式“x+y=z”，其中包含有3个变元，故称为三元谓词。依此类推，可推出关于n元谓词的概念。 顺便指出：在多元谓词中，变元的排序很重要，一旦确定，就不可随意交换。,命题逻辑,2022/11/30,11/117,定义3.4 谓词表达形式中所包容相叠加的含义层次数数目，称为谓词的阶。例2-3 为了说明谓词的阶，我们来比较下列谓词形式的命题： LIFELESS(outer-stars)；外星球没有智能生命。 INCORRECT(lifeless(outer-stars)；说“外星球没有智能生命”是不确切的。解：在上述谓词形式的命题中，谓词只有一层含义，称为一阶谓词；谓词在前一层含义基础上，又增加了一层新意，共有二层含义。故把谓词称为二阶谓词。依此类推，可推出关于n阶谓词的概念。注意：在谓词逻辑演算中，最重要的有三大类：即：命题逻辑演算、 一阶谓词逻辑演算和二阶谓词演算。,命题逻辑,4. 命题与谓词逻辑的关系,2022/11/30,12/117,命题逻辑表示比较简单，只能表达具体固定的情况，命题是谓词逻辑特殊事例的生动描述，,谓词逻辑可以灵活表现多种或变化的情况；谓词表达是命题逻辑的抽象与推广。,总的看来，命题和谓词的知识表示形式可以相互转换，而谓词比命题有更强的表达能力。 显而易见，谓词是一种描述个体群之间的相互关系、性质及其逻辑结构的数学表示。人们把采用这种表示的运算，又称为谓词逻辑。 比较起来：命题逻辑演算太简单，只能解决具体容易的问题；二阶谓词演算又太复杂，以至迄今为止，尚未找到最根本有效的算法。 因此，在人工智能中，目前使用最多的还是一阶谓词逻辑演算。,一阶逻辑,命题或谓词逻辑推理演算，主要可利用连接词和量词，把单个的谓词组合成为谓词公式来完成。 基于命题和谓词逻辑可相互转换的特性，这里约定：对命题和谓词逻辑的相关公式表达、相关定理、定律的论证和推导等，不再加以严格区别。,2022/11/30,13/117,一阶逻辑,1. 连接词 (Connectives) 连接词共有五个： 符号“”称为“否定”(Negation)或补，表示“非”的连接关系。即当命题P为真时，则P 为假；反之，当命题P为假，则P 为真。 符号“”称为“合取”(Conjunction)，表示“与”(AND)或“同时”的关系。例如，PQ，读作“P与Q”。 符号“”称为“析取”(Disjunction)，它表示“或”(OR)的连接关系。例如，PQ，读作“P或Q”。,2022/11/30,14/117,一阶逻辑, 符号“”称为“条件”(Conditional)或者“蕴涵” (Implication)，它表示“如果，则”的定义关系。例如，在PQ的表达式中，表示了“如果P，则Q”的条件推导关系。这里，又称P为前件，表示条件的前提，称Q为后件，表示逻辑结论。 条件表达式有一个重要特性： 当前件P=F时，无论后件Q为何值(T或者F)，条件式PQ真值总是为T； 当前件P=T时，条件式PQ的真值总是与后件Q真值相同。 符号“”称为“双条件”(Biconditional)或者等价(Equivalence) 连接关系。例如，表达式PQ，读作“P当且仅当Q”。或者说它表示的含义为：P为真，当且仅当Q为真。,2022/11/30,15/117,一阶逻辑,2022/11/30,16/117,表3.1 连接词定义真值表,一阶逻辑,2. 量词 (Quantifiers) 量词，表示了个体与个体域之间的包含关系。 全称量词(Universal Quantifier)：用字符“x”表达，表示了该量词作用的辖域为个体域中“所有的个体x”或“每一个体x都”要遵从所约定的谓词关系。 例3.4 (x)(现代理工科大学生(x)学习计算机应用基础(x)；解：该谓词逻辑表达的含义是：“所有现代理工科的大学生x，都必须学习计算机应用基础课程”。,2022/11/30,17/117,一阶逻辑,2. 量词 (Quantifiers) 存在量词(Existential Quantifier)：用字符“彐x”表达，表示了该量词要求“存在于个体域中的某些个体x”或“某个个体x”，要服从所约定的谓词关系。例3.5 (x)(彐y)(CLASSMATE(x, y)COLLEGE OF COMPUTER(x)； 解：该谓词逻辑表达的意思是：在所有的计算机学院学生中，相对于每一位同学x，必然存在一个个体y，y同学与x满足同班同学的关系。,2022/11/30,18/117,一阶逻辑,3. 命题公式及其描述举例： 小张既聪明，又勤奋，所以他的学习成绩一直很好。P：小张聪明Q：小张勤奋R：小张学习成绩一直很好 小王总是在图书馆看书，除非他病了或图书馆不开门。P：小王病了Q：图书馆开门R：小王在图书馆看书,2022/11/30,19/117,得到： （ P Q） R,得到： （ P Q） R,一阶逻辑, 若张先生是小张的父亲，则小张是王太太的儿子。解：先设定谓词，再设定变元，并将变元代之以常量，用连接词运算符连接并加以描述：设定谓词：FATHER (x,y)： x是y的父亲 SON (y,w)： y是w的儿子 常量： z 表示张先生；mz 表示小张；wtt王太太 则可描述为： FATHER (z, mz) SON (mz, wtt) （2）若x是小张的父亲，且y是小张的兄弟，则x也是y的父亲。解：设定谓词：FATHER (x,y)： x是y的父亲 BROTHER (y,w)： y是w的兄弟 常量： mz 表示小张则可描述为： FATHER (x, mz) BROTHER (y, mz) FATHER (x, y),2022/11/30,20/117,4. 谓词公式及其描述举例：,一阶逻辑,（3）*在那遥远的地方，有位好姑娘，人们走过她的身旁，都要回头留恋地张望。解： (彐x)好姑娘(x)居住的地方(z，x) 遥远的(z)(y)人(y)行走经过(y, z)回头留恋地张望(y),2022/11/30,21/117,一阶逻辑,5.谓词公式概念 使用连接词和量词，把若干谓词连接组合在一起，就得到了谓词逻辑公式(PLF：Predicate Logic Formula)的表达。定义3.5 仅能表达单一意义且不可再细划分的简单命题称为原子命题。例如，一阶零元(目)命题、一阶一元命题、一阶二元命题等都是原子命题。定义3.6 用连接词或者量词把若干原子命题联结组合在一起，就得到了命题公式(PF：Proposition Formula)，又称之为命题合式公式。定义3.7 采用参量变元来替代命题合式公式中的常量，就得到了原子谓词公式，又称之为谓词合式公式（PWFF：Predicate Well-Formed Formula），简称合式公式或WFF。,2022/11/30,22/117,一阶逻辑,谓词合式公式及其生成规则的定理。 定理3.1 谓词合式公式可依照下述递归(Recursion)过程得到： 原子公式是谓词合式公式； 若A是谓词合式公式，x是A中的任一个变元，则A,( x)A和(彐x)A也都是合式公式； 若A、B都是谓词合式公式，则A,B, AB, AB,AB,AB也都是合式公式； 若有限次使用上述各步生成的公式，仍是合式公式。,2022/11/30,23/117,一阶逻辑,注意：为了使合式公式WFF在连接和运算中表达简洁一致，对WFF还有如下规定： WFF最外层括号可以省略； 括号内连接符运算优先，连接符运算优先次序为 ； 同级连接符的运算按照排列顺序进行。,2022/11/30,24/117,一阶逻辑,6. 谓词公式的解释 首先以个体域中任意常量来替换谓词公式中的变元，使谓词公式转换为一组确定的命题公式；随后赋予各命题逻辑以真值，就得到了对应于该谓词公式的某个含义的解释。 由于存在多种组合情况，则一个谓词公式可有许多个解释。,2022/11/30,25/117,一阶逻辑,下面是关于谓词公式解释的定义。 定义3.8 设D为谓词合式公式PWFF的个体域，按照如下规定对PWFF中的各参量赋值： 为每个个体常量指派D中的一个元素； 为每个n元函数指派一个从D n到D的映像，其中 D n=(x1,x2,xn) /x1,xnD 为每个n元谓词指派一个从D n到真值F,T的映像。 则称这些指派为公式P在D上的一个解释。若某个解释I使PWFF为真(T)，则称I是该公式的一个正模型，简称模型；反之，若某个解释I，使PWFF为假(F)， 则称I是该公式的一个反模型。,2022/11/30,26/117,一阶逻辑,7. 谓词公式的永真性判定 人们若把想要完成的智能任务表示为一个谓词公式，从而把问题的求解转化为求解该公式的真值问题： 如果某公式的真值总为T，则称它是永真的；否则，就称其为非永真或为假。,2022/11/30,27/117,一阶逻辑,例3.6： （1）若 OCITY(x) 表示其含意为：x是一座历史名城。 其中， x西安，洛阳，深圳，刘平，雪花，华盛顿，墨水，开封， 那么， x 的哪些取值的真值为T？哪些取值的真值又为F？它的哪些解释是一个正模型？而哪些解释又是反模型？ （2）若 WHITE(w) 表示其含意为：w是白的。 其中，w 煤球，雪花，大海，刘平，面粉，墨水，玫瑰花， 那么，w 的哪些取值其真值为T？哪些取值的真值又为F？它的哪些解释为正模型？而哪些解释又属于反模型？ （3）若有公式 OCITY(x) WHITE(w) ，其取值和解释又如何呢？ （4）若有公式 OCITY(x) WHITE(w) ，其取值和解释又如何呢？,2022/11/30,28/117,一阶逻辑,谓词公式是否为永真的定义： 定义3.9 如果谓词公式P对个体域D上的任何一个解释都取得真值T，则称P在D上是永真的；如果P在每个非空个体域上都是永真的，则称P永真。 定义3.10 对于谓词公式P，若至少存在一个解释，使得谓词公式P在此解释下的真值为T，则称公式P是兼容的或可满足的；反之，如果存在一个解释集(Set)，使得谓词公式P在其中的任何解释下的真值都为F，则称公式P对该解释集是不兼容的或不可满足的。,2022/11/30,29/117,一阶逻辑,判断谓词公式是否为永真的定理： 定理3.2 如果谓词合式公式WFF对于个体域中的任何一个解释I都有 (I) WFF（I）=T成立，则该公式WFF是一个永真公式。 类同上述，可否引入关于“永假的”、“非永真的”、“非永假的”概念与定义，并得出关于谓词公式永真性问题的若干定理呢？ 永假公式定理3.3 如果谓词合式公式WFF对于个体域中的任何一个解释I都有 (I) WFF（I）= F成立，则该公式WFF是一个永假公式。,2022/11/30,30/117,一阶逻辑,非永真公式定理3.4 如果谓词合式公式WFF在个体域中存在解释I，使得 (彐I) WFF（I）=F 成立，则该公式WFF是一个非永真公式；并且该解释I是此公式的一个反模型。 非永假公式定理3.5 如果谓词合式公式WFF在个体域中存在解释I，使得 (彐I) WFF（I）=T成立，则该公式WFF是一个非永假公式；并且该解释I是此公式的一个模型。 由定义3.10可知，非永假公式可叫做是兼容的或可满足的，而永假公式又称为不可满足的或不兼容的。,2022/11/30,31/117,一阶逻辑,常用的谓词逻辑演算律主要有两大类：一类是逻辑等价律，另一类是逻辑蕴涵律。下面分别加以介绍。 8.谓词逻辑等价律 定义3.11 设P与Q是两个谓词公式，D是它们共同的个体域，若P与Q对于D上的任何一个解释都有相同的真值，则称公式P和Q在D上是逻辑等价的，记为 P Q ；如果D是任意个体域，则称公式P和Q是逻辑等价的，记作 PQ。,2022/11/30,32/117,D,谓词逻辑等价律(一),E1 P P 双重否定律E2 PP P 吸收律（又称等幂律）E3 PP P E4 PQ QP 交换律 E5 PQ QPE6 (PQ)R P(QR) 结合律 E7 (PQ)R P(QR)E8 P(QR) (PQ)(PR) 分配律 E9 P(QR) (PQ)(PR),2022/11/30,33/117,一阶逻辑,谓词逻辑等价律(二),E10 P(PQ) P 吸收律E11 P(PQ) PE12 (PQ) P Q 德摩根定律E13 (PQ) P QE14 PQ PQ 蕴涵化归律E15 PQ (PQ)(QP) 等价律 E16 PT P 谓词与真值演算律E17 PF FE18 PT TE19 PF P,2022/11/30,34/117,一阶逻辑,谓词逻辑等价律(三),E20 PP F 补余律E21 PP TE22 P(QR) PQR 输出律E23 (PQ)(P Q) P 归谬律E24 PQ QP 逆反律E25 (x)A A （A中不含x）E26 (x)A AE27 (x)(P(x)Q(x) (x)P(x)(x)Q(x) 量词分配律E28 (x)(P(x)Q (x) (x)P(x)(x)Q(x)E29 (x)P(x) (x)P(x) 量词转换律E30 (x)P(x) (x)P(x),2022/11/30,35/117,一阶逻辑,谓词逻辑等价律(四),E31 (x)P(x)A (x)(P(x)A) 量词辖域扩张、收缩律E32 (x)P(x)A (x)(P(x)A) （A中不含x）E33 (x)P(x)A (x)(P(x)A) （A中不含x）E34 (x)P(x)A (x)(P(x)A) （A中不含x）E35 (x)(y)P(x, y) (y)(x)P(x, y) 量词交换律E36 (x)( y)P(x, y) ( y)(x)P(x, y) E37 (x)P(x)A (x)(P(x)A) 量词转换及扩张、收缩律E38 (x)P(x)A (x)(P(x)A) （A中不含x）E39 A(x)P(x) (x)(AP(x)E40 A(x)P(x) (x)(AP(x)E41 PQRPQR 复合化归律E42 PQRPQRE43 P(QR)PQRE44 (PQ)R (PR)(QR) (PR)(QR),2022/11/30,36/117,一阶逻辑,一阶逻辑,9. 谓词逻辑蕴涵律 定义3.12 在谓词公式P与Q中，若PQ是永真的，则称P永真蕴涵Q；并称P为前提，Q为P的逻辑结论，记作P Q。,2022/11/30,37/117,谓词逻辑蕴涵律,I1 P PQ；Q PQ；QPQ 附加律 I2 PQ P； PQ Q 化简律I3 P，PQ Q 假言推理I4 (PQ) Q P 拒取式推理I5 P ，PQ Q 析取三段论推理I6 (PQ)(QR) PR 假言三段论推理I7 PQ (QR)(PR)I8 (PQ)(RS) PRQSI9 (PQ)(QS) PRI10 PQ，PQ，QR R 二难推理I11 (x)P(x) P(y) 全称固化律(y为个体域中的个体常量)I12 (x)P(x) P(y) 存在固化律,2022/11/30,38/117,一阶逻辑,一阶逻辑,10. 几条重要的推理规则 P规则：在进行推理的任何步骤上，都可以引入前提P。 T规则：在进行推理时，若同时有一个或多个谓词公式永真(T)蕴含公式S，则可把S引入推理过程中。 CP规则：若从公式C和前提集合P能推出S来，则由P可推出：PS。,2022/11/30,39/117,一阶逻辑, 反证法规则：P Q，当且仅当P Q F。即要证明Q成为P的逻辑结论，其充要条件是后一式必须成立。由反证法规则推广之，可得到如下定理： 定理3.6 Q为P1，P2，PN的逻辑结论，当且仅当 （P1P2PN Q F顺便指出，这是一条使用了反证法的定理，也是迄今实现机器定理证明一种较为可靠的传统途径。,2022/11/30,40/117,其他逻辑系统“非二值”逻辑,正如计算机中使用“0”和“1”两个代码来解释世界一样，人们在基于符号的命题与谓词逻辑中，试图只使用“F”和“T”二个真值来描述智能特性。因此，人们把这种逻辑描述，又常称之为二值逻辑或标准逻辑。 但是，发展中的世界，事物运动变化，气象万千，是否“非真即假”二值逻辑就能全部包容呢？事实上，在“T”和“F”两极之间，世界万物还有着无限精彩表现。由于这些逻辑的特性往往都不是二值的，故统称其为多值逻辑，或称为“非二值”逻辑。,2022/11/30,41/117,其他逻辑系统“非二值”逻辑,人们从实际应用出发已经发明和建立了许多适用于不同目的的逻辑系统：(1) 为了表示关于认知的有关概念，如相信、知道、愿望、意图、目标、承诺等等，人们引进了刻划各种认知概念的模态逻辑； (2) 为了刻划智能系统中的时间因素，人们在逻辑系统中引进时间的概念，提出了各种时序逻辑； (3) 为了描述各种不确定的和不精确的概念，人们引进了所谓模糊逻辑；模糊逻辑是直接建立在自然语言上的逻辑系统，与其它逻辑系统相比较，它考虑了更多的自然语言的成分。 按照其创始人 Zadeh 的说法就是词语上的计算， 表示为一个公式， 即 fuzzy logiccomputing with words；,2022/11/30,42/117,其他逻辑系统“非二值”逻辑,(4) 行为或者动作的概念在智能系统中是一个关键的概念。动作的概念与一般逻辑中的静态的概念很不相同，它是一个动态的概念，动作的发生影响着智能系统的性质。为了刻划动作的概念， 人们引进了一些新的逻辑体系来刻划它。 (5) 人类在决策时，对于各种方案和目标有一定的偏好和选择。这时“偏爱”就成为了一个基本的概念。为了表述和模拟人类在决策时的选择的规律和行为，对于“偏爱”这个词的研究就是不可避免的。于是，基于管理科学的所谓的偏爱逻辑被提出并加以研究。 (6) 时间是智能系统中最重要的几个概念之一。人类使用各类副词来对时间概念加以描述。例如， “一会儿” “相当长” “断断续续地” “偶尔”等等，含有这些词的句子显然是很难用经典的时序逻辑来刻划的，于是有人引进了一种逻辑系统专门刻划这类句子。其基本思想是利用数学中积分的思想，通过对时间的某种像积分那样的表示和运算来形式化这些句子,2022/11/30,43/117,其他逻辑系统逻辑程序设计,Prolog 程序就是一种逻辑程序，它是一种交互式的描述性语言，第一个正式版本是 1970 年代法国Marseilles 大学的 Alain Colmerauer 作为 PROgramming in LOGic的工具开发出来的。只要给定所需的事实和规则，Prolog 使用演绎推理方法就可对问题进行求解。Prolog 特点： （1）Prolog 是数据和程序的统一。Prolog提供了一种一致的数据结构：项。所有数据和程序都是由项构造而成的。在智能程序中常需要将一段程序的输出数据作为新产生的程序来执行，因此人工智能语言应具有数据和程序结构一致的特性。 （2） Prolog 能够自动实现模式匹配和回溯。这些是人工智能系统中最常用的、最基本的操作。 （3） Prolog 具有递归的特点，它反映在 Prolog 程序和数据结构的设计中。由于这一特性，一个大的数据结构常常可以用一个小的程序来处理。 一般情况下， 对一个应用来说，用 Prolog 语言写的程序长度是用 C+语言写的程序长度的十分只一。,2022/11/30,44/117,其他逻辑系统逻辑程序设计,Horn 子句一个子句由两部分组成：头部和体。IF-THEN 规则的结论称为头部，前提部分称为体。 定义 3. 13 Horn 子句是头部最多包含一个文字（命题或谓词）的子句。 Horn 子句在Prolog 中有三种表示形式： （1） 无条件子句（事实） ：A. （2） 条件子句(规则)：A:-B1,Bn. （3） 目标子句(问题)：?- B1,Bn. 上述三种 Horn 子句均具有明显的非形式语义： （1） 无条件子句 A：表示对变量的任何赋值，A均为真。 （2） 条件子句 A:-B1,Bn：表示对变量的任何赋值，如果 B1,Bn 均为真，则 A 为真。 （3） 目标子句?- B1,Bn：其逻辑形式为 x1xn(B1Bn)， 等价于x1xn(B1Bn)。它视作推理的目标。,2022/11/30,45/117,其他逻辑系统逻辑程序设计,定义 3.14 逻辑程序就是由 Horn 子句构成的程序。在逻辑程序中，头部具有相同谓词符的那些子句称为该谓词的定义。 例如下面两个谓词逻辑句子，每个句子都只有一个头。 Father(X,Y) :- Child(Y,X), Male(X). Son(Y,X) :- Child(Y,X), Male(Y). 上述两个子句都是 Horn子句，它们构成一个逻辑程序。假设还有下面三个事实子句： Child( xiao-li, lao-li). Male(xiao-li). Male(lao-li). 如果把上述规则和事实加入 Prolog 中，编译执行后，给出下面的查询，则有： （1） 目标： ?- Father(X,Y). 则会得到： Father(lao-li, xiao-li). （2） 目标： ?- Son(Y,X). 则会得到： Son(xiao-li, lao-li).,2022/11/30,46/117,其他逻辑系统非单调逻辑,单调逻辑 在现有知识的基础上，通过严密的逻辑论证和推理获得的新知识必须与已有的知识相一致。 具体地说，设有知识系统 A，如果已知 A 蕴涵着知识 B，即 AB ，则可推理得出知识 B。在此过程中，严格要求 B 必须遵从知识系统 A。 单调逻辑的推理规则是单调的。设 表示推理规则集，则单调逻辑的语言 Th() = A | A具有如下单调性： (1) Th() (2) 如果 1 2，则 Th(1) Th(2) (3) Th(Th() = Th() (幂等性) 其中 (3)又称为不动点 (fixed point)。单调推理规则的显著特性之一就是它的语言是封闭的最小不动点，亦即 Th(1) = s |1 S 且Th(S) = 2。,2022/11/30,47/117,其他逻辑系统非单调逻辑,非单调推理 推理系统的定理集合并不随推理过程的进行而单调地增大，新推出的定理很可能会否定、改变原来的一些定理，使得原来能够解释的某些现象变得不能解释了。 假如把人们在不同认识阶段的知识用集合 F 来表示，则这样的集合是时间 t 的函数 F(t) 。每个集合 F(t) 表示人们在时刻 t 的知识总和，则这些集合不是单调增大的。形式地说，如果 t1t2，则 F(t1) F(t2) 并不成立。然而人们的知识却一直在不断增长。导致这一现象的根本原因就是人们推理时所依据的知识具有不完全性。非单调逻辑是处理不完全知识的工具。,2022/11/30,48/117,其他逻辑系统非单调逻辑,非单调推理三个主要流派： McCarthy 提出的限制理论：当且仅当没有事实证明 S在更大的范围成立时，S只在指定的范围成立； Reiter的缺省逻辑： “S在缺省的条件下成立”是指 “当且仅当没有事实证明 S不成立时 S是成立的” ； Moore 的自认知逻辑： “如果我知道 S，并且我不知道有其他任何事实与 S矛盾，则 S是成立的” 。,2022/11/30,49/117,其他逻辑系统非单调逻辑,对逻辑进行扩展，将非单调推理形式化，称为非单调逻辑。 语言方面的扩充是指增强其表达能力； 语义方面的扩充是指对真值的真假两种情况进行修正；一是对推理模式的扩展，这涉及非单调推理的过程化方面，称为非单调系统。 非单调逻辑大致分为两类：一类基于最小化语义，称为最小化非单调逻辑；另一类基于定点定义，称为定点非单调逻辑。 最小化非单调逻辑可以分为基于最小化模型和基于最小化知识模型。前者主要有封闭世 界假设、 McCarthy的限制逻辑 （circumscription） 等， 后者包括 Konolige 的忽略逻辑 （ignorance）等。,2022/11/30,50/117,其他逻辑系统非单调逻辑,定点非单调逻辑可以分为缺省逻辑(default)和自认知逻辑(autoepistemic)。McDermott 和Doyle 提出的非单调模态逻辑 NML 旨在研究非单调逻辑的一般基础,是一种一般缺省逻辑。 非单调系统的实现，可以通过对矛盾的检测进行真值的修正来维护相容性，可称为真值维护系统， 包括Doyle提出的真值维护系统TMS， Dekleer提出的基于假设的真值维护系统ATMS等等。,2022/11/30,51/117,其他逻辑系统封闭世界假设,封闭世界假设（Closed World AssumptionCWA）是一种对由一组基本信念集合 KB 定义的理论 T(KB)进行完备化的方法。一个理论 T(KB)是完备的，是说其包含（显式或隐含）了每一个基原子公式或该公式否定。 CWA的基本思想是：如果无法证明 P，则就认为它是否定的。即： 如果从知识库中无法证明 P或者P，则就向 KB 中增加P。 这就是说你假定知道所有有关世界的事情（即世界是封闭的） 。,2022/11/30,52/117,其他逻辑系统封闭世界假设,CWA的最大用处是完备化数据库系统。例如，我们可以设计一个关于国家邻接的数据库Neighbor(x, y)。基于 CWA，凡是未在该数据库中说明是邻接的国家都是不邻接的。 假定 KB： Neighbor(China, Russia). Neighbor(China, Mongolia). xy (Neighbor(x, y) Neighbor(y, x) 则 T(KB)是不完全的，因为无论是 Neighbor(Russia, Mongolia)还是Neighbor(Russia, Mongolia)都不在 KB 中。,2022/11/30,53/117,其他逻辑系统封闭世界假设,CWA 对理论的完备化是仅仅通过向基本信念集合 KB 中增加基原子公式的取反来实现的。换言之，若一个基原子公式不能经由逻辑推理从基本信念集 KB 导出，就将其取反作为KB 的扩充。显然，CWA是非单调的，因为一旦以后有新的基原子公式加进 KB，则为完备 T（KB）而生成的扩充集就必须收缩（删除该基原子公式的否定） 。例如对于国家相邻问题，可以向 KB 中增加Neighbor(Russia, Mongolia)实现完备化。,2022/11/30,54/117,其他逻辑系统情景演算,情景演算是分析处理和研究涉及动作和进化问题的最常用的形式工具。 多类逻辑（ LR）：建立在对情景演算的直观理解的意义上，把情景演算的概念和方法在这种特殊的多类一阶逻辑的框架之内进行描述，以便为有关的研究提供一个坚实的系统的理论基础。把情景演算集成在一个多类逻辑框架里，这一做法的核心是：为了刻划一个动作，只需要描述动作发生的条件和动作发生以后对其环境所产生的效果这两件事。 为此，在逻辑框架 LR 中引入了“动作” ， “状态”和“一般对象”这三种个体类型，然后通过一系列的逻辑句子来表述这三种对象的最一般关系以及动作发生的前提和后果。每个这样的句子集被称为一个基本的动作理论。从纯粹逻辑学的观点看，所谓的“动作的基本理论”就是在特定的多类逻辑中的普通逻辑学意义下的一个理论。,2022/11/30,55/117,其他逻辑系统情景演算,LR 被定义成一种多类逻辑，在其形式语言 中引入了三种关于个体的类型，即状态类型s、对象类型o 和动作类型 a。 一个类型为 s 的常量符号 S0 （表示起始状态）； 一个类型为的二元函数符号 do （描述一个动作的发生使得状态从一个变成另外一个）； 一个类型为的二元关系符号 Poss（表示一个动作在一个状态之下是可能发生的）； 一个类型为的二元关系符号（表示状态之间的先后关系） 。,2022/11/30,56/117,其他逻辑系统动态描述逻辑 DDL,描述逻辑是一种基于对象的知识表示的形式化，也叫概念表示语言或术语逻辑。它是一阶逻辑的一个可判定的子集，具有合适定义的语义，并且具有很强的表达能力。一个描述逻辑系统包含四个基本组成部分：表示概念和关系的构造集；TBox 包含断言；ABox实例断言；TBox和 ABox上的推理机制。 一个描述逻辑系统的表示能力和推理能力取决于对以上几个要素的选择以及不同的假设。 描述逻辑中有两个基本元素： 概念解释为一个领域的子集； 关系则表示在领域中个体之间所具有的相互关系，是在领域集合上的一种二元关系。 动态描述逻辑是在传统描述逻辑的基础上扩充得到的。,2022/11/30,57/117,约束推理,约束通常是指一个包含若干变量的关系表达式，用以表示这些变量所必须满足的条件。 约束满足问题(Constraint Satisfaction Problem, 简称 CSP) 一组变量与一组变量间的约束。一般而言，变量表示领域参数，每个变量都有一个固定的值域。一个变量的值域可能是有限的，例如一个布尔变量的值域包含两个值；也可能是离散无限的，如整数域；也可能是连续的，如实数域。约束可用于描述领域对象的性质、相互关系、任务要求、目标等。 约束满足问题的目标就是找到所有变量的一个（或多个）赋值，使所有约束都得到满足。 约束满足问题在一般情形下是一个 NP 问题，所以必须使用各种策略与启发式信息。,2022/11/30,58/117,约束推理,约束表示易于理解、编码及有效实现，它具有以下优点: (1) 约束表示允许以说明性的方式来表达领域知识，表达能力较强，应用程序只需指定问题的目标条件及数据间的相互关系。因而具有逻辑表示的类似性质。 (2) 约束表示允许变量的域包含任意多个值，而不像命题只取真假二值。所以它保存了问题的一些结构信息，如变量域的大小、变量间的相关性等，从而为问题求解提供启发式信息。 (3) 易于并行实现。因为约束网络上的信息传播可以认为是同时的。 (4) 适合于递增型系统。约束可以递增式地加入到约束网络。 (5) 易于与领域相关的问题求解模型相衔接。各种数学规划技术，方程求解技术等, 都可以自然地嵌入约束系统。,2022/11/30,59/117,约束推理,根据联系于约束网络节点上的数据类型，可以将约束推理分为以下几种： (1) 关系推理： 推理过程中推出的新的约束关系, 并将其加到约束网络中。 Kuiper 的 ENV系统、Simmon 的Quantity Lattice 系统，及 Brooks 的CMS 系统,都属于关系推理。 (2) 标记推理：每个节点标注以可能值的集合，在传播过程中约束用于限制这些集合。 (3) 值推理：节点标记以常量值。约束用已标记节点的值求出标记节点的值。SKETCHPAD及 THINGLAB都使用值推理。 (4) 表达式推理：是值推理的推广，其中节点可能标以关于其它节点的表达式。当一个节点标记以不同的表达式时, 应使其等同起来, 并求解结果方程。 CONSTRAINTS 就使用这种推理。,2022/11/30,60/117,约束推理,约束分类, 按复杂性的次序列举如下： 一元谓词。 序关系语言，只包含偏序关系或实变量上的大小关系。 形如“x - y c”或“x - y c”的方程。 单位系数的线性方程与不等式，即所有的系数为 -1, 0, 1。 任意系数的线性方程与不等式。 约束的布尔组合。 代数与三角方程。,2022/11/30,61/117,约束推理,约束推理的研究： 约束搜索 主要研究有限域上的约束满足。大体包括下列方法： 回溯法。 约束传播。 智能回溯与真值维护。 可变次序例示。 局部修正法。,2022/11/30,62/117,约束推理,约束语言 CONSTRAINTS ：是一个面向电路描述的约束表示语言。使用了符号处理技术来求解数学方程，系统采用表达式推理与值推理，并实现相关制导的回溯。 Bertrand ：Bertrand 是由 Leler 开发的基于增强型项重写技术的系统 ，是在项重写系统的基础上加上赋值功能与类型机制。能够解决实数与有理数上的线性方程。 约束逻辑程序设计语言 CHIP：是在 Prolog 的基础上引入约束传播机制，以提高搜索效率，增强表达能力。通过提供几种新的计算域而增强逻辑程序设计的能力。,2022/11/30,63/117,约束推理,约束语言约束层次与HCLP： 将需要尽可能满