1、,高等學(xué)校21世紀(jì)教材,電子教案,離散數(shù)學(xué),人民郵電出版社,第一章命題邏輯,命題邏輯，也稱命題演算，記為L(zhǎng)s。它與謂詞邏輯構(gòu)成數(shù)理邏輯的基礎(chǔ)，而命題邏輯又是謂詞邏輯的基礎(chǔ)。數(shù)理邏輯是用數(shù)學(xué)方法即通過(guò)引入表意符號(hào)研究推理的學(xué)問(wèn)。因此，數(shù)理邏輯又名為符號(hào)邏輯。 命題邏輯是研究由命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系。,退出,1.1 命題與聯(lián)結(jié)詞 1.2 命題變?cè)秃鲜焦?1.3 公式分類與等價(jià)公式 1.4 對(duì)偶式與蘊(yùn)涵式 1.5 聯(lián)結(jié)詞的擴(kuò)充與功能完全組 1.6 公式標(biāo)準(zhǔn)型范式 1.7 公式的主范式 1.8 命題邏輯的推理理論,1.1 命題與聯(lián)結(jié)詞,. 命題的概念 所謂命題，是指具有非真

2、必假的陳述句。而疑問(wèn)句、祈使句和感嘆句等因都不能判斷其真假，故都不是命題。命題僅有兩種可能的真值真和假，且二者只能居其一。真用1或T表示，假用0或F表示。由于命題只有兩種真值，所以稱這種邏輯為二值邏輯。命題的真值是具有客觀性質(zhì)的，而不是由人的主觀決定的。,如果一陳述句再也不能分解成更為簡(jiǎn)單的語(yǔ)句，由它構(gòu)成的命題稱為原子命題。原子命題是命題邏輯的基本單位。 命題分為兩類，第一類是原子命題，原子命題用大寫英文字母P，Q，R及其帶下標(biāo)的Pi，Qi，Ri，表示。 第二類是復(fù)合命題，它由原子命題、命題聯(lián)結(jié)詞和圓括號(hào)組成。,. 命題聯(lián)結(jié)詞 定義1.1.1設(shè)P表示一個(gè)命題，由命題聯(lián)結(jié)詞l和命題P連接成lP，

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

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

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

6、P Q為命題P和Q的雙條件式復(fù)合命題，簡(jiǎn)稱雙條件命題，P Q讀做“P當(dāng)且僅當(dāng)Q”，或“P等價(jià)Q”。稱為雙條件聯(lián)結(jié)詞。 當(dāng)P和Q的真值相同時(shí)，P Q的真值為真；否則，P Q的真值為假。雙條件聯(lián)結(jié)詞的定義由表1.1.5表示之。,在本節(jié)結(jié)束時(shí)，應(yīng)強(qiáng)調(diào)指出的是：復(fù)合命題的真值只取決于各原子命題的真值，而與它們的內(nèi)容、含義無(wú)關(guān)，與原子命題之間是否有關(guān)系無(wú)關(guān)。理解和掌握這一點(diǎn)是至關(guān)重要的，請(qǐng)讀者認(rèn)真去領(lǐng)會(huì)。,1.2 命題變?cè)秃鲜焦?. 命題變?cè)?在命題邏輯中，命題又有命題常元和命題變?cè)?。一個(gè)確定的具體的命題，稱為命題常元；一個(gè)不確定的泛指的任意命題，稱為命題變?cè)?。顯然，命題變?cè)皇敲}，只有用一個(gè)

7、特定的命題取代才能確定它的真值：真或假。這時(shí)也說(shuō)對(duì)該命題變?cè)概烧嬷怠?命題常元和命題變?cè)捎米帜窹等表示。由于在命題邏輯中并不關(guān)心具體命題的涵義，只關(guān)心其真值，因此，可以形式地定義它們?nèi)缦拢?定義1.2.1以真或1、假或0為其變域的變?cè)?，稱為命題變?cè)?；真?、假或0稱為命題常元。,2.合式公式 通常把含有命題變?cè)臄嘌苑Q為命題公式。但這沒(méi)能指出命題公式的結(jié)構(gòu)，因?yàn)椴皇撬杏擅}變?cè)?、?lián)結(jié)詞和括號(hào)所組成的字符串都能成為命題公式。為此常使用歸納定義命題公式，以便構(gòu)成的公式有規(guī)則可循。由這種定義產(chǎn)生的公式稱為合式公式。 定義1.2.2單個(gè)命題變?cè)兔}常元稱為原子命題公式，簡(jiǎn)稱原子公式。,定義1

8、.2.3合式公式是由下列規(guī)則生成的公式： 單個(gè)原子公式是合式公式。 若A是一個(gè)合式公式，則(lA)也是一個(gè)合式公式。 若A、B是合式公式，則(AB)、(AB)、(AB)和(A B)都是合式公式。 只有有限次使用、和生成的公式才是合式公式。,當(dāng)合式公式比較復(fù)雜時(shí)，常常使用很多圓括號(hào)，為了減少圓括號(hào)的使用量，可作以下約定： 規(guī)定聯(lián)結(jié)詞的優(yōu)先級(jí)由高到低的次序?yàn)椋簂、 相同的聯(lián)結(jié)詞按從左至右次序計(jì)算時(shí)，圓括號(hào)可省略。 最外層的圓括號(hào)可以省略。 為了方便計(jì)，合式公式也簡(jiǎn)稱公式。,.公式真值表 定義1.2.4對(duì)于公式中命題變?cè)拿恳环N可能的真值指派，以及由它們確定出的公式真值所列成的表，稱為該公式的真值表

9、。 定義1.2.5如果B是公式A中的一部分，且B為公式，則稱B是公式A的子公式。,用歸納法不難證明，對(duì)于含有n個(gè)命題變?cè)墓剑?n個(gè)真值指派，即在該公式的真值表中有2n行。 為方便構(gòu)造真值表， 特約定如下： 命題變?cè)醋值湫蚺帕小?對(duì)每個(gè)指派，以二進(jìn)制數(shù)從小到大或從大到小順序列出。 若公式較復(fù)雜，可先列出各子公式的真值(若有括號(hào)，則應(yīng)從里層向外層展開(kāi))，最后列出所求公式的真值。,4.命題的符號(hào)化 把一個(gè)用文字?jǐn)⑹龅拿}相應(yīng)地寫成由命題標(biāo)識(shí)符、聯(lián)結(jié)詞和圓括號(hào)表示的合式公式，稱為 命題的符號(hào)化。符號(hào)化應(yīng)該注意下列事項(xiàng): 確定給定句子是否為命題。 句子中連詞是否為命題聯(lián)結(jié)詞。 要正確地表示原子命

10、題和適當(dāng)選擇命題聯(lián)結(jié)詞。,命題符號(hào)化是很重要的，一定要掌握好，在命題推理中常常最先遇到的就是符號(hào)化一個(gè)問(wèn)題，解決不好，等于說(shuō)推理的首要前提沒(méi)有了。,1.3 公式分類與等價(jià)公式,. 公式分類 定義1.3.1設(shè) A 為任意公式，則 對(duì)應(yīng)每一個(gè)指派，公式 A 均相應(yīng)確定真值為真，稱 A 為重言式，或永真式。 對(duì)應(yīng)每一個(gè)指派，公式 A 均相應(yīng)確定真值為假，稱 A 為矛盾式，或永假式。 至少存在一個(gè)指派，公式 A 相應(yīng)確定真值為真，稱 A 為可滿足式。,由定義可知，重言式必是可滿足式，反之一般不真。 重點(diǎn)將研究重言式，它最有用，因?yàn)樗幸韵绿攸c(diǎn)： 重言式的否定是矛盾式，矛盾式的否定是重言式，這樣只研究其

11、一就可以了。 兩重言式的合取式、析取式、條件式和雙條件式等都仍是重言式。于是，由簡(jiǎn)單的重言式可構(gòu)造出復(fù)雜的重言式。 由重言式使用公認(rèn)的規(guī)則可以產(chǎn)生許多有用等價(jià)式和蘊(yùn)涵式。,判定給定公式是否為永真式、永假式或可滿足式的問(wèn)題，稱為給定公式的判定問(wèn)題。 在Ls中，由于任何一個(gè)命題公式的指派數(shù)目總是有限的，所以Ls的判定問(wèn)題是可解的。其判定方法有真值表法和公式推演法。,.等價(jià)公式 定義1.3.2設(shè)A和B是兩個(gè)命題公式，如果A、B在其任意指派下，其真值都是相同的，則稱A和B是等價(jià)的，或邏輯相等，記作AB，讀作A等價(jià)B，稱AB為等價(jià)式。 顯然，若公式A和B的真值表是相同的，則A和B等價(jià)。因此，驗(yàn)證兩公式是

12、否等價(jià)，只需做出它們的真值表即可。,在這里，請(qǐng)讀者注意和的區(qū)別與聯(lián)系。 區(qū)別：是邏輯聯(lián)結(jié)詞，屬于目標(biāo)語(yǔ)言中的符號(hào)，它出現(xiàn)在命題公式中；不是邏輯聯(lián)結(jié)詞，屬于元語(yǔ)言中的符號(hào)，表示兩個(gè)命題公式的一種關(guān)系，不屬于這兩個(gè)公式的任何一個(gè)公式中的符號(hào)。 聯(lián)系：可用下面定理表明之。,定理1.3.1A B當(dāng)且僅當(dāng)AB是永真式。 有時(shí)也稱A B是永真雙條件式。 等價(jià)式有下列性質(zhì)： 自反性，即對(duì)任意公式A，有A A。 對(duì)稱性，即對(duì)任意公式A和B，若A B，則B A。 傳遞性，即對(duì)任意公式A、B和C，若A B、B C，則A C。,.基本等價(jià)式命題定律 在判定公式間是否等價(jià)，有一些簡(jiǎn)單而又經(jīng)常使用的等價(jià)式，稱為基本等價(jià)

13、式或稱命題定律。牢固地記住它并能熟練運(yùn)用，是學(xué)好數(shù)理邏輯的關(guān)鍵之一，讀者應(yīng)該注意到這一點(diǎn)?，F(xiàn)將這些命題定律列出如下： (1)雙否定：AA。 (2)交換律：ABBA，ABBA，ABBA。,(3) 結(jié)合律：(AB)CA(BC)，(AB)CA(BC)，(AB)CA(BC)。 (4) 分配律：A(BC)(AB)(AC)，A(BC)(AB)(AC)。 (5) 德摩根律：(AB)AB，(AB)AB。 (6) 等冪律：AAA，AAA。,(7) 同一律：ATA，AFA。 (8) 零 律：AFF，ATT。 (9) 吸收律：A(AB)A，A(AB)A。 (10) 互補(bǔ)律：AAF，(矛盾律) AAT。(排中律) (

14、11) 條件式轉(zhuǎn)化律：ABAB，ABBA。,(12) 雙條件式轉(zhuǎn)化律：AB(AB)(BA)(AB)(AB) AB(AB) (13) 輸出律：(AB)CA(BC)。 (14) 歸謬律：(AB)(AB)A。 上面這些定律，即是通常所說(shuō)的布爾代數(shù)或邏輯代數(shù)的重要組成部分，它們的正確性利用真值表是不難給出證明的。,.代入規(guī)則和替換規(guī)則 在定義合成公式時(shí)，已看到了邏輯聯(lián)結(jié)詞能夠從已知公式形成新的公式，從這個(gè)意義上可把邏輯聯(lián)結(jié)詞看成運(yùn)算。除邏輯聯(lián)結(jié)詞外，還要介紹“代入”和“替換”，它們也有從已知公式得到新的公式的作用，因此有人也將它們看成運(yùn)算，這不無(wú)道理，而且在今后討論中，它的作用也是不容忽視的。,(1)

15、代入規(guī)則 定理1.3.2 在一個(gè)永真式A中，任何一個(gè)原子命題變?cè)猂出現(xiàn)的每一處， 用另一個(gè)公式代入，所得公式B仍是永真式。本定理稱為代入規(guī)則。 (2)替換規(guī)則 定理1.3.3 設(shè)A1是合式公式A的子公式，若A1B1，并且將A中的A1用B1 替換得到公式B，則AB。稱該定理為替換規(guī)則。 滿足定理1.3.3條件的替換，稱為等價(jià)替換。,代入和替換有兩點(diǎn)區(qū)別： 代入是對(duì)原子命題變?cè)缘?，而替換可對(duì)命題公式實(shí)行。 代入必須是處處代入，替換則可部分替換，亦可全部替換。,1.4 對(duì)偶式與蘊(yùn)涵式,.對(duì)偶式 在上節(jié)介紹的命題定律中，多數(shù)是成對(duì)出現(xiàn)的，這些成對(duì)出現(xiàn)的定律就是對(duì)偶性質(zhì)的反映，即對(duì)偶式。利用對(duì)偶式的

16、命題定律，可以擴(kuò)大等價(jià)式的個(gè)數(shù)，也可減少證明的次數(shù)。,定義1.4.1 在給定的僅使用聯(lián)結(jié)詞、和的命題公式A中，若把和互換，F(xiàn)和T互換而得到一個(gè)命題公式A*，則稱A*為A的對(duì)偶式。 顯然，A也是A*的對(duì)偶式?？梢?jiàn)A與A*互為對(duì)偶式。,定理1.4.1(對(duì)偶定理) 設(shè)A和A*互為對(duì)偶式，P1，P2，Pn是出現(xiàn)A和A* 中的原子命題變?cè)瑒t A(P1，P2，Pn)A*(P1，P2，Pn) A(P1，P2，Pn)A*(P1，P2，Pn) 表明，公式A的否定等價(jià)于其命題變?cè)穸ǖ膶?duì)偶式；表明，命題變?cè)穸ǖ墓降葍r(jià)于對(duì)偶式之否定。,定理1.4.2 設(shè)A和B為兩個(gè)命題公式，若AB則A*B*。 有了等價(jià)式、代

17、入規(guī)則、替換規(guī)則和對(duì)偶定理，便可以得到更多的永真式，證明更多的等價(jià)式，使化簡(jiǎn)命題公式更為方便。,.蘊(yùn)涵式 定義1.4.2 設(shè)A和B是兩個(gè)命題公式，若AB是永真式，則稱A蘊(yùn)涵B，記作AB，稱AB為蘊(yùn)涵式或永真條件式。 符號(hào)和的區(qū)別與聯(lián)系類似于和的關(guān)系。區(qū)別：是邏輯聯(lián)結(jié)詞，屬于對(duì)象語(yǔ)言中的符號(hào)，是公式中的符號(hào)；而不是聯(lián)結(jié)詞，屬于元語(yǔ)言中的符號(hào)，表示兩個(gè)公式之間的關(guān)系，不是兩公式中符號(hào)。聯(lián)系：AB成立，其充要條件AB是永真式。,蘊(yùn)涵式有下列性質(zhì)： 自反性，即對(duì)任意公式A，有AA。 傳遞性，即對(duì)任意公式A、B和C，若AB，BC，則AC。 對(duì)任意公式A、B和C，若AB，AC，則A(BC)。 對(duì)任意公式A

18、、B和C，若AC，BC，則ABC。,這些性質(zhì)的正確性，請(qǐng)讀者自己驗(yàn)證。 下面給出等價(jià)式與蘊(yùn)涵式之間的關(guān)系。 定理1.4.3 設(shè)A和B是兩命題公式，AB的充要條件是AB且BA。,.蘊(yùn)涵式證明方法 除真值表外，還有兩種方法： 前件真導(dǎo)后件真方法 設(shè)公式的前件為真，若能推導(dǎo)出后件也為真，則條件式是永真式，故蘊(yùn)涵式成立。 因?yàn)橛CAB，即證AB是永真式。對(duì)于AB，除在A取真和B取假時(shí)，AB為假外，余下AB皆為真。所以，若AB的前件A為真，由此可推出B亦為真，則AB是永真式，即AB。, 后件假導(dǎo)前件假方法 設(shè)條件式后件為假，若能推導(dǎo)出前件也為假，則條件式是永真式，即蘊(yùn)涵式成立。 因?yàn)槿鬉B的后件B取假，

19、由此可推出A取假，即推證了：BA。又因ABBA，故AB成立。,1.5 聯(lián)結(jié)詞的擴(kuò)充與功能完全組,. 聯(lián)結(jié)詞的擴(kuò)充 定義1.5.1 設(shè)P和Q是任兩個(gè)原子命題， 由合取非聯(lián)結(jié)詞和P，Q連接成PQ，稱它為P和Q的合取非式復(fù)合命題，讀作“P合取非Q”。PQ的真值由命題P和Q的真值確定：當(dāng)且僅當(dāng)P和 Q均為時(shí)，PQ為，否則PQ為?！昂先》恰庇殖７Q為“與非”。,由析取非聯(lián)結(jié)詞和P，Q連接成PQ，稱它為P和Q的析取非式復(fù)合命題，讀作“P析取非Q”。PQ的真值由P和Q的真值確定：當(dāng)且僅當(dāng)P和Q均為時(shí)，PQ為，否則PQ為。“析取非”又常稱為“或非”。 由條件非聯(lián)結(jié)詞和P，Q連接成PQ，稱它為P和Q的條件非式復(fù)合

20、命題，讀作“P條件非Q”。PQ的真值由P和Q的真值確定：當(dāng)且僅當(dāng)P為而Q為時(shí)，PQ為；否則PQ為。,由雙條件非聯(lián)結(jié)詞把P，Q連接成PQ，稱它為P和Q的雙條件非式復(fù)合命題，讀作“P雙條件非Q”。PQ的真值由P和 Q的真值確定：當(dāng)且僅當(dāng)P和Q的真值不同時(shí)，PQ為，否則PQ為?！半p條件非”又常稱為“異或”，也常用符號(hào)表示之。 上面4個(gè)聯(lián)結(jié)詞構(gòu)成的復(fù)合命題，其真值表如下：,由表可知，PQ(PQ) PQ(PQ) PQ(PQ) PQ(PQ),.與非、或非和異或的性質(zhì) 與非、或非以及異或在計(jì)算機(jī)科學(xué)中是經(jīng)常使用的3個(gè)聯(lián)結(jié)詞，因此，掌握它們的性質(zhì)是十分必要的。令P、Q和R是原子命題變?cè)?與非的性質(zhì) (a)P

21、QQP (b) PPP (c) (PQ)(PQ)PQ (d) (PP)(QQ)PQ, 或非的性質(zhì) (a) PQQP (b) PPP (c)(PQ)(PQ)PQ (d) (PP)(QQ)PQ 從上述的性質(zhì)可知，聯(lián)結(jié)詞、和可分別用聯(lián)結(jié)詞或者取代，讀者可以自行驗(yàn)證，和都不滿足結(jié)合律。, 異或的性質(zhì) (a)PQQP (b) P(QR)(PQ)R (c) P(QR)(PQ)(PR) (d) PPF，F(xiàn)PP，TPP (e) 若PQR，則QRP，PPQ，且PQRF。,以上所有性質(zhì)，用真值表或命題定律都是不難證明的。 至此，已有了9個(gè)聯(lián)結(jié)詞，是否還需要擴(kuò)充呢？事實(shí)上，兩上命題變無(wú)P和Q，與9個(gè)聯(lián)結(jié)詞一共可構(gòu)成

22、 類命題公式，如下表示之：,從列表可知，除命題常元F，T及命題變?cè)旧硗猓}聯(lián)結(jié)詞一共有9個(gè)就夠了。為了方便，可規(guī)定其優(yōu)先級(jí)，由高到低次序?yàn)?，等?.聯(lián)結(jié)詞功能完全組 已知有9個(gè)聯(lián)結(jié)詞就夠用了，能不能少呢？若能少，表明有些聯(lián)結(jié)詞的邏輯功能可由其他聯(lián)結(jié)詞替代。事實(shí)上，也確實(shí)如此，因?yàn)橛邢铝械葍r(jià)式： PQ(PQ) PQ(PQ) PQ(PQ) PQ(PQ) 可見(jiàn)，擴(kuò)充的4個(gè)聯(lián)結(jié)詞，和能由原有5個(gè)聯(lián)結(jié)詞分別替代之。,又由命題定律： PQ(PQ)(QP) PQPQ PQ(PQ) PQ(PQ) 可知，原有5個(gè)聯(lián)結(jié)詞，和又能由聯(lián)結(jié)詞組，或，取代。那么，究竟最少用幾個(gè)聯(lián)結(jié)詞？就是說(shuō)，用最少的幾個(gè)聯(lián)結(jié)詞就能等

23、價(jià)表示所有的命題公式?；蛘哒f(shuō)，用最少的幾個(gè)聯(lián)結(jié)詞就能替代所有聯(lián)結(jié)詞的功能。這便是所要定義的聯(lián)結(jié)詞功能完全組。,定義1.5.2 稱G為聯(lián)結(jié)詞功能完全組，如果G滿足下列兩條件：由G中聯(lián)結(jié)詞構(gòu)成的公式能等價(jià)表示任意命題公式；G 中的任一聯(lián)結(jié)詞不能用其余下聯(lián)結(jié)詞等價(jià)表示。 可以證明，都是聯(lián)結(jié)詞功能完全組；而，都不是聯(lián)結(jié)詞功能完全組，但為了表示方便，仍經(jīng)常使用聯(lián)結(jié)詞組，。,1.6 公式標(biāo)準(zhǔn)型范式,.簡(jiǎn)單合取式與簡(jiǎn)單析取式 定義1.6.1 在一公式中，僅由命題變?cè)捌浞穸?gòu)成的合取式， 稱該公式為簡(jiǎn)單合取式，其中每個(gè)命題變?cè)蚱浞穸?，稱為合取項(xiàng)。 定義1.6.2 在一公式中，僅由命題變?cè)捌浞穸?gòu)成的析取

24、式， 稱該公式為簡(jiǎn)單析取式，其中每個(gè)命題變?cè)蚱浞穸?，稱為析取項(xiàng)。,例如，公式P，Q，PQ和PQP等都是簡(jiǎn)單合取式，而P，Q和P為相應(yīng)的簡(jiǎn)單合取式的合取項(xiàng)；公式P，Q，PQ，PQP等都是簡(jiǎn)單析取式，而P，Q和P為相應(yīng)簡(jiǎn)單析取式的析取項(xiàng)。 注意，一個(gè)命題變?cè)蚱浞穸瓤梢允呛?jiǎn)單合取式，也可是簡(jiǎn)單析取式，如例中P，Q等。,定理1.6.1 簡(jiǎn)單合取式為永假式的充要條件是：它同時(shí)含有某個(gè)命題變?cè)捌浞穸ā?定理1.6.2 簡(jiǎn)單析取式為永真式的充要條件是：它同時(shí)含有某個(gè)命題變?cè)捌浞穸ā?.析取范式與合取范式 定義1.6.3 一個(gè)命題公式A稱為析取范式，當(dāng)且僅當(dāng)A可表為簡(jiǎn)單合取式的析取，即AAi；其中A

25、i為簡(jiǎn)單合取式，i=1，2，n。 定義1.6.4 一個(gè)命題公式A稱為合取范式，當(dāng)且僅當(dāng)A可表為簡(jiǎn)單析取式的合取，即AAi；其中Ai為簡(jiǎn)單析取式，1in。,定理1.6.3 對(duì)于任何一命題公式，都存在與其等價(jià)的析取范式和合取范式。 求范式算法： 使用命題定律，消去公式中除、和以外公式中出現(xiàn)的所有聯(lián)結(jié)詞； 使用(P)P和德摩根律，將公式中出現(xiàn)的聯(lián)結(jié)詞都移到命題變?cè)埃?利用結(jié)合律、分配律等將公式化成析取范式或合取范式。,.范式的應(yīng)用 利用析取范式和合取范式可對(duì)公式進(jìn)行判定。 定理1.6.4 公式A為永假式的充要條件是A 的析取范式中每個(gè)簡(jiǎn)單合取式至少包含一個(gè)命題變?cè)捌浞穸ā?定理1.6.5 公式

26、A為永真式的充要條件是A 的合取范式中每個(gè)簡(jiǎn)單析取式至少包含一個(gè)命題變?cè)捌浞穸ā?.范式不唯一性,1.7 公式的主范式,范式基本解決了公式的判定問(wèn)題。但由于范式不唯一性，對(duì)識(shí)別公式間是否等價(jià)帶來(lái)一定困難，而公式的主范式解決了這個(gè)問(wèn)題。下面將分別討論主范式中的主析取范式和主合取范式。,.主析取范式 (1) 小項(xiàng)的概念和性質(zhì) 定義1.7.1 在含有n個(gè)命題變?cè)暮?jiǎn)單合取式中， 若每個(gè)命題變?cè)c其否定不同時(shí)存在，而二者之一出現(xiàn)一次且僅出現(xiàn)一次，則稱該簡(jiǎn)單合取式為小項(xiàng)，或布爾積。,例如，兩個(gè)命題變?cè)狿和Q，其構(gòu)成的小項(xiàng)有PQ，PQ，PQ和PQ；而三個(gè)命題變?cè)狿、Q和R，其構(gòu)成的小項(xiàng)有PQR，PQR，

27、PQR，PQR，PQR ，PQR，PQR，PQR。 可以證明，n個(gè)命題變?cè)残纬?n個(gè)小項(xiàng)。,如果將命題變?cè)醋值湫蚺帕校⑶野衙}變?cè)c1對(duì)應(yīng)，命題變?cè)姆穸ㄅc0對(duì)應(yīng)，則可對(duì)2n個(gè)小項(xiàng)依二進(jìn)制數(shù)編碼，記為mi，其下標(biāo)i是由二進(jìn)制數(shù)轉(zhuǎn)化的十進(jìn)制數(shù)。用這種編碼所求得2n個(gè)小項(xiàng)的真值表，可明顯地反映出小項(xiàng)的性質(zhì)。 表1.7.1和表1.7.2分別給出了2個(gè)命題變?cè)狿和Q、3個(gè)命題變?cè)狿、Q和R的小項(xiàng)真值表。,從表1.7.1，表1.7.2可看出，小項(xiàng)有如下性質(zhì)： (a)沒(méi)有兩個(gè)小項(xiàng)是等價(jià)的，即是說(shuō)各小項(xiàng)的真值表都是不同的； (b)任意兩個(gè)不同的小項(xiàng)的合取式是永假的：mimj，ij。 (c)所有小項(xiàng)之析

28、取為永真： mi。 (d)每個(gè)小項(xiàng)只有一個(gè)解釋為真，且其真值1位于主對(duì)角線上。,(2) 主析取范式定義與存在定理 定義1.7.2 在給定公式的析取范式中，若其簡(jiǎn)單合取式都是小項(xiàng)， 則稱該范式為主析取范式。 定理1.7.1 任意含n個(gè)命題變?cè)姆怯兰倜}公式A 都存在與其等價(jià)的主析取范式。,(3) 主析取范式的求法 主析取范式求法有兩種：真值表法和公式化歸法。定理1.7.1的證明已給出了用真值表求主析取范式的方法，而公式化歸法給出如下： (a)把給定公式化成析取范式； (b) 刪除析取范式中所有為永假的簡(jiǎn)單合取式；,(c) 用等冪律化簡(jiǎn)簡(jiǎn)單合取式中同一命題變?cè)闹貜?fù)出現(xiàn)為一次出現(xiàn)，如PPP。 (

29、d) 用同一律補(bǔ)進(jìn)簡(jiǎn)單合取式中未出現(xiàn)的所有命題變?cè)?，如Q，則PPQQ)，并用分配律展開(kāi)之，將相同的簡(jiǎn)單合取式的多次出現(xiàn)化為一次出現(xiàn)， 這樣得到了給定公式的主析取范式。,(4) 主析取范式的惟一性 定理1.7.2 任意含n個(gè)命題變?cè)姆怯兰倜}公式，其主析取范式是惟一的。,.主合取范式 (1) 大項(xiàng)的概念和性質(zhì) 定義1.7.3 在n個(gè)命題變?cè)暮?jiǎn)單析取式中，若每個(gè)命題變?cè)c其否定不同時(shí)存在，而二者之一必出現(xiàn)一次且僅出現(xiàn)一次，則稱該簡(jiǎn)單析取式為大項(xiàng)，或布爾和。,例如，由兩個(gè)命題變?cè)狿和Q，構(gòu)成大項(xiàng)有PQ，PQ，PQ，PQ；三個(gè)命題變?cè)狿，Q和R，構(gòu)成PQR，PQR，PQR，PQR，PQR，PQR，

30、PQR，PQR。 能夠證明，n個(gè)命題變?cè)灿?n個(gè)大項(xiàng)。,如果將n個(gè)命題變?cè)判?，并且把命題變?cè)c對(duì)應(yīng)，命題變?cè)姆穸ㄅc對(duì)應(yīng)，則可對(duì)2n個(gè)大項(xiàng)按二進(jìn)制數(shù)編碼，記為Mi，其下標(biāo)i是由二進(jìn)制數(shù)化成的十進(jìn)制數(shù)。用這種編碼所求的2n個(gè)大項(xiàng)的真值表，能直接反映出大項(xiàng)的性質(zhì)。 表1.7.3給出了2個(gè)命題變?cè)狿和構(gòu)成所有大項(xiàng)的真值表。,類似可給出個(gè)命題變?cè)?、和的所有大?xiàng)的真值表，留給讀者完成。 從表1.7.3可看出大項(xiàng)的性質(zhì)： (a)沒(méi)有兩個(gè)大項(xiàng)是等價(jià)的。 (b)任何兩個(gè)不同大項(xiàng)之析取是永真的，即MiMj，ij。 (c) 所有大項(xiàng)之合取為永假，即Mi。 (d) 每個(gè)大項(xiàng)只有一個(gè)解釋為假，且其真值0位于主對(duì)角

31、線上。,(2) 主合取范式的定義與其存在定理 定義1.7.4 在給定公式的合取范式中，若其所有簡(jiǎn)單析取式都是大項(xiàng)， 稱該范式為主合取范式。 定理1.7.3 任意含有n個(gè)命題變?cè)姆怯勒婷}公式A，都存在與其等價(jià)的主合取范式。 定理1.7.4 任意含n個(gè)命題變?cè)姆怯勒婷}公式A，其主合取范式是唯一的。 上述兩定理的證明，類似于定理1.7.1和定理1.7.2。,主合取范式的求法也有兩種，類似于主析取范式的求法。 .主析取范式與主合取范式之間的關(guān)系 由于主范式是由小項(xiàng)或大項(xiàng)構(gòu)成，從小項(xiàng)和大項(xiàng)的定義，可知兩者有下列關(guān)系： miMi Mimi 因此，主析取范式和主合取范式有著“互補(bǔ)”關(guān)系，即是由給定公

32、式的主析取范式可以求出其主命取范式。,設(shè)命題公式A中含有n個(gè)命題變?cè)?，且A的主析取范式中含有k個(gè)小項(xiàng) ， ， ，則A的主析取范式中必含有2n-k個(gè)小項(xiàng)，不妨含為 ， ， ，即A 。于是 AA( ) ,由此可知，從A的主析取范式求其主合取范式的步驟為： (a)求出A的主析取范式中設(shè)有包含的小項(xiàng)。 (b) 求出與(a)中小項(xiàng)的下標(biāo)相同的大項(xiàng)。 (c) 做(b)中大項(xiàng)之合取，即為A的主合取范式。 例如，(PQ)Qm1m3，則(PQ)QM0M2。,.主范式的應(yīng)用 利用主范式可以求解判問(wèn)題或者證明等價(jià)式成立。 （1）判定問(wèn)題 根據(jù)主范式的定義和定理，也可以判定含n個(gè)命題變?cè)墓剑潢P(guān)鍵是先求出給定公式

33、的主范式；其次按下列條件判定之： (a)若A，或A可化為與其等價(jià)的、含2n個(gè)小項(xiàng)的主析取范式，則A為永真式。,(b)若A，或A可化為與其等價(jià)的、含2n個(gè)大項(xiàng)的主合取范式，則A為永假式。 (c)若A不與或者等價(jià)，且又不含2n個(gè)小項(xiàng)或者大項(xiàng)，則A為可滿足的。 （2）證明等價(jià)式成立 由于任一公式的主范式是唯一的，所以將給定的公式求出其主范式，若主范式相同，則給定兩公式是等價(jià)的。,1.8 命題邏輯的推理理論,在邏輯學(xué)中，把從前題（又叫公理或假設(shè)）出發(fā)，依據(jù)公認(rèn)的推理規(guī)則，推導(dǎo)出一個(gè)結(jié)論，這一過(guò)程稱為有效推理或形式證明。所得結(jié)論叫做有效結(jié)論，這里最關(guān)心的不是結(jié)論的真實(shí)性而是推理的有效性。前提的實(shí)際真值不

34、作為確定推理有效性的依據(jù)。但是，如果前提全是真，則有效結(jié)論也應(yīng)該真而絕非假。,在數(shù)理邏輯中，集中注意的是研究和提供用來(lái)從前提導(dǎo)出結(jié)論的推理規(guī)則和論證原理，與這些規(guī)則有關(guān)的理論稱為推理理論。 提請(qǐng)注意，必須把推理的有效性和結(jié)論的真實(shí)性區(qū)別開(kāi)。有效的推理不一定產(chǎn)生真實(shí)的結(jié)論，產(chǎn)生真實(shí)結(jié)論的推理過(guò)程未必一定是有效的。再說(shuō)，有效的推理中可能包含假的前提；而無(wú)效的推理卻可能包含真的前提。,可見(jiàn)，推理的有效性是一回事，前提與結(jié)論的真實(shí)與否是另一回事。所謂推理有效，指它的結(jié)論是它的前提的合乎邏輯的結(jié)果，也即，如果它的前提都為真，那么所得結(jié)論也必然為真，而并不是要求前提或結(jié)論一定為真或?yàn)榧?。如果推理是有效的?/p>

35、，那么不可能它的前提都為真時(shí)而它的結(jié)論為假。,.推理的基本概念和推理形式 推理也稱論證，它是指由已知命題得到新的命題的思維過(guò)程，其中已知命題稱為推理的前提或假設(shè)，推得的新命題稱為推理的結(jié)論。 在數(shù)理邏輯中，前提H是一個(gè)或者n個(gè)命題公式H1,H2,Hn；結(jié)論是一個(gè)命題公式C。由前提到結(jié)論的推理形式可表為H1,H2,HnC，其中符號(hào)表示推出?？梢?jiàn)，推理形式是命題公式的一個(gè)有限序列，它的最后一個(gè)公式是結(jié)論，余下的為前提或假設(shè)。,定義1.8.1 如果存在H1，H2，Hn，C的一個(gè)指派，使得每個(gè)Hi(1in)為真而C為假推理形式H1，H2，HnC是無(wú)效的；否則，推理是有效的，此時(shí)稱C是H1，H2，Hn的

36、有效結(jié)論，或稱C是從前提H1，H2，Hn邏輯推出的結(jié)論。 定理1.8.1 推理形式H1，H2，HnC是有效的，當(dāng)且僅當(dāng)命題公式(H1H2Hn)C是永真式，亦即(H1H2Hn)C。,.推理規(guī)則 在數(shù)理邏輯中，從前提推導(dǎo)出結(jié)論，要依據(jù)事先提供的公認(rèn)的推理規(guī)則，它們是： 規(guī)則(也稱前提引入規(guī)則)：在推導(dǎo)過(guò)程中，前提可視需要引入使用。 規(guī)則(也稱結(jié)論引入規(guī)則)：在推導(dǎo)過(guò)程中，前面已導(dǎo)出的有效結(jié)論都可作為后續(xù)推導(dǎo)的前提引入。,此外，在從前提推出的結(jié)論為條件式時(shí)，還需要下面規(guī)則： 規(guī)則(也稱條件證明引入規(guī)則)：若推出有效結(jié)論為條件式RC時(shí)，只需將其前件R加入到前提中作為附加前提且再去推出后件C即可。 規(guī)則

37、的正確性可由下面定理得到保證： 定理1.8.2 若H1，H2，Hn，RC，則H1，H2，HnRC。,.推理定律 在推理過(guò)程中，除使用推理規(guī)則后，還需要使用許多條推理定律，這些定律可由以前講過(guò)的命題定律、蘊(yùn)涵式及運(yùn)用定理1.8.1而得到。下面只給出了由蘊(yùn)涵式得出的推理定律，它們是： (1) P，QP (2) P，QQ (3) PPQ (4) PPQ,(5) QPQ (6) (PQ)P (7) (PQ)Q (8) P，(PQ)Q (9) Q，(PQ)P (10) P，(PQ)Q (11) (PQ)，(QR)PR (12) (PQ)，(QR)PR (13) (PQ)，(RS)，(PR)QS,(14) (PQ)，(RS)(PR)QS 特別當(dāng)Q=S時(shí)，有 (PQ)，(RQ)，(PR)Q (PQ)，(RS