自考離散數(shù)學(xué)第2章

1、離散數(shù)學(xué)第二章 謂詞演算主要內(nèi)容2.1謂詞的概念與表示2.2量詞與合式公式2.3謂詞演算的等價(jià)式與蘊(yùn)含式2.4前束范式2.5謂詞演算的推理理論2.1 2.1 謂詞的概念與表示客體：指可以獨(dú)立存在的對(duì)象，一個(gè)具體的事物，一個(gè)抽象的概念謂詞：指明客體性質(zhì)或指明客體之間關(guān)系例：（1）王強(qiáng)是個(gè)大學(xué)生 （2）7是質(zhì)數(shù) （3）哥白尼指出地球繞太陽(yáng)轉(zhuǎn) （4）濟(jì)南位于北京與上海之間我們將用大寫(xiě)字母表示謂詞，小寫(xiě)字母表示客體名稱。2.1 2.1 謂詞的概念與表示個(gè)體常項(xiàng)：具體、特定的個(gè)體個(gè)體變項(xiàng)：抽象、泛指的個(gè)體個(gè)體域（論域）：個(gè)體變項(xiàng)的取值范圍全總個(gè)體域：一切事物組成的個(gè)體域 謂詞常項(xiàng)：表示具體性質(zhì)或關(guān)系的謂

2、詞定義2.1.1 由一個(gè)謂詞，一些個(gè)體變?cè)M成的表達(dá)式簡(jiǎn)稱為謂詞變項(xiàng)或命題函數(shù)。謂詞變項(xiàng)中，個(gè)體變?cè)臄?shù)目稱為謂詞變項(xiàng)的元數(shù)。如F(x)為一元謂詞，L(x,y)為二元謂詞。F(a)（a為常量）為0元謂詞2.1 2.1 謂詞的概念與表示例：以謂詞表達(dá)下述命題。某人大于18歲，身體健康，無(wú)色盲，大學(xué)畢業(yè)，則他可參加飛行員考試。解：設(shè)某人為a。A(x):x超過(guò)18歲；B(x):x身體健康；C(x):x色盲；D(x):x大學(xué)畢業(yè)；E(x):x參加飛行員考試；)()()()()(aEaDaCaBaA2.1 2.1 謂詞的概念與表示例：用0元謂詞符號(hào)化下列命題。（a）如果3小于4，且4小于5，則3小于5.

3、（b）如果某數(shù)是有理數(shù)，則某數(shù)可寫(xiě)成分?jǐn)?shù)。解：（a）設(shè)L(x,y):x小于y （b）設(shè)G(x):x是有理數(shù)；H(x):x可寫(xiě)成分?jǐn)?shù)；a：某數(shù)。)5 , 3()5 , 4()4 , 3(LLL)()(aHaG2.1 2.1 謂詞的概念與表示練習(xí)：P29 32.2 2.2 量詞與合式公式量詞：表示數(shù)量的詞量詞有2種：1.全稱量詞：對(duì)應(yīng)日常語(yǔ)言中的“一切”“任意的”“所有”“凡是”等詞。用符號(hào)“ ”表示。 表示對(duì)個(gè)體域里所有的x，而 表示個(gè)體域里所有個(gè)體，都有性質(zhì)F。2.存在量詞：對(duì)應(yīng)日常語(yǔ)言中的“存在的”“有一個(gè)”“至少有一個(gè)”等詞。用符號(hào)“ ”表示。 表示存在個(gè)體域中的個(gè)體，而 表示存在個(gè)體域中

4、的個(gè)體具有性質(zhì)F。x)(xxFx)(xxF2.2 2.2 量詞與合式公式例：每個(gè)自然數(shù)都是實(shí)數(shù)。解：個(gè)體域設(shè)為自然數(shù)集N，令R(x):表示x是實(shí)數(shù)。若不指明論域，那么可設(shè)N(x)：x是自然數(shù)，R(x):x是實(shí)數(shù)例：有些人可以活過(guò)百歲。解：若把人類(lèi)領(lǐng)域作為論域，令G(x):x可以活過(guò)百歲。若不指明論域，令S(x):x是人，G(x):x可以活過(guò)百歲。)(xxR)()(xRxNx)()(xGxSx)(xxG2.2 2.2 量詞與合式公式例：每個(gè)自然數(shù)都是實(shí)數(shù)。解：個(gè)體域設(shè)為自然數(shù)集N，令R(x):表示x是實(shí)數(shù)。若不指明論域，那么可設(shè)N(x)：x是自然數(shù)，R(x):x是實(shí)數(shù)例：有些人可以活過(guò)百歲。解：

5、若把人類(lèi)領(lǐng)域作為論域，令G(x):x可以活過(guò)百歲。若不指明論域，令S(x):x是人，G(x):x可以活過(guò)百歲。N(x),S(x)都是用來(lái)指明論域，它們稱特性謂詞。在全稱量詞中，特性謂詞是條件式的前件。在存在量詞中，特性謂詞后跟一個(gè)合取項(xiàng)。)(xxR)()(xRxNx)()(xGxSx)(xxG2.2 2.2 量詞與合式公式例：凡是偶數(shù)均能被2整除。解：E(x):x是偶數(shù)；G(x)：x能被2整除。例：沒(méi)有不犯錯(cuò)誤的人。解：設(shè)M(x):x是人；F(x):x犯錯(cuò)誤。本題可改述為：所有人都犯錯(cuò)誤。)()(xGxEx)()(xFxMx)()(xFxMx2.2 2.2 量詞與合式公式例：著名的蘇格拉底三段

6、論可敘述如下：（a）所有人都要死的；（b）因?yàn)樘K格拉底是人；（c）所以蘇格拉底總是要死的。解：設(shè)M(x):x是人；D(x):x是要死的；a：蘇格拉底（a）（b）M(a)（c）D(a)前提： ，M(a) 結(jié)論：D(a)()(xDxMx)()(xDxMx2.2 2.2 量詞與合式公式2.2 2.2 量詞與合式公式2.2 2.2 量詞與合式公式2.2 2.2 量詞與合式公式定義2.2.1 由一個(gè)或幾個(gè)原子命題函數(shù)以及邏輯聯(lián)結(jié)詞組合而成的表達(dá)式稱為復(fù)合命題函數(shù)。定義2.2.2 謂詞演算的合式公式，可由下述各條組成（合式公式A記為WffA）：（1）原子謂詞公式是合式公式。（2）若A是合式公式，則A是一個(gè)

7、合式公式。（3）若A和B都是合式公式，則（AB），（AB），（AB），（AB）是合式公式。（4）如果A是合式公式，x是A中出現(xiàn)的任何變?cè)?，則 和 都是合式公式。（5）只有經(jīng)過(guò)有限次應(yīng)用規(guī)則（1）（2）（3）（4）所得到的公式是合式公式。Ax)(Ax)(2.2 2.2 量詞與合式公式2.2 2.2 量詞與合式公式定義2.2.3 給定謂詞合式公式A，其中一部分公式形式為 或稱量詞 ， 后面所跟的x為指導(dǎo)變?cè)蜃饔米冊(cè)?。稱B(x)為相應(yīng)量詞的轄域（或作用域）。 在轄域中，x的一切出現(xiàn)稱為約束出現(xiàn)。B(x)中除去約束出現(xiàn)的其他變項(xiàng)的出現(xiàn)為自由出現(xiàn)。)()(xBx)()(xBx2.2 2.2 量詞與合式

8、公式例：指出下列各合式公式中的指導(dǎo)變?cè)?，量詞的轄域，個(gè)體變項(xiàng)的自由出現(xiàn)和約束出現(xiàn)。（a）（b）（c）),()()()(yxRyxPx),()()(yxGxFx),()(),(),()()(yxPxzyQyxPyx2.2 2.2 量詞與合式公式2.2 2.2 量詞與合式公式2.2 2.2 量詞與合式公式在謂詞合式公式中，有的個(gè)體變?cè)瓤梢允羌s束出現(xiàn)，又可以是自由出現(xiàn)，為了避免混淆采用下列兩個(gè)規(guī)則：（1）約束變?cè)拿?guī)則，在量詞轄域中，某個(gè)約束出現(xiàn)的個(gè)體變?cè)跋鄳?yīng)指導(dǎo)變?cè)某杀据犛蛑形闯霈F(xiàn)過(guò)的個(gè)體變?cè)?，其余不變。?）自由變?cè)胍?guī)則，對(duì)某個(gè)自由出現(xiàn)的個(gè)體變?cè)捎脗€(gè)體常元或用與原子公式中與所有個(gè)體

9、變?cè)煌膫€(gè)體變?cè)ゴ?，且處處代入。例：?duì) 換名。解：例：對(duì)公式 中的自由變?cè)?。解?,(),()()(yxQyxRxPx),(),()()(yxQyzRzPz),(),()()(yxRyxQyPx),(),()()(zxRzxQzPx2.3 2.3 謂詞演算的等價(jià)式與蘊(yùn)含式當(dāng)確定論域后 ，與 都是一個(gè)特定的命題。例如 表示x是個(gè)大學(xué)生，論域是a,b,c,則： 即是S(a)S(b)S(c) 即是S(a)S(b)S(c)例：如果論域是集合a,b,c,試消去下面公式中的量詞：解：原式 (R(a)R(b)R(c)(S(a)S(b)S(c)()(xPx)()()()(xSxxRx)()(xPx)

10、()(xSx)()(xSx)()(xSx2.3 2.3 謂詞演算的等價(jià)式與蘊(yùn)含式2.3 2.3 謂詞演算的等價(jià)式與蘊(yùn)含式例 ： 給 定 論 域 D = 2 , 3 ， a = 2 ， f （ 2 ） = 3 ， f （ 3 ） = 2 ，S(2)=F,S(3)=T,G(2,2)=T,G(3,2)=T,L(2,2)=L(3,3)=T,L(2,3)=L(3,2)=F。在上述賦值下，求下列各式的真值。（a）（b）（c）),()(yxLyx ),()()(axGxSx)(,()()(xfxGxfSx2.3 2.3 謂詞演算的等價(jià)式與蘊(yùn)含式例：尋求下式的真值。 ，其中P:21,Q(x):x3，R(x):

11、x5,a=5，且論域-2,3,6)()()(aRxQPx2.3 2.3 謂詞演算的等價(jià)式與蘊(yùn)含式2.3 2.3 謂詞演算的等價(jià)式與蘊(yùn)含式定義2.3.1 給定任何兩個(gè)謂詞公式WffA和WffB，設(shè)它們有共同的個(gè)體域E，若對(duì)A和B的任一組變?cè)M(jìn)行賦值，所得命題的真值相同，則稱謂詞公式A和B在E上是等價(jià)的，并記作定義2.3.2 給定任意謂詞公式WffA，其個(gè)體域?yàn)镋，對(duì)于A的所有賦值WffA都為真，則稱WffA在E上有效的（或永真的）定義2.3.3 一個(gè)謂詞公式WffA，如果在所有賦值下都為假，則稱WffA為不可滿足。定義2.3.4 一個(gè)謂詞公式WffA，如果至少在一種賦值下為真，則稱WffA為可滿

12、足。BA 2.3 2.3 謂詞演算的等價(jià)式與蘊(yùn)含式定理 2.3.1 量詞與否定聯(lián)結(jié)詞之間有如下關(guān)系：（1）（2）)()(xQxxxQ)()(xQxxxQ2.3 2.3 謂詞演算的等價(jià)式與蘊(yùn)含式2.3 2.3 謂詞演算的等價(jià)式與蘊(yùn)含式表2.3.12.3 2.3 謂詞演算的等價(jià)式與蘊(yùn)含式2.3 2.3 謂詞演算的等價(jià)式與蘊(yùn)含式2.3 2.3 謂詞演算的等價(jià)式與蘊(yùn)含式2.4 2.4 前束范式定義2.4.1 一個(gè)公式，如果量詞均在全式的開(kāi)頭，它們的作用域，延伸到整個(gè)公式的末尾，則該公式叫做前束范式。定理2.4.1 任意一個(gè)謂詞公式均和一個(gè)前束范式等價(jià)。例：把公式 化為前束范式。)()()()(xQxx

13、Px)()()()()()()()()()()()()()()(xQxPxxQxxPxxQxxPxxQxxPx2.4 2.4 前束范式例：把下列公式化為前束范式。（1）（2）)()(xxGxxF)()()()()()(xRxyQyxPx2.3 2.3 謂詞演算的等價(jià)式與蘊(yùn)含式2.5 2.5 謂詞演算的推理理論（1）全稱指定規(guī)則（US）：由 得到P(c)。 P是謂詞，而c是論域中的任意某個(gè)個(gè)體，如果論域中全部個(gè)體有P(x)，那么全稱指定規(guī)則有結(jié)論P(yáng)(c)（2）全稱推廣規(guī)則（UG）：由P(c)得到 如果能夠證明對(duì)論域中任一客體x斷言P(x)都成立，則全稱推廣規(guī)則可得到結(jié)論（3）存在指定規(guī)則（ES）

14、：由 得到P(c) C是論域中某些個(gè)體（不是任意存在的）（4）存在推廣規(guī)則（EG）：由P(c)得到)()(xPx)()(xPx)()(xPx)()(xPx)()(xPx2.5 2.5 謂詞演算的推理理論例：著名的蘇格拉底論證可以用下式表示：H(x):x是一個(gè)人；M(x):x是要死的；s：蘇格拉底。用推論方法證明。（1） P（2）H(s)M(s) US(1)（3）H(s) P（4）M(s) T(2)(3)I)()()()()(sMsHxMxHx)()()(xMxHx2.5 2.5 謂詞演算的推理理論例：專業(yè)委員會(huì)成員都是教授，并且是計(jì)算機(jī)設(shè)計(jì)師，有些成員是資深專家，所以有的成員是計(jì)算機(jī)設(shè)計(jì)師，且

15、是資深專家。請(qǐng)用謂詞推理理論證明上述推理。證：設(shè)個(gè)體域?yàn)槿倐€(gè)體域。M(x):x是專業(yè)委員會(huì)成員；H(x):x是教授；G(x):x是計(jì)算機(jī)設(shè)計(jì)師；R(x):x是資深專家。前提結(jié)論)()()()(sGxHxMx)()()(xRxMx)()()()(xGxRxMx2.5 2.5 謂詞演算的推理理論證：前提 結(jié)論 P M(c)R(c) ES(1) P M(c)H(c)G(c) US(3) M(c) T(2)I H(c)G(c) T(4)(5)I R(c) T(2)I G(c) T(6)I M(c)R(c)G(c) T(5)(7)(8)I EG(9)()()()(sGxHxMx)()()(xRxMx)()()()(xGxRxMx)()()(xRxMx)()()()(sGxHxMx)()()()(xGxRxMx2.5 2.5 謂詞演算的推理理論例：證明 P(附加前提) T(1)E T(2)I T(3)E T(2)I T(5)E G(c) ES(4) Q(c) US(6) G(c)Q(c) T(7)(8)I （G(c)Q(c)） T(9)E)()()()()()()(xQxxGxxQxGx)()()()(xQxxGx)()()()(xQxxGx)()(xGx)()(xGx )()(xQx)()(xQx 2.5 2.5 謂詞演算的推理理論（11