课件代数结构第二章

1、 1.1.个体、谓词和量词个体、谓词和量词 2.2.谓词公式谓词公式 3.3.等值演算等值演算 4.4.范式范式 5.5.推理理论推理理论 6.6.谓词逻辑在计算机科学中的应用谓词逻辑在计算机科学中的应用考虑如下考虑如下3 3个命题或推理：个命题或推理：1 1 “有一个整数大于其他每个整数有一个整数大于其他每个整数”2 2 “任给任给 0 0，存在，存在 0 0，如果，如果|x-a|x-a| ，则，则|f(x)-b|f(x)-b|y) x(Z(x)y(Z(y) N(x,y) (xy)2.1 个体、谓词和量词个体、谓词和量词2 2 “任给任给 00，存在，存在 00，如果，如果|x-a|x-a|

2、 ，则，则|f(x)-b|f(x)-b|0)( )( 0) (|x-a| )(f(x)-b|x) y(yy)5 推理理论推理理论2 2 全称量词引入规则（全称量词引入规则（UGUG规则）规则）A(y) A(y) xA(x)xA(x)成立的条件是：成立的条件是：(1).(1). y y在在A(y)A(y)中自由出现中自由出现，且任意，且任意y y，A(y)A(y)为真为真；(2).(2). 替换替换y y的的x x要选择在要选择在A(y)A(y)中不出现的变元符号；中不出现的变元符号； z(zy) z z(zz)5 推理理论推理理论3 3 存在量词引入规则（存在量词引入规则（EGEG规则）规则）

3、A(c) A(c) xA(x)xA(x)成立的条件是：成立的条件是：(1).c(1).c是特定的个体常量；是特定的个体常量；(2).(2).替换替换c c的的x x要选择在要选择在A(c)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 4 存在量词消除规则（存在量词消除规则（ES

4、ES规则）规则） xA(x) xA(x) A(c) A(c)成立的条件是：成立的条件是：(1).c(1).c是特定的个体常量，是特定的个体常量，c c不能在前面的公式序列中出现；不能在前面的公式序列中出现；(2).c(2).c不在不在A(x)A(x)中出现；中出现；(3).A(x)(3).A(x)中自由出现的个体变元只有中自由出现的个体变元只有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)不能使用存在量词消除规则，因为不能使用存在量词消除规则，因为

5、(2)中含有除中含有除y以外的以外的自由变元自由变元z。5 推理理论推理理论推理方法推理方法直接法直接法间接法（反证法、间接法（反证法、CPCP规则）规则）5 推理理论推理理论示例示例 证明证明 ( x)(C(x)W(x)R(x)( x) (C(x)Q(x)= ( x) (Q (x)R(x)【分析分析】谓词逻辑的推理演算不能用真值表法，所以谓词逻辑的推理演算不能用真值表法，所以证明方法有直接证法、反正法和证明方法有直接证法、反正法和CP规则法。当要规则法。当要推理的结论是蕴含式时才能用推理的结论是蕴含式时才能用CP规则法，能用规则法，能用CP规则法的尽量用规则法的尽量用CP规则法，因为此方法增

6、加了一规则法，因为此方法增加了一个前提条件。该题只能用直接证法、反正法。个前提条件。该题只能用直接证法、反正法。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,

7、1) 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)

8、( xP(x)xQ(x) P(附加附加) (2) x P(x)x Q(x) R,E,(1) (3) x P(x) T,I,(2) (4) P(a) ES,(3) (5) x Q(x) T,I,(2) (6) Q(a) US,(5) (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 推理理论推理理论示例示例 所有的有理数都是实数；所有的无理数也是实数；虚数不是实数。所有的有理数都是实数；所有的无

9、理数也是实数；虚数不是实数。因此，虚数既不是有理数，也不是无理数。因此，虚数既不是有理数，也不是无理数。解解 个体域为全总域，需要引入的谓词包括：个体域为全总域，需要引入的谓词包括：Q(Q(x x): ): x x 是有理数；是有理数；R(R(x x): ): x x是实数；是实数；N(N(x x): ): x x是无理数；是无理数；C(C(x x): ): x x是是虚数。上述推理可符号化为：虚数。上述推理可符号化为：前提前提： x x(Q(Q(x x) )R(R(x x)、 x x(N(N(x x) )R(R(x x)、 x x(C(C(x x) ) R(R(x x)结论结论： x x(C

10、(C(x x) ) ( ( Q(Q(x x) ) N(N(x x)， 验证该结论的公式序列如下：验证该结论的公式序列如下：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)

11、 N(y) / 合取的引入合取的引入(12). C(y)( Q(y) N(y) / T, I (7)和和(11)(13). x(C(x) ( Q(x) N(x) /UG5 推理理论推理理论示例示例 每个旅客或者坐头等舱或者坐二等舱；每个旅客当且仅当他富裕每个旅客或者坐头等舱或者坐二等舱；每个旅客当且仅当他富裕时坐头等舱；有些旅客富裕但并非所有的旅客都富裕。因此，有些旅时坐头等舱；有些旅客富裕但并非所有的旅客都富裕。因此，有些旅客坐二等舱。客坐二等舱。解解 个体域为全总域，引入下列谓词：个体域为全总域，引入下列谓词：P(P(x x): ): x x是旅客；是旅客；Q(Q(x x): ): x x

12、坐头等坐头等舱；舱；R(R(x x): ): x x坐二等舱；坐二等舱；S(S(x x): ): x x是富裕的。是富裕的。原推理可符号化为：原推理可符号化为：前提前提： x x(P(P(x x) )(Q(Q(x x) ) R(R(x x)、 x x(P(P(x x) )(Q(Q(x x) )S(S(x x)、 x (P(P(x x) ) S(S(x x)、 ( ( x x(P(P(x x) )S(S(x x)结论结论： x x(P(P(x x) ) R(R(x x)，验证该结论的公式序列如下：，验证该结论的公式序列如下：5 推理理论推理理论(1). (x(P(x)S(x) / P(2). x

13、(P(x)S(x) / T, I (2)(3). P(c)S(c) / 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).(9). x x(P(P(x x) )(Q(Q(x x) )S(S(x x)/P)/P(10).P(10).P(c c) )(Q(Q(c c) )S(S(c c)/ US(9)/ US(9)(11).Q(11).Q(c c) )S(S(c c) / T, I (4)(11) /

14、 T, I (4)(11)(12).Q(12).Q(c c) )S(S(c c)/ T, I(11)/ T, I(11)(13). (13). Q(Q(c c) )/ T, I (12)(5)/ T, I (12)(5)(14). R(14). R(c c) )/ T, I (13)(8)/ T, I (13)(8)(15). P(15). P(c c) ) R( R(c c)/ T, I(4)(14)/ T, I(4)(14)(16). (16). x x(P(P(x x) ) R(R(x x) / EG) / EG5 推理理论推理理论练习练习 每一个大学生不是文科生就是理科生；有的大学生爱

15、好文学；小张每一个大学生不是文科生就是理科生；有的大学生爱好文学；小张不是文科生但他爱好文学。因此，如果小张是大学生，他就是理科生；不是文科生但他爱好文学。因此，如果小张是大学生，他就是理科生；解解：个体域取全总域，要引入的谓词包括：个体域取全总域，要引入的谓词包括：P(P(x x): ): x x 是一个大学生；是一个大学生；Q(Q(x x): ): x x是文科生；是文科生；S(S(x x): ): x x 是理科生；是理科生；T(T(x x): ): x x 爱好文学。爱好文学。要引入的个体常量是：要引入的个体常量是：c c : : 小张。小张。因此上述推理可符号化为：因此上述推理可符号化为： 前提前提： x x(P(P(x x) )(Q(Q(x x) ) S(S(x x)、 x x(P(P(x x) ) T(T(x x)、