离散数学的谓词逻辑详解

1、2022-2-241谓谓 词词 逻逻 辑辑2022-2-242命题逻辑的局限性命题逻辑的局限性 苏格拉底三段论： P P：所有的人都是要死的。：所有的人都是要死的。 Q Q：苏格拉底是人：苏格拉底是人 。 R R：所以苏格拉底要死：所以苏格拉底要死 。 凭直觉知道这个结论是真的，推理是有效的。但是，借助命题演算的推理理论，却不能推导出这个结论（无法证明它的正确性）。Why ?2022-2-243 此三段论的论断显然正确。 但是，在命题逻辑中无法得到正确性的反应: PQR 不是重言式！命题逻辑不能正确反映此三段论的推理过程。这是命题逻辑的局限性!2022-2-244原原 因因o 在命题逻辑中无法

2、将简单命题之间的内在联系反映出来。命题逻辑中描述的上述三段论，即PQR，使R与命题P、Q无关的独立命题。n 但是，实际上R与命题P、Q是有关系的，只是这种关系在命题逻辑中得不到反映。o 要反映这种内在联系，需对简单命题作进一步分解进一步分解，分解出其中的成份，包括：个体词，谓词，量词，函词等，研究它们的形式结构及逻辑关系，总结出正确的推理形式和规则，这就是一阶逻辑所研究的内容.o 一阶逻辑也称谓词逻辑。谓词逻辑是一种表达能力更强的逻辑。2022-2-245谓词逻辑谓词逻辑o 我们将介绍谓词逻辑的基本概念和符号。关于命题、命我们将介绍谓词逻辑的基本概念和符号。关于命题、命题的真值、命题词、命题常

3、量和命题变元以及逻辑五个题的真值、命题词、命题常量和命题变元以及逻辑五个联结词其含意和在命题逻辑中的基本相同，联结词其含意和在命题逻辑中的基本相同，o 本章中只介绍谓词逻辑中新出现的基本概念和符号，其本章中只介绍谓词逻辑中新出现的基本概念和符号，其中主要的是中主要的是个体词，谓词，量词以及函词个体词，谓词，量词以及函词。2022-2-2461.谓词与个体词 将简单命题分解成个体与谓词这样两个组成部分。谓词，通常是用来描述个体的性质或特征，或者个体之间的关系。谓词逻辑，是命题逻辑的扩充与发展 。例例1 1：下面两个命题 1. 张华是学生 2. 李明是学生 a: 张华 b:李明 H H：是学生 ，

4、则 H H（x x）:x是学生 1，2可分别表示成 H(aH(a) ) ，H(bH(b).). 这样表示就揭示了两命题间有相同的谓语这一特征。 2022-2-247例例2 2：张华比李明高 令 a:张华 b:李明 L(x，y):x高于y 该命题可表示为： L(aL(a，b)b)例1和例2中的 H、L称为谓词， 其中H是一元谓词，表示个体的性质（是什么）， L是二元谓词，表示个体之间的关系。 注注： （1）常用大写拉丁字母表示谓词常用大写拉丁字母表示谓词. . （2）谓词是用来刻划个体的性质或者个体之间谓词是用来刻划个体的性质或者个体之间的关系的。的关系的。2022-2-248命题函数与命题例:

5、 令P(x)表示x为质数，则P(x)为一元谓词。 令 H(x，y)表示“x高于y”,则 H(x，y)为二元谓词。 则：H(张三，李四) 表示“张三高于李四”，是命题。注意注意： P(x.y), H(x，y)为命题函数. P(2)与 H(张三，李四)才是命题。谓词中如果有谓词中如果有n n个变元则称为个变元则称为n n元谓词元谓词. n. n元谓词反映了个体元谓词反映了个体之间的之间的n n元关系元关系. . 2022-2-2492.个体词个体词v个体是可以独立存在的实体，它可以是一个具体的个体是可以独立存在的实体，它可以是一个具体的 事物事物-个体常元，个体常元，常用小写拉丁字母常用小写拉丁字

6、母a，b，c等表等表示。示。也可以是一个抽象的概念（即没指定哪一个个体）也可以是一个抽象的概念（即没指定哪一个个体） -个体变元个体变元，常用小写拉丁字母：，常用小写拉丁字母：x，y，z等表等表示示2022-2-2410函词函词例：张华的哥哥比李明高张华的哥哥比李明高 a:张华 b:李明 L(x，y):x高于y f(x):x的哥哥则上述符号化为： L(f(aL(f(a) )，b)b) f f称为函词函词定义定义：一个：一个n n元函词元函词即是一个论域上的一个即是一个论域上的一个n n元函数元函数2022-2-2411v 变元在谓词中的次序直接影响了谓词的取值变元在谓词中的次序直接影响了谓词的

7、取值 。如:设谓词P(x，y)为“x比y高”， 设张三为170cm，李四为180cm.则: P(李四，张三)为真命题。 P(张三，李四)为假命题.概念的讨论概念的讨论2022-2-2412命题的符号化命题的符号化o 例例1:武汉位于重庆与上海之间武汉位于重庆与上海之间.n解:用个体词a，b，c分别表示武汉，重庆和上海， 谓词P(x，y，z)表示x位于y与z之间， 则该命题表示为:P(a，b，c).p 例例2：如果王英坐在李红的后面，则王英比李红高：如果王英坐在李红的后面，则王英比李红高.解：令 a:王英;b:李红;P(x，y):x坐在y的后面; G(x，y):x比y高.则该命题表示为：P(a，

8、b)G(a，b).2022-2-24133. 量词量词 使用前面介绍的概念，还不足以表达日常生活中的使用前面介绍的概念，还不足以表达日常生活中的各种命题。各种命题。 例如：例如： “ 所有的正整数都是素数所有的正整数都是素数 ” “ 有些正整数是素数有些正整数是素数 ” 两种量词两种量词: 全称量词和存在量词全称量词和存在量词.2022-2-2414全称量词全称量词: : 1.全称量词全称量词 ： （任意，所有）（任意，所有） x: “对一切对一切x”，“对所有的对所有的x”， “对任一对任一x” 如：如： x P(x) “对一切对一切x，P(x)是真是真” x P(x) “并非对一切并非对一

9、切x，P(x)是真是真” x P(x) “对一切对一切x， P(x) 是真是真” 如如: “ 所有人都是要死的所有人都是要死的”设设x的个体域为全体人的集合，则可表示为的个体域为全体人的集合，则可表示为 x D(x) 2022-2-2415存在量词存在量词: 2. 存在量词：存在量词： （存在）（存在） x: “存在存在x“、 ”某些某些x“、 ”至少有一至少有一x”如：如： x P(x) “存在存在x， P(x)是真是真” x P(x) “存在存在x， P(x)是真，并非这是真，并非这样样” x P(x) “存在存在x， P(x)是真是真” 如如: “有些有理数是整数。有些有理数是整数。”

10、令(x）：x是整数，设x的个体域为有理数集合，则命题可表示为： x I(x） 2022-2-2416 4. 4. 论论 域域 含有量词的命题的表达式的形式，与论域有关。用量词量化含有量词的命题的表达式的形式，与论域有关。用量词量化后的命题，其值也与后的命题，其值也与论域论域有关有关。 例例 1 1 x x（x=0)x=0) 若论域为整数集，则此命题值为真，若论域为整数集，则此命题值为真， 若论域为正整数集，则命题的值为假。若论域为正整数集，则命题的值为假。 为了方便，引入全总个体域，记为：为了方便，引入全总个体域，记为：U U，简称，简称全域全域: : 定义定义: :宇宙间所有的个体聚集在一起

11、所构成的集合称为宇宙间所有的个体聚集在一起所构成的集合称为全域。全域。 2022-2-2417特性谓词特性谓词o 后面的讨论中，除特殊说明外，均使用后面的讨论中，除特殊说明外，均使用全域全域。而对个体。而对个体变化的真正取值范围，用特性谓词加以限制。变化的真正取值范围，用特性谓词加以限制。 一般地，对全称量词，特性谓词作蕴含的前件引入；而一般地，对全称量词，特性谓词作蕴含的前件引入；而对存在量词，特性谓词常作为合取项引入。对存在量词，特性谓词常作为合取项引入。2022-2-2418例例 (1) “(1) “所有的人都是要死的。所有的人都是要死的。” (2) “(2) “有的人不怕死。有的人不怕

12、死。” 1.1.当当x x的个体域为的个体域为全体人全体人组成的集合时，符号化上述命题。组成的集合时，符号化上述命题。解解: : 令令D D（x x）：）：x x是要死的，令是要死的，令G G（x x）：）：x x怕死。怕死。 则（则（1 1）可表示为）可表示为: : x x D(xD(x) )。 （2 2）可表示为）可表示为: : x x G(xG(x) )。 2022-2-2419论域为全域时论域为全域时2. 当取当取x x的个体域为全域时，必须引入一个特性谓词将的个体域为全域时，必须引入一个特性谓词将“人人”从全域中分离出来。从全域中分离出来。 （1）对所有个体而言，如果它是人，则它是要

13、死的。 （2）存在着个体，它是人并且它不怕死 于是令于是令 M M（x x）：）：x x是人。是人。 （1 1） x x（M(x)D(xM(x)D(x) （2 2） x x (M (M（x x） G G（x x） 命题符号化命题符号化(翻译翻译)：o 将汉语(或其他自然语言)语句翻译成逻辑表达式，这在数学、逻辑编程、人工智能、软件工程以及许多其他学科中都是一项重要的任务。翻译的目的是生成简单而有用的逻辑表达式。2022-2-2421命题符号化命题符号化：例：没有不犯错误的人例：没有不犯错误的人令H（x）： x是人， M（x）： x犯错误例：存在着偶质数例：存在着偶质数令E(x)：x是偶数，P(

14、x)：x是质数则有：则有： x(E(x)P(xx(E(x)P(x).()()()(:xMxHxxMxHx则有2022-2-2422例例：每个自然数都有后继数每个自然数都有后继数若令：N（x）：x 是自然数， H（x，y）：y是x的后继数例：对平面上的任意两点，有且仅有一条直线通过这两点。例：对平面上的任意两点，有且仅有一条直线通过这两点。若令P（x）： x是一个点，L（x）：x是一条直线，T（x，y，z）：z通过x，y，E（x，y）：x等于y).,()()(:yxHyNyxNx则有).,(),()(),()()()(:zuEuyxTuLuzyxTzLzyPxPyx则有2022-2-2423 例

15、例5 将下列命题符号化将下列命题符号化(使用全域使用全域)。 (1) 发光的并非都是金子发光的并非都是金子 令：令：P（x）：）：x发光；发光；G（x）：）：x是金子。是金子。则该命题可表示为则该命题可表示为 ： （2）所有运动员都钦佩某些教练。）所有运动员都钦佩某些教练。 令：令：P（x）：）：x是运动员；是运动员；T（x）：）：x是教练；是教练；Q（x，y）：）：x钦佩钦佩y。则该命题可表示为则该命题可表示为 ：2022-2-2424 （3）凡是实数均能比较大小。）凡是实数均能比较大小。 若令若令R（x）：）：x是实数；是实数；G（x，y)：x与与y可比较大小可比较大小. 则该命题可表示为

16、：则该命题可表示为：例例6将苏格拉底三段论进行符号化：将苏格拉底三段论进行符号化：令：令：(x)：x是人是人(x): x要死要死则则2022-2-2425 量化断言与命题的关系量化断言与命题的关系 (1)1)如果论述域是有限的，不妨设论述域是如果论述域是有限的，不妨设论述域是11，2 2，33，则，则 x P(x)x P(x)P(1)P(2)P(3)P(1)P(2)P(3) x x P(xP(x) ) P(1)P(2)P(3) P(1)P(2)P(3) (2) (2) 如果论述域是可数无限，例如自然数集合，我们可以这如果论述域是可数无限，例如自然数集合，我们可以这样理解：样理解： ( ( x)

17、P(xx)P(x) ) P(1)P(2)P(3)P(1)P(2)P(3) ( ( x)P(xx)P(x) ) P(1)P(2)P(3)P(1)P(2)P(3) (3)(3)如果论述域不可数无限，则无法表达如果论述域不可数无限，则无法表达。 2022-2-2426练习练习 任何金属都可以溶解在某种液体中任何金属都可以溶解在某种液体中.令J(x):x是金属; E(x):x是液体;S(x，y):x可以溶解在y中，);,()()(:yxSyEyxJx则可以表示为2022-2-2427原子与公式原子与公式 设设P(x1，xn)是是n元谓词，则称其为为原子公式，或元谓词，则称其为为原子公式，或简称简称原子

18、原子谓词公式，简称为谓词公式，简称为公式公式，其递归定义为：，其递归定义为：（1）原子是合式公式；）原子是合式公式；（2）若）若A是合式公式，则是合式公式，则(A)也是合式公式；也是合式公式；（3）若）若A，B是合式公式，则是合式公式，则(AB)， (AB)， (AB)， (AB)也是合式公式；也是合式公式；（4）若）若A是合式公式，是合式公式，x是是A中的变量符号，中的变量符号，（5）只有有限次地使用（）只有有限次地使用（1）（4）所生成的符号串）所生成的符号串才是合式公式。才是合式公式。.,也是合式公式则xAxA 2022-2-2428o 前面各命题符号化的结果都是合式公式。前面各命题符号

19、化的结果都是合式公式。o 对于一个谓词，如果其中每一个变量都在一个量词的对于一个谓词，如果其中每一个变量都在一个量词的作用之下，则它就不再是命题函数而是一个命题了。作用之下，则它就不再是命题函数而是一个命题了。o 但是，这种命题和命题逻辑中的命题还是有区别的。但是，这种命题和命题逻辑中的命题还是有区别的。因为这种命题中毕竟还有变量，尽管这种变量和命题因为这种命题中毕竟还有变量，尽管这种变量和命题函数中的变量有所不同。因此，有必要区分这些变量。函数中的变量有所不同。因此，有必要区分这些变量。2022-2-2429例例1 ：令：令 P（x， y）：）：“ xy.),()(yxxFyA令则A(y)是

20、真命题,),(是假命题规则后的式子：但使用xxxFxUG是错误的。故)()(xxAyA原因是:条件2)不满足。2022-2-2459存在推广规则存在推广规则EG)()(:)(xxAcAEG规则 使用此规则时注意使用此规则时注意: (1) c是个体域中某个确定的个体。是个体域中某个确定的个体。 (2) 代替代替c的的x不能已在不能已在A(c)中出现。中出现。例如：设例如：设A(x，y):xy，考查下面的推理过，考查下面的推理过程程: (1) A(x，c) (2) ),(xxxA是错误的！原因在于代替是错误的！原因在于代替c的的x已在已在A(x)中出现中出现2022-2-2460存在指定规则存在指

21、定规则(ES规则规则):)()(cAxxA成立条件：成立条件：1) c是使是使A(c)为真的常量符号为真的常量符号;),()(,)2acaBxxB则比如规则若在此之前也使用过该若推理过程中3)A(x)中的自由变元只有x.例如例如：设D为自然数集， F(x)表示“x是奇数”，G(x)表示“x是偶数”.)()(是真命题则xxGxxF注意：以上四条规则中的注意：以上四条规则中的A(x)都是公式都是公式2022-2-2461但，若不注意使用条件，则有：)()()1 (xxGxxF前提引入)()2(xxF化简，根据（1）)() 3(cFES规则，根据（2）)()4(xxG化简，根据（1）)()5(cGE

22、S规则，根据（4）)()()6(cGcF合取，根据（3），（5）)()()7(xGxFxEG规则，根据（6）于是得出：)()()()(xGxFxxxGxxF（）违反了条件2）2022-2-2462例例 1 证明：证明：)()()()()()(xCxBxxAxCxxBxAx证明如下：)()() 1 (xBxAx前提引入)()()2(yByAUS规则，根据（1）)()() 3(xAxCx前提引入)()()4(aAaCES规则，根据（3）)()5(aC化简，根据（4）)()6(aA化简，根据（4）)()7(aB假言推理，根据（2），（6）)()()8(aCaB合取，根据（5），（7）)()()9(x

23、CxBxEG规则，根据（8）2022-2-2463本例也可作如下证明：)()()1(xAxCx前提引入ES规则，根据（1）)()3(aA化简，根据（2）)()()4(xBxAx前提引入)()()5(aBaAUS规则，根据（4）)()6(aB假言推理，根据(3)，(5)()7(aC化简，根据（2）)()()8(aCaB合取，根据（6），（7）)()()9(xCxBxEG规则，根据（8）)()()2(aAaC2022-2-2464例例 2 证明证明： 苏格拉底三段论苏格拉底三段论“凡人都是要死的，苏格拉底是人，凡人都是要死的，苏格拉底是人，所以苏格拉底是要死的所以苏格拉底是要死的”。证明证明:结论

24、: D(a)首先将命题符号化：设M(x):x是人. D(x):x是要死的. a:苏格拉底.)(),()(aMxDxMx前提:证明:)()() 1 (xDxMx)()()2(aDaM)() 3(aM)()4(aD规则US规则，（1）规则假言推理，（2），（3）2022-2-2465例例 3o有些病人相信所有的医生，但是病人都不相信骗子。证明：有些病人相信所有的医生，但是病人都不相信骗子。证明：医生都不是骗子。医生都不是骗子。o证明：证明：v命题符号化：设论域为全域命题符号化：设论域为全域 P(x):x x是病人；是病人；D(x):x是医生；是医生；Q(x):x是骗子；是骗子；R(x，y):x相信

25、相信y。v前提：前提： x(P(x) y(D(y)R(x，y)， x y(P(x)Q(y) R(x，y)v结论：结论： x(D(x) Q(x)v证明：证明：2022-2-24661)1) x(x(P(x)P(x) y(D(y)Ry(D(y)R(x(x，y) y) 前提引入前提引入2)2)P(c)P(c) y(D(y)Ry(D(y)R(c(c，y) ESy) ES，(1)(1)3)3) x x y(y(P(x)P(x)Q(y)Q(y) R R(x(x，y) y) 前提引入前提引入4)4) y(y(P(c)P(c)Q(y)Q(y) R R(c(c，y) USy) US，(3)(3)5)5)P(c)

26、P(c)Q(z)Q(z) R R(c(c，z) USz) US，(4)(4)6)6) ( (P(c)P(c)Q(z)Q(z) R R(c(c，z) z) 蕴涵等值式，蕴涵等值式，(5)(5)7)7) P(c)P(c) Q(z)Q(z) R R(c(c，z) De Morganz) De Morgan律，律，(6)(6)8)8) P(c)(P(c)(Q(z)Q(z) R R(c(c，z) z) 蕴涵等值式，蕴涵等值式，(7)(7)9)9)P(cP(c) ) 化简，化简，(2)(2)10)10) Q(z)Q(z) R R(c(c，z) z) 析取三段论，析取三段论，(8)(8)，(9)(9)11)

27、11) R R(c(c，z)z) Q(zQ(z) ) 等值演算，等值演算，(10)(10)12)12) y(D(y)Ry(D(y)R(c(c，y) y) 化简，化简，(2)(2)13)13) D(z)RD(z)R(c(c，z) USz) US，(12)(12)14)14) D(z)D(z) Q(zQ(z) ) 假言三段论，假言三段论，(11)(11)，(13)(13)15)15) x(x(D(x)D(x) Q(xQ(x) UG) UG，(14) (14) 2022-2-2467例例 4：指出下面推理的错误：指出下面推理的错误1)1) x(F(x)G(xx(F(x)G(x) ) 前提引入前提引入

28、2)2)F(y)G(yF(y)G(y) US) US，(1)(1)3)3) xF(xxF(x) ) 前提引入前提引入4)4)F(yF(y) ES) ES，(3)(3)5)5)G(yG(y) ) 假言推理，假言推理，(2)(2)，(4)(4)6)6) xG(xxG(x) UG) UG，(5)(5)没有满足ES规则的条件1即： xA(x)A(c)c是使A(c)为真的常量符号。 F(c) ES，(3) G(c) 假言推理，(2)，(4)xG(x) EG，(5)2022-2-2468例例证明下述论证的正确性人会说话，猴子不会说话，因此猴子不是人。人会说话，猴子不会说话，因此猴子不是人。解：设论域为全域

29、。设解：设论域为全域。设 M(x):x是人。是人。 S(x): x会说话。会说话。B(x):x是猴子。是猴子。则前提为：则前提为： x(M(x)S(x)和和 x(B(x)S(x) 结论为：结论为： x(B(x)M(x)证明: 1 x(M(x)S(x) P规则，前提规则，前提 2 M(x)S(x) T，1，US 3 x(B(x)S(x) P规则，前提规则，前提 4 B(x)S(x) T，3，US 5 S(x) B(x) T，4， 逆反律逆反律 6 M(x) B(x) T，2，5，I6 7 B(x) M(x) T，6，逆反律，逆反律 8 x(B(x)M(x) T，7，UG2022-2-2469练习

30、：符号化下列命题，并论证其结论：练习：符号化下列命题，并论证其结论：a)任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或 者喜欢乘汽车，或者喜欢骑自行车。有的人不爱骑自行车，者喜欢乘汽车，或者喜欢骑自行车。有的人不爱骑自行车，因而有的人不爱步行。因而有的人不爱步行。o命题符号化：设命题符号化：设P(x):x喜欢步行。喜欢步行。Q(x):x喜欢乘汽车喜欢乘汽车. R(x):x喜欢骑自行车。喜欢骑自行车。o推理的形式结构：推理的形式结构：)()()()(),()()(),()()(xPxxRxxRxQxxQxPx2022-2-2470结构形式：)()()()(),()()(),()()(