《第二章谓词逻辑》由会员分享，可在线阅读，更多相关《第二章谓词逻辑（112页珍藏版）》请在金锄头文库上搜索。
1、离散数学,国际学院 孙延鹏 Email：meng_yu_,2018/9/9,国际学院,2,解：假设,(著名的苏格拉底三段论)设自然语言中的三个命题： 所有的人都是要死的； 苏格拉底是人。 所以，苏格拉底是要死的。,P：所有的人都是要死的；Q：苏格拉底是人。R：所以，苏格拉底是要死的。则有：PQ R但在上述式子中，取P：1，Q：1，R：0，此时，R不是P，Q的逻辑结果。,第二章谓词逻辑,2018/9/9,国际学院,3,一个推理，得出矛盾的结论，问题在哪里呢? 问题就在于这类推理中，各命题之间的逻辑关系不是体现在原子命题之间，而是体现在构成原子命题的内部成分之间，即体现在命题结构的更深层次上。对此
2、，命题逻辑是无能为力的。所以，在研究某些推理时，有必要对原子命题作进一步分析，分析出其中的个体词，谓词和量词，研究它们的形式结构的逻辑关系、正确的推理形式和规则，这些正是谓词逻辑的基本内容。,2018/9/9,国际学院,4,2.1谓词的基本概念与表示,例2.1：如有句子：张红是一个大学生；王南是一个大学生；李华是一个大学生。 则在命题中必须要用三个命题P，Q，R来表示。,但是，它们都具有一个共同的特征： “是一个大学生” 因此，若将句子分解成： “主语谓语” 用P表示“是一个大学生”，P后紧跟“某某人”。则上述句子可写为：P(张红)；P(王南)；P(李华)。一般地， P(x)：x是一个大学生。
3、,P：谓词 x：个体词 P(x)：命题函数,2018/9/9,国际学院,5,2.1.1、谓词定义2.1：在句子中，可以独立存在的客体称为个体词，而用以刻划客体的性质或客体之间的关系即是谓词。个体词用a,b,c,.x,y,z,a1,a2,a3等表示，谓词用A,B,C,.P，Q，R,A1,A2,A3,等表示。,例上海，教师，*班级，电子计算机等等都是个体词。,2018/9/9,国际学院,6,成都是一个省会城市。 离散数学是计算机的基础课程。 刘东是一个游泳健将。 人是聪明的。,例2.2,2018/9/9,国际学院,7,表示具体或特定的个体词称为个体常量，一般个体词常量用带或不带下标的小写英文字母a
4、,b,c,a1,a2,a3.,表示。 表示抽象的或泛指的个体词称为个体变量，一般用带或不带下标的小写英文字母x,y,z,.,x1,x2,x3,表示。 个体词的取值范围称为个体域或论域，常用D表示。而宇宙间的所有个体域聚集在一起所构成的个体域称为全总个体域。 设D为非空的个体域，定义在Dn(表示n个个体都在个体域D上取值)上取值于0,1上的n元函数，称为n元命题函数或n元谓词,记为P(x1,x2,xn)。此时，个体变量x1,x2,xn的定义域都为D，P(x1,x2,xn)的值域为0，1。,定义2.2,2018/9/9,国际学院,8,设有如下命题：P：上海是一个现代化的城市；Q：甲是乙的父亲；R：
5、3介于2和5之间。T：李兰与高翔是同班同学。 解：设有如下命题函数：C（x）： x是一个现代化的城市；F（x，y）： x是y的父亲；B（x，y，z）：x介于y和z之间；S（x，y）： x与y是同班。,例2.3,2018/9/9,国际学院,9,则上述命题可表示为：P：C（上海）Q：F（甲，乙）R：B（3，2，5）T：S（李兰，高翔） 上述符号P、Q、R、T表示的是命题，而符号C（上海）、F（甲，乙）、B（3，2，5）、S（李兰，高翔）则是命题所对应的谓词表示形式，它们都有确切的真值。,2018/9/9,国际学院,10,a:上海；b:甲，c:乙；d:3，e:2，f:5；g:李兰，h:高翔。则上述命
6、题又可表示为：P：C（a）Q：F（b，c）R：B（d，e，f）T：S（g，h）,2018/9/9,国际学院,11,例2.4,设S（x）表示：x是大学生。 D:某大学班级中的学生，则S(x)是永真式。 D:某中学里班级中的学生，则S(x)是永假式。 D: x是所有的中国人，则这些人中有的是大学生，有的不是大学生，那么对有些人来讲，S（x）为真，对另外一些x来说，S（x）为假。,2018/9/9,国际学院,12,谓词中个体词的顺序是十分重要的，不能随意变更。 一元谓词用以描述某一个个体的某种特性或性质，而n元谓词则用以描述n个个体之间的关系。 0元谓词(不含个体词的)实际上就是一般的命题。,几个结
7、论,2018/9/9,国际学院,13,4)具体命题的谓词表示形式和n元命题函数(n元谓词)是不同的，前者是有真值的，而后者不是命题，它的真值是不确定的。如上例中C(上海)是有真值的，但C(x)却没有真值。 5)一个n元谓词不是一个命题，但将n元谓词中的个体变元都用个体域中具体的个体取代后，就成为一个命题。而且，个体变元在不同的个体域中取不同的值对是否成为命题及命题的真值有很大的影响。,2018/9/9,国际学院,14,2.2量词,例2.5符号化下述命题： 所有的老虎都要吃人； 每一个人都会犯错误； 有一些人会摔跤； 有一些人是大学生； 每一个带伞的人都不怕雨； 有一些自然数是素数。 上述每一个
8、描述量词的语句下划有“下划线”。,2018/9/9,国际学院,15,例2.5(续),解：设立如下谓词：R（x）：x会吃人； P（x）：x会犯错误；N（x）：x会摔跤；Q（x）：x是大学生；C（x）：x不怕雨；S（x）：x是素数。,则有：（1）所有的x，R（x） x老虎；（2）每一个x，P（x） x人；（3）有一些x，N（x） x人；（4）有一些x，Q（x） x人；（5）每一个x，C（x） x带伞的人；（6）有一些x，S（x） x 自然数。,2018/9/9,国际学院,16,量词的定义,上述一系列例子，都仅仅只符号化了一部分内容，而对句子中的“对每一个”，“对任意的”，“有一些”等等无法用谓词来
9、表示，这些都是与个体词的数量有关的语句。为了把它们符号化，引进如下两个符号： (x):所有的x； (x)：有些x； 任意的x； 至少有一个x； 一切的x； 存在x； 每一个x；等等。 等等。 补充：符号!称为存在唯一量词符，用来表达“恰有一个”、“存在唯一”等词语；!x称为存在唯一量词，称x为指导变元。,2018/9/9,国际学院,17,量词的定义,定义2.3(x)称为全称量词。(x)为存在量词,其中的x称为作用变量。一般将其量词加在其谓词之前，记为(x)F(x),(x)F(x)，此时，F(x)称为全称量词和存在量词的辖域。仅跟量词之后的谓词为此量词的辖域,2018/9/9,国际学院,18,例
10、2.5(续),(x)R(x) (x老虎) (x)P(x) (x人) (x)N(x) (x人) (x)Q(x) (x人) (x)C(x) (x带伞的人) (x)S(x) (x自然数) 三段论中的P也可表示为：(x)(H(x)D(x)。,在例2. 5中，利用量词则有：,2018/9/9,国际学院,19,不便之处,从书写上十分不便，总要特别注明个体域。 在同一个比较复杂的句子中，对于不同命题函数中的个体可能属于不同的个体域，此时无法清晰表达。 如讨论求上述例中(1)和(3)的合取而得的新命题有： (x)R(x)(x)Q(x)。 其中，全称量词中的x苹果，存在量词中的x实数。 有时，由于个体域的注明不
11、清楚，造成无法确定其真值。对于同一个公式，不同的个体域有可能带来不同的真值。如(x)(x65)， (1)、在实数范围内时，确有x-1使得x65，因此，(x)(x65)为“真”。(2)、在正整数范围内时，则找不到任何x，使得x65为“真”，所以，(x)(x65)为“假”。,2018/9/9,国际学院,20,全总个体域,对于全称量词，刻划其对应个体域的特性谓词作为蕴涵的前件加入。 对于存在量词，刻划其对应个体域的特性谓词作为合取式之合取项加入。,基于上述情况，必需要对个体域进行统一，全部使用全总个体域，此时，对每一个句子中个体变量的变化范围用一定之特性谓词刻划之。而统一成全总个体域后，此全总个体域
12、在谓词公式中就不必特别说明，常常省略不记。同时，这种特性谓词在加入到命题函数中时必定遵循如下原则：,2018/9/9,国际学院,21,例2.5(续),解： U(x)：x是老虎； (x)(U(x)R(x) H(x)：x是人； (x)(H(x)P(x) H(x)：x是人； (x)(H(x)N(x) H(x)：x是人； (x)(H(x)Q(x) M(x)：x是带伞的人； (x)(M(x)L(x) T(x)：x是自然数； (x)(T(x)S(x),对于例2.5中的例子运用特性谓词描述。,上述三段论可完整翻译为： (x)(H(x)D(x)，H(S)D(S),2018/9/9,国际学院,22,2.3 谓词
13、公式与解释,同命题演算一样，在谓词逻辑中也同样包含命题变元和命题联结词，为了能够进行演绎和推理，为了对谓词逻辑中关于谓词的表达式加以形式化，利用联结词、谓词与量词构成命题函数，我们必须引入公式的概念。,2018/9/9,国际学院,23,四类符号,常量符号：一般用a,b,c,a1,b1,c1,来表示，它可以是D中的某个元素; 变量符号：一般用x,y,z,x1,y1,z1,来表示.它可以取值于D中的任意元素； 函数符号（普通函数）：一般用f,g,h,f1,g1,h1,来表示。n元函数符号f(x1,x2,.xn)可以是DnD的任意一个函数； 谓词符号（命题函数） ：一般用P,Q,R,.,P1,Q1,
14、R1,.来表示。n元谓词符号P(x1,x2,.xn)可以是Dn0,1的任意一个谓词。,2018/9/9,国际学院,24,例2.6,（1）设：f（x，y）=x+y； N（x）:x是自然数。 则f(4，6)表示个体常量“10”， 而N(f(4，6)表示“10”是自然数。 （2）设： f(x)：x的父亲； P（x）：x是教授。c ：周红 则P(f(c)表示“周红的父亲是教授”这一命题。,2018/9/9,国际学院,25,2.3.1谓词的合式公式,定义2.6 满足下列条件的表达式，称为合式公式,简称公式。,定义2.5：形如Q,Q(x),Q(x,y),Q(a,y)，Q(f(x),y)等公式是原子谓词公式
15、，简称原子公式。,原子公式是合式公式； 若G，H是合式公式，则(G)、(H)、(GH)、(GH)、(GH)、(GH)也是合式公式； 若G是合适公式，x是个体变量，则(x)G、(x)G也是合式公式； 仅仅有1)-3)产生的表达式才是合式公式。,2018/9/9,国际学院,26,(P(x)(Q(x,y)R(x,a,f(z)(p(x)R(y)(x)(P(x) 等都是公式。 而(P(x)R(x)(x)(x)P(x) 等则不是公式。,例2.7,2018/9/9,国际学院,27,(1)天下乌鸦一般黑； (2)那位身体强健的、用功的、肯于思考的大学生，解决了一个数学难题； (3)张强和李平都是足球运动员； (4)每个实数都存在比它大的另外的实数； (5)并非所有的动物都是脊椎动物； (6)尽管有人很聪明，但未必一切人都聪明； (7)对于任意给定的0，必存在着0，使得对任意的x，只要|x-a|，就有： |f(x)-f(a)|成立。,例2.8 符号化下述语句,2018/9/9,国际学院,28,解：（1）天下乌鸦一般黑；设F（x）：x是乌鸦；G（x，y）：x与y一般黑。 则句子(1)可完整地符号化为：(x)(y)(F(x)F(y)G(x，y) 或 (x)(y)(F(x)F(y)G(x,y),
