離散數(shù)學(xué)課件-第1章-5(下)

1、12022/8/16離散數(shù)學(xué)Discrete Mathematics 汪榮貴 教授合肥工業(yè)大學(xué)軟件學(xué)院專用課件2010.6第一章 邏輯與證明 學(xué)習(xí)內(nèi)容1.1 邏輯1.2 命題等價(jià)1.3 謂詞和量詞 1.4 對(duì)偶與范式1.5 推理規(guī)則1.6 證明導(dǎo)論1.7 證明的方法和策略1.8 數(shù)理邏輯的應(yīng)用謂詞邏輯推理謂詞邏輯的推理方法，可以看作是命題邏輯推理方法的擴(kuò)張。 因?yàn)橹^詞邏輯的很多等價(jià)式和蘊(yùn)含式，是命題邏輯有關(guān)公式的推廣，所以命題邏輯中的推理規(guī)則，如P、T和CP規(guī)則等亦可在謂詞的推理理論中應(yīng)用。在謂詞推理中，某些前提與結(jié)論可能是受量詞限制的，為了使用等價(jià)式和蘊(yùn)含式，必須在推理過(guò)程中有消去和添加量詞

2、的規(guī)則，以便使謂詞邏輯的推理過(guò)程可類似于命題邏輯中推理理論那樣進(jìn)行。由前面的敘述我們知道：謂詞邏輯推理方法： 真值表法、直接證法、間接證法。所用公式：命題邏輯部分使用的I1I16的蘊(yùn)含規(guī)則，以及 E1E22的等價(jià)式規(guī)則。推理規(guī)則：P、T、CP、US、ES、EG、UG后四個(gè)規(guī)則，是處理量詞的，因?yàn)橥评頃r(shí)要使用不含量詞的命題公式，所以要去掉量詞，如果結(jié)論有量詞，還要添加量詞。后面介紹四個(gè)新規(guī)則。一.全稱特指規(guī)則 US (Universal Specialization)形式： xA(x)A(c) (其中c是論域內(nèi)指定客體)含義：如果xA(x)為真，則在論域內(nèi)任 何指定客體c，都使得A(c)為真。作

3、用：去掉全稱量詞。要求：c不是A(x)中的符號(hào)。二.全稱推廣規(guī)則UG (Universal Generalization)形式： A(c)xA(x) (其中c是論域內(nèi)任何指定客體)含義：如果在論域內(nèi)任何指定客體c都使 得A(c)為真，則xA(x)為真。作用：添加全稱量詞。要求：x不是A(c)中的符號(hào)。 c一定是任意的客體，否則不可全稱 推廣。三.存在指定規(guī)則ES (Existential Specialization)形式： xA(x)A(c) (其中c是論域內(nèi)指定客體)含義：如果xA(x)為真，則在論域內(nèi)指定客體c， 都使得A(c)為真。作用：去掉存在量詞。要求： c不是A(x)中的符號(hào)。

4、用ES指定的客體c不應(yīng)該是在此之前用US規(guī)則或者用ES規(guī)則所指定的客體c(即本次用ES特指客體c，不應(yīng)該是以前特指的客體)。四.存在推廣規(guī)則 EG (Existential Generalization) 形式： A(c)xA(x) (其中c是論域內(nèi)指定客體) 含義：如果在論域內(nèi)指定客體c使得 A(c)為真，則xA(x)為真。 作用：添加存在量詞。 要求：x不是A(c)中的符號(hào)?！緀xample 1】令A(yù)(x)表示x是自然數(shù)，B(x)表示x是整數(shù)。 x(A(x)B(x) P A(c)B(c) US 如c= 1 xA(x) P A(c) ES A(0.1)為F xB(x) P B(c) ES 如

5、c=-1 xA(x) P A(c) ES A(-1)為F【example 2】所有金屬都導(dǎo)電。銅是金屬。故銅導(dǎo)電。 令M(x):x是金屬。C(x):x導(dǎo)電。a:銅。 符號(hào)化為： x(M(x)C(x),M(a) C(a) x(M(x)C(x) P M(a)C(a) US M(a) P C(a) T I【example 3】所有自然數(shù)都是整數(shù)。有些數(shù)是自然數(shù)。因此有些數(shù)是整數(shù)。 令A(yù)(x)表示x是自然數(shù)，B(x)表示x是整數(shù)。 x(A(x)B(x)， xA(x) xB(x) xA(x) P A(c) ES x(A(x)B(x) P A(c)B(c) US B(c) T I11 xB(x) EG 在

6、例3中，如果按下面方法推理，是否正確？x(A(x)B(x)， xA(x) xB(x) x(A(x)B(x) P A(c)B(c) US xA(x) P A(c) ES B(c) T I11 xB(x) EG 問(wèn)題在哪里?【example 4】不認(rèn)識(shí)錯(cuò)誤的人，也不能改正錯(cuò)誤。 有些誠(chéng)實(shí)的人改正了錯(cuò)誤。 所以有些誠(chéng)實(shí)的人是認(rèn)識(shí)了錯(cuò)誤的人。Solution： 設(shè)A(x):x是認(rèn)識(shí)錯(cuò)誤的人。 B(x):x改正了錯(cuò)誤。C(x):x是誠(chéng)實(shí)的人。符號(hào)化為： x(A(x)B(x)，x(C(x)B(x), x(C(x)A(x)x(A(x)B(x),x(C(x)B(x),x(C(x)A(x) x(C(x)B(x)

7、 P C(c)B(c) ES C(c) T I B(c) T I x(A(x)B(x) P A(c)B(c) US A(c) T I A(c) T E C(c)A(c) T I x(C(x)A(x) EG Proof：【example 5】一些病人喜歡所有醫(yī)生。 任何病人都不喜歡庸醫(yī)。所以沒有醫(yī)生是庸醫(yī)。 solution： 設(shè): P(x):x是病人, D(x):x是醫(yī)生, Q(x):x是庸醫(yī), L(x,y): x喜歡y. 符號(hào)化為： x(P(x)y(D(y)L(x,y), x ( P(x) y (Q(y)L(x,y) y(D(y)Q(y)Proof： x(P(x)y(D(y)L(x,y)，x

8、(P(x)y(Q(y)L(x,y) y(D(y)Q(y) x(P(x)y(D(y)L(x,y) P P(a)y(D(y)L(a,y) ES P(a) T I y(D(y)L(a,y) T I x(P(x)y(Q(y)L(x,y) P P(a)y(Q(y)L(a,y) US y(Q(y)L(a,y) T I D(b)L(a,b) US Q(b)L(a,b) US L(a,b) Q(b) T E D(b)Q(b) T I D(b)Q(b) T E (D(b)Q(b) T E y(D(y)Q(y) UG y(D(y)Q(y) T E【example 6】證明：x(A(x)B(x),x(B(x)C(x

9、),xC(x)xA(x) (1) x(A(x)B(x) P(2) A(a)B(a) ES (1) (3) x(B(x)C(x) P(4) B(a)C(a) US (3)(5) xC(x) P(6) C(a) US (5) (7 ) B(a) T (4)(6) I(8) A(a) T (2)(7) I(9) xA(x) EG (8)【example 7】x(P(x)Q(x) xP(x)xQ(x)用CP規(guī)則證明：Proof： xP(x) P(附加前提) x(P(x)Q(x) P P(a)Q(a) ES P(a) US Q(a) T I xQ(x) EG xP(x)xQ(x) CP用反證法證明例7：

10、 x(P(x)Q(x) xP(x)xQ(x) (xP(x)xQ(x) P(假設(shè)前提) (xP(x)xQ(x) T E xP(x)xQ(x) T E xP(x) T I xQ(x) T I x(P(x)Q(x) P P(a)Q(a) ES P(a) US Q(a) T I xQ(x) EG xQ(x)xQ(x) T I【example 8】用推理證明公式： yxA(x,y)xyA(x,y)Proof： yxA(x,y) P xA(x,b) ES A(a,b) US yA(a,y) EG xyA(x,y) UG 推理時(shí)注意事項(xiàng)：1.注意使用ES、US、EG、UG的限制條件。2.對(duì)于同一個(gè)客體變?cè)?/p>

11、同時(shí)帶和的前提，去量詞時(shí)，應(yīng)先去后去，這樣才能特指同一個(gè)客體 c。3.去量詞時(shí)，該量詞必須是公式最左邊的量詞，且此量詞的前邊無(wú)任何符號(hào)，它的轄域作用到公式末尾。4. 添加量詞時(shí)，也要加在公式的最左邊，(即新加的量詞前也無(wú) 任何符號(hào)！)且其轄域作用到公式的末尾。下面的作法是錯(cuò)誤的： xP(x)yQ(y) P xP(x)Q(b) ES (3)P(a)Q(b) US(2)正確作法是： x P(x)yQ(y) P(2)xP(x)yQ(y) T(1) E(3) xP(x)yQ(y) T(2) E(4) xy(P(x)Q(y) T(3) E(5) y(P(a)Q(y) ES(4) (6) P(a)Q(b)

12、 ES(4)(7) P(a)Q(b) T(5)E【練習(xí)】證明(x)(H(x) M(x) H(s) M(s) 這是著名的蘇格拉底論證。其中 H(x) ：x是一個(gè)人。 M(x) ：x是要死的。 s：蘇格拉底。262022/8/16Proof： (1) (x)(H(x) M(x) P (2) H(s) M(s) US(1) (3) H(s) P (4) M(s) T(2)(3)I2. 證明(x) (P(x) Q(x) (x) P(x) (x) Q(x)Proof： 把 (x) P(x) (x) Q(x)作為附加前提。(x) P(x) (x) Q(x) P(x) P(x) (x) Q(x) T(1)E(x) P(x) T(2)I(x)