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

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

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

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

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

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

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

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

8、公式例：指出下列各合式公式中的指導變元，量詞的轄域，個體變項的自由出現(xiàn)和約束出現(xiàn)。（a）（b）（c）),()()()(yxRyxPx),()()(yxGxFx),()(),(),()()(yxPxzyQyxPyx2.2 2.2 量詞與合式公式2.2 2.2 量詞與合式公式2.2 2.2 量詞與合式公式在謂詞合式公式中，有的個體變元既可以是約束出現(xiàn)，又可以是自由出現(xiàn)，為了避免混淆采用下列兩個規(guī)則：（1）約束變元改名規(guī)則，在量詞轄域中，某個約束出現(xiàn)的個體變元及相應指導變元改成本轄域中未出現(xiàn)過的個體變元，其余不變。（2）自由變元代入規(guī)則，對某個自由出現(xiàn)的個體變元可用個體常元或用與原子公式中與所有個體

9、變元不同的個體變元去代入，且處處代入。例：對 換名。解：例：對公式 中的自由變元代入。解：),(),()()(yxQyxRxPx),(),()()(yxQyzRzPz),(),()()(yxRyxQyPx),(),()()(zxRzxQzPx2.3 2.3 謂詞演算的等價式與蘊含式當確定論域后 ，與 都是一個特定的命題。例如 表示x是個大學生，論域是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 謂詞演算的等價式與蘊含式2.3 2.3 謂詞演算的等價式與蘊含式例 ： 給 定 論 域 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 謂詞演算的等價式與蘊含式例：尋求下式的真值。 ，其中P:21,Q(x):x3，R(x):

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

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

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

14、：由 得到P(c) C是論域中某些個體（不是任意存在的）（4）存在推廣規(guī)則（EG）：由P(c)得到)()(xPx)()(xPx)()(xPx)()(xPx)()(xPx2.5 2.5 謂詞演算的推理理論例：著名的蘇格拉底論證可以用下式表示：H(x):x是一個人；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è)委員會成員都是教授，并且是計算機設計師，有些成員是資深專家，所以有的成員是計算機設計師，且

15、是資深專家。請用謂詞推理理論證明上述推理。證：設個體域為全總個體域。M(x):x是專業(yè)委員會成員；H(x):x是教授；G(x):x是計算機設計師；R(x):x是資深專家。前提結論)()()()(sGxHxMx)()()(xRxMx)()()()(xGxRxMx2.5 2.5 謂詞演算的推理理論證：前提 結論 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