離散數(shù)學(xué)命題邏輯北航

1、第一篇 數(shù)理邏輯第一章 命題邏輯 1.1命題符號化及其聯(lián)結(jié)詞 1.1.1 命題 命 題 真 值 原子命題 復(fù)合命題 命題：能夠確定真假的陳述句 命題的真值：對于一個(gè)確定的命題，總會有一個(gè)“值”，或“真” 或“假”，稱為命題的真值。 真：T或1 假：F或0p判斷一個(gè)句子是否為命題的關(guān)鍵： 1.是否為陳述句 2.是否能確定真值，即真值是否唯一 例1.1.1 判斷下列句子是否為命題（1）10是整數(shù)（2）北京是我們祖國的首都（3）雪是黑色的（4）今天是7號（5）1+11=100（6）向右看齊?。?）你吃過飯了嗎？（8）我在說謊（9）我不給所有自己給自己理發(fā)的人理發(fā) 我只給所有自己不給自己理發(fā)的人理發(fā)（

2、10）別的星球上有生物（11）明天下雨有些陳述句在目前看來無法確定真值，但從事物本質(zhì)而言其本身有確定的真假，所以也是命題 原子命題：不能分解為更簡單的命題的命題稱為原子命題 復(fù)合命題：由聯(lián)結(jié)詞、標(biāo)點(diǎn)符號把幾個(gè)原子命題聯(lián)結(jié)起來構(gòu)成的命題稱為復(fù)合命題 例1.1.2 判斷下列句子哪些是原子命題，哪些是復(fù)合命題？ （1）煤是白的 （2）我學(xué)英語，或者學(xué)法語 （3）2是素?cái)?shù) （4）如果天氣好，我就去游泳1.1.2 命題表示法 命題標(biāo)識符：表示命題的符號 通常使用大寫英文字母A、B、C、X、Y、Z或帶下標(biāo)的英文字母A1、B2等來表示，也可使用數(shù)字表示例1.1.3： P：今天是7號 P1：今天是7號 6：今

3、天是7號 命題常量：一個(gè)命題標(biāo)識符如表示一個(gè)確定的命題，則稱為命題常量，例1.3中三個(gè)標(biāo)識符都是命題常量 命題變量：如果一個(gè)命題標(biāo)識符并不能表示一個(gè)確定的命題，而只表示任意命題的位置標(biāo)示，就稱為命題變量 命題變量可以代表任意命題，不能確定真值，故不是命題，但可以對命題變量進(jìn)行指派，即利用一個(gè)確定的命題取代命題變量1.1.3 聯(lián)結(jié)詞 聯(lián)結(jié)詞是復(fù)合命題中的重要組成部分，為了便于書寫及運(yùn)算，需進(jìn)行明確規(guī)定及符號化，五種重要的聯(lián)結(jié)詞有：否定（ ）、合?。?）、析?。?）、條件（ ）、雙條件（ ）1.否定 定義1.1.1 假設(shè)P為一命題，則P的否定為一新命題，記作 P，稱為非P，若P的真值為真（T或1）

4、，則P為假（F或0）；若P的真值為假（F或0），則P為真（T或1） 例1.1.4 P:今天是7號 P:今天不是7號 以表格的形式來列出P和P的所有真值情況 說明：（1）否定是一元聯(lián)結(jié)詞 （2）滿足雙重否定定律： （ P） P，其中 “”表示符號兩邊兩個(gè)命題在任何情況下真值都相同PPTFFT2.合取 定義1.1.2 給定兩個(gè)命題P和Q，把它們的合取作為一個(gè)新命題，記作PQ，讀作P且Q或P與Q，滿足：當(dāng)且僅當(dāng)P和Q真值同時(shí)為T時(shí)，PQ為T，在其它情況下，PQ均為F 例1.1.5 P：今天是晴天，Q：昨天是晴天，R：房間里有十張桌子 PQ：今天和昨天都是晴天 PR：今天是晴天且房間里有十張桌子 P和

5、R在自然語言中沒有任何相關(guān)聯(lián)系，PR也沒有意義，但在數(shù)理邏輯中仍然是一個(gè)命題 以真值表來表示合取的定義： 性質(zhì)：（1）PP P （2）PQ QP （3）(PQ)R P(QR) （4）PT P ，PF F （5）P P F 說明：是二元聯(lián)結(jié)詞 PQPQTTTTFFFTFFFF3.析取 定義1.1.3 給定兩個(gè)命題P和Q，把它們的析取作為一個(gè)新命題，記作PQ，讀作P或Q，滿足：當(dāng)且僅當(dāng)P和Q真值同時(shí)為F時(shí)，PQ為F，在其它情況下，PQ均為T 例1.1.6 （1） P：同學(xué)們學(xué)過英語，Q：同學(xué)們學(xué)過日語 PQ：同學(xué)們學(xué)過英語或日語 （2）選小張或小王做班長 （3）小李小李現(xiàn)在在宿舍或在教室自然語言中

6、或有多種理解，（1）為可兼或，而（2）和（3）為不可兼或，析取定義中或?yàn)榭杉婊?真值表： 性質(zhì)：（1）PP P （2）PQ QP （3）(PQ)R P(QR) （4）PT T ，PF P （5）P P T 說明：是二元聯(lián)結(jié)詞PQPQTTTTFTFTTFFF4.條件 定義1.1.4 給定兩個(gè)命題P和Q，把它們的條件命題作為一個(gè)新命題，記作PQ，讀作如果P，那么Q，滿足：當(dāng)且僅當(dāng)P真值為T, Q的真值為F時(shí)， PQ為F，在其它情況下， PQ均為T，其中稱P為前件或前提，Q為后件或結(jié)論 例1.1.7 （1）P：某動物為哺乳動物，Q：該動物為胎生 PQ：如果某動物為哺乳動物，那么它必為胎生 （2）P：

7、雪是黑的，Q：太陽從西邊升起 PQ：如果雪是黑的，那么太陽從西邊升起（3）P：我去上海，Q：我給你買新衣服 PQ：如果我去上海，那么我給你買新衣服 四種情況：P真，Q真，則PQ為真 P真，Q假，則PQ為假 P假，Q真，則PQ為真 P假，Q假，則PQ為真 真值表：PQPQTTTTFFFTTFFT 說明：（1）“”為二元聯(lián)結(jié)詞 （2）前件為F時(shí),條件命題必為T （3）自然語言中，“如果P那么Q”中P與Q之間往往具有一定的內(nèi)在聯(lián)系，但在數(shù)理邏輯中PQ中的P與Q不一定有相互關(guān)系練習(xí)：將下列命題符號化（1）只要天不下雨，我就騎自行車上班（2）只有天不下雨，我才騎自行車上班（3）除非下雨，否則我就騎自行車

8、上班（4）如果下雨，我就不騎自行車上班5.雙條件 定義1.1.5 給定兩個(gè)命題P和Q，把它們的雙條件命題作為一個(gè)新命題，記作P Q，讀作P當(dāng)且僅當(dāng)Q，滿足：當(dāng)且僅當(dāng)P與Q的真值相同時(shí)， PQ為T，在其它情況下， PQ均為F 例1.1.8 （1）P：兩個(gè)三角形全等，Q：兩個(gè)三角形三組對應(yīng)邊相等 PQ：兩個(gè)三角形全等當(dāng)且僅當(dāng)它們的三組對應(yīng)邊都相等 （2）P：5+58，Q：2是素?cái)?shù) PQ：5+58當(dāng)且僅當(dāng)2是素?cái)?shù)（3）P：a2+b2=0，Q：a=0, b=0 PQ ：a2+b2=0當(dāng)且僅當(dāng)a=0, b=0 真值表 說明：（1）為二元聯(lián)結(jié)詞 （2）同樣可以無因果對應(yīng)關(guān)系，根據(jù)聯(lián)結(jié)詞的定義判斷命題真值

9、PQPQ TTTTFFFTFFFT 例1.1.9 分析下列各命題的真值（1）2+2=4當(dāng)且僅當(dāng)3是奇數(shù)（2）2+2=4當(dāng)且僅當(dāng)3不是奇數(shù)（1）2+24當(dāng)且僅當(dāng)3是奇數(shù)（2）2+24當(dāng)且僅當(dāng)3不是奇數(shù)1.2 命題公式與翻譯1.2.1 命題公式定義1.2.1 命題公式即合式公式，規(guī)定為：（1）單個(gè)命題變量本身是一個(gè)合式公式；（2）如果A是一個(gè)合式公式，那么 A也是合式公式；（3）如果A和B都是合式公式，那么AB, AB, AB, AB都是合式公式；（4）只有有限次使用（1）-（3）組成的符號串才是合式公式 例1.2.1 判斷下列公式哪些是合式公式 (1) PQR (2) (PQ)R (3) (PQ

10、R) (4) (PQ)(QR)(ST) (5) PQR1.2.2 命題符號化 命題邏輯中，利用之前介紹的五種聯(lián)結(jié)詞和合式公式的定義可將復(fù)合命題用符號來表示，稱為命題符號化，命題符號化的步驟如下：（1）找出各原子命題并分別用命題標(biāo)識符表示；（2）使用適合的 聯(lián)結(jié)詞，將原子命題聯(lián)結(jié)起來，組成復(fù)合命題的符號化形式例1.2.2 將下列命題符號化（1）小王是游泳冠軍或百米賽跑冠軍 （ PQ ）（2）選小王或小李中的一人做班長 （(PQ)(PQ)）（3）小張現(xiàn)在在宿舍或者在教室 （(PQ)） 例1.2.3 將下列命題符號化（1）如果我上街，我就去書店看看，除非我很累（ (PR )Q）（2）小王是電子工程學(xué)

11、院的學(xué)生，他是1983或1984年生的，他是三好學(xué)生 （P(QR)S）五個(gè)聯(lián)結(jié)詞的優(yōu)先級順序：，(， )1.3 真值表與等價(jià)公式1.3.1 真值表 定義1.3.1 設(shè)A為命題公式，P1,P2,，Pn是其中出現(xiàn)的所有命題變量，給P1,P2,，Pn指定一組真值，稱為對A的一個(gè)賦值或解釋；若指定的真值使得A的值為真，則稱這個(gè)賦值為A的成真賦值，否則稱為成假賦值1.3.1 真值表 定義1.3.2 含n個(gè)命題變量的命題公式，共有2n組賦值，將命題公式A在所有賦值之下取值的情況列成表，稱為A的真值表 定義1.3.3 如果X是合式公式A的一部分，且X本身也是一個(gè)合式公式，那么稱X是A的子公式 構(gòu)造真值表的步

12、驟為：（1）從簡單到復(fù)雜列出命題公式中的所有子公式（2）列出每個(gè)命題變量的所有可能的賦值組合情況（3）計(jì)算各個(gè)子公式在所有賦值組合下的真值例1.3.1 求下列公式的真值表（1） PQ （2）P(Q P)（3）(P(PQ)Q （4）(PQ)R例1.3.1中（3）在真值表中對各種賦值均為真，而（4）中取值均為假 定義1.3.4 設(shè)A是一個(gè)命題公式（1）若A在它的各種賦值情況下均為真，則A稱為永真式或重言式永真式或重言式，記作T;（2）若A在它的各種賦值情況下均為假，則A稱為永假式或矛盾式永假式或矛盾式，記作F;（3）若A至少存在一個(gè)賦值是成真賦值，則稱A為可滿足式可滿足式1.3.2 公式的等價(jià) 假

13、設(shè)A是任意由P和Q兩個(gè)命題變量組成的命題公式，真值表情況可能如下： A的真值表取值情況最多只可能有24種 那么，n個(gè)命題變量也只能生成22n個(gè)真值不同的命題公式，而由符號組成的合式公式卻有很多種 例1.3.2 在同一個(gè)表中構(gòu)造 PQ和PQ的真值表PQATTT或FTFT或FFTT或FFFT或F定義1.3.5 設(shè)A、B為兩個(gè)命題公式， P1,P2,，Pn是A和B中出現(xiàn)的所有命題變量，給P1,P2,，Pn指定任意一組賦值，A和B的真值都相同，則稱A和B是等價(jià)的或邏輯相等的，記作AB說明：（1）“”不是聯(lián)結(jié)詞，只是表示等價(jià)的符號 （2）“”具有自反性、對稱性和傳遞性 例1.3.3 判斷下列命題公式是否

14、等價(jià) （1） (PQ)與 PQ （2） (PQ)與 P Q24條命題定律和等價(jià)公式，課本P15驗(yàn)證分配率和吸收率另外五條等價(jià)式：條件等價(jià)式： PQPQ雙條件等價(jià)式：PQ(PQ) (QP)假言易位：PQQP雙條件否定：PQPQ歸謬論：(PQ) (PQ) P1.3.3 等值演算 定理1.3.1 （置換規(guī)則）設(shè)X是合式公式A的子公式，用公式Y(jié)置換A中的X得到公式B，若XY, 那么AB根據(jù)定理1.3.1和24條等價(jià)公式驗(yàn)證合式公式之間的等價(jià)性例1.3.4 驗(yàn)證如下的等價(jià)式（1） P(QR) (PQ)R（2）P(PQ)(PQ)（3）P(QR) R(QP)1.4 重言式和蘊(yùn)含式 定理1.4.1 任何兩個(gè)重

15、言式的合取和析取仍然是重言式證明：假設(shè)A,B為兩個(gè)重言式，則對任意賦值，A,B真值均為T，則： AB T, AB T定理1.4.2 假設(shè)A為重言式，則對A中任何命題變量P用任何合式公式置換得到的公式B仍為重言式定理1.4.3 假設(shè)A、B為兩個(gè)命題公式，A B當(dāng)且僅當(dāng)A B為重言式 定義1. 4 .1 當(dāng)且僅當(dāng)PQ為永真式時(shí)，我們稱“P蘊(yùn)含Q”，記作PQ例1.4.1 證明下列蘊(yùn)含式（1）PQP（2） Q(PQ) P（3）(PQ) (QR) PR 基本蘊(yùn)涵式（1）PQP ;（2）PQQ；（3）PPQ；（4）QPQ；（5）P(PQ)；（6）Q(PQ)；（7）(PQ)P；（8）(PQ)Q；（9）P (

16、PQ)Q；（10）Q (PQ)P；（11）P(PQ)Q；（12）(PQ)(QR)PR；（13）(PQ)(PR) (QR)R；（14）(PQ)(RS)(PR)(QS)；（1515）( (PQ)( (QR) PR說明：A, B AB 定理1.4.4 P,Q為任意兩個(gè)命題公式PQ的充分必要條件是PQ且QP定理1.4.5 設(shè)A,B,C為合式公式（1）若AB，且A為永真式，則B為永真式（2）若AB，BC，則AC（3）若AB，AC，則A(BC)（4）若AC，BC，則(AB)C例1.4.2 邏輯推證公式： ABC,C, D,D, C CD D A B1.5 其它聯(lián)結(jié)詞和全功能集1.5 .1 其它聯(lián)結(jié)詞定義1

17、.5.1 設(shè)P,Q為兩個(gè)命題公式，復(fù)合命題“P與Q之間恰有一個(gè)成立”，稱為P與Q的排斥或，記作P Q，也稱為P與Q的不可兼析取，P Q為T當(dāng)且僅當(dāng)P與Q中有且僅有一個(gè)為T（交換律、結(jié)合律）（性質(zhì)：p24）真值表：PQP QTTFTFTFTTFFF 定理1.5.1 設(shè)P,Q,R為命題公式，若P Q R,則（1）P RQ;（2）Q RP;（3）P Q R為永假式 定義1.5.2 設(shè)P,Q為兩個(gè)命題公式，復(fù)合命題“P不蘊(yùn)涵Q”稱為P與Q的條件否定記作P Q，P Q為T當(dāng)且僅當(dāng)P為T,Q為F，顯然P Q (PQ)定義1.5.3 設(shè)P,Q為兩個(gè)命題公式，復(fù)合命題“P與Q的否定”稱為P與Q的與非式，記作P

18、Q, PQ為T當(dāng)且僅當(dāng)P,Q不同時(shí)為T，顯然PQ (PQ)性質(zhì)：p26定義1.5.4設(shè)P,Q為兩個(gè)命題公式，復(fù)合命題“P或Q的否定”稱為P與Q的或非式，記作PQ, PQ為T當(dāng)且僅當(dāng)P,Q同時(shí)為F，顯然PQ (PQ)性質(zhì)：p261.5 .2 聯(lián)結(jié)詞全功能集定義1.5.5 在一個(gè)聯(lián)結(jié)詞的集合中，如果一個(gè)聯(lián)結(jié)詞可以用集合中其余的聯(lián)結(jié)詞表示，則稱該聯(lián)結(jié)詞為冗余的聯(lián)結(jié)詞，否則稱為獨(dú)立的聯(lián)結(jié)詞前面定義的五個(gè)聯(lián)結(jié)詞組成集合 ,而PQ PQ，PQ(PQ) (QP)顯然，是冗余的，考慮集合 ,中是否有冗余？定義1.5.6 若合式公式都可用僅含某一聯(lián)結(jié)詞集合中的聯(lián)結(jié)詞來表示，則稱該集合為全功能集，若其中不包含冗余

19、的聯(lián)結(jié)詞，則稱它為極小的全功能集（ ,和 ,）1.6 對偶和范式 1.6.1 對偶對偶定義1.6.1 在僅含有聯(lián)結(jié)詞、的命題公式A中，將聯(lián)結(jié)詞換成，將換成，如果A中含有特殊變元T或F亦相互替代，所得的命題公式A*稱為A的對偶式。例：公式（PQ）（PQ） 的對偶式為：（PQ）（PQ） 例1.6.1 寫出下列公式的對偶式（1）（2）（3）PQ()()PQPR()PTR 例1.6.2 設(shè)A*（P,Q,R）為P(QR)，證明 A*(P,Q, R)A(P,Q,R) 定理1.6.1 設(shè)A和A*互為對偶式，P1,P2,Pn為其中出現(xiàn)的所有命題變量，則（1）A(P1,P2,Pn)A*(P1,P2,Pn) （2

20、）A(P1,P2,Pn)A*(P1,P2,Pn) 定理1.6.2（對偶原理） 設(shè)P1,P2,Pn為出現(xiàn)在命題公式A和B中的所有命題變量，若AB則A*B*證明：1.6.2 范式 定義1.6. 2 僅由有限個(gè)命題變元或其否定相互析取得到的公式稱為簡單析取式簡單析取式，僅由有限個(gè)命題變元或其否定相互合取得到的公式稱為簡單合取式簡單合取式 例如PQ為簡單析取式，而PQR為簡單合取式 定義1.6.3 僅由有限個(gè)簡單合取式構(gòu)成的析取式稱為析取范式析取范式；僅由有限個(gè)簡單析取式構(gòu)成的合取式稱為合取范式合取范式 例如（PQ）（PQR）為合取范式 ，而其對偶式（PQ）（PQR）為析取范式 定理（范式存在定理）定

21、理（范式存在定理）任何命題公式都存在著與之等價(jià)的析取范式和合取范式。 求合取范式和析取范式步驟（1）消去除（ ， ）外的聯(lián)結(jié)詞（2）否定號消去或內(nèi)移（3）利用分配率、結(jié)合律將公式歸約為合取范式和析取范式例1.6.3 求公式(PQ) R) P的合取范式和析取范式結(jié)論：合取范式和析取范式不唯一 練習(xí)：求下列公式合取范式和析取范式（1）(PQ) R（2） (P (QR)( P ( Q R) 1.6.3 主析取范式主析取范式定義定義1.6.3 在含有n個(gè)命題變元P1，P2，Pn的簡單合取式中，若每個(gè)命題變元或其否定不同時(shí)存在，但二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個(gè)命題變元或其否定出現(xiàn)在從左起的第i個(gè)位

22、置上（若命題變元無腳標(biāo)，則按字典順序排列，這樣的簡單合取式稱為極小項(xiàng)極小項(xiàng)。一般來說，含有n個(gè)命題變量共有2n個(gè)極小項(xiàng)個(gè)極小項(xiàng)P33列出了含有P,Q,R三個(gè)變量的所有極小項(xiàng)的真值表以及所有使得極小項(xiàng)為T的賦值，并按二進(jìn)制數(shù)給予編號 性質(zhì)：（1）指派與編碼同，則真值為T;（2）任兩個(gè)不同極小項(xiàng)合取式為永假；（3）全體極小項(xiàng)析取為永真定義1.6.4 在含有n個(gè)命題變量的命題公式A中，若A的析取范式中的簡單合取式均為極小項(xiàng)，則稱該析取范式為主析取范式求公式PQ的主析取范式定理定理1.6.4 任何命題公式的主析取范式都是存在的且是唯一的。 求主析取范式步驟：（1）求A的析取范式A（2）若A中某些簡單合

23、取式B中不含Pi或Pi，則將B展成：BB TB (Pi Pi) (B Pi ) (B Pi ) （3）將重復(fù)的極小項(xiàng)，永假式消去（4）將極小項(xiàng)按編碼從小到大排序例1.6.4 求P Q R的主析取范式定理1.6.5 在真值表中，一個(gè)公式的真值為T的指派所對應(yīng)的極小項(xiàng)的析取，即為該公式的主析取范式(另一種求解主析取范式的方法)仍以例1.6.4為例主析取范式的應(yīng)用：判斷公式等價(jià)，判斷公式類型（永真、永假等） 例 求下列各式的主析取范式（1） (PQ) (P R)（2） P Q R（3） (PQ) R定義1.6.5 在含有n個(gè)命題變元P1，P2，Pn的簡單析取式中，若每個(gè)命題變元或其否定不同時(shí)存在，但

24、二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個(gè)命題變元或其否定出現(xiàn)在從左起的第i個(gè)位置上（若命題變元無腳標(biāo)，則按字典順序排列，這樣的簡單析取式稱為極大項(xiàng)。同樣含有n個(gè)命題變量共有2n個(gè)極大項(xiàng)P36列出了含有P,Q,R三個(gè)變量的所有極大項(xiàng)使得賦值為F的二進(jìn)制數(shù)編碼1.6.4 主合取范式主合取范式 性質(zhì)性質(zhì)：（1）指派與編碼同，則真值為F;（2）任兩個(gè)不同極大項(xiàng)析取式為永真；（3）全體極大項(xiàng)合取為永假定義定義1.6.4 在含有n個(gè)命題變量的命題公式A中，若A的合取范式中的簡單析取式均為極大項(xiàng)，則稱該合取范式為主合取范式進(jìn)一步求例例1.6.3的主合取范式定理定理1.6.4 任何命題公式的主合取范式都是存在的且

25、是唯一的。 求主合取范式步驟：（1）求A的合取范式A（2）若A中某些簡單析取式B中不含Pi或Pi，則將B展成：BBFB (Pi Pi) (B Pi ) (BPi ) （3）將重復(fù)的命題變量，永真式或極大項(xiàng)都消去（4）將極大項(xiàng)按編碼從小到大排序求例1.6.4 中公式的主合取范式主合取范式同樣可用真值表法來求解（自學(xué)）比較例題可發(fā)現(xiàn)：主合取范式中未包含的編碼對應(yīng)的極小項(xiàng)組合在一起即構(gòu)成主析取范式 例1.6.5 求(P (QR)( P ( Q R) 的主析取范式和主合取范式1.7 推理理論 推理從前提推出結(jié)論的過程 前提已知的命題公式 結(jié)論從前提出發(fā)運(yùn)用推理規(guī)則所推出的命題公式 定義1.7.1 設(shè)A,B為兩個(gè)命題公式，當(dāng)且僅當(dāng)AB為永真式時(shí)，即AB，稱B為A的有效結(jié)論，或稱B可由A邏輯推出n個(gè)前提的情況： (H1H2Hn)C 稱C是H1,H2,Hn的有效結(jié)論推理方法有：（1）真值表法；（2）直接證法; （