《代数结构谓词逻辑课件》由会员分享，可在线阅读，更多相关《代数结构谓词逻辑课件（80页珍藏版）》请在金锄头文库上搜索。
1、“人都是要死的，人都是要死的，苏格拉底是人，苏格拉底是人，所以苏格拉底是要死的。所以苏格拉底是要死的。”苏格拉底三段论苏格拉底三段论第1页，共80页。第二讲第二讲 谓词逻辑谓词逻辑（Predicate QogicPredicate Qogic）1.1.个体、谓词和量词个体、谓词和量词 2.2.谓词公式谓词公式 3.3.等值演算等值演算 4.4.范式范式 5.5.推理理论推理理论 6.6.谓词逻辑在计算机科学中的应用谓词逻辑在计算机科学中的应用第2页，共80页。考虑如下考虑如下3 3个命题或推理：个命题或推理：1“1“有一个整数大于其他每个整数有一个整数大于其他每个整数”2“2“任给任给 0 0
2、，存在，存在 0 0，如果，如果|x-a|x-a|，则，则|f(x)-b|f(x)-b|y)x(Z(x)y(Z(y)N(x,y)(xy)第5页，共80页。2.1 个体、谓词和量词个体、谓词和量词2 “2 “任给任给 00，存在，存在 00，如果，如果|x-a|x-a|，则，则|f(x)-b|f(x)-b|0)()(0)(|x-a|)(f(x)-b|x)y(yy)第66页，共80页。5 推理理论推理理论2 2 全称量词引入规则（全称量词引入规则（UGUG规则）规则）A(y)A(y)xA(x)xA(x)成立的条件是：成立的条件是：(1).(1).y y在在A(y)A(y)中自由出现中自由出现，且任
3、意，且任意y y，A(y)A(y)为真为真；(2).(2).替换替换y y的的x x要选择在要选择在A(y)A(y)中不出现的变元符号；中不出现的变元符号；z(zy)z z(zz)第67页，共80页。5 推理理论推理理论3 3 存在量词引入规则（存在量词引入规则（EGEG规则）规则）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)在使用存在量词引入规则时，替
4、换个体在使用存在量词引入规则时，替换个体c的变元应选的变元应选择在公式中没有出现的变元符号，正确的推理是：择在公式中没有出现的变元符号，正确的推理是：(1).P(x)Q(c)(2).(y)(P(x)Q(y)第68页，共80页。5 推理理论推理理论4 4 存在量词消除规则（存在量词消除规则（ESES规则）规则）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)中自由出现的个体
5、变元只有中自由出现的个体变元只有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。第69页，共80页。5 推理理论推理理论推理方法推理方法直接法直接法间接法（反证法、间接法（反证法、CPCP规则）规则）第70页，共80页。5 推理理论推理理论示例示例 证明证明(x)(C(x)W(x)R(x)(x)(C(x)Q(x)=(x)(Q(x)R(x)【分析分析】谓词逻辑
6、的推理演算不能用真值表法，所以证明方谓词逻辑的推理演算不能用真值表法，所以证明方法有直接证法、反正法和法有直接证法、反正法和CP规则法。当要推理的结论规则法。当要推理的结论是蕴含式时才能用是蕴含式时才能用CP规则法，能用规则法，能用CP规则法的尽量规则法的尽量用用CP规则法，因为此方法增加了一个前提条件。该题只能规则法，因为此方法增加了一个前提条件。该题只能用直接证法、反正法。用直接证法、反正法。第71页，共80页。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)
7、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)4)(C(a)Q(a)ES,2)(3)、4)次序不能颠倒次序不能颠倒)第72页，共80页。5 推理理论推理理论示例示例 将下列推理符号化并给出形式证明将下列推理符号化并给出形式证明:晚会上所有人都唱歌或跳舞了，因此或者所有人都唱歌了，或者有晚会上所有人都唱歌或跳舞了，因此或者所有人都唱歌了，或者有些人跳舞了。（个体域为参加晚会的人）些人跳舞了。（
8、个体域为参加晚会的人）解解 设设P(x)：x唱歌了，唱歌了，Q(x)：x跳舞了，则跳舞了，则前提：前提：x(P(x)Q(x)结论结论：xP(x)xQ(x)推理形式：推理形式：x(P(x)Q(x)xP(x)xQ(x)第73页，共80页。5 推理理论推理理论 (1)(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
9、),矛盾矛盾 因此，假设不成立，原推理形式正确。因此，假设不成立，原推理形式正确。第74页，共80页。5 推理理论推理理论示例示例 所有的有理数都是实数；所有的无理数也是实数；虚数不是实数。因此，虚数所有的有理数都是实数；所有的无理数也是实数；虚数不是实数。因此，虚数既不是有理数，也不是无理数。既不是有理数，也不是无理数。解解 个体域为全总域，需要引入的谓词包括：个体域为全总域，需要引入的谓词包括：Q(Q(x x):):x x 是有理数；是有理数；R(R(x x):):x x是实数；是实数；N(N(x x):):x x是无理数；是无理数；C(C(x x):):x x是虚数。上是虚数。上述推理可
10、符号化为：述推理可符号化为：前提前提：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(C(x x)(Q(Q(x x)N(N(x x)，验证该结论的公式序列如下：验证该结论的公式序列如下：第75页，共80页。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
11、).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)/UG第76页，共80页。5 推理理论推理理论示例示例 每个旅客或者坐头等舱或者坐二等舱；每个旅客当且仅当他富裕时坐头等舱；有些每个旅客或者坐头等舱或者坐二等舱；每个旅客当且仅当他富裕时坐头等舱；有些旅客富裕但并非所有的旅客都富裕。因此，有些旅客坐二等舱。旅客富裕但并非所有的旅客都富裕。因此，有些旅客坐二等舱。解解 个体域为全总域，引入下列谓词：个体
12、域为全总域，引入下列谓词：P(P(x x):):x x是旅客；是旅客；Q(Q(x x):):x x坐头等舱；坐头等舱；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)，验证该结论的公式序列如下：，验证该结论的公式序列如下：第77页，共80页。5 推理理论推
13、理理论(1).(x(P(x)S(x)/P(2).x(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)/T,I(4)(11)(12).Q(12).Q
14、(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)/EG第78页，共80页。5 推理理论推理理论练习练习 每一个大学生不是文科生就是理科生；有的大学生爱好文学；小张不是文科生每一个大学生不是文科生就是理科生；有的大学生爱好文学；小张不是文科生但他爱好文学。因此，如果小张是
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)、Q(Q(c c)T(T(c c)结论结论：P(P(c c)S(S(c c)，验证该结论的公式序列为：验证该结论的公式序列为：第79页，共80页。5 推理理论推理理论(1).Q(c)T(c)/P(2).x(P(x)(Q(x)S(x)/P(3).P(c)(Q(c)S(c)/US(2)(4).P(c)/P（附加）（附加）(5).Q(c)S(c)/T,I(3)(4)(6).Q(c)/T,I(1)(7).S(c)/T,I(5)(6)第80页，共80页。
