《离散数学》课件第二章

1、“人都是要死的，苏格拉底是人，所以苏格拉底是要死的。” 苏格拉底三段论第二讲 谓词逻辑（Predicate Qogic） 1.个体、谓词和量词 2.谓词公式 3.等值演算 4.范式 5.推理理论 6.谓词逻辑在计算机科学中的应用考虑如下3个命题或推理：1 “有一个整数大于其他每个整数”2 “任给 0，存在 0，如果|x-a|，则|f(x)-b|y) x(Z(x)y(Z(y) N(x,y) (xy)2.1 个体、谓词和量词2 “任给0，存在0，如果|x-a|，则|f(x)-b|0)()(0)(|x-a|)(f(x)-b|x)y(yy)5 推理理论2 全称量词引入规则（UG规则）A(y) xA(x

2、)成立的条件是：(1).y在A(y)中自由出现，且任意y，A(y)为真；(2).替换y的x要选择在A(y)中不出现的变元符号；z(zy)zz(zz)5 推理理论3 存在量词引入规则（EG规则）A(c) xA(x)成立的条件是：(1).c是特定的个体常量；(2).替换c的x要选择在A(c)中不出现的变元符号；(1).P(x)Q(c) (2).(x)(P(x)Q(x)在使用存在量词引入规则时，替换个体c的变元应选择在公式中没有出现的变元符号，正确的推理是：(1).P(x)Q(c)(2).(y)(P(x)Q(y)5 推理理论4 存在量词消除规则（ES规则）xA(x) A(c)成立的条件是：(1).c

3、是特定的个体常量，c不能在前面的公式序列中出现；(2).c不在A(x)中出现；(3).A(x)中自由出现的个体变元只有x。(1)(x)(y)(x y)/ P(2).(y)(z y) / US(3).(z c) / ES(4).(x)(x c)/ UG(5).c c / US 由(2)得到(3)不能使用存在量词消除规则，因为(2)中含有除y以外的自由变元z。5 推理理论推理方法直接法间接法（反证法、CP规则）5 推理理论示例 证明 (x)(C(x)W(x)R(x)(x) (C(x)Q(x)= (x) (Q (x)R(x)【分析】谓词逻辑的推理演算不能用真值表法，所以证明方法有直接证法、反正法和C

4、P规则法。当要推理的结论是蕴含式时才能用CP规则法，能用CP规则法的尽量用CP规则法，因为此方法增加了一个前提条件。该题只能用直接证法、反正法。5 推理理论证明方法一（直接证法）：1) (x)(C(x)W(x)R(x) P2) (x) (C(x)Q(x) P3) (C(a)Q(a) ES, 2)4) C(a)W(a)R(a) US,1) 5) C(a) T,I,3)6) W(a)R(a) T,I,4)、5)7) Q(a) T,I,3)8) R(a) T,I,6)9) Q(a)R(a) T,I,7)、8)10) (x) (Q (x)R(x) EG,9)3) C(a)W(a)R(a) US,1)

5、4) (C(a)Q(a) ES, 2)(3)、4)次序不能颠倒)5 推理理论示例 将下列推理符号化并给出形式证明: 晚会上所有人都唱歌或跳舞了，因此或者所有人都唱歌了，或者有些人跳舞了。（个体域为参加晚会的人）解 设P(x)：x唱歌了，Q(x)：x跳舞了，则前提：x(P(x)Q(x)结论：xP(x)xQ(x)推理形式：x(P(x)Q(x)xP(x)xQ(x)5 推理理论 (1) (xP(x)xQ(x) P(附加) (2) xP(x)xQ(x) R,E,(1) (3) xP(x) T,I,(2) (4) P(a) ES,(3) (5) xQ(x) T,I,(2) (6) Q(a) US,(5)

6、(7) x(P(x)Q(x) P (8) P(a)Q(a) US,(7) (9) Q(a) T,I,(4),(8) (10) Q(a)Q(a) T,I,(6),(9),矛盾 因此，假设不成立，原推理形式正确。5 推理理论示例 所有的有理数都是实数；所有的无理数也是实数；虚数不是实数。因此，虚数既不是有理数，也不是无理数。解 个体域为全总域，需要引入的谓词包括：Q(x): x 是有理数；R(x): x是实数；N(x): x是无理数；C(x): x是虚数。上述推理可符号化为：前提：x(Q(x)R(x)、x(N(x)R(x)、x(C(x) R(x)结论：x(C(x) (Q(x) N(x)， 验证该结

7、论的公式序列如下：5 推理理论(1). x(Q(x)R(x) / P(2). Q(y)R(y) / US(3). x(N(x)R(x) / P(4). N(y)R(y) / US(5). x(C(x) R(x) / P(6). C(y) R(y) / US(7). C(y) / P(附加)(8). R(y) / 分离规则，(6)和(7)(9). Q(y) / 拒取式，(8)和(2)(10). N(y) / 拒取式，(8)和(4)(11). Q(y) N(y) / 合取的引入(12). C(y)(Q(y) N(y) / T, I (7)和(11)(13). x(C(x) (Q(x) N(x) /

8、UG5 推理理论示例 每个旅客或者坐头等舱或者坐二等舱；每个旅客当且仅当他富裕时坐头等舱；有些旅客富裕但并非所有的旅客都富裕。因此，有些旅客坐二等舱。解 个体域为全总域，引入下列谓词：P(x): x是旅客；Q(x): x坐头等舱；R(x): x坐二等舱；S(x): x是富裕的。原推理可符号化为：前提：x(P(x)(Q(x)R(x)、x(P(x)(Q(x)S(x)、x (P(x)S(x)、(x(P(x)S(x)结论：x(P(x)R(x)，验证该结论的公式序列如下：5 推理理论(1). (x(P(x)S(x) / P(2). x(P(x)S(x) / T, I (2)(3). P(c)S(c) /

9、 ES(4). P(c) / T, I (3)(5). S(c) / T, I (3)(6). x(P(x)(Q(x)R(x) / P(7). P(c)(Q(c)R(c) / US, (6)(8). Q(c)R(c) / T, I (4)(7)(9).x(P(x)(Q(x)S(x)/P(10).P(c)(Q(c)S(c)/ US(9)(11).Q(c)S(c) / T, I (4)(11)(12).Q(c)S(c)/ T, I(11)(13). Q(c)/ T, I (12)(5)(14). R(c)/ T, I (13)(8)(15). P(c) R(c)/ T, I(4)(14)(16). x(P(x)R(x) / EG5 推理理论练习 每一个大学生不是文科生就是理科生；有的大学生爱好文学；小张不是文科生但他爱好文学。因此，如果小张是大学生，他就是理科生；解：个体域取全总域，要引入的谓词包括：P(x): x 是一个大学生；Q(x): x是文科生；S(x): x 是理科生；T(x): x 爱好文学。要引入的个体常量是：c : 小张。因此上述推理可符号化为： 前提：x(P(x)(Q(x)S(x)、x(P(x)T(x)、Q(c)T(c)结论：P(c)S(c)，验证该结论的公式序列为：