人工智能课件2

1、 第2章人工智能逻辑 1第2章 人工智能逻辑 2.1 命题逻辑与谓词逻辑 2.2 谓词公式及其逻辑表达式 2.3* 谓词逻辑的演算律 2.4 “非二值”逻辑 2.5# 模糊逻辑22.1 命题逻辑与谓词逻辑什么是逻辑？简单地说，逻辑就是人们用以处理问题而抽象的一种思维规则或计算方法。本章主要对人工智能常用的谓词逻辑以及非二值逻辑进行了讨论，扼要介绍了目前智能领域发展引用的多种逻辑。32.1.1 命题逻辑命题逻辑的关系表达直观、生动而简洁，它是谓词逻辑得以发展的前导和基础。把命题逻辑加以简单的形式化，就能扩展应用于谓词逻辑推理中。1. 命题和个体 设有如下符号命名的语句： X：爱因斯坦是一位伟人。

2、Y：海水是甜的。W：3+4=9上述X、Y、Z都是陈述性语句，分别具有肯定(True)或否定(False)意义的真值，我们把它们都称之为命题。其中，诸如“爱因斯坦”，“海水”，数字“3”、“4”等，它们是命题中的行为中心对象，又称为个体。 42.1.1 命题逻辑 定义2.1 命题(Proposition)，即具有真(T)假(F)意义的陈述性语句。注意： 命题一定是陈述性语句；如上述X、Y、W等。 例如，下面句子是陈述性语句吗？请勿吸烟。昨晚你看足球联赛了吗？西湖好美呵！命题既可用自然语言(包括中、外文)形式表示，也可用大写的英文字符或字符串来命名。命题反映了人脑进行思维的一种判断，可见命题表达自

3、身就含有智能特性。52.1.1 命题逻辑（1）个体是命题中的中心对象，通常由名词构成。个体可以是具体的人物、物体、一组数字、地名等，也可以是某个抽象的概念。例如，机器人、海棠花、理想、快乐、智能等均可作为个体。（2）个体的取值范围称为个体域。个体域可以是有限的，也可以是无限的。 定义2.2 所谓个体，是指可以独立存在的某个事物。 62.1.1 命题逻辑2. 谓词及变元 为了对许多具有进步影响人物都使用形同X命题方式赞扬之，可使用一种类同数学函数的形式语言用含有变量字符或字符串的谓词来定义：表达为英文字符串形式： GIANT(x).其被赋予的汉语解释是： x是一位伟人。 把 GIANT(x)称为

4、谓词（Predicate），其中GIANT ( )是谓词名；括号中的参量x叫做谓词的变元，又称之为项。GIANT( ) 谓词名谓词变元 72.1.1 命题逻辑2. 谓词及变元 这种由定义的谓词名、变元，共同构成了具有陈述性表达的形式化语句，称为谓词。一个谓词可以有n（其中n=0,1,2, ）个变元，并称之为n元谓词。 在谓词中，谓词名表达了语句中除主语个体之外的其余部分，常采用自然语言的谓语动作词根来表达；谓词的变元可在相应个体域集合中取值任意一个元素。 GIANT( ) 谓词名谓词变元 82.1.1 命题逻辑2. 谓词及变元例2-1 假如定义英文字符串“OCITY(x) ” 设其含意为：x是

5、一座历史名城。 解：这里x可以取值“西安” 真值为T；x取值“深圳” 真值为F。若取值“北京”则为T、“华盛顿”T、“野玫瑰”F、 “机器人” 为F等。 由上例可见，当使用特定的个体常量取代了谓词中的变元，该谓词就转换成为一个命题；反之，如果把命题中有独立结构的个体常量替换成变元参量，则又可把命题转换成为一个具有谓词结构的表达式了。 92.1.1 命题逻辑3. 谓词的元和谓词的阶 下面先给出关于谓词的元的定义，然后再举例对定义加以解释和说明。定义2.3 谓词中包含个体或变元的数目，称为谓词的元或谓词的目。例2-2 比较下列谓词或谓词形式的命题：LIKE(john，mary)；ROBOT(joh

6、n)；ROBOT(mary)； ADDQ(x，y，z)。试解释具体含义，并指出它们各是几元谓词。解：上述谓词意即“机器人约翰喜欢玛丽”；和都只有一个个体，称为一元谓词；相应则称为二元谓词；表示为表达式“x+y=z”，其中包含有3个变元，故称为三元谓词。依此类推，可推出关于n元谓词的概念。 顺便指出：在多元谓词中，变元的排序很重要，一旦确定，就不可随意交换。 102.1.1 命题逻辑3. 谓词的元和谓词的阶 定义2.4 谓词表达形式中所包容相叠加的含义层次数数目，称为谓词的阶。例2-3 为了说明谓词的阶，我们来比较下列谓词形式的命题：LIFELESS(outer-stars)；外星球没有智能生命

7、。INCORRECT(lifeless(outer-stars)；说“外星球没有智能生命”是不确切的。解：在上述谓词形式的命题中，谓词只有一层含义，称为一阶谓词；谓词在前一层含义基础上，又增加了一层新意，共有二层含义。故把谓词称为二阶谓词。依此类推，可推出关于n阶谓词的概念。注意：在谓词逻辑演算中，最重要的有三大类：即：命题逻辑演算、 一阶谓词逻辑演算和二阶谓词演算。 112.1.1 命题逻辑4. 命题与谓词逻辑的关系 命题逻辑表示比较简单，只能表达具体固定的情况，命题是谓词逻辑特殊事例的生动描述，谓词逻辑可以灵活表现多种或变化的情况；谓词表达是命题逻辑的抽象与推广。总的看来，命题和谓词的知识

8、表示形式可以相互转换，而谓词比命题有更强的表达能力。显而易见，谓词是一种描述个体群之间的相互关系、性质及其逻辑结构的数学表示。人们把采用这种表示的运算，又称为谓词逻辑。比较起来：命题逻辑演算太简单，只能解决具体容易的问题；二阶谓词演算又太复杂，以至迄今为止，尚未找到最根本有效的算法。 因此，在人工智能中，目前使用最多的还是一阶谓词逻辑演算。 122.1.2命题和谓词逻辑基础 命题或谓词逻辑推理演算，主要可利用连接词和量词，把单个的谓词组合成为谓词公式来完成。基于命题和谓词逻辑可相互转换的特性，这里约定：在后继学习中，对命题和谓词逻辑的相关公式表达、相关定理、定律的论证和推导等，不再加以严格区别

9、。132.1.2命题和谓词逻辑基础 1. 连接词 (Connectives) 所引入的连接词共有五个。 符号“”称为“否定”(Negation)或补，表示“非”的连接关系。即当命题P为真时，则P 为假；反之，当命题P为假，则P 为真。符号“”称为“合取”(Conjunction)，表示“与”(AND)或“同时”的关系。例如，PQ，读作“P与Q”。符号“”称为“析取”(Disjunction)，它表示“或”(OR)的连接关系。例如，PQ，读作“P或Q”。142.1.2命题和谓词逻辑基础 1. 连接词 (Connectives) 符号“”称为“条件”(Conditional)或者“蕴涵”(Impl

10、ication)，它表示“如果，则”的定义关系。例如，在PQ的表达式中，表示了“如果P，则Q”的条件推导关系。这里，又称P为前件，称Q后件。P表示了条件的前提；Q表示了逻辑结论。应该强调指出，条件表达式有一个重要特性：当前件P=F时，无论后件Q为何值(T或者F)，条件式PQ真值总是为T；当前件P=T时，条件式PQ的真值总是与后件Q真值相同。 符号“”称为“双条件”(Biconditional)或者等价(Equivalence) 连接关系。例如，表达式PQ，读作“P当且仅当Q”。或者说它表示的含义为：P为真，当且仅当Q为真。 152.1.2命题和谓词逻辑基础 1. 连接词 (Connective

11、s) P Q P PQ PQ PQ PQ F F T F F T T F T T T F T ? F T F F T F F F T T F T T T T表2-1 连接词定义真值表 162.1.2命题和谓词逻辑基础 2. 量词 (Quantifiers) 量词，表示了个体与个体域之间的包含关系。 全称量词(Universal Quantifier)：用字符“x”表达，表示了该量词作用的辖域为个体域中“所有的个体x”或“每一个体x都”要遵从所约定的谓词关系。例2-4 (x)(现代理工科大学生(x)学习计算机应用基础(x)；解：该谓词逻辑表达的含义是：“所有现代理工科的大学生x，都必须学习计算机

12、应用基础课程”。 172.1.2命题和谓词逻辑基础 2. 量词 (Quantifiers) 存在量词(Existential Quantifier)：用字符“彐x”表达，表示了该量词要求“存在于个体域中的某些个体x”或“某个个体x”，要服从所约定的谓词关系。例2-5，(x)(彐y)(CLASSMATE(x, y)COLLEGE OF COMPUTER(x)； 解：该谓词逻辑表达的意思是：在所有的计算机学院学生中，相对于每一位同学x，必然存在一个个体y，y同学与x满足同班同学的关系。 182.1.3命题和谓词逻辑举例 3. 命题公式及其描述举例： 小张既聪明，又勤奋，所以他的学习成绩一直很好。P

13、：小张聪明Q：小张勤奋R：小张学习成绩一直很好得到： （ P Q） R192.1.3命题和谓词逻辑举例 小王总是在图书馆看书，除非他病了或图书馆不开门。P：小王病了Q：图书馆开门R：小王在图书馆看书得到： （ P Q） R3. 命题公式及其描述举例：202.1.3命题和谓词逻辑举例 （1）若x是小张的父亲，且y是小张的兄弟，则x也是y的父亲。解：先设定谓词，再设定变元，并将变元代之以常量，用连接词运算符连接并加以描述：设定谓词：FATHER (x,y)： x是y的父亲 BROTHER (y,w)： y是w的兄弟 常量： mz 表示小张则可描述为： FATHER (x, mz) BROTHER

14、(y, mz) FATHER (x, y) 4. 谓词公式及其描述举例：212.1.3命题和谓词逻辑举例 （2）*在那遥远的地方，有位好姑娘，人们走过她的身旁，都要回头留恋地张望。解： (彐x)好姑娘(x)居住的地方(z，x) 遥远的(z)(y)人(y)行走经过(y, z) 回头留恋地张望(y)4. 谓词公式及其描述举例：222.2 谓词公式及其逻辑表达式 2.2.1 谓词公式概念复习与扩充： 使用连接词和量词，把若干谓词连接组合在一起，就得到了谓词逻辑公式(PLF：Predicate Logic Formula)的表达。下面我们给出谓词公式的相关各种概念与定义。定义2.5 仅能表达单一意义且

15、不可再细划分的简单命题称为原子命题。例如，一阶零元(目)命题、一阶一元命题、一阶二元命题等都是原子命题。定义2.6 用连接词或者量词把若干原子命题联结组合在一起，就得到了命题公式(PF：Proposition Formula)，又称之为命题合式公式。定义2.7 采用参量变元来替代命题合式公式中的常量，就得到了原子谓词公式，又称之为谓词合式公式（PWFF：Predicate Well-Formed Formula），简称合式公式或WFF。 23 2.2.2 谓词公式概念 综上所述，我们可以给出下述关于谓词合式公式及其生成规则的定理。 定理2.1 谓词合式公式可依照下述递归(Recursion)过

16、程得到：原子公式是谓词合式公式；若A是谓词合式公式，x是A中的任一个变元，则A,( x)A和(彐x)A也都是合式公式；若A、B都是谓词合式公式，则A,B, AB, AB,AB,AB也都是合式公式；若有限次使用上述各步生成的公式，仍是合式公式。24 2.2.2 谓词公式概念 注意：为了使合式公式WFF在连接和运算中表达简洁一致，对WFF还有如下规定： WFF最外层括号可以省略；括号内连接符运算优先，连接符运算优先次序为 ； 同级连接符的运算按照排列顺序进行。 25 2.2.2 谓词公式的解释 谓词公式的解释：首先以个体域中任意常量来替换谓词公式中的变元，使谓词公式转换为一组确定的命题公式；随后赋

17、予各命题逻辑以真值，就得到了对应于该谓词公式的某个含义的解释。 由于存在多种组合情况，则一个谓词公式可有许多个解释。 26定义：设D是谓词公式P的非空个体域，若对P中的个体常量、函数和谓词按如下规定赋值： （1）为每个个体常量指派D中的一个元素； （2）为每个n元函数指派一个从Dn到D的一个映射，其中 Dn (x1,x2,xn)|x1,x2,xn D （3）为每个n元谓词指派一个从Dn到T,F的映射 则称这些指派为P在D上的一个解释。若某个解释I使谓词公式为真(T)，则称I是该公式的一个正模型，简称模型；反之，若某个解释I，使谓词公式为假(F)， 则称I是该公式的一个反模型。27例：设个体域D

18、=1,2，求公式A=( x)(彐y)P(x,y) 在D上的解释，并指出在每一种解释下公式A的真值。解: 由于公式A中没有包含个体常量和函数，因此可以直接为谓词指派真值，设有: 这就是公式A在D上的一个解释。从这个解释可以看出： 当x=1、y=1 时，有P(x,y)的真值为T； 当x=2，y=1 时，有P(x,y)的真值为T；即对x 在D上的任意取值，都存在y=1使P(x,y)的真值为T。因此，在此解释下公式A的真值为T。 P(1,1)P(1,2)P(2,1)P(2,2)TFTF28需要注意，一个谓词公式在其个体域上的解释不是唯一的。例如，对公式A，若给出另一组真值指派 这也是公式A在D上的一个

19、解释。从这个解释可以看出： 当x=1、y=1 时，有P(x,y) 的真值为T； 当x=2、y=1 时，有p(x,y)的真值为F； 同样 当x=1、y=2 时，有P(x,y) 的真值为T； 当x=2、y=2 时，有P(x,y)的真值为F；即对x在D上的任意取值，不存在一个y 使得P(x,y)的真值为T。因此，在此解释下公式A的真值为F。 实际上，A在 D上共有 16种解释，这里就不再一列举。P(1,1)P(1,2)P(2,1)P(2,2)TTFF29例：设个体域D=1，2，求公式B=（ x）P（f（x），a）在D上的解释，并指出在该解释下公式B的真值。 解：设对个体常量a和函数f（x）的真值指派

20、为： 对谓词的真值指派为： 这里，由于已知指派a=1，所以P（1，2）和P（2，2）不可能出现，故没有给它们指派真值。 上述指派是公式B在D上的一个解释。在此解释下有 当x=1时，a=1使P（1，1）=T 当x=2时，a=1使P（2，1）=T即对x在D上的任意取值，都有P（f(x)，a）的真值为T。因此，在此解释下公式B的真值为T。af(1)f(2)112P(1,1)P(1,2)P(2,1)P(2,2)TT 由上面的例子可以看出，谓词公式的真值都是针对某一个解释而言的，它可能在某一个解释下真值为 T，而在另一个解释下为 F。30 2.2.3 谓词公式的永真性判定 人们若把想要完成的智能任务表示

21、为一个谓词公式，从而把问题的求解转化为求解该公式的真值问题： 如果某公式的真值总为T，则称它是永真的；否则，就称其为非永真或为假。 这就是我们要讨论的所谓永真性的问题。31 2.2.3 谓词公式的永真性判定 下面使用谓词公式的解释概念，给出关于谓词公式是否为永真的定义。 定义2.9 如果谓词公式P对个体域D上的任何一个解释都取得真值T，则称P在D上是永真的；如果P在每个非空个体域上都是永真的，则称P永真。 定义2.10 对于谓词公式P，若至少存在一个解释，使得谓词公式P在此解释下的真值为T，则称公式P是兼容的或可满足的；反之，如果存在一个解释集(Set)，使得谓词公式P在其中的任何解释下的真值

22、都为F，则称公式P对该解释集是不兼容的或不可满足的。 32 2.2.3 谓词公式的永真性判定 根据上述定义，就能总结得出如下判断谓词公式是否为 永真的定理。 定理2.2 如果谓词合式公式WFF对于个体域中的任何一个解释I都有 (I) WFF（I）=T成立，则该公式WFF是一个永真公式。 类同上述，可否引入关于“永假的”、“非永真的”、“非永假的”概念与定义，并得出关于谓词公式永真性问题的若干定理呢？ 永假公式定理2.3 如果谓词合式公式WFF对于个体域中的任何一个解释I都有 (I) WFF（I）= F成立，则该公式WFF是一个永假公式。33 2.2.3 谓词公式的永真性判定 非永真公式定理2.

23、4 如果谓词合式公式WFF在个体域中存在解释I，使得 (彐I) WFF（I）=F 成立，则该公式WFF是一个非永真公式；并且该解释I是此公式的一个反模型。非永假公式定理2.5 如果谓词合式公式WFF在个体域中存在解释I，使得 (彐I) WFF（I）=T成立，则该公式WFF是一个非永假公式；并且该解释I是此公式的一个模型。 由定义2.10可知，非永假公式可叫做是兼容的或可满足的，而永假公式又称为不可满足的或不兼容的。 342.3* 谓词逻辑的演算律 常用的谓词逻辑演算律主要有两大类：一类是逻辑等价律，另一类是逻辑蕴涵律。下面分别加以介绍。 2.3.1 谓词逻辑等价律 定义2.11 设P与Q是两个

24、谓词公式，D是它们共同的个体域，若P与Q对于D上的任何一个解释都有相同的真值，则称公式P和Q在D上是逻辑等价的，记为P Q ；如果D是任意个体域，则称公式P和Q是逻辑等价的，记作PQ。35谓词逻辑等价律(一)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)36谓词逻辑等价律(二)E10 P(PQ) P 吸收律E11 P(PQ) PE12 (PQ) P Q 德摩根定律E13 (PQ)

25、P QE14 PQ PQ 蕴涵化归律E15 PQ (PQ)(QP) 等价律 E16 PT P 谓词与真值演算律E17 PF FE18 PT TE19 PF P 37谓词逻辑等价律(三)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(

26、x)38谓词逻辑等价律(四)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)

27、E40 A(x)P(x) (x)(AP(x)E41 PQRPQR 复合化归律E42 PQRPQRE43 P(QR)PQRE44 (PQ)R (PR)(QR) (PR)(QR)392.3* 谓词逻辑的演算律 2.3.2 谓词逻辑蕴涵律 定义2.12 在谓词公式P与Q中，若PQ是永真的，则称P永真蕴涵Q；并称P为前提，Q为P的逻辑结论，记作P Q。 40谓词逻辑蕴涵律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 (Q

28、R)(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) 存在固化律41 P规则：在进行推理的任何步骤上，都可以引入前提P。 T规则：在进行推理时，若同时有一个或多个谓词公式永真(T)蕴含公式S，则可把S引入推理过程中。 CP规则：若从公式C和前提集合P能推出S来，则由P可推出：PS。2.3.3 几条重要的推理规则42反证法规则：P Q，当且仅当P Q F。即要证明Q成为P的逻辑结论，其充要条件是后一式必须成立。由反证法规则推广之，可得到如

29、下定理：定理2.6 Q为P1，P2，PN的逻辑结论，当且仅当 （P1P2PN Q F顺便指出，这是一条使用了反证法的定理，也是迄今实现机器定理证明一种较为可靠的传统途径。 2.3.3 几条重要的推理规则432.4 “非二值”逻辑 正如计算机中使用“0”和“1”两个代码来解释世界一样，人们在基于符号的命题与谓词逻辑中，试图只使用“F”和“T”二个真值来描述智能特性。因此，人们把这种逻辑描述，又常称之为二值逻辑或标准逻辑。但是，发展中的世界，事物运动变化，气象万千，是否“非真即假”二值逻辑就能全部包容呢？事实上，在“T”和“F”两极之间，世界万物还有着无限精彩表现。例如，依据研究需要，还可以定义“

30、三值”以及多值逻辑、随机表达逻辑、时态逻辑、模态逻辑、模糊逻辑等。由于这些逻辑的特性往往都不是二值的，故统称其为多值逻辑，或称为“非二值”逻辑。 442.4 “非二值”逻辑2.4.1 多值逻辑的演算 定义T(P)来表示命题P为真的程度。则：即T(P)是某个介于0到1之间的任意实数，称T(P)为命题P的真度。 按如下规则来进行连接词的逻辑运算： （1）（2）（3）（4）（5） 45 2.4.1 多值逻辑的演算 例如，对于 ，除了可用上面给出的定义计算 外，还可以按下述某个定义的规则来计算其值：46 2.4.1 多值逻辑的演算 计算 还可以按下述某个定义的规则来计算其值：47 那么在实际应用中应选

31、用哪种定义来计算 T(PQ) 呢？一般要具体情况具体分析对待，即选择更贴切实际情况的那一种。 应该指出：上述关于连接词运算规则的定义，只是作为一种数理逻辑概念象征性的引入，并未深入加以严格证明。读者在应用中可以继续延伸甚至发挥这种思想，从而提出新的或自己独到的数学理念，以便进行相关研究工作。 2.4.1 多值逻辑的演算48 三值逻辑是多值逻辑的一种，顾名思义，即限定命题真值具有“真”、“假”、和介于“真”与“假之间共三个状态值的逻辑。 2.4.2三值逻辑及其布可阀（Bochvar）逻辑 49 P Q P PQ PQ PQ PQ 0 0 1 0 0 1 1 0 0.5 1 0.5 0 1 0.5

32、 0 1 1 1 0 1 0 0.5 0 0.5 0.5 0 0.5 0.5 0.5 0.5 0.5 0.5 0.5 1 1 0.5 1 0.5 1 0.5 1 0.5 1 0 0 1 0 0 0 1 0.5 0 1 0.5 0.5 0.5 1 1 0 1 1 1 1表2-4 一种特定计算规则的三值逻辑真值表 50 关于布可阀（Bochvar）逻辑，我们可以通过朗读下面由四个命题构成的一首小诗来说明：2.4.2三值逻辑及其布可阀（Bochvar）逻辑 这是一个黄昏的早晨。 我走在那宽敞的羊肠小道上。 温暖的寒风扑面。 树阴中阳光灿烂。 51 例如，有人写了以下一个随意命题 X：这个命题是假的。请问，单就命题“X”自身的真值来判断，其真值是“真”还是“假”呢？为什么？ 可见，Bochvar逻辑常常表现出与某种矛盾状态有关，有时人们称之为语义悖论问题。 2.4.2三值逻辑及其布可阀（Bochvar）逻辑 52 人们在智能活动与研究中，除了广泛地使用着诸如命题和谓词等确定性逻辑之外，还常常使用一些非确定性、估计的或预测性的逻辑。例如，在