离散数学(第25)陈瑜 - 副本

1、2022-1-5计算机科学与工程学院1陈瑜陈瑜EmailEmail：2022-1-52022-1-52022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院2 2主要内容主要内容n 1.1. 谓词逻辑的推理方法谓词逻辑的推理方法n 2.2.消解消解( (归结归结) )法法2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院3 32.5 2.5 谓词逻辑的推理谓词逻辑的推理n推理演算过程：推理演算过程：首先将以自然语句表示的推理问题引入谓词首先将以自然语句表示的推理问题引入谓词 加以形式化；加以形式化；若不能直接使用基本推理公式则若不能直接使用基本推理公式则消

2、去量词消去量词；在在无量词的情形下无量词的情形下使用推理规则和公式进行使用推理规则和公式进行 推理；推理；最后最后再引入量词再引入量词以求得结论。以求得结论。 2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院4 4 推理规则推理规则n命题逻辑推理的三条推理规则继续实用命题逻辑推理的三条推理规则继续实用于谓词逻辑推理！于谓词逻辑推理！（P P、T T、CPCP）n在前面介绍的推理演算过程中，如何消在前面介绍的推理演算过程中，如何消去量词或引入量词？去量词或引入量词？n下面介绍下面介绍4 4条专门针对量词的推理规则。条专门针对量词的推理规则。2022-1-52022-1-5

3、计算机科学与工程学院计算机科学与工程学院5 5 推理规则推理规则n命题逻辑推理的三条推理规则继续实用于谓词逻辑推理！（P、T、CP）n在前面介绍的推理演算过程中，如何消在前面介绍的推理演算过程中，如何消去量词或引入量词？去量词或引入量词？n下面介绍下面介绍4 4条专门针对量词的推理规则。条专门针对量词的推理规则。2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院6 6 推理规则推理规则n量词的四条重要的推理规则：量词的四条重要的推理规则：1) 1) USUS规则规则( (全称指定规则、全称指定规则、全称量词消去规则全称量词消去规则) )： ( ( x)G(x)x)G(x)

4、G(y) G(y) 或或 ( ( x)G(x)x)G(x)G(c) G(c) n注意：以上注意：以上2 2公式的成立条件：公式的成立条件： 1 1）y y是任意的不在是任意的不在G G（x x）中受约束出现的个体变项；）中受约束出现的个体变项； 2 2）c c为任意个体变项；为任意个体变项；nUSUS规则表明规则表明“每一个均成立，则其中任一个也必成每一个均成立，则其中任一个也必成立立”。 2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院7 7 推理规则推理规则n量词的四条重要的推理规则：量词的四条重要的推理规则：1) 1) USUS规则规则(全称指定规则、全称量词消去

5、规则)： (x)G(x)G(y) 或 (x)G(x)G(c) n注意：注意：以上以上2 2公式的公式的成立条件：成立条件： 1 1）y y是任意的不在是任意的不在G G（x x）中受约束出现的个体变项；）中受约束出现的个体变项； 2 2）c c为任意个体变项；为任意个体变项；nUSUS规则表明规则表明“每一个均成立，则其中任一个也必成每一个均成立，则其中任一个也必成立立”。 2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院8 8 推理规则推理规则2) 2) UGUG规则规则( (全称推广规则、全称推广规则、全称量词附加规则全称量词附加规则) )： G(y) G(y) (

6、 ( x)G(x)x)G(x)n注意：以上公式的成立条件：注意：以上公式的成立条件： 1 1）y y在在G G（x x）中自由出现，并且）中自由出现，并且y y取任意取任意yDyD时，时，G G（y y）为真；为真； 2 2）取代）取代y y的的x x不能在不能在G G（y y）中出现；）中出现； 3 3）USUS规则不是规则不是UGUG规则的逆命题；规则的逆命题； 4 4）USUS规则中规则中y y是是“某一个某一个”，而，而UGUG规则中的规则中的y y是是“每一每一个个”。 2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院9 9 推理规则推理规则2) 2) UGU

7、G规则规则( (全称推广规则、全称量词附加规则全称推广规则、全称量词附加规则) )： G(y) G(y) ( ( x)G(x)x)G(x)n注意：注意：以上公式的以上公式的成立条件：成立条件： 1 1）y y在在G G（x x）中自由出现，并且）中自由出现，并且y y取任意取任意y yD D时，时，G G（y y）均为真；均为真； 2 2）取代）取代y y的的x x不能不能在在G G（y y）中出现；）中出现； 3 3）USUS规则规则不是不是UGUG规则的逆命题；规则的逆命题； 4 4）USUS规则中规则中y y是是“某一个某一个”，而，而UGUG规则中的规则中的y y是是“每一每一个个”。

8、 2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院1010 推理规则推理规则3) 3) ESES规则规则( (存在指定规则、存在指定规则、存在量词消去规则存在量词消去规则) )： （ x)G(xx)G(x） G G（c c）n注意：以上公式的成立条件：注意：以上公式的成立条件： 1 1）c c是使是使G G（x x）为真的特定的个体常项；）为真的特定的个体常项； 2 2）c c不曾在不曾在G G（x x）中出现过；）中出现过； 3 3）G G（x x）中除）中除x x外，还有其他自由变项时，不可用此外，还有其他自由变项时，不可用此规则；规则；n尤其第一条，尤其第一条，c

9、 c不是任取一个，而是某些特定的个体！不是任取一个，而是某些特定的个体！ 例：例：G G（x x）：）：x x是男生，是男生，c c：王芳。则：（：王芳。则：（ x)G(xx)G(x） G G（c c）是错误的推理！）是错误的推理！ 2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院1111 推理规则推理规则3) 3) ES规则(存在指定规则、存在量词消去规则)： （x)G(x） G（c）n注意：注意：以上公式的以上公式的成立条件：成立条件： 1 1）c c是使是使G G（x x）为真的）为真的特定的特定的个体常项；个体常项； 2 2）c c不曾在不曾在G G（x x）中

10、出现过；）中出现过； 3 3）G G（x x）中除）中除x x外，还有其他自由变项时，外，还有其他自由变项时，不可用不可用此此规则；规则；n尤其第一条，尤其第一条，c c不是任取一个，而是某些特定的个体！不是任取一个，而是某些特定的个体！ 例：例：G G（x x）：）：x x是男生，是男生，c c：王芳。则：（：王芳。则：（ x)G(xx)G(x） G G（c c）是错误的推理！）是错误的推理！ 2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院1212 推理规则推理规则3) 3) ES规则(存在指定规则、存在量词消去规则)： （x)G(x） G（c）n注意：以上公式的成

11、立条件：注意：以上公式的成立条件： 1 1）c c是使是使G G（x x）为真的特定的个体常项；）为真的特定的个体常项； 2 2）c c不曾在不曾在G G（x x）中出现过；）中出现过； 3 3）G G（x x）中除）中除x x外，还有其他自由变项时，不可用此外，还有其他自由变项时，不可用此规则；规则；n尤其第一条，尤其第一条，c c不是任取一个，而是不是任取一个，而是某些特定某些特定的个体！的个体！ 例：例：G G（x x）：）：x x是男生，是男生，c c：王芳。则：（：王芳。则：（ x)G(xx)G(x） G G（c c）是错误的推理！）是错误的推理！ 2022-1-52022-1-5计

12、算机科学与工程学院计算机科学与工程学院1313 推理规则推理规则4) 4) EGEG规则规则( (存在推广规则、存在推广规则、存在量词附加规则存在量词附加规则) )： G G（c c） （ x)G(xx)G(x） n注意：注意：以上公式的以上公式的成立条件：成立条件： 1 1）c c是是某个某个个体常项；个体常项； 2 2）取代）取代c c的的x x不能在不能在G G（c c）中出现过；）中出现过； 2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院1414推理方法推理方法1 1）直接证明法）直接证明法2 2）CPCP规则证明法规则证明法3 3）反证法等。）反证法等。20

13、22-1-52022-1-5计算机科学与工程学院计算机科学与工程学院1515n 例例5-15-1：证明论断：证明论断“人都是要死的，苏格拉底人都是要死的，苏格拉底是人，所以苏格拉底是要死的是人，所以苏格拉底是要死的”的正确性。的正确性。证：证： 设谓词设谓词 ManMan（x x）：）：x x是人；是人； MortalMortal（x x）：）：x x是要死的；是要死的； 客体客体 s s：苏格拉底。则以上论断符号化为：苏格拉底。则以上论断符号化为： ( (x)Man(x) )Man(x) Mortal(x) Man(s) Mortal(s) 2022-1-52022-1-5计算机科学与工程学

14、院计算机科学与工程学院1616n 例5-1：证明论断“人都是要死的，苏格拉底是人，所以苏格拉底是要死的”的正确性。证：证： 设谓词设谓词 ManMan（x x）：）：x x是人；是人； MortalMortal（x x）：）：x x是要死的；是要死的； 客体客体 s s：苏格拉底。则以上论断符号化为：苏格拉底。则以上论断符号化为： ( (x)Man(x) )Man(x) Mortal(x) Man(s) Mortal(s) 2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院1717证证: : ( (续续) )（直接证明法可采用如下步骤进行）直接证明法可采用如下步骤进行）

15、1)(1)(x)Man(x) )Man(x) Mortal(x) P P 2) Man(s) 2) Man(s) Mortal(s) US 1) US 1) 3) Man(s) P 3) Man(s) P 4) Mortal(s) T(2,3)I 4) Mortal(s) T(2,3)I3 3 2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院1818n 例：例： （p40 p40 例例2.192.19）2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院1919n 例例5-25-2：试证：试证( ( x)x)( (C(x)C(x)W(x)R(x)W(

16、x)R(x) )( ( x)x)( (C(x)Q(x)C(x)Q(x) ) （ x x）( (Q(x)R(x)Q(x)R(x) )分析：分析： 前提：前提： ( ( x)(C(x)x)(C(x)W(xW(x） R(x) R(x)， （ x x）(C(x)Q(x)(C(x)Q(x) 结论：结论： （ x x）(Q(x)R(x)(Q(x)R(x)思路：在使用前提时，尽量先使用思路：在使用前提时，尽量先使用 前提。因为前提。因为 成立，即有一个特定的个体成立，即有一个特定的个体c c存在，并且存在，并且c c对对 前提中每个个体均成立，但反之不一定成立。前提中每个个体均成立，但反之不一定成立。202

17、2-1-52022-1-5计算机科学与工程学院计算机科学与工程学院2020n 例例5-25-2：试证：试证( ( x)x)( (C(x)C(x)W(x)R(x)W(x)R(x) )( ( x)(C(x)Q(x)x)(C(x)Q(x) ) （ x x）( (Q(x)R(x)Q(x)R(x) )分析：分析： 前提：前提： ( ( x)x)( (C(x)C(x)W(xW(x） R(x) R(x) )， （ x x）( (C(x)Q(x)C(x)Q(x) ) 结论：结论： （ x x）( (Q(x)R(x)Q(x)R(x) )思路：在使用前提时，尽量先使用思路：在使用前提时，尽量先使用 前提。因为前提

18、。因为 成立，即有一个特定的个体成立，即有一个特定的个体c c存在，并且存在，并且c c对对 前提中每个个体均成立，但反之不一定成立。前提中每个个体均成立，但反之不一定成立。2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院2121n 例例5-25-2：试证：试证( ( x)(C(x)x)(C(x)W(x)R(x)(W(x)R(x)( x)(C(x)Q(x) x)(C(x)Q(x) （ x x）(Q(x)R(x)(Q(x)R(x)分析：分析： 前提：前提： ( ( x)(C(x)x)(C(x)W(xW(x） R(x) R(x)， （ x x）(C(x)Q(x)(C(x)Q

19、(x) 结论：结论： （ x x）(Q(x)R(x)(Q(x)R(x)思路：思路：在使用前提时，尽量先使用在使用前提时，尽量先使用 前提。因为前提。因为 成立，即有一个特定的个体成立，即有一个特定的个体c c存在，并且存在，并且c c对对 前提中每个个体均成立，但反之不一定成立。前提中每个个体均成立，但反之不一定成立。2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院2222证明：证明：（1 1） （ x x）(C(x)Q(x) P(C(x)Q(x) P（2 2） C(a) Q(a) ES (1)C(a) Q(a) ES (1) ( (注：此处注：此处a a是是特定特定的

20、）的）（3 3） ( ( x)(C(x)x)(C(x)W(xW(x） R(x) P R(x) P（4 4） C(a)C(a)W(aW(a） R(a) US R(a) US （3 3） （注：因（注：因（3 3）中）中 “任意任意”的，所以此处可以使的，所以此处可以使用用 (2)(2)中的中的a a。若（。若（3 3）中是）中是 ，则此处不可用，则此处不可用a a。）。）（5 5） C(a) T (2)IC(a) T (2)I2 22022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院2323证明：证明：（1 1） （ x x）(C(x)Q(x) P(C(x)Q(x) P（2

21、2） C(C(a a) Q() Q(a a) ES (1) ES (1) ( (注：此处注：此处a a是是特定特定的）的）（3 3） ( ( x)(C(x)x)(C(x)W(xW(x） R(x) P R(x) P（4 4） C(a)C(a)W(aW(a） R(a) US R(a) US （3 3） （注：因（注：因（3 3）中）中 “任意任意”的，所以此处可以使的，所以此处可以使用用 (2)(2)中的中的a a。若（。若（3 3）中是）中是 ，则此处不可用，则此处不可用a a。）。）（5 5） C(a) T (2)IC(a) T (2)I2 22022-1-52022-1-5计算机科学与工程学

22、院计算机科学与工程学院2424证明：证明：（1 1） （ x x）(C(x)Q(x) P(C(x)Q(x) P（2 2） C(a) Q(a) ES (1)C(a) Q(a) ES (1) ( (注：此处注：此处a a是是特定特定的）的）（3 3） ( ( x)(C(x)x)(C(x)W(xW(x） R(x) P R(x) P（4 4） C(a)C(a)W(aW(a） R(a) US R(a) US （3 3） （注：因（注：因（3 3）中）中 “任意任意”的，所以此处可以使的，所以此处可以使用用 (2)(2)中的中的a a。若（。若（3 3）中是）中是 ，则此处不可用，则此处不可用a a。）。

23、）（5 5） C(a) T (2)IC(a) T (2)I2 22022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院2525证明：证明：（1 1） （x）(C(x)Q(x) P（2 2） C(a) Q(a) ES (1) (注：此处a是特定的）（3 3） ( ( x)(C(x)x)(C(x)W(xW(x） R(x) P R(x) P（4 4） C(C(a a) )W(W(a a） R( R(a a) US ) US （3 3） （注：因（注：因（3 3）中）中 “任意任意”的，所以此处可以使的，所以此处可以使用用 (2)(2)中的中的a a。若（。若（3 3）中是）中是 ，

24、则此处不可用，则此处不可用a a。）。）（5 5） C(a) T (2)IC(a) T (2)I2 22022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院2626证明：证明：（1 1） （x）(C(x)Q(x) P（2 2） C(a) Q(a) ES (1)C(a) Q(a) ES (1) ( (注：此处注：此处a a是是特定特定的）的）（3 3） (x)(C(x)W(x） R(x) P（4 4） C(a)W(a） R(a) US （3） （注：因（3）中“任意”的，所以此处可以使用 (2)中的a。若（3）中是 ，则此处不可用a。）（5 5） C(a) C(a) T (2)

25、IT (2)I2 22022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院2727证明（续）证明（续） ：（6 6） W(aW(a） R(a) T(4)(5)I R(a) T(4)(5)I3 3（7 7） R(a) T(6)IR(a) T(6)I2 2（8 8） Q(a) T(2)IQ(a) T(2)I2 2（9 9） Q(aQ(a） R(a) T(7)(8)I R(a) T(7)(8)I1 1（1010）（）（ x x）(Q(x)R(x) EG (9)(Q(x)R(x) EG (9)证毕证毕 2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院2828证

26、明（续）证明（续） ：（6 6） W(aW(a） R(a) T(4)(5)I R(a) T(4)(5)I3 3（7 7） R(a) T(6)IR(a) T(6)I2 2（8 8） Q(a) T(2)IQ(a) T(2)I2 2（9 9） Q(aQ(a） R(a) T(7)(8)I R(a) T(7)(8)I1 1（1010）（）（ x x）(Q(x)R(x) EG (9)(Q(x)R(x) EG (9)证毕证毕 2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院2929证明（续）证明（续） ：（6 6） W(a） R(a) T(4)(5)I3（7 7） R(a) T(6)

27、I2（8 8） Q(a) T(2)IQ(a) T(2)I2 2（9 9） Q(aQ(a） R(a) T(7)(8)I R(a) T(7)(8)I1 1（1010）（）（ x x）(Q(x)R(x) EG (9)(Q(x)R(x) EG (9)证毕证毕 2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院3030证明（续）证明（续） ：（6 6） W(a） R(a) T(4)(5)I3（7 7） R(a) T(6)IR(a) T(6)I2 2（8 8） Q(a) T(2)IQ(a) T(2)I2 2（9 9） Q(Q(a a） R( R(a a) T(7)(8)I) T(7)

28、(8)I1 1（1010）（）（ x x）(Q(x)R(x) EG (9)(Q(x)R(x) EG (9)证毕证毕 2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院3131证明（续）证明（续） ：（6 6） W(a） R(a) T(4)(5)I3（7 7） R(a) T(6)I2（8 8） Q(a) T(2)I2（9 9） Q(aQ(a） R(a) T(7)(8)I R(a) T(7)(8)I1 1（1010）（ x x）(Q(x)R(x) EG (9)(Q(x)R(x) EG (9)证毕证毕 2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院32

29、32例例5-35-3：试证明：试证明： 前提：前提： ( ( x)(F(x)H(x), x)(F(x)H(x), ( ( x)(G(x)x)(G(x)H(x)H(x) 结论：结论： ( ( x)(G(x)x)(G(x)F F(x) (x) 证明：证明：n ( ( x)(F(x)H(x) Px)(F(x)H(x) P(2) (2) ( x)(x)(F(x) F(x) H(x) T(1)EH(x) T(1)E(3) (3) ( x)( H(x) x)( H(x) F(x) T(2)EF(x) T(2)E(4) H(y) (4) H(y) F(y) US(3)F(y) US(3)(5) (5) (

30、x)(G(x)x)(G(x)H(x) PH(x) Pn G(y) G(y)H(y) US (5)H(y) US (5)n(7) G(y)(7) G(y) F(y) T(4)(6)IF(y) T(4)(6)I6 6(8) (8) ( x)(G(x)x)(G(x)F F(x) UG(7)(x) UG(7)证毕证毕 ( (因为（因为（7 7）中）中y y指代任意的指代任意的) )2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院3333例例5-35-3：试证明：试证明： 前提：前提： ( ( x)(F(x)H(x), x)(F(x)H(x), ( ( x)(G(x)x)(G(x

31、)H(x) H(x) 结论：结论： ( ( x)(G(x)x)(G(x)F F(x)(x) 证明：证明：n ( ( x)(F(x)H(x) Px)(F(x)H(x) P(2) (2) ( x)(x)(F(x) F(x) H(x) T(1)EH(x) T(1)E(3) (3) ( x)( H(x) x)( H(x) F(x) T(2)EF(x) T(2)E(4) H(y) (4) H(y) F(y) US(3)F(y) US(3)(5) (5) ( x)(G(x)x)(G(x)H(x) PH(x) Pn G(y) G(y)H(y) US (5)H(y) US (5)n(7) G(y)(7) G(

32、y) F(y) T(4)(6)IF(y) T(4)(6)I6 6(8) (8) ( x)(G(x)x)(G(x)F F(x) UG(7)(x) UG(7)证毕证毕 ( (因为（因为（7 7）中）中y y指代任意的指代任意的) )2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院3434例例5-35-3：试证明：试证明： 前提：前提： ( ( x)(F(x)H(x), x)(F(x)H(x), ( ( x)(G(x)x)(G(x)H(x) H(x) 结论：结论： ( ( x)(G(x)x)(G(x)F F(x)(x) 证明：证明：n ( ( x)(F(x)H(x) Px)(

33、F(x)H(x) P(2)(2) ( ( x)(x)(F(x) F(x) H(x) T(1)EH(x) T(1)E(3) (3) ( x)( H(x) x)( H(x) F(x) T(2)EF(x) T(2)E(4) H(y) (4) H(y) F(y) US(3)F(y) US(3)(5) (5) ( x)(G(x)x)(G(x)H(x) PH(x) Pn G(y) G(y)H(y) US (5)H(y) US (5)n(7) G(y)(7) G(y) F(y) T(4)(6)IF(y) T(4)(6)I6 6(8) (8) ( x)(G(x)x)(G(x)F F(x) UG(7)(x) U

34、G(7)证毕证毕 ( (因为（因为（7 7）中）中y y指代任意的指代任意的) )2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院3535例例5-35-3：试证明：试证明： 前提：前提： ( ( x)(F(x)H(x), x)(F(x)H(x), ( ( x)(G(x)x)(G(x)H(x) H(x) 结论：结论： ( ( x)(G(x)x)(G(x)F F(x)(x) 证明：证明：n (x)(F(x)H(x) P(2)(2) ( ( x)(x)(F(x) F(x) H(x) T(1)EH(x) T(1)E(3)(3) ( ( x)( H(x) x)( H(x) F(x

35、) T(2)EF(x) T(2)E(4) H(y) (4) H(y) F(y) US(3)F(y) US(3)(5) (5) ( x)(G(x)x)(G(x)H(x) PH(x) Pn G(y) G(y)H(y) US (5)H(y) US (5)n(7) G(y)(7) G(y) F(y) T(4)(6)IF(y) T(4)(6)I6 6(8) (8) ( x)(G(x)x)(G(x)F F(x) UG(7)(x) UG(7)证毕证毕 ( (因为（因为（7 7）中）中y y指代任意的指代任意的) )2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院3636例例5-35-

36、3：试证明：试证明： 前提：前提： ( ( x)(F(x)H(x), x)(F(x)H(x), ( ( x)(G(x)x)(G(x)H(x) H(x) 结论：结论： ( ( x)(G(x)x)(G(x)F F(x)(x) 证明：证明：n (x)(F(x)H(x) P(2)(2) (x)(F(x) H(x) T(1)E(3)(3) ( ( x)( H(x) x)( H(x) F(x) T(2)EF(x) T(2)E(4)(4) H(y) H(y) F(y) US(3)F(y) US(3)(5) (5) ( x)(G(x)x)(G(x)H(x) PH(x) Pn G(y) G(y)H(y) US

37、(5)H(y) US (5)n(7) G(y)(7) G(y) F(y) T(4)(6)IF(y) T(4)(6)I6 6(8) (8) ( x)(G(x)x)(G(x)F F(x) UG(7)(x) UG(7)证毕证毕 ( (因为（因为（7 7）中）中y y指代任意的指代任意的) )2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院3737例例5-35-3：试证明：试证明： 前提：前提： ( ( x)(F(x)H(x), x)(F(x)H(x), ( ( x)(G(x)x)(G(x)H(x) H(x) 结论：结论： ( ( x)(G(x)x)(G(x)F F(x)(x)

38、 证明：证明：n (x)(F(x)H(x) P(2)(2) (x)(F(x) H(x) T(1)E(3)(3) (x)( H(x) F(x) T(2)E(4)(4) H(y) F(y) US(3)(5)(5) ( ( x)(G(x)x)(G(x)H(x) PH(x) Pn G(y) G(y)H(y) US (5)H(y) US (5)n(7) G(y)(7) G(y) F(y) T(4)(6)IF(y) T(4)(6)I6 6(8) (8) ( x)(G(x)x)(G(x)F F(x) UG(7)(x) UG(7)证毕证毕 ( (因为（因为（7 7）中）中y y指代任意的指代任意的) )202

39、2-1-52022-1-5计算机科学与工程学院计算机科学与工程学院3838例例5-35-3：试证明：试证明： 前提：前提： ( ( x)(F(x)H(x), x)(F(x)H(x), ( ( x)(G(x)x)(G(x)H(x) H(x) 结论：结论： ( ( x)(G(x)x)(G(x)F F(x)(x) 证明：证明：n (x)(F(x)H(x) P(2)(2) (x)(F(x) H(x) T(1)E(3)(3) (x)( H(x) F(x) T(2)E(4)(4) H(y) F(y) US(3)(5)(5) ( ( x)(G(x)x)(G(x)H(x) PH(x) Pn G(y) G(y)

40、H(y) US (5)H(y) US (5)n(7) G(y)(7) G(y) F(y) T(4)(6)IF(y) T(4)(6)I6 6(8) (8) ( x)(G(x)x)(G(x)F F(x) UG(7)(x) UG(7)证毕证毕 ( (因为（因为（7 7）中）中y y指代任意的指代任意的) )2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院3939例例5-35-3：试证明：试证明： 前提：前提： ( ( x)(F(x)H(x), x)(F(x)H(x), ( ( x)(G(x)x)(G(x)H(x) H(x) 结论：结论： ( ( x)(G(x)x)(G(x)F

41、 F(x)(x) 证明：证明：n (x)(F(x)H(x) P(2)(2) (x)(F(x) H(x) T(1)E(3)(3) (x)( H(x) F(x) T(2)E(4)(4) H(y) H(y) F(y) US(3)F(y) US(3)(5)(5) (x)(G(x)H(x) Pn G(y) G(y)H(y) US (5)H(y) US (5)n(7)(7) G(y)G(y) F(y) T(4)(6)IF(y) T(4)(6)I6 6(8) (8) ( x)(G(x)x)(G(x)F F(x) UG(7)(x) UG(7)证毕证毕 ( (因为（因为（7 7）中）中y y指代任意的指代任意的

42、) )2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院4040例例5-35-3：试证明：试证明： 前提：前提： ( ( x)(F(x)H(x), x)(F(x)H(x), ( ( x)(G(x)x)(G(x)H(x) H(x) 结论：结论： ( ( x)(G(x)x)(G(x)F F(x)(x) 证明：证明：n (x)(F(x)H(x) P(2)(2) (x)(F(x) H(x) T(1)E(3)(3) (x)( H(x) F(x) T(2)E(4)(4) H(y) F(y) US(3)(5)(5) (x)(G(x)H(x) Pn G(y)H(y) US (5)n(7)

43、(7) G(y)G(y) F(y) T(4)(6)IF(y) T(4)(6)I6 6(8)(8) ( ( x)(G(x)x)(G(x)F F(x) UG(7)(x) UG(7)证毕证毕 ( (因为（因为（7 7）中）中y y指代任意的指代任意的) )2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院4141n 例例5-45-4： “有些病人相信所有的医生，而病人均不相有些病人相信所有的医生，而病人均不相信江湖骗子信江湖骗子”。试证明试证明“医生不是骗子医生不是骗子”。 符号化：符号化：R(x):xR(x):x是病人是病人 D(x):xD(x):x是医生是医生 S(x):x

44、S(x):x是江湖骗子是江湖骗子 L(x,y):xL(x,y):x相信相信y y 前提：前提：( ( x)(R(x)(x)(R(x)( y)(D(yy)(D(y） L(x,y), L(x,y), ( ( x )(R(x) x )(R(x) ( ( y)(S(yy)(S(y） L(x,y)L(x,y) 结论：结论： ( ( x )(D(x) x )(D(x) S(x)S(x) 思路：先用思路：先用 再用再用 ，即先找特殊的再找一般的！，即先找特殊的再找一般的！2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院4242n 例例5-45-4： “ “有些病人相信所有的医生，而病

45、人均不相有些病人相信所有的医生，而病人均不相信江湖骗子信江湖骗子”。试证明。试证明“医生不是骗子医生不是骗子”。 符号化：符号化：R(x):xR(x):x是病人是病人 D(x):xD(x):x是医生是医生 S(x):xS(x):x是江湖骗子是江湖骗子 L(x,y):xL(x,y):x相信相信y y 前提：前提：( ( x)(R(x)(x)(R(x)( y)(D(yy)(D(y） L(x,y), L(x,y), ( ( x )(R(x) x )(R(x) ( ( y)(S(yy)(S(y） L(x,y)L(x,y) 结论：结论： ( ( x )(D(x) x )(D(x) S(x)S(x) 思路

46、：先用思路：先用 再用再用 ，即先找特殊的再找一般的！，即先找特殊的再找一般的！2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院4343n 例例5-45-4： “有些病人相信所有的医生，而病人均不相有些病人相信所有的医生，而病人均不相信江湖骗子信江湖骗子”。试证明。试证明“医生不是骗子医生不是骗子”。 符号化：符号化：R(x):xR(x):x是病人是病人 D(x):xD(x):x是医生是医生 S(x):xS(x):x是江湖骗子是江湖骗子 L(x,y):xL(x,y):x相信相信y y 前提：前提：( ( x)x)( (R(x)(R(x)( y)y)( (D(yD(y）

47、L(x,y) L(x,y) ) ), , ( ( x )x )( (R(x) R(x) ( ( y)y)( (S(yS(y） L(x,y)L(x,y) ) ) 结论：结论： ( ( x )(D(x) x )(D(x) S(x)S(x) 思路：先用思路：先用 再用再用 ，即先找特殊的再找一般的！，即先找特殊的再找一般的！2022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院4444n 例例5-45-4： “有些病人相信所有的医生，而病人均不相有些病人相信所有的医生，而病人均不相信江湖骗子信江湖骗子”。试证明。试证明“医生不是骗子医生不是骗子”。 符号化：符号化：R(x):xR(

48、x):x是病人是病人 D(x):xD(x):x是医生是医生 S(x):xS(x):x是江湖骗子是江湖骗子 L(x,y):xL(x,y):x相信相信y y 前提：前提：( ( x)(R(x)(x)(R(x)( y)(D(yy)(D(y） L(x,y), L(x,y), ( ( x )(R(x) x )(R(x) ( ( y)(S(yy)(S(y） L(x,y)L(x,y) 结论：结论： ( ( x )(D(x) x )(D(x) S(x)S(x) 思路：思路：先用先用 再用再用 ，即先找特殊的再找一般的！，即先找特殊的再找一般的！2022-1-52022-1-5计算机科学与工程学院计算机科学与工

49、程学院4545证明：证明： (1) (1) ( ( x)(R(x)(x)(R(x)( y)(D(yy)(D(y） L(x,y) P L(x,y) P(2) R(a)(2) R(a)( y)(D(yy)(D(y） L(a,y) ES (1) L(a,y) ES (1) (a (a是相信所有医生的那个人是相信所有医生的那个人) ) (3) (3) ( y)(D(yy)(D(y） L(a,y) T(2)I L(a,y) T(2)I2 2(4) D(t(4) D(t） L(a,t) US L(a,t) US（3 3） ( (此处此处t t是所有的人，与（是所有的人，与（2 2）中）中a a不同不同)

50、) (5) (5) ( x)(R(x) x)(R(x) ( ( y)(S(y)y)(S(y)L(x,y) PL(x,y) P(6) R(a) (6) R(a) ( ( y)(S(y)y)(S(y)L(a,y) US (5)L(a,y) US (5) ( (注意此处的注意此处的a a：既然：既然(5)(5)中指所有的人，那么就应包中指所有的人，那么就应包括括(2)(2)中的那个特定的人）中的那个特定的人）(7) R(a) T(2)I(7) R(a) T(2)I2 22022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院4646证明：证明： (1) (1) ( ( x)(R(x)

51、(x)(R(x)( y)(D(yy)(D(y） L(x,y) P L(x,y) P(2) (2) R(a)(R(a)( y)(D(yy)(D(y） L(a,y) ES (1) L(a,y) ES (1) (a(a是相信所有医生的那个人是相信所有医生的那个人) ) (3) (3) ( y)(D(yy)(D(y） L(a,y) T(2)I L(a,y) T(2)I2 2(4) D(t(4) D(t） L(a,t) US L(a,t) US（3 3） ( (此处此处t t是所有的人，与（是所有的人，与（2 2）中）中a a不同不同) ) (5) (5) ( x)(R(x) x)(R(x) ( ( y

52、)(S(y)y)(S(y)L(x,y) PL(x,y) P(6) R(a) (6) R(a) ( ( y)(S(y)y)(S(y)L(a,y) US (5)L(a,y) US (5) ( (注意此处的注意此处的a a：既然：既然(5)(5)中指所有的人，那么就应包中指所有的人，那么就应包括括(2)(2)中的那个特定的人）中的那个特定的人）(7) R(a) T(2)I(7) R(a) T(2)I2 22022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院4747证明：证明： (1) (1) (x)(R(x)(y)(D(y） L(x,y) P(2) (2) R(a)(R(a)(

53、y)(D(yy)(D(y） L(a,y) ES (1) L(a,y) ES (1) (a (a是相信所有医生的那个人是相信所有医生的那个人) ) (3) (3) ( ( y)(D(yy)(D(y） L(a,y) T(2)I L(a,y) T(2)I2 2(4) D(t(4) D(t） L(a,t) US L(a,t) US（3 3） ( (此处此处t t是所有的人，与（是所有的人，与（2 2）中）中a a不同不同) ) (5) (5) ( x)(R(x) x)(R(x) ( ( y)(S(y)y)(S(y)L(x,y) PL(x,y) P(6) R(a) (6) R(a) ( ( y)(S(y

54、)y)(S(y)L(a,y) US (5)L(a,y) US (5) ( (注意此处的注意此处的a a：既然：既然(5)(5)中指所有的人，那么就应包中指所有的人，那么就应包括括(2)(2)中的那个特定的人）中的那个特定的人）(7) R(a) T(2)I(7) R(a) T(2)I2 22022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院4848证明：证明： (1) (1) (x)(R(x)(y)(D(y） L(x,y) P(2) (2) R(a)(y)(D(y） L(a,y) ES (1) (a是相信所有医生的那个人) (3) (3) ( ( y)(D(yy)(D(y）

55、L(a,y) T(2)I L(a,y) T(2)I2 2(4) (4) D(tD(t） L(a,t) US L(a,t) US（3 3） ( (此处此处t t是所有的人，与（是所有的人，与（2 2）中）中a a不同不同) ) (5) (5) ( x)(R(x) x)(R(x) ( ( y)(S(y)y)(S(y)L(x,y) PL(x,y) P(6) R(a) (6) R(a) ( ( y)(S(y)y)(S(y)L(a,y) US (5)L(a,y) US (5) ( (注意此处的注意此处的a a：既然：既然(5)(5)中指所有的人，那么就应包中指所有的人，那么就应包括括(2)(2)中的那个

56、特定的人）中的那个特定的人）(7) R(a) T(2)I(7) R(a) T(2)I2 22022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院4949证明：证明： (1) (1) (x)(R(x)(y)(D(y） L(x,y) P(2) (2) R(a)(y)(D(y） L(a,y) ES (1) (a是相信所有医生的那个人) (3) (3) (y)(D(y） L(a,y) T(2)I2(4) (4) D(t） L(a,t) US（3） (此处t是所有的人，与（2）中a不同) (5) (5) ( ( x)(R(x) x)(R(x) ( ( y)(S(y)y)(S(y)L(x

57、,y) PL(x,y) P(6) R(a) (6) R(a) ( ( y)(S(y)y)(S(y)L(a,y) US (5)L(a,y) US (5) ( (注意此处的注意此处的a a：既然：既然(5)(5)中指所有的人，那么就应包中指所有的人，那么就应包括括(2)(2)中的那个特定的人）中的那个特定的人）(7) R(a) T(2)I(7) R(a) T(2)I2 22022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院5050证明：证明： (1) (1) (x)(R(x)(y)(D(y） L(x,y) P(2) (2) R(a)(y)(D(y） L(a,y) ES (1)

58、(a是相信所有医生的那个人) (3) (3) (y)(D(y） L(a,y) T(2)I2(4) (4) D(t） L(a,t) US（3） (此处t是所有的人，与（2）中a不同) (5) (5) ( ( x)(R(x) x)(R(x) ( ( y)(S(y)y)(S(y)L(x,y) PL(x,y) P(6)(6) R(a) R(a) ( ( y)(S(y)y)(S(y)L(a,y) US (5)L(a,y) US (5) ( (注意此处的注意此处的a a：既然：既然(5)(5)中指所有的人，那么就应包中指所有的人，那么就应包括括(2)(2)中的那个特定的人）中的那个特定的人）(7) R(a

59、) T(2)I(7) R(a) T(2)I2 22022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院5151证明：证明： (1) (1) (x)(R(x)(y)(D(y） L(x,y) P(2) (2) R(a)(R(a)( y)(D(yy)(D(y） L(a,y) ES (1) L(a,y) ES (1) (a(a是相信所有医生的那个人是相信所有医生的那个人) ) (3) (3) (y)(D(y） L(a,y) T(2)I2(4) (4) D(t） L(a,t) US（3） (此处t是所有的人，与（2）中a不同) (5) (5) (x)(R(x) (y)(S(y)L(x,

60、y) P(6)(6) R(a) (y)(S(y)L(a,y) US (5) (注意此处的a：既然(5)中指所有的人，那么就应包括(2)中的那个特定的人）(7) (7) R(a) T(2)IR(a) T(2)I2 22022-1-52022-1-5计算机科学与工程学院计算机科学与工程学院5252证明：证明： (8) (8) ( ( y)(S(y)y)(S(y)L(a,y) T(6)(7)IL(a,y) T(6)(7)I3 3(9) S(t) (9) S(t) L(a,t) US (8)L(a,t) US (8)(10) L(a,t) (10) L(a,t) S(t) T(9)ES(t) T(9)