第2章 谓词逻辑(一)

1、离 散 数 学 戎 玫 20059 第2章 谓词逻辑2.1 个体、谓词与量词2.2 谓词公式2.3 谓词演算的等价式与蕴含式2.4 前束范式2.5 谓词逻辑的推理理论2.1 .1 个体 苏格拉底推论所有的人总是要死的苏格拉底是人苏格拉底总是要死的将原子命题进一步细分，分解出个体、谓词和量词，以表达个体与总体的内在联系和数量关系，即谓词逻辑研究的内容。2.1 个体、谓词与量词2.1 .1 个体考察下面的三个原子命题： 李玲是优秀共产党员。 张华比李红高。 小高坐在小王和小刘的中间。个体是指所研究对象中可以独立存在的具体的或抽象的客体。个体常用小写英文字母或小写英文字母带下标表示，叫做个体标识符。

2、 表示具体或特定个体的标识符称个体常元。例如：李玲、张华可如下表示： a：李玲 b：张华 2.1 .1 个体将表示任意个体或泛指某类个体的标识符称为个体变元，常表示为x、y、z、等或这些英文字母带下标。个体变元的变化范围称为个体域或论域。个体域可以是有穷集合，也可以是无穷集合，包含任意个体域的个体域称为全总个体域，它是由宇宙间一切对象组成的集合。在本书中，如无特别说明，所采用的都是全总个体域。 2.1.2谓 词刻划个体性质或几个个体关系的模式叫做谓词。谓词常用大写英文字母表示，叫做谓词标识符。例如可以用F，G，H表示前面三个命题中谓词： F：是优秀共产党员。 可以分解成为个体“李玲”和“是优秀

3、共产党员”两部分。“是优秀共产党员”是用来描述个体“李玲”的性质； G：比高。 H：坐在和的中间。 2.1.2谓 词把与一个个体相关联的谓词叫做一元谓词。把与两个个体相关联的谓词叫做二元谓词。把与三个个体相关联的谓词叫做三元谓词。一般的，把与n个个体相关联的谓词叫做n元谓词。 F是一元谓词； G是二元谓词； H是三元谓词； 2.1.2谓 词设F是一元谓词，a是个体常元，用F(a)表示个体常元a具有性质F；设G是二元谓词，a,b是个体常元，用G(a,b)表示个体常元a和b具有关系G；于是上面三个命题就表示为： F(a)：李玲是优秀共产党员。 G(b,c)：张华比李红高。 H(d,e,f)：小高坐

4、在小王和小刘的中间。将谓词后面填上相关联的个体常元所得的式子叫做谓词填式。F(a)，G(b,c)，H(d,e,f)都是谓词填式。谓词填式表示的是命题。 2.1.2谓 词类似的，用F(x)表示个体变元x具有性质F ，F(x)叫做一元命题函数；用G(x, y)表示个体变元x和y具有关系G ，G(x，y)叫做二元命题函数；用P(x1,x2,xn)(n1)表示个体变元x1, x2, ,xn具有关系P。 P(x1,x2, ,xn) 为n元命题函数。命题函数没有确定的真值，它不是命题。只要用个体常元取代所有的个体变元，就得到了命题。 2.1.2谓 词例，H(x,y)：x+y0，此命题函数是否为命题？令 a

5、：5, b：7 H(a,b) 是否为命题？真值？用个体常元取代命题函数的所有个体变元所得到的表达式就是谓词填式，谓词填式也叫做0元命题函数。F(a)，G(b,c)，H(d,e,f)都是0元命题函数，它们都是命题。命题逻辑中的命题均可以表示为谓词逻辑中的0元命题函数(谓词填式)，命题成为命题函数的特例。 2.1.2谓 词【例2.1】将下列命题符号化，并讨论它们的真值。 2与3都是偶数。 如果5大于3，则2大于6。 解： 设F(x)：x是偶数。 a：2，b：3 该命题符号化为： F(a)F(b) F(b)表示3是偶数，它是个假命题。所以F(a)F(b)为假。 设G(x,y)： x大于y a：5，b

6、：3，c：2，d：6 该命题符号化为：G(a,b)G(c,d) G(a,b)表示5大于3，它是真命题。G(c,d)表示2大于6，这是个假命题。所以G(a,b)G(c,d)为假。 2.1.3 量词量词分两种： 全称量词全称量词符号化为“”。 即“一切的”，“所有的”，“每一个” 等。用(x)，(y)等表示个体域里的所有个体，(x)F(x) 表示个体域中的所有个体都有性质F。 存在量词存在量词符号化为“”。即“存在”，“有一个”，“有些” 等。用(x)，(y)等表示个体域里有些个体，用(x)F(x) 表示在个体域中存在个体具有性质F。全称量词与存在量词统称为量词。 2.1.3 量词【例2.2】个体

7、域是人类集合，对下列命题符号化。 凡人要死。 有的人是研究生。解： 令F (x)：x要死。 命题“凡人要死。”符号化为：(x)F (x) 令G(x)：x是研究生。 命题“有的人是研究生。”符号化为：(x)G(x) 在命题函数前加上量词(x)和(x)分别叫做个体变元x被全称量化和存在量化。如果对命题函数中所有命题变元进行全称量化或存在量化，该函数就变成了命题。2.1.3 量词【例2.3】对下列命题符号化，并在，三个个体域中考察命题的真值。 命题： 所有数小于5。 至少有一个数小于5。 个体域： -1，0，1，2，4 3，-2，7，8 15，20，24 解：设L(x)：x小于5。 “所有数小于5。

8、”符号化为：(x) L(x) 在个体域，中，它们的真值分别为：真，假，假。 “至少有一个数小于5。”符号化为：(x)L(x)在个体域，中，它们的真值分别为：真，真，假。2.1.3 量词设个体域为D=-2,3,6，谓词P(x)：x3，G(x)：x5，R(x)：x7，求下列各谓词公式的真值。1、 (x)(P(x) G(x) 。2、 (x)(R(x) P(x)G(5)3、 (x)(P(x)G(x)解：2.1.3 量词命题函数中的个体变元量化以后变成命题，其真值与个体域的选择有关，为了统一我们使用全总个体域，而对于其它个体域用一个谓词来表示，即特性谓词。特性谓词：用一个谓词来表示除全总个体域外的特殊的

9、个体域。特性谓词加入的方法为： 对全称量词，特性谓词作为条件命题的前件加入。 对存在量词，特性谓词作为合取项加入。2.1.3 量词【例2.4】对下列命题在，两个个体域中符号化。 命题： 所有老虎是要吃人。 存在一个老虎要吃人。 个体域： 所有老虎组成的集合。 全总个体域。解：设A(x)：x是要吃人的。个体域为所有老虎的集合。 符号化为 (x)A(x) 符号化为 (x)A(x) 个体域为全总个体域。设特性谓词T(x)：x是老虎。 符号化为 (x)(T(x)A(x) 符号化为 (x) (T(x)A(x)2.1.3 量词有些自然数是素数。金子是闪光的，但闪光的并不都是金子。所有运动员都钦佩某些教练员

10、。解：设N(x)：x是自然数。 P(x)：x是素数。 (x)(N(x) P(x)解：设G(x)：x是金子。 S(x)：x是闪光的。 (x)(G(x)S(x)(x)(S(x)G(x)解：设L(x)：x是运动员。 C(x)：x是教练员。 A(x,y)：x钦佩y。 (x)(L(x)(y)(C(y)A(x，y) 2.2.1 谓词公式定义2.2.1 按下列规则构成的表达式称为谓词演算的合式公式，简称谓词公式。 谓词演算的原子公式是合式公式。 若A是合式公式，则A是合式公式。 若A和B是合式公式，则(AB)，(AB)，(AB)和(AB)是合式公式。 如果A是合式公式，x是A中出现的任意个体变元，则(x)A

11、，(x)A是合式公式。 只有有限次地应用、所得的公式是合式公式。 2.2.1 谓词公式谓词公式也有以下约定： 最外层的括号可以省略。 如果按、在运算中的优先级别，省略括号后不改变原来的运算次序，可以省略括号，但量词后面括号不能省略。 2.2.1 谓词公式【例2.5】并非每个实数都是有理数。 解：设R(x)：x是实数 Q(x)：x是有理数 该命题符号化为：(x)(R(x)Q(x)【例2.6】没有不犯错误的人。 解：设M(x)：x是人 F(x)：x犯错误 符号化为：(x) (M(x)F(x)【例2.7】并不是所有的兔子都比所有的乌龟跑得快。 解：设F(x)：x是兔子。 G(x)：x是乌龟。 H(x

12、,y)：x比y跑得快。 该命题符号化为：(x) (y) (F(x)G(y)H(x,y) 2.2.2约束变元与自由变元定义2.2.2 如果A是谓词公式B的一部分且是谓词公式，则称A是B的子公式。定义2.2.3 紧接量词以后的最小子公式叫做该量词的辖域或作用域。定义2.2.4 量词(x)和(x)中的x叫做该量词的指导变元或作用变元。定义2.2.5 量词(x)和(x)的辖域内x的一切出现叫约束出现，x叫做约束变元；约束变元以外的其它变元的出现叫自由出现，自由出现的变元叫自由变元。2.2.2约束变元与自由变元【例2.10】说明下列各式量词的辖域，找出约束变元和自由变元。 (x)P(x)Q(y) (x)

13、 (P(x)(y)Q(x,y) (x) P(x)(y)Q(x,y) (x)(y)(P(x,y)Q(y,z) (x) R(x,y) 解：(x)的辖域为P(x)，x是约束变元，y是自由变元。 (x)的辖域为P(x)(y)Q(x,y)，(y)的辖域为Q(x,y)，x和y都是约束变元，无自由变元。 (x)的辖域为P(x)，(y)的辖域为Q(x,y)，P(x)中的x和Q(x,y) 中的y是约束变元，Q(x,y)中的x是自由变元。 (x)的辖域为(y)(P(x,y)Q(y,z)，(y)的辖域为P(x,y)Q(y,z)，(x)的辖域为R(x,y)，x是约束变元，z是自由变元，(P(x,y)Q(y,z)中的y

14、是约束变元，R(x,y)中的y是自由变元。2.2.2约束变元与自由变元换名规则： 对约束变元可以换名，其更改变元名称的范围是量词的指导变元，以及该量词辖域中的所有该变元，公式的其余部分不变。 换名时一定要更改成辖域中没有出现的变元名，最好是公式中没有的变量名。代入规则是： 对于谓词公式中的自由变元可以代入，代入时需对公式中该变元自由出现的每处进行。 代入的变元与原公式中其他变元的名称不能相同。2.2.2约束变元与自由变元【例2.11】对(x)(y)(P(x,y)Q(y,z)(x) R(x,y)中的约束变元y换名。 解：用u置换约束变元y。换名后为： (x)(u)(P(x,u)Q(u,z)(x)

15、 R(x,y) 不能换成： (x)(u)(P(x,u)Q(y,z)(x) R(x, y) 也不能换成：(x)(z)(P(x, z)Q(z,z)(x) R(x,y) 【例2.12】对(x)(P(y)R(x,y)(y)Q(y) 中的自由变元y进行代入。 解：用z代换y，代入后为： (x)(P(z)R(x,z)(y)Q(y) 不能换成： (x)(P(x)R(x,x)(y)Q(y) 或 (x)(P(z)R(x,y)(y)Q(y)2.2.2 约束变元与自由变元自然数有以下三条公理：1、每个数都有唯一的一个数是它的后继数。2、没有一个数使数1是它的后继数。3、每个不等于1的数都有唯一的一个数是它的直接先驱

16、数。解：设N(x)：x是自然数。 S(x,y)：y是x的后继(x是y的先驱)。1、 (x)(N(x)(y)(N(y)S(x，y)(z)(zy) N(z)S(x,z) 2、 (x)(N(x)S(x,1) 3、 (x)(N(x) S(x,2) (y)(N(y)S(y，x) (z)(zy)N(z)S(z,x) 2.3谓词演算的等价式与蕴含式定义2.3.1 设A是谓词公式，如果对A的任何赋值，A都为真，则称A是有效的或永真的。定义2.3.2 设A是谓词公式，如果对A的任何赋值，A都为假，则称A是不可满足的或永假的。定义2.3.3 设A是谓词公式，如果至少有一组赋值使A为真，则称A是可满足的。定义2.3

17、.4 设A、B是任意两个谓词公式，对A、B的任何赋值，若其真值相同，则称A与B是等价的，记作AB；若AB是有效的，则称A蕴含B，记作AB。2.3谓词演算的等价式与蕴含式1命题逻辑中的等价式的推广 命题演算中的所有等价式都是谓词演算中的等价式。 从定义2.2.1可以看出，命题演算的合式公式都是谓词演算的合式公式。再根据定义2.3.4，命题演算中的所有等价式都是谓词演算中的等价式。 命题逻辑中的等价式的推广 在命题逻辑中，重言式的同一分量出现的每一处都用同一合式公式置换，其结果仍是重言式(定理1.4.2)。在谓词逻辑中可以推广为：在永真的谓词公式中，命题变元出现的每一处都用同一谓词公式置换，其结果

18、仍是永真式。2.3谓词演算的等价式与蕴含式2消去量词等价式 设个体域为有限集a1，a2，an，A(x)是含自由变元x的任意谓词公式，有下列等价式成立： (x)A(x)A(a1)A(a2)A(an) (x)A(x)A(a1)A(a2)A(an)3量词否定等价式 设A(x)是含自由变元x的任意谓词公式。则 (x)A(x)(x)A(x) (x)A(x)(x)A(x) 约定，量词之前的否定联结词，不是否定该量词，而是否定该量词及其辖域。 2.3谓词演算的等价式与蕴含式4量词作用域的扩展与收缩等价式 设A(x)是含自由变元x的任意谓词公式。B是不含变元x的谓词公式，则 (x)(A(x)B)(x)A(x)

19、B (x)(A(x)B)(x)A(x)B (x)(A(x)B)(x)A(x)B (x)(A(x)B)(x)A(x)B 利用上述四式可以得到以下四式： (x)(A(x)B)(x)A(x)B (x)(A(x)B)(x)A(x)B (x)(BA(x)B(x)A(x) (x)(BA(x)B(x)A(x) 2.3谓词演算的等价式与蕴含式5量词分配等价式 设A(x)和B(x)是含自由变元x的任意谓词公式，则 (x)(A(x)B(x)(x)A(x)(x)B(x) (x)(A(x)B(x)(x)A(x)(x)B(x) 前者可以理解为：“所有的x有性质A和性质B”和“所有的x有性质A且所有的x有性质B”是等同的。后者可以利用前者来证明。 2.3谓词演算的等价式与蕴含式6量词与联结词的蕴含式 设A(x)和B(x)是含自由变元x的任意谓词公式。 (x)A(x)(x)B(x)(x) (A(x)B(x) (x) (A(x)B(x)(x)A(x)(x)B(x) (x) (A(x)B(x)(x)A(x)(x)B(x) (x) (A(x)B(x)(x)A(x) (x)B(x) 2.3谓词演算的等价式与蕴含式【例2.15】证明 (x)(A(x)B(x)(x)A(x)(x)B(x) 解： 由第一式可得： (x)A(x)(x)B(x)(x)(A(x)B(x)而 (x)A(x)(x)B(x)