人工智能初步(第一讲)命题逻辑与谓词逻辑.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,人工智能数学基础（一）,命题逻辑与谓词逻辑,人类智能在计算机上的模拟就是人工智能，而智能的核心是思维，因而如何把人们的思维活动形式化、符号化，使其得以在计算机上实现，就成为人工智能研究的重要课题。在这方面，逻辑的有关理论、方法、技术起着十分重要的作用。,人工智能中用到的逻辑可以概括地分为两大类：,一类是经典逻辑和一阶谓词逻辑，其特点是任何一个命题的真值或者为“真”，或者为“假”，二者必居其一。,另一类是泛指除经典逻辑外地那些逻辑，主要包括三值逻辑、多值逻辑、模糊逻辑、模态逻辑及时态逻辑等。,命题逻辑与谓词逻辑是最先应用于人工智能的两种逻辑，对于知识的形式化表示，特别是定理的证明发挥了重要作用。谓词逻辑是在命题逻辑基础上发展起来的，命题逻辑可看作是谓词逻辑的一种特殊形式。下面我们来讨论谓词逻辑的主要概念及有关定理。,定义,1,、,命题是具有真假意义的语句。,命题代表人们进行思维时的一种判断，若命题的意义为真，称它的真值为真，记作,T,；若命题的意义为假，称它的真值为假，记作,F,。一个命题不能同时既为真又为假，但可以在一定条件下为真，在另一种条件下为假。没有真假意义的语句（如感叹句、疑问句等）不是命题。,例如：“北京是中华人民共和国首都”；,“,106”,；,都是真值为,T,的命题；,“太阳从西边升起”；,“煤炭是白色的”；,都是真值为,F,的命题。,一、命题,“,1+1,10”,在二进制情况下是真值为,T,的命题，但在十进制情况下却是真值为,F,的命题。,我们通常用大写的英文字母表示一个命题，例如可以用英文字母,P,表示“武汉是个城市”这个命题。,思考,：命题这种表示方法有其局限么？,这种表示方发有较大的局限性，它无法把它所描述的客观事物的结构及逻辑特征反映出来，也不能把不同事物间的共同特征表述出来。,例如，对于“小张是老张的儿子”这一命题，若用英文字母表示，如用字母,P,表示，则无论如何也看不除老张与小张是父子关系。又如“张三是学生”，“李四也是学生”这两个命题，用命题逻辑表示时，也无法把两者的共同特征（都是学生）形式的表示出来。由于这些原因，在命题逻辑的基础上发展起来了谓词逻辑。,在谓词逻辑中，命题是用谓词来表示的，一个谓词可分为谓词名与个体这两个部分。个体表示某个独立存在的事物或者某个抽象的概念；谓词名用于刻画个体的性质、状态或个体间的关系。,例如，对于“张三是学生”这个命题，用谓词可表示为,student,（,zhang,）。期中，,student,是谓词名，,zhang,是个体，,student,刻画了,zhang,的职业是学生这一特征。,二、,谓词,谓词的一般表示形式是：,P,（,x1,x2,x3,xn,）,其中，,P,是谓词名，,x1,x2,x3,xn,是个体。谓词名通常用大写英文字母表示，个体通常用小写英文字母表示。,在谓词中，个体可以是常量，也可以是变元，还可以是一个函数。例如，对于,x10,，可以表示为,more,（,x,，,10,），期中,x,是变元。又如“小张的父亲是老师”，可以表示为,teacher,（,father,（,zhang,），期中，,father,（,zhang,）是一个函数。,当谓词中的变元都用特定的个体取代时，谓词就具有一个确定的真值：,T,或,F,。,谓词中包含的个体数目称为谓词的元数。,在谓词,P,（,x1,x2,x3,xn,）中，若,xi,（,i,1,，,，,n,）都是个体常量、变元或函数，称它为一阶谓词。如果某个,xi,本身又是一个一阶谓词，则称它为二阶谓词，如此类推。,个体变元的取值范围称为个体域,。个体域可以是有限的，也可以是无限的。例如用,I,（,x,）表示“,x,是整数”，则个体域是所有整数。,命题与函数不同，谓词的真值是“真”或“假”，而函数的值是个体域中的某个个体，函数无真值可言，它只是在个体域中从一个个体到另一个个体的映射。,1.,连接词,可以用以下连接词，把一些简单命题连接起来构成一个复合命题，以表示一个比较复杂的含义。,：称为“非”或“否定”：其作用是否定位于它后面的命题。当命题,P,为真是，为假；当,P,为假时,为真。,：称为“析取”：表示被它连接的两个命题具有“或”关系。,：称为“合取”：表示被它连接的两个命题具有“与”关系。,：称为“条件”或“蕴含”。“,P Q”,表示“,P,蕴含,Q”,，即“如果,P,，则,Q”,，其中,P,称为条件的前件，,Q,称为条件的后件。,：“双条件”：表示“,P,当且仅当,Q”,。,三、谓词公式,P,Q,P,PQ,PQ,P,Q,P,Q,T,T,F,T,T,T,T,T,F,F,T,F,F,F,F,T,T,T,F,T,F,F,F,T,F,F,T,T,谓词逻辑真值表,为刻画谓词与个体间的关系，在谓词逻辑中引入了两个量词，一个是全称量词（,x,），它表示“对个体域中的所有（或任一个）个体,x”,；另一个是存在量词（,x,），它表示“在个体域中存在个体,x”,。,例如谓词,P,（,x,）表示,x,是正数，,F,（,x,，,y,）表示,x,与,y,是朋友，则：,(,x)P(x),表示某个个体域中的所有个体,x,都是正数。,(,x)(,y)F,（,x,y,）表示对于个体域中的任何个体,x,，都存在个体,y,，,x,与,y,是朋友。,(,x)(,y)F,（,x,y,）表示在个体域中存在个体,x,，他与个体中的任何个体,y,都是朋友。,(,x)(,y)F,（,x,y,）表示在个体域中存在个体,x,与个体,y,，,x,与,y,是朋友。,(,x)(,y)F,（,x,y,）表示对于个体域中的任何两个个体,x,和,y,，,x,与,y,都是朋友。,2.,量词,定义,2,、可以按下述规则得到谓词演算的合式公式：,（,1,），单个谓词是合式公式，成为原子谓词公式；,（,2,），若,A,是合式公式，则,A,也是合式公式；,（,3,），若,A,，,B,都是合式公式，则,A,B ,A,B,A B,A,B,也都是合式公式；,（,4,），若,A,是合式公式，,x,是任一个体变元，则,(,x)A,和,(,x)A,也都是合式公式。,在合式公式中，连接词的优先级别是：,3.,谓词公式,另外，位于量词后面的单个谓词或者用括号括起来的合式公式成为量词的辖域，辖域内与量词中同名的变元成为约束变元，不受约束的变元称为自由变元。例如,(,x)(P(x,y,)Q,（,x,y,),R(x,y,),其中，,(,P(x,y,)Q,（,x,y,),是,(,x),的辖域，辖域内的变元,x,是受,(x),约束的变元，而,R,（,x,，,y,）中的,x,是自由变元，公式中的所有,y,都是自由变元。,在谓词公式中，变元的名字是无关紧要的，可以把一个名字换成另一个名字。但必须注意，当对量词辖域内的约束变元更名时，必须把同名的约束变元都统一改成相同的名字，且不能与辖域内的自由变元同名；当辖域内的自由变元改名时，不能改成与约束变元相同的名字。例如，对于公式,(,x)P,（,x,y,），可改名为,(,z)P,（,z,t,），这里把约束变元,x,变成了,z,，把自由变元,y,改成了,t,。,命题公式时谓词的一种特殊情况，它时用连接词把命题常量、命题变元连接起来所构成的合式公式。例如：,(P,Q),P(Q,R),(P Q),(Q R),(P R),都是命题公式。,思考,：“如果明天天晴我们就去郊游”用谓词逻辑可以怎么表示？,四、命题公式的解释,在命题逻辑中，对命题公式中各个命题变元的一次真值指派成为命题公式的一个解释,。,一旦解释后，根据各连接词的定义就可以求出命题公式的真值。,下面首先给出解释的定义，然后用例子说明如何构造一个解释以及如何根据解释求出谓词公式的真值。,定义,3,、设,D,为谓词公式,P,的个体域，若对,P,中的个体常量、函数合谓词按如下规定赋值：,为每个个体常量指派,D,中的一个元素；,为每个,n,元函数指派一个从,Dn,到,D,的映射，期中,Dn,(x1,x2,xn)/x1,xnD,为每个,n,元谓词指派一个从,Dn,到,F,T,的映射。,则称这些指派为公式,P,在,D,上的一个解释。,例,1,、设个体域,D,（,1,，,2,），求公式,(,x)(,y)P,（,x,y,）在,D,上的解释，并指出在每一种解释辖公式,A,的真值。,解,：在公式,A,中没有包括个体常量合函数，所以可直接为谓词指派真值，设为,P(1,，,1),T,，,P,（,1,，,2,）,F,，,P,（,2,，,1,）,T,，,P,（,2,，,2,）,F,这就是公式,A,在,D,上的一个解释。在此解释下，因为,x,1,时有,y,1,使,P,（,x,，,y,）的真值为,T,，,x,2,时也有,y,1,使,P(x,y,),的真值为,T,，即对于,D,中的梭鱼哦,x,都有,y,1,使,P,（,x,，,y,）的真值为,T,，所以在此解释下,A,的真值为,T,。,还可以对公式,A,中的谓词指派另外一组真值，设为,P(1,，,1),T,，,P,（,1,，,2,）,T,，,P,（,2,，,1,）,F,，,P,（,2,，,2,）,F,这是对公式,A,的另一个解释，在此解释下，对,D,中的所有,x,（即,x,1,与,x,2,）不存在一个,y,似的公式,A,的真值为,T,，所以在此解释下,A,的真值为,F,。,思考,：公式,A,在,D,上共有多少种解释？试列出其中的几个，并求出公式,A,的真值。,习题：,1,、不管黑猫白猫,抓住老鼠就是好猫。写出原命题的谓词表达式。（提示：设,C(x,):x,是猫,B(x,):x,黑的,W(x,):x,是白的,G(x,):x,是好的,M(x,):x,是老鼠,K(x,y):x,抓住,y,）,