离散数学第二章(第3讲)课件.ppt

1、6 谓词逻辑的推理理论谓词逻辑的推理理论1、关于量词的四个推理规则、关于量词的四个推理规则（1）全称指定规则（）全称指定规则（US规则）规则）该规则表示成：该规则表示成：xA(x)A(c)(x,c 个体域个体域)如果对个体域中所有客体x,A(x)成立，则对个体域中某个任意客体c，A(c)成立。（2）全称推广规则（）全称推广规则（UG规则）规则）如果能够证明对个体域中每一个客体如果能够证明对个体域中每一个客体c，命题，命题A(c)都成立，则可得到结论都成立，则可得到结论 xA(x)成立。成立。该规则表示成：该规则表示成：A(c)xA(x)（3）存在指定规则（）存在指定规则（ES规则）规则）该规则

2、表示成：该规则表示成：xA(x)A(c)如果对于个体域中某些客体A(x)成立，则必有某个特定的客体c，使A(c)成立。（4）存在推广规则（）存在推广规则（EG规则）规则）如果对个体域中某个特定客体如果对个体域中某个特定客体c，有，有A(c)成立，成立，则在个体域中，必存在则在个体域中，必存在x，使，使A(x)成立。成立。该规则表示成：该规则表示成：A(c)xA(x)2、规则使用说明、规则使用说明（3 3）推导中既用）推导中既用ESES，又用，又用USUS，则必须先用则必须先用ES ES，后，后用用USUS方可取相同变元，反之不行。方可取相同变元，反之不行。xPxP(x)(x)P(c)P(c)x

3、 xQ Q(x)(x)Q(c)Q(c)（2 2）在使用）在使用ES,USES,US时时,要求谓词公式必须是前束范式要求谓词公式必须是前束范式（1 1）用用US,ESUS,ES在推导中去掉量词，用在推导中去掉量词，用UG,EGUG,EG使结论量化使结论量化（加上量词）。（加上量词）。（4 4）推导中连续使用）推导中连续使用USUS规则可用相同变元规则可用相同变元 x xP P(x)(x)P(c)P(c)x xQ Q(x)(x)Q(c)Q(c)（5 5）推导中连续使用）推导中连续使用ESES规则时，使用一次更改一个变元。规则时，使用一次更改一个变元。x xP P(x)(x)P(c)P(c)x xQ

4、 Q(x)(x)Q(d)Q(d)n例例 指出下列推导中的错误，并加以改正。指出下列推导中的错误，并加以改正。(1)(1)xP(x)xP(x)P P (2)P(c)(2)P(c)ES(1)ES(1)(3)(3)xQ(x)xQ(x)P P (4)Q(c)(4)Q(c)ES(2)ES(2)解：解：第二次使用存在量词消去规则时，所指定的第二次使用存在量词消去规则时，所指定的特定个体应该是证明序列以前公式中没有出现过的，特定个体应该是证明序列以前公式中没有出现过的，正确的推理是：正确的推理是：(1)(1)xP(x)xP(x)P P (2)P(c)(2)P(c)ES(1)ES(1)(3)(3)xQ(x)x

5、Q(x)P P (4)Q(d)(4)Q(d)ES(2)ES(2)3、推理证明推理证明 (1)命题逻辑中的命题逻辑中的P规则规则,T规则都可以引用到谓词逻规则都可以引用到谓词逻辑的推理中。辑的推理中。(2)使用量词的四个推理规则对量词进行适当处理。使用量词的四个推理规则对量词进行适当处理。(3)推理过程中使用谓词逻辑的等价公式和永真蕴含推理过程中使用谓词逻辑的等价公式和永真蕴含公式。公式。(4)推理证明方法包括推理证明方法包括直接证法和间接证法，其证明直接证法和间接证法，其证明思想与命题逻辑中的类似。间接证法包括思想与命题逻辑中的类似。间接证法包括CP规则规则证明和反证法证明。证明和反证法证明。

6、（1 1）直接证法）直接证法 例例 证明苏格拉底三段论：证明苏格拉底三段论：“人都是要死的，人都是要死的，苏格拉底是人，所以苏格拉底是要死的。苏格拉底是人，所以苏格拉底是要死的。”4、推理证明实例推理证明实例则翻译为：则翻译为：x(M(x)x(M(x)D(x)D(x)，M(s)M(s)D(s)D(s)解：设解：设M(x)M(x)：x x是人；是人；（特性谓词）（特性谓词）D(x)D(x)：x x是要死的；是要死的；M(s)M(s)：苏格拉底是人；：苏格拉底是人；D(s)D(s)：苏格拉底是要死的。：苏格拉底是要死的。例例:证明苏格拉底论证证明苏格拉底论证（x）(M(x)D(x)，M(s)D(s

7、)(1)x(M(x)D(x)P (2)M(s)D(s)US(1)(3)M(s)P (4)D(s)T(2)(3)I例例 证明证明:x(P(x)Q(x)x P(x)xQ(x)(1)x P(x)附加前提附加前提(2)x(P(x)Q(x)P(3)P(c)Q(c)ES(2)(4)P(c)US(1)(5)Q(c)T(3)(4)I(6)xQ(x)EG(5)(7)x P(x)xQ(x)CP（2 2）CP 规则证明规则证明例例 将下列推理符号化并给出形式证明将下列推理符号化并给出形式证明:每一个大学生不是文科生就是理科生；有的大学生每一个大学生不是文科生就是理科生；有的大学生是优等生；小张不是文科生但他是优等生

8、。因此，如果是优等生；小张不是文科生但他是优等生。因此，如果小张是大学生，他就是理科生。小张是大学生，他就是理科生。解：解：个体域取全总个体域，设个体域取全总个体域，设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)x(P(x)(Q(x)S(x),x(P(x)T(x)，Q(c)T(c)P(c)S(c)推理形式如下：推理形式如下：(1)P(c)附加前提附加前提 (2)x(P(x)(Q(x)S(x

9、)P(3)P(c)(Q(c)S(c)US(2)(4)Q(c)S(c)T(1)(3)I(5)Q(c)T(c)P(6)Q(c)T(5)I(7)Q(c)S(c)T(4)E (8)S(c)T(6)(7)I (9)P(c)S(c)CP 例例 证明：证明：x(P(x)Q(x),xP(x)xQ(x)(1)xQ(x)附加前提附加前提(2)xQ(x)T(1)E(3)Q(c)US(2)(4)xP(x)P (5)P(c)US(4)(6)P(c)Q(c)T(3)(5)I(7)x(P(x)Q(x)UG(6)(8)x(P(x)Q(x)P(9)x(P(x)Q(x)x(P(x)Q(x)T(7)(8)I（3 3）反证法）反证法

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