02-离散谓词逻辑-1.1-1.3

1、第二章 谓词逻辑1命题逻辑存在的问题在命题逻辑中，把命题分解到原子命题为止，仅研究以原子命题为基本单位的复合命题之间的逻辑关系和推理。有些推理难以用命题演算确切表达。例如：“所有人总是要死的”“苏格拉底是人”“所以苏格拉底是要死的”PQRLs表示为：P, Q R 而(P Q) R并不是永真式命题逻辑存在的问题问题在于：各个命题之间的逻辑关系，不是体现在原子命题之间，而是体现在构成原子命题的内部成分之间，即体现在命题结构的更深层次上所以，在研究某些推理时，有必要对原子命题做进一步分析，分析出其中的个体词、谓词和量词，研究它们的形式结构和逻辑关系，正确的推理形式和规则这就是谓词逻辑（Lp）的基本内

2、容命题逻辑存在的问题例如：“所有人总是要死的”“苏格拉底是人”“所以苏格拉底是要死的”“人”这个群体具有“是要死的”的特性“苏格拉底”是“人”这个群体中的一个个体“苏格拉底”具有“人”这个群体的“是要死的”特性第一节 个体、谓词和量词第一节 个体、谓词和量词命题是具有真假意义的陈述句，从语法上分析，一个陈述句由主语和谓语两个部分组成。在谓词逻辑中，为揭示命题内部结构及不同命题的内部结构关系，就按这两个部分进行分析主语称为个体或客体谓语称作谓词个体和谓词一、个体和谓词定义：在原子命题中，所描述的对象，称为个体用以描述个体性质，或个体间关系的部分，称为谓词个体个体，是指可以独立存在的事物，可以是具

3、体的，也可以是抽象的。例如：李明、香蕉、电视机、精神、思想，等表示特定的个体，称为个体常元通常用 a, b, c, 或ai, bi, ci, 表示例如：李明、字母A、数字5表示不确定的个体，叫作个体变元通常用 x, y, z, 或xi, yi, zi, 表示例如：花朵、星星、男生、学校谓词当谓词与一个个体相关时，刻划了该个体的性质例如：5是质数，A是字母一元谓词当谓词与两个或两个以上个体相关时，刻划了个体间的关系例如：李明生于北京，10比5大二元谓词谓词一般用大写字母 P, Q, R, 或 Pi, Qi, Ri, 表示命题的谓词形式二、命题的谓词形式单独的个体和谓词不能构成命题命题的表示：将表

4、示个体的小写字母，写在表示谓词的大写字母右侧的括号里。命题的谓词形式“李明是大学生”其中：李明是个体，用a表示“是大学生”是谓词，用S表示则该命题表示为 S(a)：李明是大学生“张华出生在北京”其中：张华和北京是个体，用a表示张华，用b表示北京“出生在”是谓词，用B表示则该命题表示为 B(a, b)：张华出生在北京命题的谓词形式定义：一个原子命题，用一个谓词P和n个有次序的个体常元 a1, a2, , an 表示成P (a1, a2, , an)，称为（原子）命题的谓词形式注意：命题的谓词形式中的个体出现的次序影响命题的真值。例如：P：比大，则 P(10, 5)：10比5大，真值为真而P(5,

5、 10)：5比10大，真值为假原子谓词三、原子谓词将原子命题的谓词形式进行抽象，例如n个个体常元a1, a2, , an 替换成n个个体变元x1, x2, , xn，这样便得到了一种关于命题结构的新表达形式 P (x1, x2, , xn) ，称为n元原子谓词 。例如： S(a) S(x) ：x是学生原子谓词定义：由一个谓词P和n个个体变元x1, x2, , xn组成的P (x1, x2, , xn) 称为n元原子谓词或n元命题函数简称n元谓词 。个体变元的取值范围叫作个体域或论域当n=1时，称为一元谓词当n=2时，称为二元谓词特别的，当n=0时，称为零元谓词，即命题原子谓词n元谓词并不是命题

6、，只有当所有的命题变元都用个体常元替代时，才能成为一个命题而个体变元在哪个论域取值，对命题的真值有影响例如： S(x) ：x是大学生若x的论域是某大学的全体学生，则S(x) 为真若x的论域是某小学的全体学生，则S(x) 为假若x的论域是商场的全体顾客，则S(x)的真值不确定原子谓词把一个n元谓词中的每个个体的论域综合在一起作为n元谓词的全总论域当一个命题未指定论域时，一般将全总论域作为其论域。这时往往需要一个一元谓词 P(x) 来限定个体变元x的取值范围，将 P(x) 称为特性谓词。例如： S(x) ：x是学生N(x) ：x是自然数量词四、量词对谓词的理解，如 S(x) ：x是学生（x是某单位

7、的职工）可以理解为：某单位的职工都是学生或者：某单位存在一些职工是学生为了避免歧义，表达“所有的”或者“存在一些”等表示数量的词，我们引进量词这个概念。量词定义1： ：全称量词符。表示“所有的”、“对每一个”、 “对任何一个”等词语x ：称为全称量词，x叫作指导变元( x) P(x)( x) P(x) ( x) P(x) ( x) P(x)对于一切x，P(x)为真对于一切x， P(x)为真并非对于一切x，P(x)为真并非对于一切x， P(x)为真量词定义2： ：存在量词符。表示“存在一些”、“至少有一个”、 “对于一些”等词语x ：称为存在量词，x叫作指导变元(x) P(x)(x) P(x)

8、(x) P(x) (x) P(x)存在x，使P(x)为真存在x，使 P(x)为真并非存在x，使P(x)为真并非存在x，使 P(x)为真量词定义3：!：存在唯一量词符。表示“存在唯一” 等词语!x：称为存在唯一量词，x叫作指导变元(!x) P(x)(!x) P(x) (!x) P(x) (!x) P(x)存在唯一的x，使P(x)为真存在唯一的x，使 P(x)为真并非存在唯一的x，使P(x)为真并非存在唯一的x，使 P(x)为真量词例2.1 试用量词、谓词表示下述命题所有学生都热爱祖国S(x)：x是学生（特性谓词）L(x)：x热爱祖国命题表示为：(x) ( S(x) L(x) )对于全称量词，特性

9、谓词作为蕴涵式的前件出现(x) ( S(x) L(x) )量词凡是实数，不是大于零，就是等于零或小于零R(x)：x是实数（特性谓词）B(x)：x大于零E(x)：x等于零S(x)：x小于零命题表示为：(x) ( R(x) B(x)E(x)S(x) )量词一些大学生有远大理想S(x)：x是大学生（特性谓词）P(x)：x有远大理想命题表示为：(x) ( S(x) P(x) )对于存在量词，特性谓词作为合取项出现( x) ( S(x) P (x) )量词所有的猫都是动物 （1）对任何个体域来讲，命题（1）都为真。设个体域E是 花虎，黄咪， 遍及个体域E命题（1）为真。令命题（1）正确的表达成：(x)

10、( C(x) A(x) )用个体域中任何元素去取代个体变元x，则都会获得一个真命题若选用合取式的形式把它表示成 (x) ( C(x) A(x) )用个体域中的 去取代变元x，则由C(x) A(x) 所得到的命题真值必定都为假不可以选用合取式来表达“所有的A是B” 形式的命题总结：量词与特性谓词的搭配还有一定的规律，即全称量词后跟一个条件式，特性谓词作为其前件出现；存在量词后跟一个合取式，特性谓词作为一个合取项出现C（x）：x是猫A（x）：x是动物量词一些猫是黑色的 （2）设个体域E仍然是 花虎，黄咪， 并设“花虎”是杂色的，“黄咪”是黄色的令在这种情况下个体域E中没有黑色的猫，因此命题（2）的

11、真值为假用合取式把命题（2）正确的表达成：(x) ( C(x) B(x) ) （3）由于个体域中没有黑色的猫，所以命题（3）的真值为假若选用条件命题公式的形式把它表示成 ( x) ( C(x) B(x) )用个体域中的 去取代变元x，则由C(x) B(x) 所得到的命题真值为真。（前件为假，善意推定）不可以选用条件命题公式的形式来表达“一些A是B” 形式的命题B（x）：x是黑色的 C（x）：x是猫总结：量词与特性谓词的搭配还有一定的规律，即全称量词后跟一个条件式，特性谓词作为其前件出现；存在量词后跟一个合取式，特性谓词作为一个合取项出现量词没有不犯错误的人P(x)：x是人（特性谓词）W(x)：

12、x犯错误命题表示为： (x) ( P(x) W (x) ) (x) ( P(x) W (x) )量词有些人对食物过敏P(x)：x是人（特性谓词）Q(x)：x对食物过敏命题表示为： (x) ( P(x) Q (x) )或者： P(x)：x是人， F(x)：x是食物 Q(x, y)：x对y过敏命题表示为：(x) (y) (P(x)F(y) Q (x, y)量词若一个谓词中的所有个体变元都量化了，该谓词就变成了命题。例如：P(x)：x是人， F(x)：x是食品Q(x, y)：x对y过敏 P(x)F(y)Q (x, y) 不是命题 而(x) (y) (P(x)F(y)Q (x, y) 是命题(x) (

13、y) (P(x)F(y) Q (x, y) 也是命题第二节 谓词公式与翻译第二节 谓词公式与翻译一、谓词公式项定义：项由下列规则组成 个体常元和个体变元是项若f是n元函数，且t1, t2, , tn是项，则f(t1, t2, , tn)是项所有项都由1) 2)生成项例如：f(x, y) 表示x+y，N(x)表示x是自然数 N( f(2,3) ) 即 N(5) 表示5是自然数P(x)：x是教授，f(x)：x的父亲，a：李明P( f(a) )：李明的父亲 是教授I(x)：x是整数，f(x)=x2-1，g(x)=(x+1)(x-1)E(x, y)：x=y 则 x2-1=(x+1)(x-1)(x是整数

14、)表示为： (x) ( I(x) E( f(x), g(x) ) )谓词表示个体的性质，它的取值T,F函数表示个体经过运算后得到的值，可能是任意值谓词公式谓词公式P (x1, x2, , xn)是n元原子谓词， t1, t2, , tn是项，称P (t1, t2, , tn)是原子谓词公式，简称原子公式合式谓词公式是由下列规则形成的字符串原子公式是合式谓词公式若A是合式谓词公式，则( A)是合式谓词公式若A、B是合式谓词公式，则(AB)，(AB)，(AB)，(AB) 也是合式谓词公式若A是合式谓词公式，x是个体变元，则(x) A和 (x) A都是合式谓词公式只有有限次使用1)4)形成的才是合式

15、谓词公式谓词公式例如：(x) P(x)， (x)(S(x) P(x)， P(x)Q(f(x) 都是合式谓词公式(x) (P(x) Q(x)， (x)( P(x)等都不是合式谓词公式命题公式是合式谓词公式的一个特例谓词公式的翻译二、谓词公式的翻译（符号化）把一个文字叙述的命题用谓词公式表述出来正确理解命题把每个原子命题分解成个体、谓词和量词在全总论域讨论时，要给出特性谓词找出恰当量词全称量词将特性谓词作为蕴涵式的前件存在量词将特性谓词作为合取项用恰当的联结词把命题表示出来谓词公式的翻译例2.2 用谓词公式表述下述命题张三和李四都是大学生个体：a：张三，b：李四谓词：S(x)：x是大学生符号化为：

16、S(a) S(b)李华是象棋迷或围棋迷个体：a：李华谓词：P(x)：x是象棋迷，Q(x)：x是围棋迷符号化为：P(a) Q(a)谓词公式的翻译汤姆和杰克是亲兄弟个体：a：汤姆，b：杰克谓词：B(x, y)：x和y是亲兄弟符号化为： B(a, b)没有最大的自然数可理解为：对于任何一个自然数，都存在比它大的自然数谓词：N(x)：x是自然数，B(x, y)：x比y大符号化为： (x) ( N(x) (y)(N(y)B(y, x) )谓词公式的翻译今天有雨雪，有些人会跌跤谓词：R：今天有雨，S：今天有雪，P(x)：x是人F(x)：x会跌跤符号化为： RS (x)( P(x) F(x) )尽管有人聪明

17、，但未必所有人都聪明谓词：P(x)：x是人，F(x)：x聪明符号化为： (x)( P(x)F(x) ) (x) ( P(x) F(x) )第三节 约束变元与自由变元第三节 约束变元与自由变元定义：给定一个谓词公式A，其中包含子公式形如(x)B(x)或(x)B(x) ，则称它为A的x约束部分称B(x)为相应量词的作用域或辖域在辖域B(x)中，x的所有出现称为约束出现，x为约束变元B(x)中不是约束出现的其他个体变元称为自由出现，这些变元称为自由变元约束变元与自由变元确定量词的辖域：若量词后面有括号则括号内的子公式就是该量词的辖域若量词后面无括号则与量词邻接的子公式就是该量词的辖域约束变元与自由变

18、元例2.3 指出下面合式公式的量词辖域、个体变元的约束出现和自由出现(x) ( P(x) (y) Q(x, y) )(x)的辖域是( P(x) (y) Q(x, y) )其中x和y都是约束出现(y)的辖域是Q(x, y)其中x是自由出现，y是约束出现对应整个公式来说，x约束出现1次，自由出现1次，y约束出现2次约束变元与自由变元(x) H(x) L (x, y)(x)的辖域是H(x)其中x是约束出现对于整个公式而言，x约束出现1次，自由出现1次，y自由出现1次约束变元与自由变元(x) (y)(P(x, y) Q (y, z) (x) R (x, y)(x)的辖域是(y)(P(x, y) Q (

19、y, z)其中x和y是约束出现，z为自由出现(y)的辖域是 (P(x, y) Q (y, z)其中x和z是自由出现，y为约束出现(x)的辖域是R(x, y)其中x是约束出现，y是自由出现对于整个公式而言，x和y既为约束出现又为自由出现，z为自由出现约束变元与自由变元一个公式的约束变元所使用的名称符号是无关紧要的。故： (x) P(x) 与(y) P(y) 具有相同的意义。设A（x）表示x不小于0，那么：(x) A(x)表示一切x都使得x不小于0(y) A(y)表示一切y都使得y不小于0(z) A(z)表示一切z都使得z不小于0这三个命题在实数域中都表示假命题“一切实数均不小于0”；同理(x)P(x) 与(y)P(y)的意义亦相同。为此：我们可以对公式中的约束变元更改名称符号，这种遵守一定规则的更改，称为约束变元的改名。约束变元与自由变元为了避免个体变元既作为约束变元，又作为自由变元出现代来的混乱，引入以下两个规则：约束变元改名规则：将量词辖域中的某个约束出现的个体变元以及相应的指导变元，改名为本辖域中未曾出现过的个体变元（最好是公式中没有出现过的个体变元），其他不变。目的：使得一个变元在一个公式中只呈一种形式出现（呈自由出现或呈约束出现）约束变元与自由变元例2.4