陳瑜Email：chenyu.inbox@gmail11/20/2023離散數(shù)學(xué)計(jì)算機(jī)學(xué)院1/8/20241計(jì)算機(jī)科學(xué)與工程學(xué)院主要內(nèi)容1.謂詞邏輯的推理方法2.消解(歸結(jié))法1/8/20242計(jì)算機(jī)科學(xué)與工程學(xué)院2.5謂詞邏輯的推理推理演算過(guò)程：①首先將以自然語(yǔ)句表示的推理問(wèn)題引入謂詞加以形式化；★②假設(shè)不能直接使用根本推理公式那么消去量詞；③在無(wú)量詞的情形下使用推理規(guī)那么和公式進(jìn)行推理；④最后再引入量詞以求得結(jié)論。

1/8/20243計(jì)算機(jī)科學(xué)與工程學(xué)院推理規(guī)那么命題邏輯推理的三條推理規(guī)那么繼續(xù)實(shí)用于謂詞邏輯推理！〔P、T、CP〕在前面介紹的推理演算過(guò)程中，如何消去量詞或引入量詞？下面介紹4條專門(mén)針對(duì)量詞的推理規(guī)那么。1/8/20244計(jì)算機(jī)科學(xué)與工程學(xué)院推理規(guī)那么命題邏輯推理的三條推理規(guī)那么繼續(xù)實(shí)用于謂詞邏輯推理！〔P、T、CP〕在前面介紹的推理演算過(guò)程中，如何消去量詞或引入量詞？下面介紹4條專門(mén)針對(duì)量詞的推理規(guī)那么。1/8/20245計(jì)算機(jī)科學(xué)與工程學(xué)院推理規(guī)那么量詞的四條重要的推理規(guī)那么：1)US規(guī)那么(全稱指定規(guī)那么、全稱量詞消去規(guī)那么)： (x)G(x)G(y)①或(x)G(x)G(c)②注意：以上2公式的成立條件：1〕y是任意的不在G〔x〕中受約束出現(xiàn)的個(gè)體變項(xiàng)；2〕c為任意個(gè)體變項(xiàng)；US規(guī)那么說(shuō)明“每一個(gè)均成立，那么其中任一個(gè)也必成立〞。

1/8/20246計(jì)算機(jī)科學(xué)與工程學(xué)院推理規(guī)那么量詞的四條重要的推理規(guī)那么：1)US規(guī)那么(全稱指定規(guī)那么、全稱量詞消去規(guī)那么)： (x)G(x)G(y)①或(x)G(x)G(c)②注意：以上2公式的成立條件：1〕y是任意的不在G〔x〕中受約束出現(xiàn)的個(gè)體變項(xiàng)；2〕c為任意個(gè)體變項(xiàng)；US規(guī)那么說(shuō)明“每一個(gè)均成立，那么其中任一個(gè)也必成立〞。1/8/20247計(jì)算機(jī)科學(xué)與工程學(xué)院推理規(guī)那么2)UG規(guī)那么(全稱推廣規(guī)那么、全稱量詞附加規(guī)那么)： G(y)(x)G(x)注意：以上公式的成立條件：1〕y在G〔x〕中自由出現(xiàn)，并且y取任意y∈D時(shí)，G〔y〕為真；2〕取代y的x不能在G〔y〕中出現(xiàn)；3〕US規(guī)那么不是UG規(guī)那么的逆命題；4〕US規(guī)那么中y是“某一個(gè)〞，而UG規(guī)那么中的y是“每一個(gè)〞。

1/8/20248計(jì)算機(jī)科學(xué)與工程學(xué)院推理規(guī)那么2)UG規(guī)那么(全稱推廣規(guī)那么、全稱量詞附加規(guī)那么)： G(y)(x)G(x)注意：以上公式的成立條件：1〕y在G〔x〕中自由出現(xiàn)，并且y取任意y∈D時(shí)，G〔y〕均為真；2〕取代y的x不能在G〔y〕中出現(xiàn)；3〕US規(guī)那么不是UG規(guī)那么的逆命題；4〕US規(guī)那么中y是“某一個(gè)〞，而UG規(guī)那么中的y是“每一個(gè)〞。

1/8/20249計(jì)算機(jī)科學(xué)與工程學(xué)院推理規(guī)那么3)ES規(guī)那么(存在指定規(guī)那么、存在量詞消去規(guī)那么)： 〔x)G(x〕G〔c〕注意：以上公式的成立條件：1〕c是使G〔x〕為真的特定的個(gè)體常項(xiàng)；2〕c不曾在G〔x〕中出現(xiàn)過(guò)；3〕G〔x〕中除x外，還有其他自由變項(xiàng)時(shí)，不可用此規(guī)那么；尤其第一條，c不是任取一個(gè)，而是某些特定的個(gè)體！例：G〔x〕：x是男生，c：王芳。那么：〔x)G(x〕G〔c〕是錯(cuò)誤的推理！

1/8/202410計(jì)算機(jī)科學(xué)與工程學(xué)院推理規(guī)那么3)ES規(guī)那么(存在指定規(guī)那么、存在量詞消去規(guī)那么)： 〔x)G(x〕G〔c〕注意：以上公式的成立條件：1〕c是使G〔x〕為真的特定的個(gè)體常項(xiàng)；2〕c不曾在G〔x〕中出現(xiàn)過(guò)；3〕G〔x〕中除x外，還有其他自由變項(xiàng)時(shí)，不可用此規(guī)那么；尤其第一條，c不是任取一個(gè)，而是某些特定的個(gè)體！例：G〔x〕：x是男生，c：王芳。那么：〔x)G(x〕G〔c〕是錯(cuò)誤的推理！

1/8/202411計(jì)算機(jī)科學(xué)與工程學(xué)院推理規(guī)那么3)ES規(guī)那么(存在指定規(guī)那么、存在量詞消去規(guī)那么)： 〔x)G(x〕G〔c〕注意：以上公式的成立條件：1〕c是使G〔x〕為真的特定的個(gè)體常項(xiàng)；2〕c不曾在G〔x〕中出現(xiàn)過(guò)；3〕G〔x〕中除x外，還有其他自由變項(xiàng)時(shí)，不可用此規(guī)那么；尤其第一條，c不是任取一個(gè)，而是某些特定的個(gè)體！例：G〔x〕：x是男生，c：王芳。那么：〔x)G(x〕G〔c〕是錯(cuò)誤的推理！

1/8/202412計(jì)算機(jī)科學(xué)與工程學(xué)院推理規(guī)那么4)EG規(guī)那么(存在推廣規(guī)那么、存在量詞附加規(guī)那么)： G〔c〕〔x)G(x〕注意：以上公式的成立條件：1〕c是某個(gè)個(gè)體常項(xiàng)；2〕取代c的x不能在G〔c〕中出現(xiàn)過(guò)；

1/8/202413計(jì)算機(jī)科學(xué)與工程學(xué)院推理方法1〕直接證明法2〕CP規(guī)那么證明法3〕反證法等。1/8/202414計(jì)算機(jī)科學(xué)與工程學(xué)院例5-1：證明論斷“人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的〞的正確性。證：設(shè)謂詞Man〔x〕：x是人；Mortal〔x〕：x是要死的；客體s：蘇格拉底。那么以上論斷符號(hào)化為：(x)[Man(x)Mortal(x)]∧Man(s)Mortal(s)

1/8/202415計(jì)算機(jī)科學(xué)與工程學(xué)院例5-1：證明論斷“人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的〞的正確性。證：設(shè)謂詞Man〔x〕：x是人；Mortal〔x〕：x是要死的；客體s：蘇格拉底。那么以上論斷符號(hào)化為：(x)[Man(x)Mortal(x)]∧Man(s)Mortal(s)

1/8/202416計(jì)算機(jī)科學(xué)與工程學(xué)院證:(續(xù))〔直接證明法可采用如下步驟進(jìn)行〕1)(x)[Man(x)Mortal(x)]P2)Man(s)Mortal(s)US1)3)Man(s)P4)Mortal(s)T(2,3)I3

1/8/202417計(jì)算機(jī)科學(xué)與工程學(xué)院例：〔p40例2.19〕1/8/202418計(jì)算機(jī)科學(xué)與工程學(xué)院例5-2：試證(x)(C(x)W(x)∧R(x))∧(x)(C(x)∧Q(x))〔x〕(Q(x)∧R(x))分析：前提：(x)(C(x)W(x〕∧R(x))，〔x〕(C(x)∧Q(x))結(jié)論：〔x〕(Q(x)∧R(x))思路：在使用前提時(shí)，盡量先使用前提。因?yàn)槌闪ⅲ从幸粋€(gè)特定的個(gè)體c存在，并且c對(duì)前提中每個(gè)個(gè)體均成立，但反之不一定成立。1/8/202419計(jì)算機(jī)科學(xué)與工程學(xué)院例5-2：試證(x)(C(x)W(x)∧R(x))∧(x)(C(x)∧Q(x))〔x〕(Q(x)∧R(x))分析：前提：(x)(C(x)W(x〕∧R(x))，〔x〕(C(x)∧Q(x))結(jié)論：〔x〕(Q(x)∧R(x))思路：在使用前提時(shí)，盡量先使用前提。因?yàn)槌闪ⅲ从幸粋€(gè)特定的個(gè)體c存在，并且c對(duì)前提中每個(gè)個(gè)體均成立，但反之不一定成立。1/8/202420計(jì)算機(jī)科學(xué)與工程學(xué)院例5-2：試證(x)(C(x)W(x)∧R(x))∧(x)(C(x)∧Q(x))〔x〕(Q(x)∧R(x))分析：前提：(x)(C(x)W(x〕∧R(x))，〔x〕(C(x)∧Q(x))結(jié)論：〔x〕(Q(x)∧R(x))思路：在使用前提時(shí)，盡量先使用前提。因?yàn)槌闪ⅲ从幸粋€(gè)特定的個(gè)體c存在，并且c對(duì)前提中每個(gè)個(gè)體均成立，但反之不一定成立。1/8/202421計(jì)算機(jī)科學(xué)與工程學(xué)院證明：〔1〕〔x〕(C(x)∧Q(x))P〔2〕C(a)∧Q(a)ES(1)(注：此處a是特定的〕〔3〕(x)(C(x)W(x〕∧R(x))P〔4〕C(a)W(a〕∧R(a))US〔3〕〔注：因〔3〕中“任意〞的，所以此處可以使用(2)中的a。假設(shè)〔3〕中是，那么此處不可用a。〕〔5〕C(a)T(2)I21/8/202422計(jì)算機(jī)科學(xué)與工程學(xué)院證明：〔1〕〔x〕(C(x)∧Q(x))P〔2〕C(a)∧Q(a)ES(1)(注：此處a是特定的〕〔3〕(x)(C(x)W(x〕∧R(x))P〔4〕C(a)W(a〕∧R(a))US〔3〕〔注：因〔3〕中“任意〞的，所以此處可以使用(2)中的a。假設(shè)〔3〕中是，那么此處不可用a。〕〔5〕C(a)T(2)I21/8/202423計(jì)算機(jī)科學(xué)與工程學(xué)院證明：〔1〕〔x〕(C(x)∧Q(x))P〔2〕C(a)∧Q(a)ES(1)(注：此處a是特定的〕〔3〕(x)(C(x)W(x〕∧R(x))P〔4〕C(a)W(a〕∧R(a))US〔3〕〔注：因〔3〕中“任意〞的，所以此處可以使用(2)中的a。假設(shè)〔3〕中是，那么此處不可用a。〕〔5〕C(a)T(2)I21/8/202424計(jì)算機(jī)科學(xué)與工程學(xué)院證明：〔1〕〔x〕(C(x)∧Q(x))P〔2〕C(a)∧Q(a)ES(1)(注：此處a是特定的〕〔3〕(x)(C(x)W(x〕∧R(x))P〔4〕C(a)W(a〕∧R(a))US〔3〕〔注：因〔3〕中“任意〞的，所以此處可以使用(2)中的a。假設(shè)〔3〕中是，那么此處不可用a。〕〔5〕C(a)T(2)I21/8/202425計(jì)算機(jī)科學(xué)與工程學(xué)院證明：〔1〕〔x〕(C(x)∧Q(x))P〔2〕C(a)∧Q(a)ES(1)(注：此處a是特定的〕〔3〕(x)(C(x)W(x〕∧R(x))P〔4〕C(a)W(a〕∧R(a))US〔3〕〔注：因〔3〕中“任意〞的，所以此處可以使用(2)中的a。假設(shè)〔3〕中是，那么此處不可用a。〕〔5〕C(a)T(2)I21/8/202426計(jì)算機(jī)科學(xué)與工程學(xué)院證明〔續(xù)〕：〔6〕W(a〕∧R(a)T(4)(5)I3〔7〕R(a)T(6)I2〔8〕Q(a)T(2)I2〔9〕Q(a〕∧R(a)T(7)(8)I1〔10〕〔x〕(Q(x)∧R(x))EG(9)證畢■

1/8/202427計(jì)算機(jī)科學(xué)與工程學(xué)院證明〔續(xù)〕：〔6〕W(a〕∧R(a)T(4)(5)I3〔7〕R(a)T(6)I2〔8〕Q(a)T(2)I2〔9〕Q(a〕∧R(a)T(7)(8)I1〔10〕〔x〕(Q(x)∧R(x))EG(9)證畢■

1/8/202428計(jì)算機(jī)科學(xué)與工程學(xué)院證明〔續(xù)〕：〔6〕W(a〕∧R(a)T(4)(5)I3〔7〕R(a)T(6)I2〔8〕Q(a)T(2)I2〔9〕Q(a〕∧R(a)T(7)(8)I1〔10〕〔x〕(Q(x)∧R(x))EG(9)證畢■

1/8/202429計(jì)算機(jī)科學(xué)與工程學(xué)院證明〔續(xù)〕：〔6〕W(a〕∧R(a)T(4)(5)I3〔7〕R(a)T(6)I2〔8〕Q(a)T(2)I2〔9〕Q(a〕∧R(a)T(7)(8)I1〔10〕〔x〕(Q(x)∧R(x))EG(9)證畢■

1/8/202430計(jì)算機(jī)科學(xué)與工程學(xué)院證明〔續(xù)〕：〔6〕W(a〕∧R(a)T(4)(5)I3〔7〕R(a)T(6)I2〔8〕Q(a)T(2)I2〔9〕Q(a〕∧R(a)T(7)(8)I1〔10〕〔x〕(Q(x)∧R(x))EG(9)證畢■

1/8/202431計(jì)算機(jī)科學(xué)與工程學(xué)院例5-3：試證明：前提：～(x)(F(x)∧H(x)),(x)(G(x)H(x))結(jié)論：(x)(G(x)～F(x))證明：～(x)(F(x)∧H(x))P(2)(x)(～F(x)∨～H(x))T(1)E(3)(x)(H(x)～F(x))T(2)E(4)H(y)～F(y)US(3)(5)(x)(G(x)H(x))PG(y)H(y)US(5)(7)G(y)～F(y)T(4)(6)I6(8)(x)(G(x)～F(x))UG(7)證畢■(因?yàn)椤?〕中y指代任意的)1/8/202432計(jì)算機(jī)科學(xué)與工程學(xué)院例5-3：試證明：前提：～(x)(F(x)∧H(x)),(x)(G(x)H(x))結(jié)論：(x)(G(x)～F(x))證明：～(x)(F(x)∧H(x))P(2)(x)(～F(x)∨～H(x))T(1)E(3)(x)(H(x)～F(x))T(2)E(4)H(y)～F(y)US(3)(5)(x)(G(x)H(x))PG(y)H(y)US(5)(7)G(y)～F(y)T(4)(6)I6(8)(x)(G(x)～F(x))UG(7)證畢■(因?yàn)椤?〕中y指代任意的)1/8/202433計(jì)算機(jī)科學(xué)與工程學(xué)院例5-3：試證明：前提：～(x)(F(x)∧H(x)),(x)(G(x)H(x))結(jié)論：(x)(G(x)～F(x))證明：～(x)(F(x)∧H(x))P(2)(x)(～F(x)∨～H(x))T(1)E(3)(x)(H(x)～F(x))T(2)E(4)H(y)～F(y)US(3)(5)(x)(G(x)H(x))PG(y)H(y)US(5)(7)G(y)～F(y)T(4)(6)I6(8)(x)(G(x)～F(x))UG(7)證畢■(因?yàn)椤?〕中y指代任意的)1/8/202434計(jì)算機(jī)科學(xué)與工程學(xué)院例5-3：試證明：前提：～(x)(F(x)∧H(x)),(x)(G(x)H(x))結(jié)論：(x)(G(x)～F(x))證明：～(x)(F(x)∧H(x))P(2)(x)(～F(x)∨～H(x))T(1)E(3)(x)(H(x)～F(x))T(2)E(4)H(y)～F(y)US(3)(5)(x)(G(x)H(x))PG(y)H(y)US(5)(7)G(y)～F(y)T(4)(6)I6(8)(x)(G(x)～F(x))UG(7)證畢■(因?yàn)椤?〕中y指代任意的)1/8/202435計(jì)算機(jī)科學(xué)與工程學(xué)院例5-3：試證明：前提：～(x)(F(x)∧H(x)),(x)(G(x)H(x))結(jié)論：(x)(G(x)～F(x))證明：～(x)(F(x)∧H(x))P(2)(x)(～F(x)∨～H(x))T(1)E(3)(x)(H(x)～F(x))T(2)E(4)H(y)～F(y)US(3)(5)(x)(G(x)H(x))PG(y)H(y)US(5)(7)G(y)～F(y)T(4)(6)I6(8)(x)(G(x)～F(x))UG(7)證畢■(因?yàn)椤?〕中y指代任意的)1/8/202436計(jì)算機(jī)科學(xué)與工程學(xué)院例5-3：試證明：前提：～(x)(F(x)∧H(x)),(x)(G(x)H(x))結(jié)論：(x)(G(x)～F(x))證明：～(x)(F(x)∧H(x))P(2)(x)(～F(x)∨～H(x))T(1)E(3)(x)(H(x)～F(x))T(2)E(4)H(y)～F(y)US(3)(5)(x)(G(x)H(x))PG(y)H(y)US(5)(7)G(y)～F(y)T(4)(6)I6(8)(x)(G(x)～F(x))UG(7)證畢■(因?yàn)椤?〕中y指代任意的)1/8/202437計(jì)算機(jī)科學(xué)與工程學(xué)院例5-3：試證明：前提：～(x)(F(x)∧H(x)),(x)(G(x)H(x))結(jié)論：(x)(G(x)～F(x))證明：～(x)(F(x)∧H(x))P(2)(x)(～F(x)∨～H(x))T(1)E(3)(x)(H(x)～F(x))T(2)E(4)H(y)～F(y)US(3)(5)(x)(G(x)H(x))PG(y)H(y)US(5)(7)G(y)～F(y)T(4)(6)I6(8)(x)(G(x)～F(x))UG(7)證畢■(因?yàn)椤?〕中y指代任意的)1/8/202438計(jì)算機(jī)科學(xué)與工程學(xué)院例5-3：試證明：前提：～(x)(F(x)∧H(x)),(x)(G(x)H(x))結(jié)論：(x)(G(x)～F(x))證明：～(x)(F(x)∧H(x))P(2)(x)(～F(x)∨～H(x))T(1)E(3)(x)(H(x)～F(x))T(2)E(4)H(y)～F(y)US(3)(5)(x)(G(x)H(x))PG(y)H(y)US(5)(7)G(y)～F(y)T(4)(6)I6(8)(x)(G(x)～F(x))UG(7)證畢■(因?yàn)椤?〕中y指代任意的)1/8/202439計(jì)算機(jī)科學(xué)與工程學(xué)院例5-3：試證明：前提：～(x)(F(x)∧H(x)),(x)(G(x)H(x))結(jié)論：(x)(G(x)～F(x))證明：～(x)(F(x)∧H(x))P(2)(x)(～F(x)∨～H(x))T(1)E(3)(x)(H(x)～F(x))T(2)E(4)H(y)～F(y)US(3)(5)(x)(G(x)H(x))PG(y)H(y)US(5)(7)G(y)～F(y)T(4)(6)I6(8)(x)(G(x)～F(x))UG(7)證畢■(因?yàn)椤?〕中y指代任意的)1/8/202440計(jì)算機(jī)科學(xué)與工程學(xué)院例5-4：“有些病人相信所有的醫(yī)生，而病人均不相信江湖騙子〞。試證明“醫(yī)生不是騙子〞。符號(hào)化：R(x):x是病人D(x):x是醫(yī)生S(x):x是江湖騙子L(x,y):x相信y前提：(x)(R(x)∧(y)(D(y〕L(x,y))),(x)(R(x)(y)(S(y〕～L(x,y)))結(jié)論：(x)(D(x)～S(x))思路：先用再用，即先找特殊的再找一般的！1/8/202441計(jì)算機(jī)科學(xué)與工程學(xué)院例5-4：“有些病人相信所有的醫(yī)生，而病人均不相信江湖騙子〞。試證明“醫(yī)生不是騙子〞。符號(hào)化：R(x):x是病人D(x):x是醫(yī)生S(x):x是江湖騙子L(x,y):x相信y前提：(x)(R(x)∧(y)(D(y〕L(x,y))),(x)(R(x)(y)(S(y〕～L(x,y)))結(jié)論：(x)(D(x)～S(x))思路：先用再用，即先找特殊的再找一般的！1/8/202442計(jì)算機(jī)科學(xué)與工程學(xué)院例5-4：“有些病人相信所有的醫(yī)生，而病人均不相信江湖騙子〞。試證明“醫(yī)生不是騙子〞。符號(hào)化：R(x):x是病人D(x):x是醫(yī)生S(x):x是江湖騙子L(x,y):x相信y前提：(x)(R(x)∧(y)(D(y〕L(x,y))),(x)(R(x)(y)(S(y〕～L(x,y)))結(jié)論：(x)(D(x)～S(x))思路：先用再用，即先找特殊的再找一般的！1/8/202443計(jì)算機(jī)科學(xué)與工程學(xué)院例5-4：“有些病人相信所有的醫(yī)生，而病人均不相信江湖騙子〞。試證明“醫(yī)生不是騙子〞。符號(hào)化：R(x):x是病人D(x):x是醫(yī)生S(x):x是江湖騙子L(x,y):x相信y前提：(x)(R(x)∧(y)(D(y〕L(x,y))),(x)(R(x)(y)(S(y〕～L(x,y)))結(jié)論：(x)(D(x)～S(x))思路：先用再用，即先找特殊的再找一般的！1/8/202444計(jì)算機(jī)科學(xué)與工程學(xué)院證明：(1)(x)(R(x)∧(y)(D(y〕L(x,y)))P(2)R(a)∧(y)(D(y〕L(a,y))ES(1)(a是相信所有醫(yī)生的那個(gè)人)(3)(y)(D(y〕L(a,y))T(2)I2(4)D(t〕L(a,t)US〔3〕(此處t是所有的人，與〔2〕中a不同)(5)(x)(R(x)(y)(S(y)～L(x,y)))P(6)R(a)(y)(S(y)～L(a,y)))US(5)(注意此處的a：既然(5)中指所有的人，那么就應(yīng)包括(2)中的那個(gè)特定的人〕(7)R(a)T(2)I21/8/202445計(jì)算機(jī)科學(xué)與工程學(xué)院證明：(1)(x)(R(x)∧(y)(D(y〕L(x,y)))P(2)R(a)∧(y)(D(y〕L(a,y))ES(1)(a是相信所有醫(yī)生的那個(gè)人)(3)(y)(D(y〕L(a,y))T(2)I2(4)D(t〕L(a,t)US〔3〕(此處t是所有的人，與〔2〕中a不同)(5)(x)(R(x)(y)(S(y)～L(x,y)))P(6)R(a)(y)(S(y)～L(a,y)))US(5)(注意此處的a：既然(5)中指所有的人，那么就應(yīng)包括(2)中的那個(gè)特定的人〕(7)R(a)T(2)I21/8/202446計(jì)算機(jī)科學(xué)與工程學(xué)院證明：(1)(x)(R(x)∧(y)(D(y〕L(x,y)))P(2)R(a)∧(y)(D(y〕L(a,y))ES(1)(a是相信所有醫(yī)生的那個(gè)人)(3)(y)(D(y〕L(a,y))T(2)I2(4)D(t〕L(a,t)US〔3〕(此處t是所有的人，與〔2〕中a不同)(5)(x)(R(x)(y)(S(y)～L(x,y)))P(6)R(a)(y)(S(y)～L(a,y)))US(5)(注意此處的a：既然(5)中指所有的人，那么就應(yīng)包括(2)中的那個(gè)特定的人〕(7)R(a)T(2)I21/8/202447計(jì)算機(jī)科學(xué)與工程學(xué)院證明：(1)(x)(R(x)∧(y)(D(y〕L(x,y)))P(2)R(a)∧(y)(D(y〕L(a,y))ES(1)(a是相信所有醫(yī)生的那個(gè)人)(3)(y)(D(y〕L(a,y))T(2)I2(4)D(t〕L(a,t)US〔3〕(此處t是所有的人，與〔2〕中a不同)(5)(x)(R(x)(y)(S(y)～L(x,y)))P(6)R(a)(y)(S(y)～L(a,y)))US(5)(注意此處的a：既然(5)中指所有的人，那么就應(yīng)包括(2)中的那個(gè)特定的人〕(7)R(a)T(2)I21/8/202448計(jì)算機(jī)科學(xué)與工程學(xué)院證明：(1)(x)(R(x)∧(y)(D(y〕L(x,y)))P(2)R(a)∧(y)(D(y〕L(a,y))ES(1)(a是相信所有醫(yī)生的那個(gè)人)(3)(y)(D(y〕L(a,y))T(2)I2(4)D(t〕L(a,t)US〔3〕(此處t是所有的人，與〔2〕中a不同)(5)(x)(R(x)(y)(S(y)～L(x,y)))P(6)R(a)(y)(S(y)～L(a,y)))US(5)(注意此處的a：既然(5)中指所有的人，那么就應(yīng)包括(2)中的那個(gè)特定的人〕(7)R(a)T(2)I21/8/202449計(jì)算機(jī)科學(xué)與工程學(xué)院證明：(1)(x)(R(x)∧(y)(D(y〕L(x,y)))P(2)R(a)∧(y)(D(y〕L(a,y))ES(1)(a是相信所有醫(yī)生的那個(gè)人)(3)(y)(D(y〕L(a,y))T(2)I2(4)D(t〕L(a,t)US〔3〕(此處t是所有的人，與〔2〕中a不同)(5)(x)(R(x)(y)(S(y)～L(x,y)))P(6)R(a)(y)(S(y)～L(a,y)))US(5)(注意此處的a：既然(5)中指所有的人，那么就應(yīng)包括(2)中的那個(gè)特定的人〕(7)R(a)T(2)I21/8/202450計(jì)算機(jī)科學(xué)與工程學(xué)院證明：(1)(x)(R(x)∧(y)(D(y〕L(x,y)))P(2)R(a)∧(y)(D(y〕L(a,y))ES(1)(a是相信所有醫(yī)生的那個(gè)人)(3)(y)(D(y〕L(a,y))T(2)I2(4)D(t〕L(a,t)US〔3〕(此處t是所有的人，與〔2〕中a不同)(5)(x)(R(x)(y)(S(y)～L(x,y)))P(6)R(a)(y)(S(y)～L(a,y)))US(5)(注意此處的a：既然(5)中指所有的人，那么就應(yīng)包括(2)中的那個(gè)特定的人〕(7)R(a)T(2)I21/8/202451計(jì)算機(jī)科學(xué)與工程學(xué)院證明：(8)(y)(S(y)～L(a,y))T(6)(7)I3(9)S(t)～L(a,t)US(8)(10)L(a,t)～S(t)T(9)E22(11)D(t)～S(t)T(4)(10)I6(12)(x)(D(x)～S(x))UG(11)證畢■(因?yàn)?11)中的t指代的是任意的人！)

1/8/202452計(jì)算機(jī)科學(xué)與工程學(xué)院證明：(8)(y)(S(y)～L(a,y))T(6)(7)I3(9)

S(t)～L(a,t)US(8)(10)L(a,t)～S(t)T(9)E22(11)D(t)～S(t)T(4)(10)I6(12)(x)(D(x)～S(x))UG(11)證畢■(因?yàn)?11)中的t指代的是任意的人！)

1/8/202453計(jì)算機(jī)科學(xué)與工程學(xué)院證明：(8)(y)(S(y)～L(a,y))T(6)(7)I3(9)

S(t)～L(a,t)US(8)(10)

L(a,t)～S(t)T(9)E22(11)D(t)～S(t)T(4)(10)I6(12)(x)(D(x)～S(x))UG(11)證畢■(因?yàn)?11)中的t指代的是任意的人！)

1/8/202454計(jì)算機(jī)科學(xué)與工程學(xué)院證明：(8)(y)(S(y)～L(a,y))T(6)(7)I3(9)

S(t)～L(a,t)US(8)(10)

L(a,t)～S(t)T(9)E22(11)D(t)～S(t)T(4)(10)I6(12)(x)(D(x)～S(x))UG(11)證畢■(因?yàn)?11)中的t指代的是任意的人！)

1/8/202455計(jì)算機(jī)科學(xué)與工程學(xué)院證明：(8)(y)(S(y)～L(a,y))T(6)(7)I3(9)

S(t)～L(a,t)US(8)(10)

L(a,t)～S(t)T(9)E22(11)D(t)～S(t)T(4)(10)I6(12)

(x)(D(x)～S(x))UG(11)證畢■

(因?yàn)?11)中的t指代的是任意的人！)

1/8/202456計(jì)算機(jī)科學(xué)與工程學(xué)院消解(歸結(jié))法消解證明的過(guò)程：(1)為了證明

G1,G2,…,Gn

H

根據(jù)反證法，即需證明

G={G1,G2,…,Gn,～H}

R∧～R(2)建立子句集①先將G化成等值的前束范式②將前束范式化成Skolem范式(消去存在量詞),得到僅含全稱量詞的公式G*,從而對(duì)G的不可滿足性,可由G*的不可滿足性得到。

1/8/202457計(jì)算機(jī)科學(xué)與工程學(xué)院消解(歸結(jié))法消解證明的過(guò)程：(1)為了證明

G1,G2,…,Gn

H根據(jù)反證法，即需證明G={G1,G2,…,Gn,～H}

R∧～R(2)建立子句集

①先將G化成等值的前束范式

②將前束范式化成Skolem范式(消去存在量詞),得到僅含全稱量詞的公式G*,從而對(duì)G的不可滿足性,可由G*的不可滿足性得到。

1/8/202458計(jì)算機(jī)科學(xué)與工程學(xué)院消解(歸結(jié))法消解證明的過(guò)程：(1)為了證明

G1,G2,…,Gn

H根據(jù)反證法，即需證明G={G1,G2,…,Gn,～H}

R∧～R(2)建立子句集

①先將G化成等值的前束范式

②將前束范式化成Skolem范式(消去存在量詞),得到僅含全稱量詞的公式G*,從而對(duì)G的不可滿足性,可由G*的不可滿足性得到。

1/8/202459計(jì)算機(jī)科學(xué)與工程學(xué)院消解(歸結(jié))法(續(xù))

③將G*的全稱量詞省略。

④G*的母式(已合取化)的合取詞‘

’以‘，’表示,得G的子句集S。(3)對(duì)S作歸結(jié)(消解)歸結(jié)：設(shè)C1,C1是兩個(gè)無(wú)共同變?cè)淖泳?L1,L2分別是C1,C2中的句節(jié)。如果L1和～L2有合一置換(一致化)

(L1,L2中的變?cè)獂用

代入),(C1

-{L1

})U(C2

-{L2

})稱作子句C1,C2的歸結(jié)式。1/8/202460計(jì)算機(jī)科學(xué)與工程學(xué)院消解(歸結(jié))法(續(xù))

③將G*的全稱量詞省略。

④G*的母式(已合取化)的合取詞‘

’以‘，’表示,得G的子句集S。(3)對(duì)S作歸結(jié)(消解)歸結(jié)：設(shè)C1,C1是兩個(gè)無(wú)共同變?cè)淖泳?L1,L2分別是C1,C2中的句節(jié)。如果L1和～L2有合一置換(一致化)

(L1,L2中的變?cè)獂用

代入),(C1

-{L1

})U(C2

-{L2

})稱作子句C1,C2的歸結(jié)式。1/8/202461計(jì)算機(jī)科學(xué)與工程學(xué)院消解(歸結(jié))法(續(xù))③將G*的全稱量詞省略。④G*的母式(已合取化)的合取詞‘

’以‘，’表示,得G的子句集S。(3)對(duì)S作歸結(jié)(消解)

歸結(jié)：設(shè)C1,C1是兩個(gè)無(wú)共同變?cè)淖泳?L1,L2分別是C1,C2中的句節(jié)。如果L1和～L2有合一置換(一致化)

(L1,L2中的變?cè)獂用

代入),(C1

-{L1

})U(C2

-{L2

})稱作子句C1,C2的歸結(jié)式。1/8/202462計(jì)算機(jī)科學(xué)與工程學(xué)院消解(歸結(jié))法〔續(xù)〕〔例如C1=P(x)Q(x)C2=～P(a)R(y)P(x)與～P(a)合一置換{a/x},即將變?cè)獂換成a,便為互補(bǔ)對(duì),可作歸結(jié)了,有歸結(jié)式R(C1,C2)=Q(a)R(y)〕對(duì)子句集S的任意兩個(gè)子句作歸結(jié)(如果可作歸結(jié))并將歸結(jié)式仍放入S,重復(fù)這一過(guò)程。(4)直到歸結(jié)出空子句□,證明結(jié)束。1/8/202463計(jì)算機(jī)科學(xué)與工程學(xué)院消解(歸結(jié))法〔續(xù)〕〔例如C1=P(x)Q(x)C2=～P(a)R(y)P(x)與～P(a)合一置換{a/x},即將變?cè)獂換成a,便為互補(bǔ)對(duì),可作歸結(jié)了,有歸結(jié)式R(C1,C2)=Q(a)R(y)〕對(duì)子句集S的任意兩個(gè)子句作歸結(jié)(如果可作歸結(jié))并將歸結(jié)式仍放入S,重復(fù)這一過(guò)程。(4)直到歸結(jié)出空子句□,證明結(jié)束。1/8/202464計(jì)算機(jī)科學(xué)與工程學(xué)院消解(歸結(jié))法〔續(xù)〕〔例如C1=P(x)Q(x)C2=～P(a)R(y)P(x)與～P(a)合一置換{a/x},即將變?cè)獂換成a,便為互補(bǔ)對(duì),可作歸結(jié)了,有歸結(jié)式R(C1,C2)=Q(a)R(y)〕對(duì)子句集S的任意兩個(gè)子句作歸結(jié)(如果可作歸結(jié))并將歸結(jié)式仍放入S,重復(fù)這一過(guò)程。(4)直到歸結(jié)出空子句□,證明結(jié)束。1/8/202465計(jì)算機(jī)科學(xué)與工程學(xué)院例5-5利用消解法證明:〔p42例2.22〕前提：(x)(P(x)(y)(Q(y)～R(x,y))),(x)(P(x)(y)(S(y)R(x,y)))結(jié)論：(x)(S(x)～Q(x))證明：首先將結(jié)論的否認(rèn)作為附加前提，與原有前提一起轉(zhuǎn)化為Skolem范式：(x)(P(x)(y)(Q(y)～R(x,y)))(x)(P(x)(y)(S(y)R(x,y)))～(x)(S(x)～Q(x))

1/8/202466計(jì)算機(jī)科學(xué)與工程學(xué)院例5-5利用消解法證明:〔p42例2.22〕前提：(x)(P(x)(y)(Q(y)～R(x,y))),(x)(P(x)(y)(S(y)R(x,y)))結(jié)論：(x)(S(x)～Q(x))證明：首先將結(jié)論的否認(rèn)作為附加前提，與原有前提一起轉(zhuǎn)化為Skolem范式：(x)(P(x)(y)(Q(y)～R(x,y)))(x)(P(x)(y)(S(y)R(x,y)))～(x)(S(x)～Q(x))

1/8/202467計(jì)算機(jī)科學(xué)與工程學(xué)院(x)(y)(～

P(x)∨

～Q(y)∨

～R(x,y))

(u)(P(u)(z)(～

S(z)∨R(u,z)))

(v)(S(v)

Q(v))(u)(v)(x)(y)(z)((～P(x)∨～Q(y)∨

～R(x,y))P(u)(～S(z)∨R(u,z))S(v)

Q(v)(x)(y)(z)((～P(x)∨～Q(y)∨

～R(x,y))P(a)(～S(z)∨R(a,z))S(b)

Q(b)①上面①即為Skolem范式，由此得到子句集：{～P(x)∨～Q(y)∨

～R(x,y)、P(a)、～S(z)∨R(a,z)、S(b)、Q(b)}。1/8/202468計(jì)算機(jī)科學(xué)與工程學(xué)院

(x)(y)(～P(x)∨～Q(y)∨

～R(x,y))

(u)(P(u)(z)(～S(z)∨R(u,z)))

(v)(S(v)

Q(v))

(u)(v)

(x)(y)(z)

[(～P(x)∨～Q(y)∨

～R(x,y))

P(u)(～S(z)∨R(u,z))

(S(v)

Q(v))](x)(y)(z)((～P(x)∨～Q(y)∨

～R(x,y))P(a)(～S(z)∨R(a,z))S(b)

Q(b)①上面①即為Skolem范式，由此得到子句集：{～P(x)∨～Q(y)∨

～R(x,y)、P(a)、～S(z)∨R(a,z)、S(b)、Q(b)}。1/8/202469計(jì)算機(jī)科學(xué)與工程學(xué)院

(x)(y)(～P(x)∨～Q(y)∨

～R(x,y))

(u)(P(u)(z)(～S(z)∨R(u,z)))(v)(S(v)

Q(v))(u)(v)(x)(y)(z)((～P(x)∨～Q(y)∨

～R(x,y))P(u)(～S(z)∨R(u,z))S(v)

Q(v)(x)(y)(z)((～P(x)∨～Q(y)∨

～R(x,y))

P(a)

(～

S(z)∨R(a,z))

S(b)

Q(b))

①

上面①即為Skolem范式，由此得到子句集：{～P(x)∨～Q(y)∨

～R(x,y)、P(a)、～S(z)∨R(a,z)、S(b)、Q(b)}。1/8/202470計(jì)算機(jī)科學(xué)與工程學(xué)院

(x)(y)(～P(x)∨～Q(y)∨

～R(x,y))

(u)(P(u)(z)(～S(z)∨R(u,z)))(v)(S(v)

Q(v))(u)(v)(x)(y)(z)((～P(x)∨～Q(y)∨

～R(x,y))P(u)(～S(z)∨R(u,z))S(v)

Q(v)(x)(y)(z)((～P(x)∨～Q(y)∨

～R(x,y))P(a)(～S(z)∨R(a,z))S(b)

Q(b)①

上面①即為Skolem范式，由此得到子句集：{～P(x)∨～Q(y)∨

～R(x,y)、P(a)、

～

S(z)∨R(a,z)、

S(b)、Q(b)}。1/8/202471計(jì)算機(jī)科學(xué)與工程學(xué)院然后，在此根底上利用代換進(jìn)行消解的過(guò)程如下：(1)～P(x)∨～Q(y)∨～R(x,y)(2)P(a)(3)～Q(y)∨～R(a,y)(1)和(2),代換{a/x}(4)Q(b)(5)～R(a,b)(3)和(4),代換{b/y}(6)～S(z)∨R(a,z)(7)～S(b)(5)和(6),代換{b/z}(8)S(b)(9)□證畢■1/8/202472計(jì)算機(jī)科學(xué)與工程學(xué)院然后，在此根底上利用代換進(jìn)行消解的過(guò)程如下：(1)～P(x)∨～Q(y)∨～R(x,y)(2)P(a)(3)～Q(y)∨～R(a,y)(1)和(2),代換{a/x}(4)Q(b)(5)～R(a,b)(3)和(4),代換{b/y}(6)～S(z)∨R(a,z)(7)～S(b)(5)和(6),代換{b/z}(8)S(b)(9)□證畢■1/8/202473計(jì)算機(jī)科學(xué)與工程學(xué)院然后，在此根底上利用代換進(jìn)行消解的過(guò)程如下：(1)～P(x)∨～Q(y)∨～R(x,y)(2)P(a)(3)～Q(y)∨～R(a,y)(1)和(2),代換{a/x}(4)Q(b)(5)～R(a,b)(3)和(4),代換{b/y}(6)～S(z)∨R(a,z)(7)～S(b)(5)和(6),代換{b/z}(8)S(b)(9)□證畢■1/8/202474計(jì)算機(jī)科學(xué)與工程學(xué)院然后，在此根底上利用代換進(jìn)行消解的過(guò)程如下：(1)～P(x)∨～Q(y)∨～R(x,y)(2)P(a)(3)～Q(y)∨～R(a,y)(1)和(2),代換{a/x}(4)Q(b)(5)～R(a,b)(3)和(4),代換{b/y}(6)～S(z)∨R(a,z)(7)～S(b)(5)和(6),代換{b/z}(8)S(b)(9)□證畢■1/8/202475計(jì)算機(jī)科學(xué)與工程學(xué)院然后，在此根底上利用代換進(jìn)行消解的過(guò)程如下：(1)～P(x)∨～Q(y)∨～R(x,y)(2)P(a)(3)～Q(y)∨～R(a,y)(1)和(2),代換{a/x}(4)Q(b)(5)～R(a,b)(3)和(4),代換{b/y}(6)～S(z)∨R(a,z)(7)～S(b)(5)和(6),代換{b/z}(8)S(b)(9)□證畢■1/8/202476計(jì)算機(jī)科學(xué)與工程學(xué)院然后，在此根底上利用代換進(jìn)行消解的過(guò)程如下：(1)～P(x)∨～Q(y)∨～R(x,y)(2)P(a)(3)～Q(y)∨～R(a,y)(1)和(2),代換{a/x}(4)Q(b)(5)～R(a,b)(3)和(4),代換{b/y}(6)～S(z)∨R(a,z)(7)～S(b)(5)和(6),代換{b/z}(8)S(b)(9)□證畢■1/8/202477計(jì)算機(jī)科學(xué)與工程學(xué)院然后，在此根底上利用代換進(jìn)行消解的過(guò)程如下：(1)～P(x)∨～Q(y)∨～R(x,y)(2)P(a)(3)～Q(y)∨～R(a,y)(1)和(2),代換{a/x}(4)Q(b)(5)～R(a,b)(3)和(4),代換{b/y}(6)～S(z)∨R(a,z)(7)～S(b)(5)和(6),代換{b/z}(8)S(b)(9)□證畢■1/8/202478計(jì)算機(jī)科學(xué)與工程學(xué)院然后，在此根底上利用代換進(jìn)行消解的過(guò)程如下：(1)～P(x)∨～Q(y)∨～R(x,y)(2)P(a)(3)～Q(y)∨～R(a,y)(1)和(2),代換{a/x}(4)Q(b)(5)～R(a,b)(3)和(4),代換{b/y}(6)～S(z)∨R(a,z)(7)～S(b)(5)和(6),代換{b/z}(8)S(b)(9)□證畢■1/8/202479計(jì)算機(jī)科學(xué)與工程學(xué)院然后，在此根底上利用代換進(jìn)行消解的過(guò)程如下：(1)～P(x)∨～Q(y)∨～R(x,y)(2)P(a)(3)～Q(y)∨～R(a,y)(1)和(2),代換{a/x}(4)Q(b)(5)～R(a,b)(3)和(4),代換{b/y}(6)～S(z)∨R(a,z)(7)～S(b)(5)和(6),代換{b/z}(8)S(b)(9)□證畢■〔(7)和〔8〕〕1/8/202480計(jì)算機(jī)科學(xué)與工程學(xué)院

小結(jié)：謂詞演算的綜合推理方法一、根本推理方法1、直接證明方法2、間接證明方法〔反證法〕3、利用CP規(guī)那么二、推理中需注意的幾個(gè)問(wèn)題1〕當(dāng)所要求的結(jié)論可能被定量時(shí)，此時(shí)可引用規(guī)那么UG和規(guī)那么EG將其量詞參加。2〕在推導(dǎo)過(guò)程中，如既要使用規(guī)那么US又要使用規(guī)那么ES消去公式中的量詞(要先使用規(guī)那么ES，再使用規(guī)那么US)。然后再使用命題演算中的推理規(guī)那么，最后使用規(guī)那么UG或規(guī)那么EG引入量詞，得到所要的結(jié)論。1/8/202481計(jì)算機(jī)科學(xué)與工程學(xué)院3〕如一個(gè)變量是用規(guī)那么ES消去量詞,對(duì)該變量在添加量詞時(shí),那么只能使用規(guī)那么EG,而不能使用規(guī)那么UG;如使用規(guī)那么US消去量詞,對(duì)該變量在添加量詞時(shí),那么可使用規(guī)那么EG和規(guī)那么UG。4〕如有兩個(gè)含有存在量詞的公式，當(dāng)用規(guī)那么ES消去量詞時(shí)，不能選用同樣的一個(gè)常量符號(hào)來(lái)取代兩個(gè)公式中的變?cè)鴳?yīng)用不同的常量符號(hào)來(lái)取代它們。1/8/202482計(jì)算機(jī)科學(xué)與工程學(xué)院5〕在用規(guī)那么US和規(guī)那么ES消去量詞時(shí)，此量詞必須位于整個(gè)公式的最前端，并且它的轄域?yàn)槠浜蟮恼麄€(gè)公式。6〕在添加量詞(x)、(x)時(shí)，所選用的x不能在公式G(c)或G(y)中以任何約束出現(xiàn)。7)在使用EG規(guī)那么引入存在量詞(x)，此x不得為G(c)或G(y)中的函數(shù)變?cè)Ｔ谑褂肬G規(guī)那么引入全稱量詞(x)時(shí)，此x不得為G(y)中的函數(shù)變?cè)?因該函數(shù)變?cè)坏米鳛樽杂勺冊(cè)?。1/8/202483計(jì)算機(jī)科學(xué)與工程學(xué)院例5-6將以下三條自然公理翻譯成謂詞公式：每個(gè)自然數(shù)有且僅有一個(gè)直接后繼；沒(méi)有任何自然數(shù)以0為其直接后繼；對(duì)0以外的任何自然數(shù)，有且僅有一個(gè)直接先行。解：設(shè)個(gè)體域D為自然數(shù)令p(x):x的直接先行;s(x):x的直接后繼;EQUAL(x,y):x=y(x)(y)[EQUAL(y,s(x))∧(z)[EQUAL(z,s(x))→EQUAL(y,z)]]

有且僅有1/8/202484計(jì)算機(jī)科學(xué)與工程學(xué)院

～(

x)[EQUAL(0,s(x))(x)[～EQUAL(x,0)→(

y)[EQUAL(y,p(x))∧(z)[EQUAL(z,p(x))→EQUAL(y,z)]]]0以外的任何自然數(shù)1/8/202485計(jì)算機(jī)科學(xué)與工程學(xué)院例5-7解：設(shè)H(x)：x是人； M(x)：x是要死的； s：蘇格拉底。那么符號(hào)化為： (x)(H(x)M(x))，H(s)M(s)證明：“所有的人都是要死的；蘇格拉底是人。所以蘇格拉底是要死的。〞證明：(1)(x)(H(x)M(x)) P (2)H(x)M(x) US,(1) (3)H(s) P (4)M(s) T,(2),(3)，I證明：(1)(x)(H(x)M(x)) P (2)H(s)M(s) US,(1) (3)H(s) P (4)M(s) T,(2),(3)，I(2)錯(cuò)了！正確的為？1/8/202486計(jì)算機(jī)科學(xué)與工程學(xué)院例5-8證明： (x)(P(x)Q(x))，(

x)P(x)(

x)Q(x)請(qǐng)看推導(dǎo)：(1)(x)(P(x)Q(x)) P(2)(P(c)Q(c)) US,(1)(3)(

x)P(x) P(4)P(c) ES,(3)(5)Q(c) T,(2),(4),I(6)(

x)Q(x) EG,(5)推導(dǎo)錯(cuò)了！應(yīng)先用ES規(guī)那么，再用US規(guī)那么，正確的為？正確地推導(dǎo)如下：(1)(

x)P(x) P(2)P(c) ES，(1)(3)(x)(P(x)Q(x)) P(4)(P(c)Q(c)) US,(3)(5)Q(c) T,(2),(4),I(6)(

x)Q(x) EG,(5)1/8/202487計(jì)算機(jī)科學(xué)與工程學(xué)院例5-9證明：1)(

x)(P(x)∧Q(x)) P 2)(P(c)∧Q(c)) ES,1) 3)P(c) T,2),I 4)Q(c) T,2),I 5)(

x)P(x) EG,3) 6)(

x)Q(x) EG,4) 7)(

x)P(x)∧(

x)Q(x) T,5),6),I證明：(

x)(P(x)∧Q(x))(

x)P(x)∧(

x)Q(x)1/8/202488計(jì)算機(jī)科學(xué)與工程學(xué)院例5-9(續(xù)1)1)(

x)P(x)∧(

x)Q(x) P2)(

x)P(x) T,1),I3)P(c) ES,2)4)(

x)Q(x) T,1),I5)Q(c) ES,4)6)(P(c)∧Q(c)) T,3),4),I(

x)(P(x)∧Q(x)) EG,6)

請(qǐng)看上述推論的逆推導(dǎo)：推導(dǎo)錯(cuò)了！選用了同樣的一個(gè)常量符號(hào)來(lái)取代兩個(gè)公式中的變?cè)_的為：正確的推導(dǎo)如下：1)(

x)P(x)∧(

x)Q(x) P2)(

x)P(x) T,1),I3)P(c) ES,2)4)(

x)Q(x) T,1),I5)Q(b) ES,4)6)(P(c)∧Q(b)) T,3),4),I7)(

x)(

y)(P(x)∧Q(y)) EG,6)這是錯(cuò)誤的結(jié)論1/8/202489計(jì)算機(jī)科學(xué)與工程學(xué)院例5-10證明下述論斷的正確性： 所有的哺乳動(dòng)物都是脊椎動(dòng)物； 并非所有的哺乳動(dòng)物都是胎生動(dòng)物； 故有些脊椎動(dòng)物不是胎生的。證明設(shè)謂詞如下： P(x)：x是哺乳動(dòng)物； Q(x)：x是脊椎動(dòng)物； R(x)：x是胎生動(dòng)物。那么有：(x)(P(x)Q(x)),～(x)(P(x)R(x)) (x)(Q(x)∧～R(x))1/8/202490計(jì)算機(jī)科學(xué)與工程學(xué)院請(qǐng)看下面推導(dǎo)：～(x)(P(x)R(x)) P～(P(x)R(x)) US,1)～(～

P(x)∨R(x)) T,2)，E(P(x)∧～

R(x)) T,3),EP(x) T,4),I～R(x) T,4),I(x)(P(x)Q(x)) PP(x)Q(x) US,7)Q(x) T,(5),(8),IQ(x)∧～R(x) T,6),9),I(

x)(Q(x)∧～R(x)) EG,10)(x)(Q(x)∧～R(x)) UG,10)2〕錯(cuò)了！在用規(guī)那么US和規(guī)那么ES消去量詞時(shí)，此量詞必須位于整個(gè)公式的最前端，并且它的轄域?yàn)槠浜蟮恼麄€(gè)公式。正確的為：1/8/202491計(jì)算機(jī)科學(xué)與工程學(xué)院證明：～(x)(P(x)R(x)) P(

x)～(～P(x)∨R(x)) T,1),E～(～P(c)∨R(c)) ES,2)(P(c)∧～R(c)) T,3),EP(c) T,4),I～R(c) T,4),I(x)(P(x)Q(x)) PP(c)Q(c) US,7)Q(c) T,5),8),IQ(c)∧～R(c) T,6),9),I(

x)(Q(x)∧～R(x)) EG,10)1/8/202492計(jì)算機(jī)科學(xué)與工程學(xué)院例5-11

證明下述論斷的正確性：每個(gè)報(bào)考研究生的大學(xué)畢業(yè)生要么參加研究生的入學(xué)考試，要么被推薦為免試生；每個(gè)報(bào)考研究生的大學(xué)畢業(yè)生當(dāng)且僅當(dāng)學(xué)習(xí)成績(jī)優(yōu)秀才被推薦為免試生；有些報(bào)考研究生的大學(xué)畢業(yè)生學(xué)習(xí)成績(jī)優(yōu)秀，但并非所有報(bào)考研究生的大學(xué)畢業(yè)生學(xué)習(xí)成績(jī)都優(yōu)秀。因此，有些報(bào)考研究生的大學(xué)畢業(yè)生要參加研究生的入學(xué)考試。1/8/202493計(jì)算機(jī)科學(xué)與工程學(xué)院例5-11(續(xù)1)解：設(shè)P(x)：x是報(bào)考研究生的大學(xué)畢業(yè)生； Q(x)：x參加研究生入學(xué)考試； R(x)：x被推薦為免試生； S(x)：x學(xué)習(xí)成績(jī)優(yōu)秀。那么原論斷可符號(hào)化為： (x)(P(x)→(Q(x)R(x))， (x)(P(x)→(R(x)S(x)))， (x)(P(x)∧S(x)), ～(x)(P(x)→S(x)) (x)(P(x)∧Q(x))1/8/202494計(jì)算機(jī)科學(xué)與工程學(xué)院例5-11(續(xù)2)證明：(1)～(x)(P(x)→S(x))P (2)(x)(P(x)∧～S(x))T,(1),E (3)P(c)∧～S(c)ES,(2) (4)P(c)T,(3),I (5)(x)(P(x)→(Q(x)R(x))P (6)P(c)→〔Q(c)R(c)〕US,(5) (7)Q(c)R(c)T,(4),(6),I (8)(x)(P(x)→(R(x)S(x)))P (9)P(c)→(R(c)S(c))US，〔8〕 (10)R(c)S(c)T,(4),(9),I1/8/202495計(jì)算機(jī)科學(xué)與工程學(xué)院例5-11(續(xù)2)證明：(1)～(x)(P(x)→S(x))P (2)(x)(P(x)∧～S(x))T,(1),E (3)P(c)∧～S(c)ES,(2) (4)P(c)T,(3),I (5)(x)(P(x)→(Q(x)R(x))P (6)P(c)→〔Q(c)R(c)〕US,(5) (7)Q(c)R(c)T,(4),(6),I (8)(x)(P(x)→(R(x)S(x)))P (9)P(c)→(R(c)S(c))US，〔8〕 (10)R(c)S(c)T,(4),(9),I1/8/202496計(jì)算機(jī)科學(xué)與工程學(xué)院例5-11(續(xù)2)證明：(1)～(x)(P(x)→S(x))P (2)(x)(P(x)∧～S(x))T,(1),E (3)P(c)∧～S(c)ES,(2) (4)P(c)T,(3),I (5)(x)(P(x)→(Q(x)R(x))P (6)P(c)→〔Q(c)R(c)〕US,(5) (7)Q(c)R(c)T,(4),(6),I (8)(x)(P(x)→(R(x)S(x)))P (9)P(c)→(R(c)S(c))US，〔8〕 (10)R(c)S(c)T,(4),(9),I1/8/202497計(jì)算機(jī)科學(xué)與工程學(xué)院例5-11(續(xù)3)(11)(R(c)→S(c))∧(S(c)→R(c))T,(10),E(12)R(c)→S(c)T,(12),I(13)～S(c)T,(3),I(14)～R(c)T,(12),(13),I(15)Q(c)T,(7),(14),I(16)P(c)∧Q(c)T,(4),(15),I(17)(

x)(P(x)∧Q(x))ES,(16)1/8/202498計(jì)算機(jī)科學(xué)與工程學(xué)院例5-11(續(xù)3)(11)(R(c)→S(c))∧(S(c)→R(c))T,(10),E(12)R(c)→S(c)T,(12),I(13)～S(c)T,(