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

1、,,高等學(xué)校21世紀(jì)教材,電子教案,離散數(shù)學(xué),人民郵電出版社,第一章命題邏輯,命題邏輯，也稱命題演算，記為Ls。它與謂詞邏輯構(gòu)成數(shù)理邏輯的基礎(chǔ)，而命題邏輯又是謂詞邏輯的基礎(chǔ)。數(shù)理邏輯是用數(shù)學(xué)方法即通過引入表意符號研究推理的學(xué)問。因此，數(shù)理邏輯又名為符號邏輯。命題邏輯是研究由命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系。,退出,1.1 命題與聯(lián)結(jié)詞1.2 命題變元和合式公式1.3 公式分類與等價公式1.4 對偶式與

2、蘊(yùn)涵式1.5 聯(lián)結(jié)詞的擴(kuò)充與功能完全組1.6 公式標(biāo)準(zhǔn)型——范式1.7 公式的主范式1.8 命題邏輯的推理理論,1.1 命題與聯(lián)結(jié)詞,１. 命題的概念所謂命題，是指具有非真必假的陳述句。而疑問句、祈使句和感嘆句等因都不能判斷其真假，故都不是命題。命題僅有兩種可能的真值—真和假，且二者只能居其一。真用1或T表示，假用0或F表示。由于命題只有兩種真值，所以稱這種邏輯為二值邏輯。命題的真值是具有客觀性質(zhì)的，而不是由人的

3、主觀決定的。,如果一陳述句再也不能分解成更為簡單的語句，由它構(gòu)成的命題稱為原子命題。原子命題是命題邏輯的基本單位。命題分為兩類，第一類是原子命題，原子命題用大寫英文字母P，Q，R…及其帶下標(biāo)的Pi，Qi，Ri，…表示。第二類是復(fù)合命題，它由原子命題、命題聯(lián)結(jié)詞和圓括號組成。,２. 命題聯(lián)結(jié)詞定義1.1.1設(shè)P表示一個命題，由命題聯(lián)結(jié)詞l和命題P連接成lP，稱lP為P的否定式復(fù)合命題， lP讀“非P”。稱l為否定聯(lián)結(jié)詞。lP

4、是真，當(dāng)且僅當(dāng)P為假；lP是假，當(dāng)且僅當(dāng)P為真。否定聯(lián)結(jié)詞“l(fā)”的定義可由表1.1.1表示之。,由于否定”修改了命題，它是對單個命題進(jìn)行操作，稱它為一元聯(lián)結(jié)詞。,定義1.1.2設(shè)P和Q為兩個命題，由命題聯(lián)結(jié)詞∧將P和Q連接成P∧Q，稱P∧Q為命題P和Q的合取式復(fù)合命題，P∧Q讀做“P與Q”，或“P且Q”。稱∧為合取聯(lián)結(jié)詞。當(dāng)且僅當(dāng)P和Q的真值同為真，命題P∧Q的真值才為真；否則，P∧Q的真值為假。合取聯(lián)結(jié)詞∧的定義由表1.1.

5、2表示之。,定義1.1.3設(shè)P和Q為兩個命題，由命題聯(lián)結(jié)詞∨把P和Q連接成P∨Q，稱P∨Q為命題P和Q的析取式復(fù)合命題，P∨Q讀做“P或Q”。稱∨為析取聯(lián)結(jié)詞。當(dāng)且僅當(dāng)P和Q的真值同為假，P∨Q的真值為假；否則，P∨Q的真值為真。析取聯(lián)結(jié)詞∨的定義由表1.1.3表示之。,由定義可知，析取聯(lián)結(jié)詞表示“可兼和”，“不可兼和”另有別的聯(lián)結(jié)詞定義之。與合取聯(lián)結(jié)詞一樣，使用析取聯(lián)結(jié)詞時，也不要求兩命題間一定有任何關(guān)系，有關(guān)例子就

6、不再給出了。,定義1.1.4設(shè)P和Q為兩個命題，由命題聯(lián)結(jié)詞→把P和Q連接成P→Q，稱P→Q為命題P和Q的條件式復(fù)合命題，簡稱條件命題。P→Q讀做“P條件Q”或者“若P則Q”。稱→為條件聯(lián)結(jié)詞。當(dāng)P的真值為真而Q的真值為假時，命題P→Q的真值為假；否則，P→Q的真值為真。條件聯(lián)結(jié)詞→的定義由表1.1.4表示之。,在條件命題P→Q中，命題P稱為P→Q的前件或前提，命題Q稱為P→Q的后件或結(jié)論。條件命題P→Q有多種方式陳述：

7、“如果P，那么Q”；“P僅當(dāng)Q”；“Q每當(dāng)P”；“P是Q的充分條件”；“Q是P的必要條件”等。,在日常生活中，用條件式表示前提和結(jié)論之間的因果或?qū)嵸|(zhì)關(guān)系，如例1.1.4中的①，這種條件式稱為形式條件命題。然而在命題邏輯中，一個條件式的前提并不要求與結(jié)論有任何關(guān)系，這種條件式稱為實(shí)質(zhì)條件命題。采用實(shí)質(zhì)條件式作定義，不單是出于“善意推斷”，主要是因?yàn)榍疤崤c結(jié)論間有無因果和實(shí)質(zhì)關(guān)系難以區(qū)分，而且實(shí)質(zhì)條件式已包含了形式條件式，更便于應(yīng)用。

8、,定義1.1.5令P、Q是兩個命題，由命題聯(lián)結(jié)詞?把P和Q連接成P ? Q，稱P ? Q為命題P和Q的雙條件式復(fù)合命題，簡稱雙條件命題，P ? Q讀做“P當(dāng)且僅當(dāng)Q”，或“P等價Q”。稱?為雙條件聯(lián)結(jié)詞。當(dāng)P和Q的真值相同時，P ? Q的真值為真；否則，P ? Q的真值為假。雙條件聯(lián)結(jié)詞?的定義由表1.1.5表示之。,在本節(jié)結(jié)束時，應(yīng)強(qiáng)調(diào)指出的是：復(fù)合命題的真值只取決于各原子命題的真值，而與它們的內(nèi)容、含義無關(guān)，與原子命題之間

9、是否有關(guān)系無關(guān)。理解和掌握這一點(diǎn)是至關(guān)重要的，請讀者認(rèn)真去領(lǐng)會。,1.2 命題變元和合式公式,１. 命題變元在命題邏輯中，命題又有命題常元和命題變元之分。一個確定的具體的命題，稱為命題常元；一個不確定的泛指的任意命題，稱為命題變元。顯然，命題變元不是命題，只有用一個特定的命題取代才能確定它的真值：真或假。這時也說對該命題變元指派真值。,命題常元和命題變元均可用字母P等表示。由于在命題邏輯中并不關(guān)心具體命題的涵義，只關(guān)心其真值，因

10、此，可以形式地定義它們?nèi)缦拢邯?定義1.2.1以真或1、假或0為其變域的變元，稱為命題變元；真或1、假或0稱為命題常元。,2.合式公式通常把含有命題變元的斷言稱為命題公式。但這沒能指出命題公式的結(jié)構(gòu)，因?yàn)椴皇撬杏擅}變元、聯(lián)結(jié)詞和括號所組成的字符串都能成為命題公式。為此常使用歸納定義命題公式，以便構(gòu)成的公式有規(guī)則可循。由這種定義產(chǎn)生的公式稱為合式公式。定義1.2.2單個命題變元和命題常元稱為原子命題公式，簡稱原

11、子公式。,定義1.2.3合式公式是由下列規(guī)則生成的公式：①單個原子公式是合式公式。②若A是一個合式公式，則(lA)也是一個合式公式。③若A、B是合式公式，則(A∧B)、(A∨B)、(A→B)和(A ? B)都是合式公式。④只有有限次使用①、②和③生成的公式才是合式公式。,當(dāng)合式公式比較復(fù)雜時，常常使用很多圓括號，為了減少圓括號的使用量，可作以下約定：①規(guī)定聯(lián)結(jié)詞的優(yōu)先級由高到低的次序?yàn)椋邯、∧、∨、→、 ? 

12、②相同的聯(lián)結(jié)詞按從左至右次序計算時，圓括號可省略。③最外層的圓括號可以省略。為了方便計，合式公式也簡稱公式。,３.公式真值表定義1.2.4對于公式中命題變元的每一種可能的真值指派，以及由它們確定出的公式真值所列成的表，稱為該公式的真值表。定義1.2.5如果B是公式A中的一部分，且B為公式，則稱B是公式A的子公式。,用歸納法不難證明，對于含有n個命題變元的公式，有2n個真值指派，即在該公式的真值表中有2n行。

13、為方便構(gòu)造真值表，特約定如下：① 命題變元按字典序排列。② 對每個指派，以二進(jìn)制數(shù)從小到大或從大到小順序列出。③ 若公式較復(fù)雜，可先列出各子公式的真值(若有括號，則應(yīng)從里層向外層展開)，最后列出所求公式的真值。,4.命題的符號化把一個用文字?jǐn)⑹龅拿}相應(yīng)地寫成由命題標(biāo)識符、聯(lián)結(jié)詞和圓括號表示的合式公式，稱為命題的符號化。符號化應(yīng)該注意下列事項:① 確定給定句子是否為命題。② 句子中連詞是否為命題聯(lián)結(jié)詞。

14、③ 要正確地表示原子命題和適當(dāng)選擇命題聯(lián)結(jié)詞。,命題符號化是很重要的，一定要掌握好，在命題推理中常常最先遇到的就是符號化一個問題，解決不好，等于說推理的首要前提沒有了。,1.3 公式分類與等價公式,１. 公式分類定義1.3.1設(shè) A 為任意公式，則① 對應(yīng)每一個指派，公式 A 均相應(yīng)確定真值為真，稱 A 為重言式，或永真式。② 對應(yīng)每一個指派，公式 A 均相應(yīng)確定真值為假，稱 A 為矛盾式，或永假式。③ 至少存

15、在一個指派，公式 A 相應(yīng)確定真值為真，稱 A 為可滿足式。,由定義可知，重言式必是可滿足式，反之一般不真。重點(diǎn)將研究重言式，它最有用，因?yàn)樗幸韵绿攸c(diǎn)：①重言式的否定是矛盾式，矛盾式的否定是重言式，這樣只研究其一就可以了。②兩重言式的合取式、析取式、條件式和雙條件式等都仍是重言式。于是，由簡單的重言式可構(gòu)造出復(fù)雜的重言式。③由重言式使用公認(rèn)的規(guī)則可以產(chǎn)生許多有用等價式和蘊(yùn)涵式。,判定給定公式是否為永真式、永假式或可

16、滿足式的問題，稱為給定公式的判定問題。在Ls中，由于任何一個命題公式的指派數(shù)目總是有限的，所以Ls的判定問題是可解的。其判定方法有真值表法和公式推演法。,２.等價公式定義1.3.2設(shè)A和B是兩個命題公式，如果A、B在其任意指派下，其真值都是相同的，則稱A和B是等價的，或邏輯相等，記作A?B，讀作A等價B，稱A?B為等價式。顯然，若公式A和B的真值表是相同的，則A和B等價。因此，驗(yàn)證兩公式是否等價，只需做出它們的真值表即

17、可。,在這里，請讀者注意?和?的區(qū)別與聯(lián)系。區(qū)別：?是邏輯聯(lián)結(jié)詞，屬于目標(biāo)語言中的符號，它出現(xiàn)在命題公式中；?不是邏輯聯(lián)結(jié)詞，屬于元語言中的符號，表示兩個命題公式的一種關(guān)系，不屬于這兩個公式的任何一個公式中的符號。聯(lián)系：可用下面定理表明之。,定理1.3.1A ? B當(dāng)且僅當(dāng)A?B是永真式。 有時也稱A ? B是永真雙條件式。等價式有下列性質(zhì)：① 自反性，即對任意公式A，有A ? A。② 對稱性，即對任意公

18、式A和B，若A ? B，則B ? A。③ 傳遞性，即對任意公式A、B和C，若A ? B、B ? C，則A ? C。,３.基本等價式——命題定律在判定公式間是否等價，有一些簡單而又經(jīng)常使用的等價式，稱為基本等價式或稱命題定律。牢固地記住它并能熟練運(yùn)用，是學(xué)好數(shù)理邏輯的關(guān)鍵之一，讀者應(yīng)該注意到這一點(diǎn)。現(xiàn)將這些命題定律列出如下：(1)雙否定：??A?A。(2)交換律：A∧B?B∧A，A∨B?B∨A，A?B?B?A。,(3) 結(jié)合律：

19、(A∧B)∧C?A∧(B∧C)，(A∨B)∨C?A∨(B∨C)，(A?B)?C?A?(B?C)。(4) 分配律：A∧(B∨C)?(A∧B)∨(A∧C)，A∨(B∧C)?(A∨B)∧(A∨C)。(5) 德·摩根律：?(A∧B)??A∨?B，?(A∨B)??A∧?B。(6) 等冪律：A∧A?A，A∨A?A。,(7) 同一律：A∧T?A，A∨F?A。(8) 零 律：A∧F?F，A∨T?T。(9) 吸收律：A∧(A∨B)?

20、A，A∨(A∧B)?A。(10) 互補(bǔ)律：A∧?A?F，(矛盾律)A∨?A?T。(排中律)(11) 條件式轉(zhuǎn)化律：A→B??A∨B，A→B??B→?A。,(12) 雙條件式轉(zhuǎn)化律：A?B?(A→B)∧(B→A)?(A∧B)∨(?A∧?B)?A?B??(A?B)(13) 輸出律：(A∧B)→C?A→(B→C)。(14) 歸謬律：(A→B)∧(A→?B)??A。上面這些定律，即是通常所說的布爾代數(shù)或邏輯代數(shù)的重要組成部分，它們

21、的正確性利用真值表是不難給出證明的。,４.代入規(guī)則和替換規(guī)則在定義合成公式時，已看到了邏輯聯(lián)結(jié)詞能夠從已知公式形成新的公式，從這個意義上可把邏輯聯(lián)結(jié)詞看成運(yùn)算。除邏輯聯(lián)結(jié)詞外，還要介紹“代入”和“替換”，它們也有從已知公式得到新的公式的作用，因此有人也將它們看成運(yùn)算，這不無道理，而且在今后討論中，它的作用也是不容忽視的。,(1)代入規(guī)則定理1.3.2 在一個永真式A中，任何一個原子命題變元R出現(xiàn)的每一處， 用另一個公式代入，所得公

22、式B仍是永真式。本定理稱為代入規(guī)則。(2)替換規(guī)則定理1.3.3 設(shè)A1是合式公式A的子公式，若A1?B1，并且將A中的A1用B1 替換得到公式B，則A?B。稱該定理為替換規(guī)則。滿足定理1.3.3條件的替換，稱為等價替換。,代入和替換有兩點(diǎn)區(qū)別：① 代入是對原子命題變元而言的，而替換可對命題公式實(shí)行。② 代入必須是處處代入，替換則可部分替換，亦可全部替換。,1.4 對偶式與蘊(yùn)涵式,１.對偶式在上節(jié)介紹的命題定律中，多

23、數(shù)是成對出現(xiàn)的，這些成對出現(xiàn)的定律就是對偶性質(zhì)的反映，即對偶式。利用對偶式的命題定律，可以擴(kuò)大等價式的個數(shù)，也可減少證明的次數(shù)。,定義1.4.1 在給定的僅使用聯(lián)結(jié)詞?、∧和∨的命題公式A中，若把∧和∨互換，F(xiàn)和T互換而得到一個命題公式A*，則稱A*為A的對偶式。顯然，A也是A*的對偶式。可見A與A*互為對偶式。,定理1.4.1(對偶定理) 設(shè)A和A*互為對偶式，P1，P2，…，Pn是出現(xiàn)A和A* 中的原子命題變元，則① ?A(

24、P1，P2，…，Pn)?A*(?P1，?P2，…，?Pn)② A(?P1，?P2，…，?Pn)??A*(P1，P2，…，Pn)①表明，公式A的否定等價于其命題變元否定的對偶式；②表明，命題變元否定的公式等價于對偶式之否定。,定理1.4.2 設(shè)A和B為兩個命題公式，若A?B則A*?B*。有了等價式、代入規(guī)則、替換規(guī)則和對偶定理，便可以得到更多的永真式，證明更多的等價式，使化簡命題公式更為方便。,２.蘊(yùn)涵式定義1.4.2 設(shè)A和

25、B是兩個命題公式，若A→B是永真式，則稱A蘊(yùn)涵B，記作A?B，稱A?B為蘊(yùn)涵式或永真條件式。符號→和?的區(qū)別與聯(lián)系類似于?和?的關(guān)系。區(qū)別：→是邏輯聯(lián)結(jié)詞，屬于對象語言中的符號，是公式中的符號；而?不是聯(lián)結(jié)詞，屬于元語言中的符號，表示兩個公式之間的關(guān)系，不是兩公式中符號。聯(lián)系：A?B成立，其充要條件A→B是永真式。,蘊(yùn)涵式有下列性質(zhì)：① 自反性，即對任意公式A，有A?A。② 傳遞性，即對任意公式A、B和C，若A?B，B?C，則A?

26、C。③ 對任意公式A、B和C，若A?B，A?C，則A?(B∧C)。④ 對任意公式A、B和C，若A?C，B?C，則A∨B?C。,這些性質(zhì)的正確性，請讀者自己驗(yàn)證。下面給出等價式與蘊(yùn)涵式之間的關(guān)系。定理1.4.3 設(shè)A和B是兩命題公式，A?B的充要條件是A?B且B?A。,３.蘊(yùn)涵式證明方法除真值表外，還有兩種方法：① 前件真導(dǎo)后件真方法設(shè)公式的前件為真，若能推導(dǎo)出后件也為真，則條件式是永真式，故蘊(yùn)涵式成立。因?yàn)橛CA?B，

27、即證A?B是永真式。對于A?B，除在A取真和B取假時，A?B為假外，余下A?B皆為真。所以，若A?B的前件A為真，由此可推出B亦為真，則A?B是永真式，即A?B。,② 后件假導(dǎo)前件假方法設(shè)條件式后件為假，若能推導(dǎo)出前件也為假，則條件式是永真式，即蘊(yùn)涵式成立。因?yàn)槿鬉→B的后件B取假，由此可推出A取假，即推證了：?B??A。又因A→B??B→?A，故A?B成立。,1.5 聯(lián)結(jié)詞的擴(kuò)充與功能完全組,１. 聯(lián)結(jié)詞的擴(kuò)充定義1.5.1

28、 設(shè)P和Q是任兩個原子命題，①由合取非聯(lián)結(jié)詞↑和P，Q連接成P↑Q，稱它為P和Q的合取非式復(fù)合命題，讀作“P合取非Q”。P↑Q的真值由命題P和Q的真值確定：當(dāng)且僅當(dāng)P和 Q均為Ｔ時，P↑Q為Ｆ，否則P↑Q為Ｔ?！昂先》恰庇殖７Q為“與非”。,②由析取非聯(lián)結(jié)詞↓和P，Q連接成P↓Q，稱它為P和Q的析取非式復(fù)合命題，讀作“P析取非Q”。P↓Q的真值由P和Q的真值確定：當(dāng)且僅當(dāng)P和Q均為Ｆ時，P↓Q為Ｔ，否則P↓Q為Ｆ。“析取非”又常稱為“

29、或非”。③由條件非聯(lián)結(jié)詞?和P，Q連接成P?Q，稱它為P和Q的條件非式復(fù)合命題，讀作“P條件非Q”。P?Q的真值由P和Q的真值確定：當(dāng)且僅當(dāng)P為Ｔ而Q為Ｆ時，P?Q為Ｔ；否則P?Q為Ｆ。,④由雙條件非聯(lián)結(jié)詞?把P，Q連接成P?Q，稱它為P和Q的雙條件非式復(fù)合命題，讀作“P雙條件非Q”。P?Q的真值由P和 Q的真值確定：當(dāng)且僅當(dāng)P和Q的真值不同時，P?Q為Ｔ，否則P?Q為Ｆ?！半p條件非”又常稱為“異或”，也常用符號?表示之。上面4個聯(lián)

30、結(jié)詞構(gòu)成的復(fù)合命題，其真值表如下：,由表可知，①P?Q??(P?Q)②P?Q??(P?Q)③P?Q??(P?Q)④P?Q??(P?Q),２.與非、或非和異或的性質(zhì)與非、或非以及異或在計算機(jī)科學(xué)中是經(jīng)常使用的3個聯(lián)結(jié)詞，因此，掌握它們的性質(zhì)是十分必要的。令P、Q和R是原子命題變元。① 與非的性質(zhì)(a)P↑Q?Q↑P(b) P↑P??P(c) (P↑Q)↑(P↑Q)?P∧Q(d) (

31、P↑P)↑(Q↑Q)?P∨Q,② 或非的性質(zhì)(a) P↓Q?Q↓P(b) P↓P??P(c)(P↓Q)↓(P↓Q)?P∨Q(d) (P↓P)↓(Q↓Q)?P∧Q從上述的性質(zhì)可知，聯(lián)結(jié)詞?、?和?可分別用聯(lián)結(jié)詞?或者?取代，讀者可以自行驗(yàn)證，?和?都不滿足結(jié)合律。,③ 異或的性質(zhì)(a)P?Q?Q?P(b) P?(Q?R)?(P?Q)?R(c) P∧(Q?R)?(P∧Q)?(P∧R)(d) P?P?F

32、，F(xiàn)?P?P，T?P??P(e) 若P?Q?R，則Q?R?P，P?P?Q，且P?Q?R?F。,以上所有性質(zhì)，用真值表或命題定律都是不難證明的。至此，已有了9個聯(lián)結(jié)詞，是否還需要擴(kuò)充呢？事實(shí)上，兩上命題變無P和Q，與9個聯(lián)結(jié)詞一共可構(gòu)成 類命題公式，如下表示之：,從列表可知，除命題常元F，T及命題變元本身外，命題聯(lián)結(jié)詞一共有9個就夠了。為了方便，可規(guī)定其優(yōu)先級，由高到低次序?yàn)?，?，?，?，?等。,３.聯(lián)結(jié)詞功能完全組已知有9

33、個聯(lián)結(jié)詞就夠用了，能不能少呢？若能少，表明有些聯(lián)結(jié)詞的邏輯功能可由其他聯(lián)結(jié)詞替代。事實(shí)上，也確實(shí)如此，因?yàn)橛邢铝械葍r式：P?Q??(P?Q)P?Q??(P?Q)P?Q??(P?Q)P?Q??(P?Q)可見，擴(kuò)充的4個聯(lián)結(jié)詞?，?，?和?能由原有5個聯(lián)結(jié)詞分別替代之。,又由命題定律：P?Q?(?P?Q)?(?Q?P)P?Q??P?QP?Q??(?P??Q)P?Q??(?P??Q)可知，原有5個聯(lián)結(jié)詞?，?，?，?和?又

34、能由聯(lián)結(jié)詞組{?，?}或{?，?}取代。那么，究竟最少用幾個聯(lián)結(jié)詞？就是說，用最少的幾個聯(lián)結(jié)詞就能等價表示所有的命題公式。或者說，用最少的幾個聯(lián)結(jié)詞就能替代所有聯(lián)結(jié)詞的功能。這便是所要定義的聯(lián)結(jié)詞功能完全組。,定義1.5.2 稱G為聯(lián)結(jié)詞功能完全組，如果G滿足下列兩條件：①由G中聯(lián)結(jié)詞構(gòu)成的公式能等價表示任意命題公式；②G 中的任一聯(lián)結(jié)詞不能用其余下聯(lián)結(jié)詞等價表示?？梢宰C明，{?，?}，{?，?}，{?，?}，{?}，{?}都是聯(lián)結(jié)

35、詞功能完全組；而{?，?}，{?}，{?}，{?}，{?，?}都不是聯(lián)結(jié)詞功能完全組，但為了表示方便，仍經(jīng)常使用聯(lián)結(jié)詞組{?，?，?}。,1.6 公式標(biāo)準(zhǔn)型——范式,１.簡單合取式與簡單析取式定義1.6.1 在一公式中，僅由命題變元及其否定構(gòu)成的合取式， 稱該公式為簡單合取式，其中每個命題變元或其否定，稱為合取項。定義1.6.2 在一公式中，僅由命題變元及其否定構(gòu)成的析取式， 稱該公式為簡單析取式，其中每個命題變元或其否定，稱

36、為析取項。,例如，公式P，?Q，P?Q和?P?Q?P等都是簡單合取式，而P，Q和?P為相應(yīng)的簡單合取式的合取項；公式P，?Q，P?Q，?P?Q?P等都是簡單析取式，而P，Q和?P為相應(yīng)簡單析取式的析取項。注意，一個命題變元或其否定既可以是簡單合取式，也可是簡單析取式，如例中P，?Q等。,定理1.6.1 簡單合取式為永假式的充要條件是：它同時含有某個命題變元及其否定。定理1.6.2 簡單析取式為永真式的充要條件是：它同時含有某個命

37、題變元及其否定。,２.析取范式與合取范式定義1.6.3 一個命題公式A稱為析取范式，當(dāng)且僅當(dāng)A可表為簡單合取式的析取，即A?Ai；其中Ai為簡單合取式，i=1，2，…，n。定義1.6.4 一個命題公式A稱為合取范式，當(dāng)且僅當(dāng)A可表為簡單析取式的合取，即A?Ai；其中Ai為簡單析取式，1≤i≤n。,定理1.6.3 對于任何一命題公式，都存在與其等價的析取范式和合取范式。求范式算法：① 使用命題定律，消去公式中除?、?和?以外公

38、式中出現(xiàn)的所有聯(lián)結(jié)詞；② 使用?(?P)?P和德·摩根律，將公式中出現(xiàn)的聯(lián)結(jié)詞?都移到命題變元之前；③ 利用結(jié)合律、分配律等將公式化成析取范式或合取范式。,３.范式的應(yīng)用利用析取范式和合取范式可對公式進(jìn)行判定。定理1.6.4 公式A為永假式的充要條件是A 的析取范式中每個簡單合取式至少包含一個命題變元及其否定。定理1.6.5 公式A為永真式的充要條件是A 的合取范式中每個簡單析取式至少包含一個命題變元及其否定。,

39、４.范式不唯一性,1.7 公式的主范式,范式基本解決了公式的判定問題。但由于范式不唯一性，對識別公式間是否等價帶來一定困難，而公式的主范式解決了這個問題。下面將分別討論主范式中的主析取范式和主合取范式。,１.主析取范式(1) 小項的概念和性質(zhì)定義1.7.1 在含有n個命題變元的簡單合取式中， 若每個命題變元與其否定不同時存在，而二者之一出現(xiàn)一次且僅出現(xiàn)一次，則稱該簡單合取式為小項，或布爾積。,例如，兩個命題變元P和Q，其構(gòu)成的小

40、項有P?Q，P??Q，?P?Q和?P??Q；而三個命題變元P、Q和R，其構(gòu)成的小項有P?Q?R，P?Q??R，P??Q?R，P??Q??R，?P?Q?R ，?P?Q??R，?P??Q?R，?P??Q??R?？梢宰C明，n個命題變元共形成2n個小項。,如果將命題變元按字典序排列，并且把命題變元與1對應(yīng)，命題變元的否定與0對應(yīng)，則可對2n個小項依二進(jìn)制數(shù)編碼，記為mi，其下標(biāo)i是由二進(jìn)制數(shù)轉(zhuǎn)化的十進(jìn)制數(shù)。用這種編碼所求得2n個小項的真值表，

41、可明顯地反映出小項的性質(zhì)。表1.7.1和表1.7.2分別給出了2個命題變元P和Q、3個命題變元P、Q和R的小項真值表。,從表1.7.1，表1.7.2可看出，小項有如下性質(zhì)：(a)沒有兩個小項是等價的，即是說各小項的真值表都是不同的；(b)任意兩個不同的小項的合取式是永假的：mi∧mj?Ｆ，i≠j。(c)所有小項之析取為永真： mi?Ｔ。(d)每個小項只有一個解釋為真，且其真值1位于主對角線上。,(2) 主析取范式

42、定義與存在定理定義1.7.2 在給定公式的析取范式中，若其簡單合取式都是小項， 則稱該范式為主析取范式。定理1.7.1 任意含n個命題變元的非永假命題公式A 都存在與其等價的主析取范式。,(3) 主析取范式的求法主析取范式求法有兩種：真值表法和公式化歸法。定理1.7.1的證明已給出了用真值表求主析取范式的方法，而公式化歸法給出如下：(a)把給定公式化成析取范式；(b) 刪除析取范式中所有為永假的簡單合取式；,(c)

43、 用等冪律化簡簡單合取式中同一命題變元的重復(fù)出現(xiàn)為一次出現(xiàn)，如P∧P?P。(d) 用同一律補(bǔ)進(jìn)簡單合取式中未出現(xiàn)的所有命題變元，如Q，則P?P∧?Q∨Q)，并用分配律展開之，將相同的簡單合取式的多次出現(xiàn)化為一次出現(xiàn)， 這樣得到了給定公式的主析取范式。,(4) 主析取范式的惟一性定理1.7.2 任意含n個命題變元的非永假命題公式，其主析取范式是惟一的。,２.主合取范式(1) 大項的概念和性質(zhì)定義1.7.3 在n個命題變元的簡

44、單析取式中，若每個命題變元與其否定不同時存在，而二者之一必出現(xiàn)一次且僅出現(xiàn)一次，則稱該簡單析取式為大項，或布爾和。,例如，由兩個命題變元P和Q，構(gòu)成大項有P?Q，P??Q，?P?Q，?P??Q；三個命題變元P，Q和R，構(gòu)成P?Q?R，P?Q??R，P??Q?R，P??Q??R，?P?Q?R，?P?Q??R，?P??Q?R，?P??Q??R。能夠證明，n個命題變元共有2n個大項。,如果將n個命題變元排序，并且把命題變元與０對應(yīng)，命題變元

45、的否定與１對應(yīng)，則可對2n個大項按二進(jìn)制數(shù)編碼，記為Mi，其下標(biāo)i是由二進(jìn)制數(shù)化成的十進(jìn)制數(shù)。用這種編碼所求的2n個大項的真值表，能直接反映出大項的性質(zhì)。表1.7.3給出了2個命題變元P和Ｑ構(gòu)成所有大項的真值表。,,,,類似可給出３個命題變元Ｐ、Ｑ和Ｒ的所有大項的真值表，留給讀者完成。從表1.7.3可看出大項的性質(zhì)：(a)沒有兩個大項是等價的。(b)任何兩個不同大項之析取是永真的，即Mi∨Mj?Ｔ，i≠j。(c) 所有大

46、項之合取為永假，即Mi?Ｆ。(d) 每個大項只有一個解釋為假，且其真值0位于主對角線上。,(2) 主合取范式的定義與其存在定理定義1.7.4 在給定公式的合取范式中，若其所有簡單析取式都是大項， 稱該范式為主合取范式。定理1.7.3 任意含有n個命題變元的非永真命題公式A，都存在與其等價的主合取范式。定理1.7.4 任意含n個命題變元的非永真命題公式A，其主合取范式是唯一的。上述兩定理的證明，類似于定理1.7.1和定理

47、1.7.2。,主合取范式的求法也有兩種，類似于主析取范式的求法。３.主析取范式與主合取范式之間的關(guān)系由于主范式是由小項或大項構(gòu)成，從小項和大項的定義，可知兩者有下列關(guān)系：?mi?Mi ?Mi?mi因此，主析取范式和主合取范式有著“互補(bǔ)”關(guān)系，即是由給定公式的主析取范式可以求出其主命取范式。,設(shè)命題公式A中含有n個命題變元，且A的主析取范式中含有k個小項 ， ，…， ，則?A的主析取范式

48、中必含有2n-k個小項，不妨含為 ， ，…， ，即?A? ∨∨…∨ 。于是A???A??(∨ ∨…∨ )?? ∧? ∧…∧? ? ∧ ∧…∧,由此可知，從A的主析取范式求其主合取范式的步驟為：(a)求出A的主析取范式中設(shè)有包含的小項。(b) 求出與(a

49、)中小項的下標(biāo)相同的大項。(c) 做(b)中大項之合取，即為A的主合取范式。例如，(P?Q)?Q?m1?m3，則(P?Q)?Q?M0?M2。,４.主范式的應(yīng)用利用主范式可以求解判問題或者證明等價式成立。（1）判定問題根據(jù)主范式的定義和定理，也可以判定含n個命題變元的公式，其關(guān)鍵是先求出給定公式的主范式Ａ；其次按下列條件判定之：(a)若A?Ｔ，或A可化為與其等價的、含2n個小項的主析取范式，則A為永真式。,(b)若A?Ｆ，或

50、A可化為與其等價的、含2n個大項的主合取范式，則A為永假式。(c)若A不與Ｔ或者Ｆ等價，且又不含2n個小項或者大項，則A為可滿足的。（2）證明等價式成立由于任一公式的主范式是唯一的，所以將給定的公式求出其主范式，若主范式相同，則給定兩公式是等價的。,1.8 命題邏輯的推理理論,在邏輯學(xué)中，把從前題（又叫公理或假設(shè)）出發(fā)，依據(jù)公認(rèn)的推理規(guī)則，推導(dǎo)出一個結(jié)論，這一過程稱為有效推理或形式證明。所得結(jié)論叫做有效結(jié)論，這里最關(guān)心的不是結(jié)論

51、的真實(shí)性而是推理的有效性。前提的實(shí)際真值不作為確定推理有效性的依據(jù)。但是，如果前提全是真，則有效結(jié)論也應(yīng)該真而絕非假。,在數(shù)理邏輯中，集中注意的是研究和提供用來從前提導(dǎo)出結(jié)論的推理規(guī)則和論證原理，與這些規(guī)則有關(guān)的理論稱為推理理論。提請注意，必須把推理的有效性和結(jié)論的真實(shí)性區(qū)別開。有效的推理不一定產(chǎn)生真實(shí)的結(jié)論，產(chǎn)生真實(shí)結(jié)論的推理過程未必一定是有效的。再說，有效的推理中可能包含假的前提；而無效的推理卻可能包含真的前提。,可見，推理的有效

52、性是一回事，前提與結(jié)論的真實(shí)與否是另一回事。所謂推理有效，指它的結(jié)論是它的前提的合乎邏輯的結(jié)果，也即，如果它的前提都為真，那么所得結(jié)論也必然為真，而并不是要求前提或結(jié)論一定為真或?yàn)榧?。如果推理是有效的話，那么不可能它的前提都為真時而它的結(jié)論為假。,１.推理的基本概念和推理形式推理也稱論證，它是指由已知命題得到新的命題的思維過程，其中已知命題稱為推理的前提或假設(shè)，推得的新命題稱為推理的結(jié)論。在數(shù)理邏輯中，前提H是一個或者n個命題公式H

53、1,H2,···Hn；結(jié)論是一個命題公式C。由前提到結(jié)論的推理形式可表為H1,H2,···,Hn?C，其中符號?表示推出···?？梢?，推理形式是命題公式的一個有限序列，它的最后一個公式是結(jié)論，余下的為前提或假設(shè)。,定義1.8.1 如果存在H1，H2，…，Hn，C的一個指派，使得每個Hi(1≤i≤n)為真而C為假推理形式H1，H2，…，Hn?C是無

54、效的；否則，推理是有效的，此時稱C是H1，H2，…，Hn的有效結(jié)論，或稱C是從前提H1，H2，…，Hn邏輯推出的結(jié)論。定理1.8.1 推理形式H1，H2，…，Hn?C是有效的，當(dāng)且僅當(dāng)命題公式(H1∧H2∧…∧Hn)→C是永真式，亦即(H1∧H2∧…∧Hn)?C。,２.推理規(guī)則在數(shù)理邏輯中，從前提推導(dǎo)出結(jié)論，要依據(jù)事先提供的公認(rèn)的推理規(guī)則，它們是：①Ｐ規(guī)則(也稱前提引入規(guī)則)：在推導(dǎo)過程中，前提可視需要引入使用。②Ｔ規(guī)則(也稱

55、結(jié)論引入規(guī)則)：在推導(dǎo)過程中，前面已導(dǎo)出的有效結(jié)論都可作為后續(xù)推導(dǎo)的前提引入。,此外，在從前提推出的結(jié)論為條件式時，還需要下面規(guī)則：③ＣＰ規(guī)則(也稱條件證明引入規(guī)則)：若推出有效結(jié)論為條件式R→C時，只需將其前件R加入到前提中作為附加前提且再去推出后件C即可。ＣＰ規(guī)則的正確性可由下面定理得到保證：定理1.8.2 若H1，H2，…，Hn，R?C，則H1，H2，…，Hn?R→C。,３.推理定律在推理過程中，除使用推理規(guī)則后，還需要

56、使用許多條推理定律，這些定律可由以前講過的命題定律、蘊(yùn)涵式及運(yùn)用定理1.8.1而得到。下面只給出了由蘊(yùn)涵式得出的推理定律，它們是：(1) P，Q?P(2) P，Q?Q(3) P?P∨Q(4) ?P?P→Q,(5) Q?P→Q(6) ?(P→Q)?P(7) ?(P→Q)??Q(8) P，(P→Q)?Q(9) ?Q，(P→Q)??P(10) ?P，(P∨Q)?Q(11) (P→Q)，(Q→R)?P→R

57、(12) (P?Q)，(Q?R)?P?R(13) (P→Q)，(R→S)，(P∧R)?Q∧S,(14) (P→Q)，(R→S)∧(P∨R)?Q∨S特別當(dāng)Q=S時，有(P→Q)，(R→Q)，(P∧R)?Q(P→Q)，(R→S)，(P∨R)?Q(15)P→Q?(P∨R)→(Q∨R)P→Q?(P∧R)→(Q∧R)此外，每個命題定律也可應(yīng)得出兩個推理定律，這些請讀者補(bǔ)全。由于推理定律是確定有效結(jié)論的不可缺少的重要根據(jù)，因此要牢記

58、并熟練運(yùn)用它們。,４.判斷有效結(jié)論的常用方法判斷有效結(jié)論的常用方法有真值表法，演繹法和間接證法。下面分別討論之。(1)真值表法根據(jù)給定前提H1，H2，…，Hn和結(jié)論C，構(gòu)造條件式(H1∧H2∧…∧Hn)→C的真值表，若它為永真式，則結(jié)論C是有效的。,為了簡便，根據(jù)條件式D：(H1∧H2∧…∧Hn)→C的真值定義，只需列出待證命題公式D的前件和后件的真值表，就可判斷結(jié)論C的有效性。方法有二：(a) 在真值表中，先找出前提H1，H2，

59、…，Hn的真值均為真的行，若相應(yīng)行中結(jié)論C 的真值也都為真，則D為真，即C為有效結(jié)論。(b)在真值表中，先找出結(jié)論C的真值為假的所有行，若這些行中，前提H1，H2，…，Hn的真值都至少有一個為假，則D為真，即C為有效結(jié)論。,（2）演繹法列出待證推理形式中前提和結(jié)論的真值表，原則上可以解決推理的有效性問題。但當(dāng)出現(xiàn)在公式中的命題變元數(shù)目很大時，真值表法又顯得不切實(shí)用，而使用演繹法卻能比較好地解決這個問題。,定義1.8.2 從前提H推出

60、結(jié)論C的一個演繹是構(gòu)造命題公式的一個有限序列：A1，A2，…，An其中，A1是前提H中的某個前提Hi；Ai(i≥2)或者是H中某個前提Hi，或者是某些Aj(j＜i＝的有效結(jié)論，并且An就是C，則稱公式C為該演繹的有效結(jié)論，或者稱從H演繹出C。通過下面例子來說明演繹具體是如何進(jìn)行。,例1.8.3 求證D是前提A，A??B，?B?C和C?D的有效結(jié)論。證明{1} (1) A??B

61、 P{2} (2) ?B?C P{1,2} (3) A?C T,(1)(2)I8{4} (4) A P{1,2,4} (5) C T,(3)(4) I8{6} (6) C?D P

62、{1,2,4,6} (7) D T,(5)(6) I8··· ··· ··· ···第1列 第2列 第3列 第4列,演繹法的具體操作可用4列若干行構(gòu)成的一張表來表示。第1列是花括號序

63、列； 第2列是圓括號序列；第3列是推導(dǎo)行即命題公式序列；第4列是注釋行序列。 推導(dǎo)行表明是前提或從部分前提推出的中間邏輯結(jié)論或最終所求的有效結(jié)論。花括號內(nèi)一些數(shù)字表明該推導(dǎo)行是由哪些前提推出的。圓括號中數(shù)字是對推導(dǎo)行按增序列統(tǒng)一編號。注釋行表示所引用推理規(guī)則和該推導(dǎo)行是由哪些公式和運(yùn)用怎樣推理定律得來的。,,③間接證法間接證法即是反證法，它是把結(jié)論的否定作為附加前提，與給定前提一起推證，若能引出矛盾，則說明結(jié)論是有效的。定義1.8.