第1章-命題演算課件

第一章命題演算§1.1命題及聯(lián)結(jié)詞可以分辨其真假的語(yǔ)句叫做命題一般用大寫字母表示例如：A：中華人民共和國(guó)的首都是北京。√B：2+4<5?！藽：我是大學(xué)生。√

請(qǐng)勿吸煙！×x+y<5?！?/p>

這束花多么好看??！×第一章命題演算§1.1命題及聯(lián)結(jié)詞1§1.1命題及聯(lián)結(jié)詞上述命題也稱為原始命題或原子命題。命題的真值有兩個(gè)即：真（T）和假（F）由復(fù)合語(yǔ)句表達(dá)的命題叫做復(fù)合命題。例如：D：你看書，我也看書。E：燈泡有故障或開關(guān)有故障。F：如果你不去，那么我也不去了?！?.1命題及聯(lián)結(jié)詞上述命題也稱為原始命題或原子命題。2§1.1命題及聯(lián)結(jié)詞1、否定定義1.1.1設(shè)P是一個(gè)命題，我們構(gòu)造一新命題是原命題的P的否定，稱它是命題P的取否命題，表示為?P。如：P：今天下雨。

?P：今天不下雨。

真值表：P?PTFFT§1.1命題及聯(lián)結(jié)詞1、否定P?PTFFT3§1.1命題及聯(lián)結(jié)詞2、合取定義1.1.2設(shè)P和Q是兩個(gè)命題，我們構(gòu)造一新命題“P與Q”，稱它是命題P和命題Q的合取命題，表示為P∧Q。如：P：我將去北京。

Q：你將去上海。

P∧Q：我將去北京并且你將去上海。

真值表：PQP∧QTTTTFFFTFFFF§1.1命題及聯(lián)結(jié)詞2、合取PQP∧QTTTTFFFT4§1.1命題及聯(lián)結(jié)詞3、析取定義1.1.3設(shè)P和Q是兩個(gè)命題，我們構(gòu)造一新命題“P或Q”，稱它是命題P和命題Q的析取命題，表示為P∨Q。如：P：燈泡有故障。

Q：開關(guān)有故障。P∨Q：燈泡有故障或開關(guān)有故障。真值表：PQP∨QTTTTFTFTTFFF§1.1命題及聯(lián)結(jié)詞3、析取PQP∨QTTTTFTF5§1.1命題及聯(lián)結(jié)詞◆上述三個(gè)聯(lián)結(jié)詞稱為基本聯(lián)結(jié)詞。4、條件定義1.1.4設(shè)P和Q是兩個(gè)命題，我們構(gòu)造一新命題“如果P則Q”，表示為P→Q。如：P：你去。

Q：我去。P→Q：如果你去，則我就去。真值表：PQP→QTTTTFFFTTFFT§1.1命題及聯(lián)結(jié)詞◆上述三個(gè)聯(lián)結(jié)詞稱為基本聯(lián)結(jié)詞。PQ6§1.1命題及聯(lián)結(jié)詞5、雙條件定義1.1.5設(shè)P和Q是兩個(gè)命題，我們構(gòu)造一新命題“P當(dāng)且僅當(dāng)Q”，表示為P?Q。如：P：兩個(gè)三角形是全等的。

Q：兩個(gè)三角形的三條對(duì)應(yīng)邊相等。P?Q：兩個(gè)三角形全等，當(dāng)且僅當(dāng)它們的三條對(duì)應(yīng)邊分別相等。真值表：PQP?QTTTTFFFTFFFT§1.1命題及聯(lián)結(jié)詞5、雙條件PQP?QTTTTFF7§1.1命題及聯(lián)結(jié)詞命題公式舉例“如果明天不下雨且不下雪，那么我去學(xué)?！绷睿篈：明天下雨。B：明天下雪。C：我去學(xué)校。則上述命題可表示為：[(?A)(?B)]→C。五個(gè)聯(lián)結(jié)詞的強(qiáng)弱順序?yàn)椋?，

，

，→，?所以上式可簡(jiǎn)寫為：

?A?B→C§1.1命題及聯(lián)結(jié)詞命題公式舉例8§1.2命題變?cè)c命題公式◆在一個(gè)命題公式中可能出現(xiàn)三類符號(hào)：大寫字母，即命題變?cè)?。?lián)結(jié)符號(hào)?，

，，→，?。括號(hào)（）。如：(P

Q)→Q。定義1.2.1（遞歸定義）

命題演算的命題公式（簡(jiǎn)稱公式）規(guī)定為：每一個(gè)命題變?cè)敲}公式。如果A是命題公式，則?A是命題公式。如果A、B是命題公式，則(AB),(AB),(A

→B),(A

?B)都是命題公式。一個(gè)由三類符號(hào)組成的符號(hào)串是命題公式，當(dāng)且僅當(dāng)是由上述三原則產(chǎn)生

?！?.2命題變?cè)c命題公式◆在一個(gè)命題公式中可能出現(xiàn)三類符9§1.2命題變?cè)c命題公式(P→Q)(Q→P)的真值表：與P?Q的真值表相同，稱這兩個(gè)命題等價(jià)?！魞蓚€(gè)真值表相同的命題稱為等價(jià)。但真值表有時(shí)很大，因此憑真值表是否相同來判斷是不現(xiàn)實(shí)的，我們還需尋找更多有效方法。PQP→QQ→P(P→Q)(Q→P)TTTTTTFFTFFTTFFFFTTT§1.2命題變?cè)c命題公式(P→Q)(Q→P)的真值表10§1.3命題演算的關(guān)系式

1.3.1命題公式的等價(jià)關(guān)系定義1.3.1設(shè)A和B是兩個(gè)命題（或命題公式），P1,P2,…,Pn是A、B中的全部變?cè)?，假如P1,P2,…,Pn，的任意一組取值，A、B的取值都相同，就稱A、B是等價(jià)的命題，表示為：AB?！糇⒁馀c?的區(qū)別AB是命題，AB不是命題。AB當(dāng)且僅當(dāng)AB為邏輯真。命題等價(jià)的三條性質(zhì)：自反性：AA對(duì)稱性：若AB，則BA傳遞性：若AB，BC，則AC§1.3命題演算的關(guān)系式

1.3.1命題公式的等價(jià)關(guān)系定義111.3.1命題公式的等價(jià)關(guān)系一些重要的等價(jià)關(guān)系（可以用真值表來驗(yàn)證）：

等冪率：PPP；PPP結(jié)合率：(PQ)RP(QR)；

(PQ)RP(QR)交換率：PQQP；PQQP分配率：P(QR)(PQ)(PR)P(QR)(PQ)(PR)同一率：PFP；PTP零元率：PTT；PFF補(bǔ)余率：P?PT；P?PF吸收率：P(PQ)P；P(PQ)P德.摩根率：?(PQ)

?P?Q；?(PQ)

?P?Q雙重否定率：??PP1.3.1命題公式的等價(jià)關(guān)系一些重要的等價(jià)關(guān)系（可以用真值表121.3.1命題公式的等價(jià)關(guān)系如果公式Q是公式P的一部分則稱Q是P的子公式。如P：A[(A→B)C]，則C，A→B，(A→B)C都是P的子公式。[(A→B)

，B)C都不是P的子公式，因?yàn)椴皇枪?。定?.3.1（代換法則）設(shè)A是P的一個(gè)子公式，AB。如果將P中的子公式代換成公式B之后得到的是公式Q，那么PQ。例1證明(PQ)(P?Q)P證(PQ)(P?Q)[(PQ)P][(PQ)?Q]

P[(P?Q)(Q?Q)]P[(P?Q)T]P(P?Q)

P1.3.1命題公式的等價(jià)關(guān)系如果公式Q是公式P的一部分則稱Q131.3.1命題公式的等價(jià)關(guān)系●可以證明：P→Q?PQP?Q(P→Q)(Q→P)

(PQ)(?P?Q)例2證明P→(Q→R)(PQ)→R例3證明P?Q[(PQ)?P]

1.3.1命題公式的等價(jià)關(guān)系●可以證明：141.3.2命題公式的蘊(yùn)含關(guān)系定義1.3.2當(dāng)且僅當(dāng)命題A→B是邏輯真是（即A→BT）時(shí)，稱“A蘊(yùn)含B”，表示為AB?！糇⒁馀c→的區(qū)別?！籼N(yùn)含關(guān)系的三個(gè)性質(zhì)：自反性：AA反對(duì)稱性：如果AB，BA，則AB傳遞性：如果AB，BC，則AC一些重要的命題蘊(yùn)含關(guān)系◆如果(H1H2…,Hm)Q，則H1,H2,…,Hm稱推出Q。定理1.3.2如果H1,H2,…,Hm和P推出Q，則H1,H2,…,Hm推出P→Q。（使用例2的結(jié)果）1.3.2命題公式的蘊(yùn)含關(guān)系定義1.3.2當(dāng)且僅當(dāng)命題A15一些重要的命題蘊(yùn)含關(guān)系1PQP2PQQ3PPQ4PPQ5QPQ6(PQ)P7(PQ)Q8P(PQ)Q9Q(PQ)P10P(PQ)Q11(PQ)(QR)PR12(PQ)(PR)(QR)R一些重要的命題蘊(yùn)含關(guān)系1PQP2PQQ3PPQ161.3.3命題公式的對(duì)偶關(guān)系◆如何一個(gè)公式P都可以經(jīng)過代換化成一個(gè)只含有?，

，三個(gè)基本聯(lián)結(jié)符的公式P。◆因此本節(jié)考慮只含有三個(gè)基本聯(lián)結(jié)符的公式。對(duì)偶：用“*”來表示。

*=，*=，?*=?

T*=F,F*=T定義1.3.3設(shè)A(P1,P2,…,Pn)是一個(gè)命題公式，其中P1,P2,…,Pn是公式中的所有命題變?cè)绻麑中基本聯(lián)結(jié)詞及T和F改為其對(duì)偶，其余不變，所得到的新公式稱作原公式的對(duì)偶，表示成A*(P1,P2,…,Pn)。顯然(A*)*=A。1.3.3命題公式的對(duì)偶關(guān)系◆如何一個(gè)公式P都可以經(jīng)過代換化171.3.3命題公式的對(duì)偶關(guān)系由德.摩根率：可得如下定理：定理1.3.3（對(duì)偶定理1）

?A(P1,P2,…,Pn)A*(?P1,?P2,…,?Pn)定理1.3.4（對(duì)偶定理）

如果AB，則A*B*1.3.3命題公式的對(duì)偶關(guān)系由德.摩根率：可得如下定理：181.4其他聯(lián)結(jié)詞1、不可兼析取定義1.4.1設(shè)P、Q是兩個(gè)命題，則稱作P和Q的不可兼析取（異或），

的真值為真，當(dāng)且僅當(dāng)P與Q的值不同。

的真值表：PQTTFTFTFTTFFF1.4其他聯(lián)結(jié)詞1、不可兼析取PQTTFTFTFTTFFF19如：P：李明正在家里學(xué)習(xí)。Q：李明正在劇場(chǎng)看戲。則“李明正在家里學(xué)習(xí)或正在劇場(chǎng)看戲”表示成。異或的性質(zhì)如：20定理1.4.1設(shè)P，Q，R為命題公式，如果

則

，

，Q，且

為矛盾式。證：如果

，則，

定理1.4.1設(shè)P，Q，R為命題公式，如果211.4其他聯(lián)結(jié)詞2、逆條件定義1.4.2設(shè)P和Q是兩個(gè)命題，復(fù)合命題

稱作命題P和Q的條件否定（逆條件）

的真值為T，當(dāng)且僅當(dāng)P為T，Q為F。

真值表：PQTTFTFTFTFFFF1.4其他聯(lián)結(jié)詞2、逆條件PQTTFTFTFTFFFF221.4其他聯(lián)結(jié)詞從定義可知：例如：P：他去。Q：你去。則

：并非如果他去你就去。1.4其他聯(lián)結(jié)詞從定義可知：231.4其他聯(lián)結(jié)詞3、與非定義1.4.3設(shè)P和Q是兩個(gè)命題，復(fù)合命題PQ稱作命題P和Q的“與非”?！舢?dāng)且僅當(dāng)P和Q的真值為T時(shí)，PQ為F，否則PQ為TPQ的真值表：從定義可知：PQ?(PQ)。PQPQTTFTFTFTTFFT1.4其他聯(lián)結(jié)詞3、與非PQPQTTFTFTFTTFFT241.4其他聯(lián)結(jié)詞例如：P：蘋果是紅的。Q：香蕉是黃的。

則PQ：并非蘋果是紅的與香蕉是黃的。與非的性質(zhì)：PP?(PP)?P(PQ)(PQ)?(PQ)PQ(PP)(QQ)?P?Q?(?P?Q)PQ1.4其他聯(lián)結(jié)詞例如：251.4其他聯(lián)結(jié)詞4、或非

定義1.4.4設(shè)P和Q是兩個(gè)命題，復(fù)合命題PQ稱作命題P和Q的“或非”。◆當(dāng)且僅當(dāng)P和Q的真值為F時(shí)，PQ為T，否則PQ為F。PQ的真值表：從定義可知：PQ?(PQ)。PQPQTTFTFFFTFFFT1.4其他聯(lián)結(jié)詞4、或非PQPQTTFTFFFTFFF261.4其他聯(lián)結(jié)詞例如：P：他在家里。Q：他在做作業(yè)。則PQ：并非他在家里或在做作業(yè)?；蚍堑男再|(zhì)：1、PP?(PP)?P2、(PQ)(PQ)?(PQ)PQ3、(PP)(QQ)?P?QPQ1.4其他聯(lián)結(jié)詞例如：271.4其他聯(lián)結(jié)詞聯(lián)結(jié)詞的強(qiáng)弱順序?，

，，，?1.4其他聯(lián)結(jié)詞聯(lián)結(jié)詞的強(qiáng)弱順序281.5范式

1.5.1析取范式和合取范式把命題公式化為一個(gè)標(biāo)準(zhǔn)形式，這個(gè)標(biāo)準(zhǔn)形式就是范式。定義1.5.1一個(gè)命題公式稱為析取范式，當(dāng)且僅當(dāng)它具有形式()，其中

都是命題變?cè)蚱浞穸ㄋM成的合取式。如：?P(PQ)(P?QR)定義1.5.2一個(gè)命題公式稱為合取范式，當(dāng)且僅當(dāng)它具有形式()，其中

都是命題變?cè)蚱浞穸ㄋM成的析取式。如：(P?Q?R)(?PQ)?Q。

1.5范式

1.5.1析取范式和合取范式把命題公式化為一291.5.1析取范式和合取范式求命題公式的析取范式（或合取范式）的三個(gè)步驟：1、利用基本等價(jià)公式將公式中的聯(lián)結(jié)詞化歸成，，?。2、利用德.摩根率將?直接移到命題變?cè)啊?、利用分配率、結(jié)合率等將公式歸納為析取范式或合取范式。

例1求?(PQ)?(PQ)的析取范式。

例2求Q?(PQ)?(PQ)的合取范式。注：一個(gè)公式的析取范式、合取范式不是唯一的。1.5.1析取范式和合取范式求命題公式的析取范式（或合取范301.5.2主析取范式和主合取范式要把一個(gè)命題公式化成一個(gè)唯一等價(jià)的標(biāo)準(zhǔn)形式，必須化成為主范式。定義1.5.3n個(gè)命題變?cè)暮先∈?，稱作布爾合取或小項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)，且只出現(xiàn)一次。例如，兩個(gè)變?cè)狿、Q的小項(xiàng)有：PQ，P?Q，?PQ，?P?Q，4個(gè)三個(gè)變?cè)男№?xiàng)有8個(gè)，n個(gè)變?cè)男№?xiàng)有

個(gè)。我們用1代表T，0代表F。1.5.2主析取范式和主合取范式要把一個(gè)命題公式化成一個(gè)唯311.5.2主析取范式和主合取范式表1.5.2P、Q、R及其小項(xiàng)真值表PQR?P?Q?R?P?QR?PQ?R?PQR00010000010100010001001100011000000101000011000001110000PQRP?Q?RP?QRPQ?RPQR000000000100000100000011000010010001010100110001011100011.5.2主析取范式和主合取范式表1.5.2P、Q、R及321.5.2主析取范式和主合取范式我們記：?P?Q?R，?P?QR，?PQ?R，?PQR，P?Q?R，P?QR，PQ?R，PQR1.5.2主析取范式和主合取范式我們記：331.5.2主析取范式和主合取范式小項(xiàng)的性質(zhì)：1、每個(gè)小項(xiàng)當(dāng)其值指派與編碼相同時(shí)，其真值為T，在其余-1種指派下為F。2、任意兩個(gè)不同小項(xiàng)的合取永假。3、全體小項(xiàng)的析取永真。定義1.5.4對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式僅由小項(xiàng)所組成，則稱該等價(jià)式為原式的主析取范式。定理1.5.1在真值表中，一個(gè)公式的真值為T的指派所對(duì)應(yīng)的小項(xiàng)的析取，即為此公式的主析取范式。1.5.2主析取范式和主合取范式小項(xiàng)的性質(zhì)：341.5.2主析取范式和主合取范式因此在求一個(gè)命題公式的主析取范式時(shí)有兩種方法：1、真值表法，例3和例4（P20）。2、利用基本等價(jià)公式推演法，例5和例6(P21)。

利用基本等價(jià)公式推演法步驟：1)、化歸為析取范式。2)、除去析取范式中所有永假的析取項(xiàng)。3)、將析取式中重復(fù)出現(xiàn)的合取項(xiàng)和相同的變?cè)喜ⅰ?)、對(duì)合取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變?cè)缓罄梅峙渎收归_公式。1.5.2主析取范式和主合取范式因此在求一個(gè)命題公式的主析351.5.2主析取范式和主合取范式與主析取范式類似的是主合取范式。定義1.5.3n個(gè)命題變?cè)暮先∈?，稱作布爾合取或大項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)，且只出現(xiàn)一次。例如，兩個(gè)變?cè)狿、Q的小項(xiàng)有：PQ，P?Q，?PQ，?P?Q，4個(gè)三個(gè)變?cè)拇箜?xiàng)有8個(gè)，n個(gè)變?cè)男№?xiàng)有

個(gè)。每個(gè)大項(xiàng)用二進(jìn)制編碼（n=2時(shí)）：=PQ，=P?Q，=?PQ，=?P?Q1.5.2主析取范式和主合取范式與主析取范式類似的是主合取361.5.2主析取范式和主合取范式大項(xiàng)的性質(zhì)：1、每個(gè)大項(xiàng)的當(dāng)其值指派與編碼相同時(shí)，其真值為F，在其余-1種指派下為T。2、任意兩個(gè)不同大項(xiàng)的析取永真。3、全體大項(xiàng)的合取永假。定義1.5.4對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式僅由大項(xiàng)所組成，則稱該等價(jià)式為原式的主合取范式。定理1.5.1在真值表中，一個(gè)公式的真值為F的指派所對(duì)應(yīng)的小項(xiàng)的析取，即為此公式的主合取范式。1.5.2主析取范式和主合取范式大項(xiàng)的性質(zhì)：371.5.2主析取范式和主合取范式因此在求一個(gè)命題公式的主合取范式時(shí)有兩種方法：1、真值表法，例7（P22）。2、利用基本等價(jià)公式推演法，例8(P23)