離散數(shù)學(xué)復(fù)習(xí)資料

1、本章重點(diǎn)：命題與聯(lián)結(jié)詞，公式與解釋，真值表，公式的類型及判定, (主)析取(合取)范式，命題邏輯的推理理論.一、重點(diǎn)內(nèi)容1. 命題命題表述為具有確定真假意義的陳述句。命題必須具備二個(gè)條件：其一，語(yǔ)句是陳述句；其二，語(yǔ)句有唯一確定的真假意義. 2. 六個(gè)聯(lián)結(jié)詞及真值表h“Ø”否定聯(lián)結(jié)詞，P是命題，ØP是P的否命題，是由聯(lián)結(jié)詞Ø和命題P組成的復(fù)合命題.P取真值1，ØP取真值0，P取真值0，ØP取真值1. 它是一元聯(lián)結(jié)詞.h“Ù”合取聯(lián)結(jié)詞，PÙQ是命題P，Q的合取式，是“Ù”和P，Q組成的復(fù)合命題. “Ù”在

2、語(yǔ)句中相當(dāng)于“不但而且”，“既又”. PÙQ取值1，當(dāng)且僅當(dāng)P，Q均取1；PÙQ取值為0，只有P，Q之一取0.h“Ú”析取聯(lián)結(jié)詞，“Ú”不可兼析取(異或)聯(lián)結(jié)詞， PÚQ是命題P，Q的析取式，是“Ú”和P，Q組成的復(fù)合命題. PÚQ是聯(lián)結(jié)詞“Ú”和P，Q組成的復(fù)合命題. 聯(lián)結(jié)詞“Ú”或“Ú”在一個(gè)語(yǔ)句中都表示“或”的含義，前者表示相容或，后者表示排斥或不相容的或. 即“PÚQ”«“(ØPÙQ)Ú(PÙØQ)”. PÚ

3、Q取值1，只要P，Q之一取值1，PÚQ取值0，只有P，Q都取值0. h“®”蘊(yùn)含聯(lián)結(jié)詞， P®Q是“®”和P，Q組成的復(fù)合命題，只有P取值為1，Q取值為0時(shí)，P®Q取值為0；其余各種情況，均有P®Q的真值為1，亦即1®0的真值為0，0®1，1®1，0®0的真值均為1. 在語(yǔ)句中，“如果P則Q”或“只有Q，才P，”表示為“P®Q”.h “«” 等價(jià)聯(lián)結(jié)詞，P«Q是P，Q的等價(jià)式，是“«”和P，Q組成的復(fù)合命題. “«”在語(yǔ)句中相當(dāng)于“當(dāng)且僅當(dāng)”，P

4、«Q取值1當(dāng)且僅當(dāng)P，Q真值相同.3. 命題公式、賦值與解釋，命題公式的分類與判別h命題公式與賦值，命題P含有n個(gè)命題變項(xiàng)P1，P2,Pn，給P1，P2,Pn各指定一個(gè)真值，稱為對(duì)P的一個(gè)賦值(真值指派). 若指定的一組值使P的真值為1，則這組值為P的真指派；若使P的真值為0，則稱這組值稱為P的假指派.h命題公式分類，在各種賦值下均為真的命題公式A，稱為重言式(永真式)；在各種賦值下均為假的命題公式A，稱為矛盾式(永假式)；命題A不是矛盾式，稱為可滿足式；判定命題公式類型的方法：其一是真值表法推導(dǎo)演算法主析取(合取)范式法，該公式的主析取范式有2n個(gè)極小項(xiàng)(即無極大項(xiàng))，則該公式是永

5、真式；該公式的主合取范式有2n個(gè)極大項(xiàng)(即無極小項(xiàng))，則該公式是永假式；該公式的主析取(或合取)范式的極小項(xiàng)(或極大項(xiàng))個(gè)數(shù)大于0小于2n,，則該公式是可滿足式.h等值式AÛB，命題公式A，B在任何賦值下，它們的真值均相同，稱A，B等值。定理1 設(shè)F(A)是含命題公式A的命題，F(xiàn)(B)是用命題公式B置換F(A)中的A之后得到的命題公式. 如果AÛB，則F(A)ÛF(B). 4. 范式h析取(合取)范式，僅有有限個(gè)簡(jiǎn)單合取式(析取式)構(gòu)成的析取式(合取式)，就是析取(合取)范式. h極小項(xiàng)(極大項(xiàng))，n個(gè)命題變項(xiàng)P1,P2,Pn，每個(gè)變項(xiàng)或它的否定兩者只有其一出現(xiàn)且

6、僅出現(xiàn)一次，第i個(gè)命題變項(xiàng)或者其否定出現(xiàn)在從左起第i個(gè)位置上(無腳標(biāo)時(shí)，按字典序排列)，這樣的簡(jiǎn)單合取式(析取式)為極小項(xiàng)(極大項(xiàng)). 以兩個(gè)命題變項(xiàng)為例，m00=ØPÙØQ，m01=ØPÙQ,m10=PÙØQ,m11=PÙQ是極小項(xiàng);M00=PÙQ，M01=PÙØQ,M10=ØPÙQ,M11=ØPÙØQ是極大項(xiàng).h主析取范式(主合取范式) 含有n個(gè)命題變項(xiàng)的命題公式，如果與一個(gè)僅有極小項(xiàng)(極大項(xiàng))的析取(合取)構(gòu)成的析取(合取)范式等

7、值，則該等值式稱為原命題公式的主析取(合取)范式。每項(xiàng)含有n個(gè)命題變項(xiàng)(變項(xiàng)字母齊全)的合取式(析取式)的析取(合取)為主析取(合取)范式.任意命題公式都存在與之等值的范式，存在與之等值的主范式，且是惟一的. 求范式，包括求析取范式、合取范式、主析取范式和主合取范式. 關(guān)鍵有兩點(diǎn)：其一是準(zhǔn)確掌握范式定義；其二是巧妙使用基本等值式中的分配律、同一律和摩根律，結(jié)果的前一步適當(dāng)使用冪等律. 求析取(合取)范式的步驟： 將公式中的聯(lián)結(jié)詞都化成Ø，Ù，Ú(即消去個(gè)數(shù)中的聯(lián)結(jié)詞®，«，Ú)； 將否定聯(lián)結(jié)詞Ø消去或移到各命題變項(xiàng)之前； 利

8、用分配律、結(jié)合律等，將公式化為析取(合取)范式. 求命題公式A的主析取(合取)范式的步驟 求公式A的析取(合取)范式； “消去”析取(合取)范式中所有永假式(永真式)的析取項(xiàng)(合取項(xiàng))，如PÙØP(PÚØP)用0(1)替代. 用冪等律將析取(合取)范式中重復(fù)出現(xiàn)的合取項(xiàng)(析取項(xiàng))或相同的變項(xiàng)合并，如PÙP(PÚP)用P替代，miÚmi(MiÙMi)用mi(Mi)替代. 若析取(合取)范式的某個(gè)合取項(xiàng)(析取項(xiàng))B不含有命題變項(xiàng)Pi或ØPi，則添加PiÚØPi(PiÙØ

9、Pi)，再利用分配律展開，使得每個(gè)合取項(xiàng)(析取項(xiàng))的命題變項(xiàng)齊全； 將極小(極大)項(xiàng)按由小到大的順序排列，用S(P)表示. 5. 命題演算的推理理論h設(shè)A1,A2,An,C是命題公式，如果是重言式，稱C是前提集合 A1,A2,An的有效結(jié)論或A1,A2,An邏輯地推出C。記作掌握演繹或形式證明. 要理解并掌握14個(gè)重言蘊(yùn)含式(即I1I14)，17個(gè)等值式(E1E17)；二是會(huì)使用三個(gè)規(guī)則(P規(guī)則、T規(guī)則和CP規(guī)則)。推理方法有：真值表法；等值演算法；主析取范式法，構(gòu)造證明法(直接證明法、附加前提證明法和間接證明法) 二、實(shí)例例1.1 判別下列語(yǔ)句是否命題？如果是命題，指出其真值. (

10、1) 中國(guó)是一個(gè)人口眾多的國(guó)家. (2) 存在最大的質(zhì)數(shù).(3) 這座樓可真高??！ (4) 請(qǐng)你跟我走!(5)火星上也有人. 解 (1) 是命題，真值為1. (2) 是命題，真值為0. (3), (4)不是命題因?yàn)椴皇顷愂鼍?(5) 是命題. 真值是唯一的，遲早會(huì)被指出. 例1.2 將下列命題符號(hào)化：(1) 雖然交通堵塞，但是老王還是準(zhǔn)時(shí)到達(dá)火車站； (2) 張力是三好生，他是北京人或是天津人.(3) 除非天下雨，否則我騎車上班.解 (1) 設(shè)P：交通堵塞，Q：老王準(zhǔn)時(shí)到達(dá)火車站. 該命題符號(hào)化為：PÙQ. (2)設(shè)P：張力是三好生； Q：張力是北京人，R：張力是天津人.該命題符號(hào)化

11、為PÙ(QÚR ). (3)設(shè)P：天下雨，Q：我不騎車上班.該命題符號(hào)化為：Q®P，義即“只有天下雨，我才不騎車上班”，不下雨是我騎車上班的必要條件。它的等價(jià)說法是“如果天不下雨，我就騎車上班”，即ØP®ØQ“如果天下雨，我就不騎車上班”，這是蘊(yùn)含關(guān)系，符號(hào)化為：P®Q注：本例各小題都是復(fù)合命題。如“李枚和張櫻花是好朋友”是簡(jiǎn)單命題，用字母P表示。顯然P：李枚是好朋友，Q：張櫻花是好朋友，符號(hào)化為QÙP是不通的.例1.3 證明：P®(Q®R)ÛPÙQ®R.證明方法1

12、 真值表法. 列公式P®(Q®R)與PÙQ®R的真值表如表11. .表11 公式P®(Q®R)與PÙQ®R的真值表 PQRQ®RP®(Q®R)PÙQPÙQ®RP®(Q®R)«PÙQ®R0001101100111011010010110111101110011011101110111100010111111111由表可知，公式P®(Q®R)與PÙQ®R的真值完全相同，故

13、P®(Q®R)ÛPÙQ®R. 或由表的最后一列可知，P®Q«ØPÚQ是重言式，故P®(Q®R)ÛPÙQ®R.注：作為本例的證明可以不要最后1列。若本例改為判斷P®(Q®R)«PÙQ®R的類型，由最后列可知P®(Q®R)«PÙQ®R是重言式.方法2 等值演算法.P®（Q®R）ÛP®(ØQÚR) (等值

14、蘊(yùn)含式)ÛØPÚ(ØQÚR) (等值蘊(yùn)含式)Û（ØPÚØQ）ÚR (結(jié)合律)ÛØ(PÙQ)ÚR (摩根律)ÛPÙQ®R (等值蘊(yùn)含式)所以，P®（Q®R）Û(PÙQ)®R例中等值演算的每一步都用到了置換規(guī)則. 由等值演算的傳遞性，可知第一個(gè)公式P®(Q®R)和最后一個(gè)公式PÙQ)®R等值. 方法3 主范式法.P®(Q®

15、R)ÛØPÚ(ØQÚR)ÛØPÚØQÚR(主合取范式)PÙQ®RÛØ(PÙQ)ÚRÛØPÚØQÚR(主合取范式)P®(Q®R)與PÙQ®R的主合取范式相同，故P®(Q®R)ÛPÙQ®R。注：(1)容易寫出P®(Q®R)與PÙQ®R的主析取范式均為m0Ú

16、;m1Úm2Úm3Úm4Úm5Úm7即 (ØPÙØQÙØR)Ú(ØPÙØQÙR)Ú(ØPÙQÙØR)Ú(ØPÙQÙR)Ú(PÙØQÙØR)Ú(PÙØQÙR)Ú (PÙQÙR)(2) 由真值表求公式P®(Q®R)的主析取范

17、式，先列出P®(Q®R)的真值表，見表11。主析取范式是公式P®(Q®R)真值為1的項(xiàng)的析取，真值為1的項(xiàng)，即極小項(xiàng)，有第1,2,3,4,5,6,8共7項(xiàng). 而極小項(xiàng)是合取式，合取式為1，必定是每個(gè)變?cè)蚱浞穸?，如表11中第1行P，Q，R均取1，所以這一項(xiàng)為ØPÙØQÙØR，類似地，7個(gè)極小項(xiàng)為：ØPÙØQÙØR，ØPÙØQÙR，ØPÙQÙØR，ØPÙQ

18、ÙR，PÙØQÙØR，PÙØQÙR，PÙQÙR所以P®(Q®R)的主析取范式為： (ØPÙØQÙØR)Ú(ØPÙØQÙR)Ú(ØPÙQÙØR)Ú(ØPÙQÙR)Ú(PÙØQÙØR)Ú(PÙØQÙR)&

19、#218; (PÙQÙR)例1.4 用等值演算法判定公式PÚ(QÙR)®PÚQÚR是永真式？永假式？可滿足式？解等值運(yùn)算法. PÚ(QÙR)®PÚQÚRÛØ(PÚ(QÙR)ÚPÚQÚRÛØ(PÙØ(QÙR)ÚØPÙ(QÙR)ÚPÚQÚRÛØ(PÙØ(

20、QÙR)Ú(ØPÙQÙR)ÚPÚQÚRÛ(Ø(PÙØ(QÙR)ÙØ(ØPÙQÙR)ÚPÚQÚRÛ(ØPÚ(QÙR)Ù(PÚØQÚØR)ÚPÚQÚRÛ(ØPÚ(QÙR) ÚPÚQÚR)Ù(P&

21、#218;ØQÚØR)ÚPÚQÚR) (Ú對(duì)Ù的分配律)Û(ØPÚP)ÚQÚRÚ(QÙR)Ù1Û1Ù1Û1因此，PÚ(QÙR)®PÚQÚR是永真式. 注：也可以用真值表法或主范式法. 例1.5 化簡(jiǎn)下式： (AÙBÙC)Ú(ØAÙBÙC)解(AÙBÙC)Ú(Ø

22、AÙBÙC)例1.6 求公式的主合取范式和主析取范式. 解先將公式化為合取范式. (去掉«) (去掉®) (合取范式)(添齊命題變項(xiàng))所求主析取范式為主合取范式的缺項(xiàng)所對(duì)應(yīng)的三個(gè)極小項(xiàng)，即為 m1Úm6Úm7ÛÛ或通過求析取范式求主析取范式. (去掉«) (去掉®) (合取范式)注：也可以用列真值表的方法，求主析取或主合取范式，見例的注.試用P，Q和聯(lián)結(jié)詞Ø，®，Ù構(gòu)造命題公式A，使得A與F等值. 解 取真值表中F為1的成真賦值01,10的析取,即為  例

23、1.7 已知P，Q，F(xiàn)的真值表如下表. PQF000011101110即命題公式與F等值.例1.8 試證明：方法1 欲證明，只需證明是重言式，即其真值是1.證明所以，推理正確。方法2 構(gòu)造推理附加前提證明法(1) S CP規(guī)則(2) ØSÚP P(3) P (1),(2)析取三段論(4) P®(Q®R) P(5)Q®R (3),(4)假言推理(6)Q P (7)R (5),(6)假言推理例1.9 填空題1. 1.       設(shè)命題公式GPÙ(ØQ

24、8;R)，則使G的真值為1的指派是， . 答案：(1,0,0,),(1,0,1),(1,1,1)解答  PQRØQGPÙ(ØQÚR)由真值表知：P，Q，R的真值指派為 (1,0,0,),(1,0,1),(1,1,1)則公式G的真值為1. 應(yīng)填寫(1,0,0,),(1,0,1),(1,1,1)0001 00011 00100 00110 01001 11011 11100 01110 12. 已知命題公式為G(ØPÚQ)®R,則命題公式G的析取范式是答案：(PÙØQ)ÚR解答

25、(ØPÚQ)®RÛØ(ØPÚQ)ÚRÛ(PÙØQ)ÚR故應(yīng)填寫(PÙØQ)ÚR.注：一個(gè)命題公式的析取范式一般不唯一。如(PÙØQ)Ú(PÙR)Ú(ØPÙR)也是該公式的一個(gè)析取范式.例1.10 單項(xiàng)選擇題1. 設(shè)命題公式Ø(PÙ(Q®ØP)，記作G，使G的真值指派為0的P，Q的真值是( )(A) (0,0) (B) (0,1) (C)

26、(1,0) (D) (1,1)答案：(C)解答 PÙ(Q®ØP)ÛPÙ(ØQÚØP)Û(PÙØQ)Ú(PÙØP)ÛPÙØQ 當(dāng)P，Q取值(1，0)時(shí)，ØPÚQ取真值為0. 故選擇(C). 2. 與命題公式P®（Q®R）等值的公式是( ) (A) (PÚQ)®R (B)(PÙQ)®R (C) (P®Q)®R (D) P®

27、(QÚR)答案：(B)解答 P®（Q®R）ÛP®(ØQÚR)ÛØPÚØQÚRÛØ(PÙQ)ÚRÛ(PÙQ)®R故應(yīng)選擇(B)3. 命題公式(PÙQ）®P是( )(A) 永真式 (B) 永假式 (C) 可滿足式 (D) 合取范式答案：(A)解答 (PÙQ）®P所以是永真式. 故選擇(A). 4. 設(shè)命題公式，則公式G與H滿足( ) 答案：(D)解答，即為重言式. 或列真

28、值表. PQØPØQGÛØ(P®Q)HÛP®(Q®ØP)G®H0011 0 1 10110 0 1 11001 1 1 11100 0 0 1可見，GÞH，故應(yīng)選擇(D).  三、練習(xí)題1. 判定下列語(yǔ)句是否為命題，若是命題，指出是簡(jiǎn)單命題或復(fù)合命題. (1) 是無理數(shù). (2) 5能被2整除.(3) 現(xiàn)在開會(huì)嗎？ (4) 2是素?cái)?shù)當(dāng)且僅當(dāng)三角形有3條邊.(5) 如果雪是黑的，則太陽(yáng)從東方升起.2. 將第1題的命題符號(hào)化，并討論其真值. 3. 設(shè)命題P,Q的真值為0，命題R,

29、S的真值為1，求命題公式的真值. 4. 用多種方法判定命題公式的類型. 5. 用多種方法證明等值式成立. 6. 已知命題P，Q和真值函數(shù)F的真值，(P,Q,F)Û(,00,0),(0,1,0),(1,0,1),(1,1,0). 試用P，Q和聯(lián)結(jié)詞Ø，Ú構(gòu)造命題公式C，使得FÛC. 7. 求命題公式的主析取范式和主合取范式. 8. 試證明：四、練習(xí)題答案1. (1) , (2)是簡(jiǎn)單命題，(3) 不是命題，(4)，(5)是復(fù)合命題. 2. (1) P:是無理數(shù),P是真命題，真值為1.(2)P： 5能被2整除，P是假命題，真值為0(4)P：2是素?cái)?shù)，Q：三角

30、形有3條邊，原命題符號(hào)化為P«Q.，真值為1 (5) P：雪是黑的，Q：太陽(yáng)從東方升起，原命題符號(hào)化為P®Q，其真值為1. 3. 真值為0. 4. 原式等值于，是非永真的可滿足式。5. 提示：用分配律、否定律、同一律. 6. 7 主析取范式：主合取范式：8. 前提：結(jié)論：證明方法1，直接證明法 (1) ØQÚR P (2) ØR P (3) ØQ (1), (2)析取三段論 (4) Ø(PÙØQ P (5) ØPÚQ (4) 置換 (6) P®Q (5)置換 (7) 

31、6;P (3),(6) 拒取式方法2，間接證明法(1) Ø(ØP) 結(jié)論否定引入(2) P (1)置換(3) Ø(PÙØQ) P(4) P®Q (3) 置換(5) Q (2),(4)假言推理(6) ØQÚR P(7) R (5),(6)析取三段論(8) ØR P(9) RÙØR (7),(8) 合取引入有(9)可知，構(gòu)造推理是正確的.¾¾第2章 謂詞邏輯 本章重點(diǎn)：謂詞與量詞，公式與解釋，前束范式，謂詞邏輯推理證明.  一、重點(diǎn)內(nèi)容1. 謂詞與量詞h謂詞，

32、在謂詞邏輯中，原子命題分解成個(gè)體詞和謂詞. 個(gè)體詞是可以獨(dú)立存在的客體，它可以是具體事物或抽象的概念。謂詞是用來刻劃個(gè)體詞的性質(zhì)或事物之間關(guān)系的詞. 個(gè)體詞分個(gè)體常項(xiàng)(用a,b,c,表示)和個(gè)體變項(xiàng)(用x,y,z,表示)；謂詞分謂詞常項(xiàng)(表示具體性質(zhì)和關(guān)系)和謂詞變項(xiàng)(表示抽象的或泛指的謂詞)，用F,G,P,表示. 注意，單獨(dú)的個(gè)體詞和謂詞不能構(gòu)成命題，將個(gè)體詞和謂詞分開不是命題. h量詞，是在命題中表示數(shù)量的詞，量詞有兩類：全稱量詞"，表示“所有的”或“每一個(gè)”；存在量詞$，表示“存在某個(gè)”或“至少有一個(gè)”. 在謂詞邏輯中，使用量詞應(yīng)注意以下幾點(diǎn)：(1) (1) 

33、0;  在不同個(gè)體域中，命題符號(hào)化的形式可能不同，命題的真值也可能會(huì)改變. (2) (2)    在考慮命題符號(hào)化時(shí)，如果對(duì)個(gè)體域未作說明，一律使用全總個(gè)體域. (3) (3)    多個(gè)量詞出現(xiàn)時(shí)，不能隨意顛倒它們的順序，否則可能會(huì)改變命題的含義. 謂詞公式只是一個(gè)符號(hào)串，沒有什么意義，但我們給這個(gè)符號(hào)串一個(gè)解釋，使它具有真值，就變成一個(gè)命題. 所謂解釋就是使公式中的每一個(gè)變項(xiàng)都有個(gè)體域中的元素相對(duì)應(yīng). 在謂詞邏輯中，命題符號(hào)化必須明確個(gè)體域，無特別說明認(rèn)為是全總個(gè)體域。一般地，使用全稱量詞"，特性謂詞后用

34、74;；使用存在量詞$，特性謂詞后用Ù.2. 公式與解釋h謂詞公式，由原子公式、聯(lián)結(jié)詞和量詞可構(gòu)成謂詞公式(嚴(yán)格定義見教材). 命題的符號(hào)化結(jié)果都是謂詞公式.例如"x(F(x)®G(x)，$x(F(x)ÙG(x)，"x"y(F(x)ÙF(y)ÙL(x,y)®H(x,y)等都是謂詞公式. h變?cè)c轄域，在謂詞公式"xA和$xA中，x是指導(dǎo)變?cè)?，A是相應(yīng)量詞的轄域. 在"x和$x的轄域A中，x的所有出現(xiàn)都是約束出現(xiàn)，即x是約束變?cè)?，不是約束出現(xiàn)的變?cè)褪亲杂勺冊(cè)? 也就是說，量詞后面的式

35、子是轄域. 量詞只對(duì)轄域內(nèi)的同一變?cè)行? h換名規(guī)則，就是把公式中量詞的指導(dǎo)變?cè)捌漭犛蛑械脑撟冊(cè)獡Q成該公式中沒有出現(xiàn)的個(gè)體變?cè)?，公式的其余部分不? h代入規(guī)則，就是把公式中的某一自由變?cè)?，用該公式中沒有出現(xiàn)的個(gè)體變?cè)?hào)替代，且要把該公式中所有的該自由變?cè)紦Q成新引入的這個(gè)符號(hào). h解釋(賦值)，謂詞公式A的個(gè)體域D是非空集合，則(1) 每一個(gè)常項(xiàng)指定D中一個(gè)元素；(2) 每一個(gè)n元函數(shù)指定Dn到D的一個(gè)函數(shù)；(3) 每一個(gè)n元謂詞指定Dn到0,1的一個(gè)謂詞；按這個(gè)規(guī)則做的一組指派，稱為A的一個(gè)解釋或賦值.在有限個(gè)體域下，消除量詞的規(guī)則為：如Da1,a2,an，則h謂詞公式分類，在任何解

36、釋下，謂詞公式A取真值1，公式A為邏輯有效式(永真式)；在任何解釋下謂詞公式A取真值0，公式A為永假式；至少有一個(gè)解釋使公式A取真值1，公式A稱為可滿足式.3. 前束范式一個(gè)謂詞公式的前束范式仍是謂詞公式. 若謂詞公式F等值地轉(zhuǎn)化成那么就是F的前束范式，其中Q1，Q2，Qk只能是"或$，x1,x2,xk是個(gè)體變?cè)珺是不含量詞的謂詞公式. 每個(gè)謂詞公式F都可以變換成與它等值的前束范式. 其步驟如下： 消去聯(lián)結(jié)詞®，«，Ú； 將聯(lián)結(jié)詞Ø移至原子謂詞公式之前； 利用換名或代入規(guī)則使所有約束變?cè)姆?hào)均不同，并且自由變?cè)c約束變?cè)姆?hào)也不同；將&q

37、uot;x,$x移至整個(gè)公式最左邊； 得到公式的前束范式. 4.謂詞邏輯的推理理論謂詞演算的推理是命題演算推理的推廣和擴(kuò)充，命題演算中的基本等值公式，重言蘊(yùn)含式以及P，T，CP規(guī)則在謂詞演算中仍然使用. 在謂詞演算推理中，某些前提和結(jié)論可能受到量詞的限制，為了使用這些推理，引入消去和附加量詞的規(guī)則，有US規(guī)則(全稱量詞消去規(guī)則)，UG規(guī)則(全稱量詞附加規(guī)則)，ES規(guī)則(存在量詞消去規(guī)則)，EG規(guī)則(存在量詞附加規(guī)則)等，以便使謂詞演算公式的推理過程可類似于命題演算的推理進(jìn)行. 二、實(shí)例例2.1 將下列命題符號(hào)化：(1) 有某些實(shí)數(shù)是有理數(shù)；(2) 所有的人都呼吸； (3)每個(gè)母親都愛自己的孩子

38、.注意：一般地，全稱量詞“"”后，跟蘊(yùn)含聯(lián)結(jié)詞“®”；存在量詞“$”后，跟合取聯(lián)結(jié)詞“Ù”.解 (1) 設(shè)R(x)：x是實(shí)數(shù)，Q(x)：x是有理數(shù)。該命題符號(hào)化$x(R(x)ÙQ(x). (2) 設(shè)全總個(gè)體域，設(shè)M(x)：x是人.，H(x)：x要呼吸，該命題符號(hào)化為："x(M(x)®H(x)該命題等價(jià)說法：“不存在不需要呼吸的人”，符號(hào)化為：Ø$x(M(x)ÙØH(x).其實(shí)它們是等值的，"x(M(x)®H(x)ÛØØ"x(M(x)®H

39、(x)ÛØ( Ø"x(ØM(x)ÚH(x)ÛØ$x(M(x)ÙØH(x)若個(gè)體域D為人的集合。H(x)：x要呼吸. 則該命題符號(hào)化為"xH(x). (3) 在全總個(gè)體域，設(shè)M(x):x是母親，L(x,y):x愛y，A(y):y是孩子, H(x,y):x屬于y命題符號(hào)化為：或若個(gè)體域D是所有母親的集合. M(x)：x愛自己的孩子，該命題符號(hào)化為"xM(x).例 2.2 指出公式中量詞的每次出現(xiàn)轄域，并指出變?cè)拿看纬霈F(xiàn)是約束出現(xiàn)，還是自由出現(xiàn)，以及公式的約束變?cè)?，自由變?cè)?解在

40、公式中，"x只有一次出現(xiàn)，轄域是；"y只有一次出現(xiàn)，轄域是；$x只有一次出現(xiàn)，轄域是H(x,y). 變?cè)獂在該公式中有四次出現(xiàn)，其中第1次、第2次出現(xiàn)是在"x及其轄域中，故是約束出現(xiàn)；第3次，第4次出現(xiàn)是在$x及其轄域中，也是約束出現(xiàn)。這四次出現(xiàn)都是約束出現(xiàn)，所以x是該公式的約束變?cè)? 變?cè)獃在該公式中也有四次出現(xiàn). 其中第1次是在"y中，第2次和第3次出現(xiàn)是在"y的轄域中，是約束出現(xiàn)，第4次出現(xiàn)是自由出現(xiàn)，故y在該公式中有3次約束出現(xiàn)，1次自由出現(xiàn)，因此變?cè)獃既是該公式的約束變?cè)?，也是自由變?cè)? 變?cè)獄在該公式中只有一次自由出現(xiàn)，所以z是該公

41、式的自由變?cè)? 注意，由例2.2看到，同一個(gè)個(gè)體變項(xiàng)，在同一個(gè)公式中，既可以是約束出現(xiàn)，也可以是自由出現(xiàn)，這種情況有時(shí)會(huì)造成一些混淆，帶來不便. 要改變這種情況，使一個(gè)個(gè)體變項(xiàng)在同一個(gè)公式中，不同時(shí)既是約束出現(xiàn)，又是自由出現(xiàn)，采取換名規(guī)則或代入規(guī)則. 在求前束范式時(shí)，尤其需要.例2.3 給定解釋I如下：     D2,3; D中特定元素a=2； 函數(shù)為； 謂詞F(x)為F(2)=0,F(3)=1，G(x,y)為G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1L(x,y)為L(zhǎng)(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0求在解釋I下各公式

42、的真值. (1) ; (2) ；(3) .解 (3)這是給定解釋下，求謂詞公式的真值，個(gè)體域有限，比較好求。只需將量詞消去，函數(shù)值代入謂詞，根據(jù)謂詞的真值，即可求出謂詞公式的真值.要判斷一個(gè)謂詞公式的真、假是較為難的. 在謂詞邏輯中，在任何解釋下都真的公式，才是永真式；在任何解釋下公式A為假，才是永假式；公式A不總是假，或者至少有一個(gè)解釋使得公式A為真，才是可滿足式. 困難之點(diǎn)是在全總個(gè)體域中所有的解釋如何說清楚.因此只能要求會(huì)作簡(jiǎn)單問題.例2.4 討論公式的類型. 解用A表示該公式.對(duì)任意解釋I，A的前件為假，無論后件真假，公式A為真. 這說明A不是永假式；取解釋I如下：個(gè)體域?yàn)檎麛?shù)集，F(xiàn)(

43、x,y)：x £ y，在I下，"x$yF(x,y)，即在整數(shù)中，任給整數(shù)x，存在y使得x£y，顯然為真，即A的前件為真. 但后件$y"xF(x,y)，即存在y對(duì)任給x使得x£y，顯然這是不成立的，亦即后件為假. 由蘊(yùn)含聯(lián)結(jié)詞的真值表1®0的真值為0，故A為假。這說明A不是永真式.綜上所述，A是可滿足式.由例2.4可知，量詞的次序不能隨便顛倒.例2.5 將公式化為前束范式. 解消去聯(lián)結(jié)詞®(若有«，Ú也要消去). 將聯(lián)結(jié)詞Ø移至原子公式之前. 換名.(自由變?cè)膟未改) 把量詞提到整個(gè)公式的前面.

44、為所求前束范式. 寫在一起，所求前束范式是(自由變?cè)膟未改)注：重要的是弄清楚前束范式的定義，求前束范式主要是利用基本等值式、蘊(yùn)含式和換名規(guī)則，把一個(gè)謂詞公式化為量詞在最前面，后面不含量詞的公式，即前束范式. 雖然前束范式是謂詞公式的一種標(biāo)準(zhǔn)形式，但是一般一個(gè)謂詞公式的前束范式并不是唯一的. 例2.6 構(gòu)造推理證明前提：$xF(x), "x(F(x)®G(x)ÙH(x) 結(jié)論：$x(F(x)ÙH(x) 證明：$xF(x) 前提引入 F(c) ES"x(F(x)®G(x)ÙH(x) 前提引入F(c)®G(c)

45、17;H(c) USG(c)ÙH(c) ,假言推理H(c)ÙG(c) 置換 H(c) 化簡(jiǎn)F(c)ÙH(c) ,合取$x(F(x)ÙH(x) EG例2.7 單項(xiàng)選擇題1. 謂詞公式中量詞"x的轄域是( )(A) (B) P(x) (C) (D) 答案：(C)解答："x后面的公式是. 故應(yīng)選擇(C). 2. 謂詞公式xA(x)ØxA(x)的類型是（）(A) 永真式 (B) 矛盾式(C) 非永真式的可滿足式 (D) 不屬于(A),(B),(C)任何類型答案：(B)解答：對(duì)于任意解釋I，xA(x)ØxA(x)Û

46、0所以xA(x)ØxA(x)是永假式. 選擇(B).3 設(shè)個(gè)體域?yàn)檎麛?shù)集，下列公式中其真值為1的是( )(A) (B) (C) (D) 答案：(A)解答：任意一個(gè)整數(shù)x，都能找到y(tǒng)x，使x+y=0, 故(A)式是永真式. 4 設(shè)L(x)：x是演員，J(x)：x是老師，A(x,y)：x佩服y. 那么命題“所有演員都佩服某些老師”符號(hào)化為( )(A) (B) (C) (D) 答案：(B)解答：將命題符號(hào)化為，故應(yīng)選擇(B). 5 在謂詞演算中，P(a)是的有效結(jié)論，根據(jù)是 ( ) (A)US規(guī)則 (B) UG規(guī)則 (C)ES規(guī)則 (D)EG規(guī)則答案：(A) 解答：全稱量詞消去規(guī)則的定義為

47、,即A(c)是的有效結(jié)論. 應(yīng)選擇(A). 例2.8 填空題1.公式的自由變?cè)?, 約束變?cè)?. 答案：y,x ; x,z解答："x的轄域是故x是約束出現(xiàn)，y是自由出現(xiàn)，的轄域是，故z是約束出現(xiàn)，y是自由出現(xiàn)，而S(x)中的x是自由出現(xiàn). 總之y,x是自由變?cè)?，x,z是約束變?cè)? 2. 謂詞邏輯公式的前束范式是 . 答案：解答：求前束范式3. 設(shè)個(gè)體域Da,b,消去公式中的量詞，則答案：解答：由"x和$x真值的定義，4. 換名規(guī)則施于變?cè)?，代入?guī)則施于變?cè)鸢福杭s束；自由. 解答：見換名規(guī)則和代入規(guī)則的定義. 三、練習(xí)題1. 將下列命題符號(hào)化：(1) 丘華和李兵都是學(xué)生

48、； (2) 存在偶素?cái)?shù)；2. 指出謂詞公式中量詞的轄域，并指出變?cè)拿看纬霈F(xiàn)是約束出現(xiàn)，還是自由出現(xiàn)，以及公式的約束變?cè)?，自由變?cè)? 3. 設(shè)個(gè)體域D岳飛，文天祥，秦薈，謂詞F(x)：x是民族英雄。求"xF(x)的真值。4. 設(shè)P是二元謂詞，給定解釋I如下：Da,b,P(a,a)=P(b,a)=1，P(b,a)=P(b,b)=0求下列公式的真值：(1) ； (2) ; (3) 5.討論公式的類型. 6. 用歸謬法，構(gòu)造下面的推理證明.Þ四、練習(xí)題答案 1. (1) 設(shè)P(x)：:x是學(xué)生。. a：丘華，b：黎兵該命題符號(hào)化為：P(a)ÙP(b)(2) 設(shè)N(x):

49、x是自然數(shù)，F(xiàn)(x)：x是偶數(shù)，Q(x)：x是素?cái)?shù)該命題符號(hào)化為$x(N(x)ÙF(x)ÙQ(x)2. 在公式中,"x有二次出現(xiàn)，第一次出現(xiàn)的轄域是中; 第二次出現(xiàn)的轄域是. 變?cè)獂在該公式中有六次出現(xiàn)，其中第1，4次出現(xiàn)和第2，3，5次出現(xiàn)均是約束出現(xiàn)；第6次是自由出現(xiàn). 變?cè)獂在該公式中5次約束出現(xiàn)，1次自由出現(xiàn). 因此變?cè)獂既是該公式的約束變?cè)?，也是自由變?cè)? 3. 設(shè)a,b,c分別為岳飛，文天祥和秦檜，"xF(x)ÛF(a)ÙF(b)ÙF(c)Û04.(1)0；(2)"x$y(P(y,x)

50、9;$yP(y,a)Ù$yP(y,b)Û(P(a,a)ÚP(b,a)Ù(P(a,b)Ú P(b,b)Û1Ù0Û0(3) $x$y(P(x,y)Û$yP(a,y)Ú$xP(b,y)=P(a,a)ÚP(a,b)ÚP(b,a)ÚP(b.b)Û15. 設(shè)I為任意一個(gè)解釋，D為個(gè)體域. 為假，則"xF(x)®$xF(x)為真. "xF(x)為真，即"x, F(x)為真, 顯然$x0ÎD, F(x0)為真，即$xF(x

51、)為真則"xF(x)®$xF(x)為真. 故在任何解釋I下"xF(x)®$xF(x)為真. "xF(x)®$xF(x)是永真式. 6. 前提：結(jié)論：證明：(1) 否定結(jié)論引入 (2) T(1)E (3) (2)ES (4) A(c)ÙØB(c) T(3) E (5) A(c) (4)化簡(jiǎn) (6) ØB(c)ÙA(c) T(4) .E            (7) ØB(c) (

52、6)化簡(jiǎn) (8) P (9) "x(ØA(x)ÚB(x) (8)化簡(jiǎn) (10) ØA(c)ÚB(c) T(9) US (11) ØA(c) T(10),(7)I10 (12) T(11),(5)合取可見，推理成立。第3章 集合論 本章重點(diǎn)：集合概念，集合的運(yùn)算，集合恒等式的證明，笛卡兒積.  一、重點(diǎn)內(nèi)容1. 集合的概念h集合與元素，具有確定的，可以區(qū)分的若干事物的全體稱為集合，其中的事物叫元素.集合A中元素的個(gè)數(shù)為集合的元數(shù)½A½. h集合的表示方法：列舉法和描述法. 列舉集合的元素，元素不能重復(fù)出現(xiàn)，

53、集合中的元素?zé)o順序之分. 集合與其元素之間存在屬于“Δ或不屬于“Ï”關(guān)系.2. 集合的關(guān)系：包含，子集，集合相等. h包含(子集)，若，則B包含A(或A包含于B)，稱A是B的子集，記，又A¹B，則A是B的真子集，記AÌB.h集合相等，若AÍB，BÍA，則AB. 注意：元素與集合,集合與子集，子集與冪集，Î與Ì(Í)，空集Æ與所有集合等的關(guān)系.3. 特殊集合：全集、空集和冪集. h全集合E，在一個(gè)具體問題中，所涉及的集合都是某個(gè)集合的子集，該集合為全集. h空集Æ，不含任何元素的集合為

54、空集. 空集是惟一的，它是任何集合的子集. h集合A的冪集P(A)，有集合A的所有子集構(gòu)成的集合P(A)=. 若½A½n, 則½P(A)½=2n. 4. 集合的運(yùn)算h集合A和B的并AÈB，由集合A和B的所有元素組成的集合.h集合A和B的交AÇB，由集合A和B的公共元素組成的集合.h集合A的補(bǔ)集A，屬于E但不屬于集合A的元素組成的集合，A. 補(bǔ)集總相對(duì)于一個(gè)全集. h集合A與B的差集AB，由屬于A，而不屬于B的所有元素組成的集合.h集合A與B的對(duì)稱差A(yù)ÅB，AÅB(AB)È(BA)或AÅB）A&#

55、200;B（AÇB）應(yīng)該很好地掌握10條運(yùn)算律(運(yùn)算的性質(zhì))(教材P7172)，即交換律、結(jié)合律、分配律、冪等律、同一律、零律、補(bǔ)余律、吸收律、摩根律和雙補(bǔ)律等. 5. 恒等式證明集合運(yùn)算部分有三個(gè)方面的問題：其一是進(jìn)行集合的運(yùn)算；其二是集合運(yùn)算式的化簡(jiǎn)；其三是集合恒等式的推理證明. 集合恒等式的證明方法通常有二：(1)要證明AB，只需要證明AÍB，又AÊB；(2)通過運(yùn)算律進(jìn)行等式推導(dǎo). 6. 有序?qū)εc笛卡兒積h有序?qū)?，就是有順序的?shù)組，如<x,y>，x,y 的位置是確定的，不能隨意放置.注意：有序?qū)?lt;a，b>¹<b,a&

56、gt;，以a,b為元素的集合a,b=b,a；有序?qū)?a,a)有意義，而集合a,a是單元素集合，應(yīng)記作a. h笛卡兒積，把集合A，B合成集合A×B，規(guī)定A×B<x,y>½xÎAÙyÎB由于有序?qū)?lt;x,y>中x,y的位置是確定的，因此A×B的記法也是確定的，不能寫成B×A. 笛卡兒積也可以多個(gè)集合合成，A1×A2××An. 笛卡兒積的運(yùn)算性質(zhì). 一般不能交換.二、實(shí)例例3.1 已知S2,a,3,4,R=a,3,4,1,指出下列命題的真值. (1) aÎS;

57、 (2) aÎR;(3) a,4,3ÍS; (4) a,1,3,4ÍR;(5) R=S; (6) aÍS(7) aÍR (8) ÆÌR(9) ÆÍaÍR (10) ÆÍS(11) ÆÎR (12) ÆÍ3,4解集合S有四個(gè)元素：2，a，3，4，而元素3又是集合. 集合R類似.(1) a，這是單元素的集合，a不是集合S的元素. 故命題“aÎS”的真值為0. (2) a是R的元素，故命題“aÎR”的真值為1.(3) a,

58、4,3都是S的元素,以此為元素構(gòu)成S的子集. 故命題“a,4,3ÍS”的真值為1.(4) a,1,3,4都是R的元素，構(gòu)成R的子集，故命題“a,1,3,4ÍR”的真值為1.(6), (8)，(9)和(12)題號(hào)的命題真值為1；而(5),(7),(10)題號(hào)命題真值為0。例3.2 設(shè)A=,Î,Ï,Ì, É選擇適當(dāng)?shù)姆?hào)填在各小題的橫線上. (1) (1,2,3,4) N; (2) (3) (4) (5) (6) 正方形 菱形 四邊形 (7) (1,2,3) 1,2,3,(1,2,3)解 (1) Ì (2) Ï, &#

59、201; (3) Ì , =(4) Ì (5) Î或Ì (6) ÌÌ (7) Î例3.3 寫出下列集合的子集：(1) A=a，b，c； (2) B=Æ； (3) C=Æ解 (1)因?yàn)?#198;是任何集合的子集，所以Æ是集合A的子集；由A的任何一個(gè)元素構(gòu)成的集合，都是A的子集，所以a，b，c是A的子集；由A的任何兩個(gè)元素構(gòu)成的集合，也是A的子集，有a，b，b,c，a, c；同理，A的三個(gè)元素構(gòu)成的集合，也是A的子集，于是集合A的所有子集為：Æ，a，b，c，a，b，b,c，a, c，a，

60、b，c=A(2) 同(1)，B的子集有：Æ，Æ. (3) 因?yàn)?#198;是任何集合的子集，故Æ也是C的子集. 因?yàn)镃中沒有元素，因此C就沒有其它子集，所以C的子集只有：Æ說明：(1) 在第1小題中，以集合A的8個(gè)子集為元素的集合，就是集合A的冪集，即P(A)= Æ，a，b，c，a，b，b,c，a, c，a，b，c集合B的冪集為；P(B)=Æ,Æ集合C的冪集：P(C)=Æ一般地，如果集合A，有那么P(A)有2n個(gè)元素(2) 根據(jù)真子集的定義，對(duì)于任何集合A，除了集合A本身不是A的真子集外，其它子集均是A的真子集.

61、于是本例集合A有7個(gè)真子集：Æ，a，b，c，a，b，b,c，a, c集合B只有1個(gè)真子集：Æ集合C沒有真子集. 例設(shè)集合A1,2,3,4,B=2,3,5,求. 解例3.5 試證A(BC)(AB)È(AÇC)證明方法1 對(duì)任意x，同理，有所以，A(BC)(AB)È(AÇC)說明：事實(shí)上，方法1的證明，完全是等值過程，可以寫作方法2 進(jìn)行恒等推導(dǎo). A(BC) =(AB)È(AÇC)例3.6 化簡(jiǎn)解例3.7 設(shè)集合 A=a,b,B=1,2,3,C=d,求A×B×C，B×A. 解先計(jì)算A&#

62、215;B<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>A×B×C<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>×d<<a,1>,d>,<<a,2>,d>,<<a,3>,d>,<<b,1>,d>,<<b,2>,d>,<<b,3>,d>

63、 B×A<1,a>,<2,a>,<3,a>,<1,b>,<2,b>,<3,b>例3.8 設(shè)集合A1,2,求A×P(A). 解 P(A)=Æ,1,2,1,2A×P(A)1,2×Æ,1,2,1,2=<1,Æ>,<2,Æ>,<1,1>,<2,1>,<1,2>,<2,2>,<1,1,2>,<2,1,2>例3.9 單項(xiàng)選擇題1. 若集合Aa,b,c,Æ

64、;為空集合，則下列表示正確的是( )(A) aÎA(B)aÌA(C) aÌA(D) ÆÎA答案：(B)解答：由集合A的元素構(gòu)成的集合是A的子集，a是A的子集，故選擇(B)正確. 2. 對(duì)任意集合S，SÈÆS，滿足( )(A) 冪等律 (B) 零一律 (C) 同一律 (D) 互補(bǔ)律答案：C解答：見集合的運(yùn)算性質(zhì)，AÈÆA和EÇAA稱為同一律. 3. 設(shè)S1Æ，S2Æ, S3P(Æ), S4P(Æ)，以下命題為假的是( )(A) S2ÎS4 (B) S1 Í S3， (C) S4 Í S2 (D) S4Î S3答案