離散數(shù)學(xué)(第五章)

1、2.1謂詞的概念與表示謂詞的概念與表示(2.2謂詞公式與翻譯謂詞公式與翻譯(Predicate formulae2.3謂詞演算的等價(jià)式與蘊(yùn)含式謂詞演算的等價(jià)式與蘊(yùn)含式(Equivalences & implications of predicate calculus)2.4前束范式前束范式(Prenex normal form2.5謂詞演算的推理理論謂詞演算的推理理論(Inference theory of predicate calculus)一、一、謂詞的等價(jià)和永真的概念謂詞的等價(jià)和永真的概念定義定義1:給定任意的謂詞公式給定任意的謂詞公式A,其個(gè)體域?yàn)槠鋫€(gè)體域?yàn)镋,對(duì)于對(duì)于A的所的所有賦

2、值有賦值,公式公式A都為真都為真,則稱則稱A在在E上是上是永真的永真的(或有效或有效的的);若對(duì)于若對(duì)于A的所有賦值的所有賦值,公式公式A都為假都為假,則稱則稱A在在E上上是是永假的永假的(或不可滿足的或不可滿足的);若至少存在著一種賦值使若至少存在著一種賦值使得公式得公式A為真為真,則稱則稱A在在E上是上是可滿足的可滿足的.v定義定義2:給定任何兩個(gè)謂詞公式給定任何兩個(gè)謂詞公式A、B，設(shè)它們有共同，設(shè)它們有共同的個(gè)體域的個(gè)體域E，若對(duì)，若對(duì)A和和B的任一組變?cè)M(jìn)行賦值，所的任一組變?cè)M(jìn)行賦值，所得命題的真值相同，則稱得命題的真值相同，則稱謂詞公式謂詞公式A和和B在在E上等價(jià)上等價(jià)，并記為，并

3、記為A B2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則 在命題邏輯中給出了一些常見等價(jià)公式和在命題邏輯中給出了一些常見等價(jià)公式和蘊(yùn)含式蘊(yùn)含式,只要用只要用原子謂詞公式原子謂詞公式去代替第一章去代替第一章中永真蘊(yùn)含式和等價(jià)公式中的中永真蘊(yùn)含式和等價(jià)公式中的原子命題變?cè)用}變?cè)?，則在第一章中永真蘊(yùn)含式和等價(jià)公式，則在第一章中永真蘊(yùn)含式和等價(jià)公式均可變成謂詞演算中的永真蘊(yùn)含式和等價(jià)均可變成謂詞演算中的永真蘊(yùn)含式和等價(jià)公式：公式：2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則 命題邏輯命題邏輯 謂詞邏輯謂詞邏輯 (x)(

4、x) (x)(x)(x) . . . . (x)(x) (x) (x) (x)(x)(x) (x)(x) (x) . . . . . .2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則下面給出涉及量詞的一些等價(jià)式。下面給出涉及量詞的一些等價(jià)式。(1) (1) 消去量詞的等價(jià)式消去量詞的等價(jià)式設(shè)個(gè)體域?yàn)椋涸O(shè)個(gè)體域?yàn)椋篠=aS=a1 1,a,a2 2,a,an n ，我們有：，我們有： x xA(x)A(x)A(A(a a1 1) ) A( A(a a2 2) ) A( A(a an n) ) xA(x) xA(x) A(A(a a1 1) ) A(A(a a2 2) ) A( A(a a

5、n n) ) 2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則v例例1 設(shè)設(shè) P(x)表示表示x喜歡夢八隊(duì)，則喜歡夢八隊(duì)，則 P(x)表示表示x不不喜歡夢八隊(duì)。喜歡夢八隊(duì)。(個(gè)體域限定為人個(gè)體域限定為人)（1）不是所有人都喜歡夢八隊(duì)：）不是所有人都喜歡夢八隊(duì)： ( x)P(x) （2）存在一些人不喜歡夢八隊(duì)：）存在一些人不喜歡夢八隊(duì)： ( x) P(x) （3）不會(huì)有人喜歡夢八隊(duì)：）不會(huì)有人喜歡夢八隊(duì)： ( x)P(x) （4）所有人都不喜歡夢八隊(duì)：）所有人都不喜歡夢八隊(duì)： ( x) P(x) v可以看出命題可以看出命題(1)(2)意義完全相同，意義完全相同，(3)(4)意義也完全相同

6、意義也完全相同2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則（2）量詞否定轉(zhuǎn)換律）量詞否定轉(zhuǎn)換律 xP(x) xP(x) xP(x) xP(x) 下面證明：下面證明： xP(x) xP(x)設(shè)個(gè)體域?yàn)椋涸O(shè)個(gè)體域?yàn)椋?S=a1,a2,an xP(x) (P(a1) P(a2) P(an) P(a1) P(a2) P(an) xP(x)2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則舉例說明量化命題和非量化命題的差別舉例說明量化命題和非量化命題的差別:否定形式不同否定形式不同例：例： 否定下列命題：否定下列命題： (a)上海是一個(gè)小城鎮(zhèn)上海是一個(gè)小城鎮(zhèn) A(s) (b)每一個(gè)自然

7、數(shù)都是偶數(shù)每一個(gè)自然數(shù)都是偶數(shù) x(N(x)E(x)上述二命題的否定為：上述二命題的否定為： (a)上海不是一個(gè)小城鎮(zhèn)上海不是一個(gè)小城鎮(zhèn) A(s) (b)有一些自然數(shù)不是偶數(shù)有一些自然數(shù)不是偶數(shù) x(N(x)E(x)x(N(x)E(x) x(N(x) E(x) x (N(x) E(x)結(jié)論：對(duì)于非量化命題的否定只需將動(dòng)詞否定，而對(duì)結(jié)論：對(duì)于非量化命題的否定只需將動(dòng)詞否定，而對(duì)于量化命題的否定不但對(duì)動(dòng)詞進(jìn)行否定而且對(duì)量詞同于量化命題的否定不但對(duì)動(dòng)詞進(jìn)行否定而且對(duì)量詞同時(shí)進(jìn)行否定，其方法是：時(shí)進(jìn)行否定，其方法是： x的否定變?yōu)榈姆穸ㄗ優(yōu)?x ， x的的否定變?yōu)榉穸ㄗ優(yōu)?x 。2.3 一階邏輯等值式

8、與置換規(guī)則一階邏輯等值式與置換規(guī)則量詞轉(zhuǎn)換律的推廣應(yīng)用量詞轉(zhuǎn)換律的推廣應(yīng)用:把把深入到謂深入到謂詞公式前面去的方法。詞公式前面去的方法。 x yP(x,y,z) x yP(x,y,z) x yP(x,y,z) 2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則（3 3）量詞轄域的擴(kuò)張與收縮）量詞轄域的擴(kuò)張與收縮量詞轄域中如果有合取或析取項(xiàng)，且其中有一個(gè)量詞轄域中如果有合取或析取項(xiàng)，且其中有一個(gè)是命題，則可將該命題移至量詞轄域之外：是命題，則可將該命題移至量詞轄域之外：（ x）（A(x)B）（ x）A(x)B（ x）（A(x)B）（ x）A(x) B（ x）（A(x)B）（ x）A(x)B

9、（ x）（A(x)B）（ x）A(x)B 2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則證明：證明： xA(x) B x(A(x) B)設(shè)個(gè)體域?yàn)椋涸O(shè)個(gè)體域?yàn)椋?S=a1,a2,an xA(x) B (A(a1) A(a2) A(an) B (A(a1) B) (A(a2) B) (A(an) B) x(A(x) B) 2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則從上述幾個(gè)等價(jià)公式可以推出如下的等價(jià)式：從上述幾個(gè)等價(jià)公式可以推出如下的等價(jià)式： xA(x)B x(A(x)B) xA(x)B x(A(x)B)A xB(x) x(AB (x)A x B(x) x(AB (x)證

10、明證明： xA(x)B x(A(x)B) xA(x)B xA(x) B x A(x) B x （ A(x) B） x(A(x)B)2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則（4 4）量詞分配律）量詞分配律 x(A(x) B(x) xA(x) xB(x) x (A(x) B(x) xA(x) xB(x) x (A(x) B(x) xA(x) xB(x) x (A(x) B(x) xA(x) xB(x) xA(x) xB(x) x(A(x) B(x) xA(x) xB(x) x(A(x) B(x)2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則證明：證明： x(A(x) B(

11、x) xA(x) xB(x)設(shè)個(gè)體域?yàn)椋涸O(shè)個(gè)體域?yàn)椋?S=a1,a2,an x(A(x) B(x) (A(a1) B(a1) . (A(an) B(an) (A(a1) A(an) (B(a1) B(an) xA(x) x B(x)2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則x(A(x)B(x) x A(x) x B(x)？ 舉例：舉例：令令 x x的個(gè)體域?yàn)檎麛?shù)。的個(gè)體域?yàn)檎麛?shù)。 A(x) A(x)：x x是奇數(shù)是奇數(shù) B(x)B(x)：x x是偶數(shù)是偶數(shù) x x ( (A(x) A(x) B(x)B(x) ) 所有正整數(shù)是奇數(shù)所有正整數(shù)是奇數(shù)或者或者偶數(shù)。偶數(shù)。 x A(x

12、) x A(x) x B(x)x B(x) 所有正整數(shù)都是奇數(shù)所有正整數(shù)都是奇數(shù)或者或者所有正整數(shù)都是所有正整數(shù)都是偶數(shù)。偶數(shù)。2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則(x)(A(x)B(x) (x)A(x) (x)B(x)？舉例：舉例：令令 x x的個(gè)體域?yàn)檎麛?shù)。的個(gè)體域?yàn)檎麛?shù)。 A(x) A(x)：x x是奇數(shù)是奇數(shù) B(x)B(x)：x x是偶數(shù)是偶數(shù) x x ( (A(x) A(x) B(x)B(x) ) 存在既是奇數(shù)存在既是奇數(shù)又是又是偶數(shù)的正整數(shù)。偶數(shù)的正整數(shù)。 x A(x) x A(x) x B(x)x B(x) 存在為奇數(shù)的正整數(shù)存在為奇數(shù)的正整數(shù)且且存在為

13、偶數(shù)的正整存在為偶數(shù)的正整數(shù)。數(shù)。2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則 量詞與聯(lián)結(jié)詞量詞與聯(lián)結(jié)詞，的關(guān)系總結(jié)的關(guān)系總結(jié)：1) x(A(x) B(x) x A(x) xB(x) x(A(x)B(x) x A(x) x B(x)2) x (A(x) B(x) x A(x) x B(x) x (A(x) B(x) x A(x) x B(x)2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則v對(duì)于二元謂詞有八種情況：對(duì)于二元謂詞有八種情況：1.( x)( y)A(x,y)2.( x)( y)A(x,y)3.( x)( y)A(x,y)4.( x)( y)A(x,y)5.( y

14、)( x)A(x,y)6.( y)( x)A(x,y)7.( y)( x)A(x,y)8.( y)( x)A(x,y)2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則（5）含有多個(gè)量詞的）含有多個(gè)量詞的等價(jià)式等價(jià)式 在含有多個(gè)量詞的謂詞公式中在含有多個(gè)量詞的謂詞公式中, x y, x y的位置是可以改變的的位置是可以改變的,且不影響命題的真值。且不影響命題的真值。 即即相同量詞間的次序是可以任意調(diào)動(dòng)的，相同量詞間的次序是可以任意調(diào)動(dòng)的，不同量詞間的次序則不能隨意調(diào)動(dòng)。所以不同量詞間的次序則不能隨意調(diào)動(dòng)。所以有：有： x yP(x,y) y xP(x,y) x yP(x,y) y xP(

15、x,y)2.3 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則 若謂詞公式中出現(xiàn)多個(gè)不同量詞時(shí)，則按照若謂詞公式中出現(xiàn)多個(gè)不同量詞時(shí)，則按照從左到右從左到右的次序讀出，不能顛倒次序。的次序讀出，不能顛倒次序。例：例： y x(xy-2)表示任何表示任何y均存在均存在x，使得，使得x( x)P(x)( x)Q(x) (附加前提法附加前提法)v證明：證明：(1) ( x)P(x) P(附加前提附加前提) (2) ( x)P(x) T(1) (3) P(c) ES(2) (4) x(P(x)Q(x) P (5) P(c)Q(c) US(4)2.5 一階邏輯的推理理論一階邏輯的推理理論v(6) Q(

16、c) T(3)(5)v(7)( x)Q(x) EG(6)v(8) ( x)P(x) ( x)Q(x) CP小結(jié)：小結(jié)：本節(jié)介紹了謂詞演算的推理規(guī)則本節(jié)介紹了謂詞演算的推理規(guī)則,并舉例說并舉例說明了它們的應(yīng)用明了它們的應(yīng)用. 重點(diǎn)重點(diǎn):深刻理解四個(gè)推理規(guī)則深刻理解四個(gè)推理規(guī)則,會(huì)應(yīng)用它們推理證明會(huì)應(yīng)用它們推理證明.作業(yè)作業(yè): P85 12、15、 242.5 一階邏輯的推理理論一階邏輯的推理理論Cp 規(guī)則證明規(guī)則證明例：證例：證: 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

17、 (2) (4) P(c) US(1) (5) Q(c) T(3)(4)I (6) xQ(x) EG(5) (7) x P(x)xQ(x) CP2.5 一階邏輯的推理理論一階邏輯的推理理論反證法反證法例：證明：例：證明： 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

18、(x) T(7)(8)I (10) F2.5 一階邏輯的推理理論一階邏輯的推理理論例例 將下列推理符號(hào)化并給出形式證明將下列推理符號(hào)化并給出形式證明: : 每一個(gè)大學(xué)生不是文科生就是理科生；有的大每一個(gè)大學(xué)生不是文科生就是理科生；有的大學(xué)生是優(yōu)等生；小張不是文科生但他是優(yōu)等生。因?qū)W生是優(yōu)等生；小張不是文科生但他是優(yōu)等生。因此，如果小張是大學(xué)生，他就是理科生。此，如果小張是大學(xué)生，他就是理科生。n解解 個(gè)體域取全總個(gè)體域，設(shè)個(gè)體域取全總個(gè)體域，設(shè)P(x)：x是大學(xué)生，是大學(xué)生，Q(x)：x是文科生，是文科生，S(x)：x是理科生，是理科生，T(x)：x是優(yōu)等生，是優(yōu)等生，c：小張，則：小張，則前提：前提： x(P(x)(Q(x) S(x)， x(P(x) T(x)， Q(c) T(c)結(jié)論：結(jié)論：P(c)S(c)2.5 一階邏輯的推理理論一階邏輯的推理理論推理形式：推理形式： 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) P (3) P(c)(Q(c) S(c) US(