第1部分 數(shù)理邏輯

1、 離 散 數(shù) 學(xué) 離 散 數(shù) 學(xué)第一部分 數(shù)理邏輯Discrete MathematicsLecturer： Email: mobile:ffice Address： 北7-1203D1引子：例：一位邏輯工作者協(xié)助公安人員審查一起謀殺案，經(jīng)調(diào)查，他認為下列情況均是真的。（1）會計張某或鄰居張某謀害了廠長。（2）如果會計張某謀害了廠長，則謀害不可能發(fā)生在半夜。（3）如果鄰居張某的證詞不正確，則在半夜時房里燈光未滅。（4）如果鄰居張某的證詞是正確的，則謀害發(fā)生在半夜。（5）在半夜房子里的燈光滅了，且會計張某曾貪污過。2數(shù)理邏輯邏輯學(xué)是一門研究思維概念、判斷、推理及其結(jié)構(gòu)和

2、相互關(guān)系的科學(xué)。分為形式邏輯和辯證邏輯。數(shù)理邏輯是用數(shù)學(xué)方法（即符號化）研究上述思維規(guī)律的科學(xué)。無論是計算機的雛形圖靈機，計算機的設(shè)計工具布爾代數(shù)，計算機程序的語言和算法，還是計算機自身的運算和控制，都和數(shù)理邏輯有著千絲萬縷的聯(lián)系。利用計算機來實現(xiàn)數(shù)理邏輯所表述的人類大腦思維的形式和規(guī)律。數(shù)理邏輯包括古典數(shù)理邏輯和現(xiàn)代數(shù)理邏輯，其基礎(chǔ)是邏輯演算。3第一章 命題邏輯基本概念1.1 命題與聯(lián)結(jié)詞1.2 命題公式及其賦值41.1 命題與聯(lián)結(jié)詞重點命題的概念五種基本的聯(lián)結(jié)詞命題符號化難點五種基本的聯(lián)結(jié)詞命題符號化5命題：非真即假的陳述句。例1.1 判斷下列句子中哪些是命題。(1) 北京是中國的首都 (

3、2) 所有的樹木都是植物。(3) 今天下雨。 (4) 請勿吸煙!(5) 這朵花多好看呀! (6) 請你把門關(guān)上!(7) 明天開會嗎? (8) 你到哪里去?(9) x+y5。 (10) 地球外的星球上也有人。(11) (12)我正在說謊。用真值來描述命題是“真” 還是“假”。分別用“1”和“0”表示(1),(2),(3),(10)是命題。 (11)、 (12)？一、命題的概念6命題一般用小寫字母p，q，r，p1，p2，等來表示。例1.2 命題表示。 p：地球外的星球上也有人。 q：小王是我的好朋友。理發(fā)師悖論 我只給不給自己理發(fā)的人理發(fā)。羅素悖論 我正在說謊。注意：悖論不是命題。一、命題的概念7

4、原子命題 ：基本的、原始的，不能再分解成更小的命題 。復(fù)合命題：由一個或幾個原子命題通過聯(lián)結(jié)詞的聯(lián)接而構(gòu)成的命題。例1.3 下列命題都是復(fù)合命題 (1) 雪不是白的(并非雪是白的)。 (2) 今晚我看書或者去看電影。 (3) 你去了學(xué)校，我去了工廠(省略了邏輯聯(lián)結(jié)詞”且”)。 (4) 如果天氣好，那么我去接你。 (5) 偶數(shù)a是質(zhì)數(shù)，當且僅當a=2。一、命題的概念8二、命題聯(lián)結(jié)詞自然語言中常用的一些聯(lián)結(jié)詞：1、表示否定的：非、不、沒有、無、并非2、表示同時的：并且、同時、和、也、同、與、不但而且 、雖然但是 、既又、一面一面3、表示或的：可能可能、或許或許、或4、表示條件的：若則、如果那么、只

5、有才、因為所以、僅當、除非才、除非否則 5、表示等價的：充分必要、當且僅當、有且只有9定義1.1 設(shè)p是命題，復(fù)合命題“非p”（或p的否定）稱為命題p的否定式，記為p。符號稱為否定聯(lián)結(jié)詞，并規(guī)定p為真當且僅當p為假。 pp1001二、命題聯(lián)結(jié)詞10自然語言中的“非”，“不”可符號化為。 例 1.4 設(shè)p：上海是中國的城市；q：每個自然數(shù)都是偶數(shù)。求 p， q表示的命題。則有 p：上海不是中國的城市; q：并非每個自然數(shù)都是偶數(shù)。二、命題聯(lián)結(jié)詞11定義1.2 設(shè)p，q是兩個命題，復(fù)合命題“p并且q”稱為命題p和q的合取式，記為pq。符號稱為合取聯(lián)結(jié)詞，并規(guī)定 pq為真當且僅當p，q同時為真。 p

6、qpq000010100111二、命題聯(lián)結(jié)詞12 例1.5 設(shè)p：他喜歡運動。q：他喜歡讀書。則pq表示的命題為？則pq表示“他即喜歡運動，又喜歡讀書?！?自然語言中“即又”，“不僅而且”，“雖然但是”等，都可以符號化為 二、命題聯(lián)結(jié)詞例：李大和李二是親兄弟。13定義1.3 設(shè)p，q是兩個命題，復(fù)合命題“p或q”稱為命題p和q的析取式，記為pq。符號稱為析取聯(lián)結(jié)詞，并規(guī)定 pq為假當且僅當p，q均為假。 pqpq000011101111 例1.6 設(shè)p：他喜歡運動。q：他喜歡讀書。則pq表示的命題為： 則pq表示：他喜歡運動或者喜歡讀書。二、命題聯(lián)結(jié)詞14 注意： 析取式pq表示的是一種相容性

7、或，即允許p與q同時為真。 例1.7 “王燕學(xué)過英語或法語”可符號化為pq，其中p：王燕學(xué)過英語，q：王燕學(xué)過法語。二、命題聯(lián)結(jié)詞但自然語言中，有時“或”表示排斥性或。 例1.8 派小王或者小李中的一個人去開會不能符號化為pq的形式，而是符號化為 (pq)(pq)15 結(jié)論： 對于命題p、q，若命題p與q可能同時為真，直接用析取式pq表示；否則，用(pq)(pq)表示。 例1.9 小王在圖書館或者宿舍原因：p與q不可能同時為真。不可以符號化為pq。二、命題聯(lián)結(jié)詞可以符號化為( pq)(pq）。又例：以下兩句均為 “排斥性或”。 他通過電視看雜技或到劇場看雜技。 他乘火車去北京或乘飛機去北京。1

8、6 定義1.4 設(shè)p，q是兩個命題，復(fù)合命題“若p則q”稱為命題p和q的蘊涵式，記為pq。符號稱為蘊涵聯(lián)結(jié)詞，并規(guī)定 pq為假當且僅當p為真而q為假。 pqpq001011100111 例1.10 設(shè)p：你的收入超過800元。 q：你得交納所得稅。 則pq表示的命題為？則pq：如果你的收入超過800元，那么你要交納所得稅。二、命題聯(lián)結(jié)詞17注意：1. 在自然語言中，“如果p，則q”中的p與q往往有某種內(nèi)在聯(lián)系，但在數(shù)理邏輯中“pq”中的p與q不一定有什么內(nèi)在聯(lián)系。 2. 在數(shù)學(xué)中，“如果p，則q”往往表示前件p為真，后件q為真的推理關(guān)系，但在數(shù)理邏輯中，當前件p為假時，pq也為真。二、命題聯(lián)結(jié)

9、詞3. 自然語言中， “只要p，就q”， “因為p，所以q” ， “當p,則q” “僅當q,才p” ， “只有q，才p”， “除非q，才p” ， “除非q，否則非p” 等等，都可以符號化為 pq。18幾個容易混淆的例子只要p，就q只要天氣好，我就上街。只有q成立，才有p成立只有天氣好，我才上街。當p成立，則q成立當你的收入超過800元，你要交納所得稅。僅當q，才p僅當天氣好時，我才上街。除非q成立，否則p不成立除非天氣好，否則我不上街。 等可以符號化為pq的形式。19 定義1.5 設(shè)p，q是兩個命題，復(fù)合命題“p當且僅當q”稱為p等值q，記為pq。符號稱為等值聯(lián)結(jié)詞，并規(guī)定 pq為真當且僅當p

10、與q同時為真或同時為假。 pqp q001010100111二、命題聯(lián)結(jié)詞20利用聯(lián)結(jié)詞可以把許多日常語句符號化。三、命題符號化基本步驟如下（1）從語句中分析出各原子命題，將它們符號化； （2）使用合適的命題聯(lián)結(jié)詞，把原子命題逐個聯(lián)結(jié)起來，組成復(fù)合命題的符號化表示。21例1.12 將下列命題符號化（1）派小王或小李出差。（2）我們不能既劃船又跑步。（3） 如果你來了，那么他唱不唱歌將看你是否伴奏而定。（4） 如果李明是體育愛好者，但不是文藝愛好者，那么李明不是文體愛好者。三、命題符號化22解 （1）令p：派小王出差；q：派小李出差。 則命題符號化為pq。 （2）令p：我們劃船；q：我們跑步。

11、則命題可表示為(pq)。 （3）令p：你來了；q：他唱歌；r：你伴奏。 則命題可表示為p(qr) （4）令p：李明是體育愛好者；q：李明是文藝愛好者。 則命題可表示為(pq)(pq)三、命題符號化23例1.13 將下列各命題符號化(1) 張三與李四是好學(xué)生。(2) 張三與李四是好朋友。(3) 不管你努力與否，比賽定會取勝。(4) 小王現(xiàn)在在圖書館或在宿舍。(5) 如果我上街，我就去書店，除非我很累。三、命題符號化24解：(1) p：張三是好學(xué)生。q：李四是好學(xué)生則原命題符號化為:pq(2) p: 張三與李四是好朋友。則原命題符號化為:p(3) p:管你努.q:比賽取勝。則原命題符號化為:（pp

12、）q(4) p：小王現(xiàn)在在圖書館。q：小王現(xiàn)在在宿舍。則原命題符號化為:pq(5) p：我上街。q：我去書店。r：我很累。則原命題符號化為:（pq）r 或 r（pq）三、命題符號化25命題的概念五種基本的聯(lián)結(jié)詞命題符號化 總結(jié)26練習(xí)1. 判斷下列語句哪些是命題。（1） 只有小孩才愛哭。（2） x+6=y。（3） 銀是白的。（4） 起來吧，我的朋友。 2 將下列命題符號化（1）除非你已滿16周歲，否則只要你身高不足4英尺就不能乘公園滑行鐵道。 （2）學(xué)過“離散數(shù)學(xué)”或“數(shù)據(jù)結(jié)構(gòu)”，但不是兩者都學(xué)過的學(xué)生，必須再選學(xué)“計算機算法”這門課。 271.2 命題公式及其賦值重點公式、賦值和真值表的概念

13、公式的類型難點賦值的概念28命題常元 一個表示確定命題的小寫字母命題變元 一個沒有指定具體內(nèi)容的命題符號一 、命題公式的概念 一個命題變元當沒有對其賦予內(nèi)容時，它的真值不能確定，一旦用一個具體的命題代入，它的真值就確定了。 29定義1.6 命題公式，簡稱公式，是按下列規(guī)則生成的: 命題常元和命題變元是公式 若G是公式，則G是公式(3) 若G，H是公式，則GH，GH，GH，GH都是公式(4) 只有有限次地應(yīng)用(1)(3)組成的符號串才是公式。 命題公式（或簡稱公式）是由0、1和命題變元以及命題聯(lián)結(jié)詞按一定的規(guī)則產(chǎn)生的符號串。一 、命題公式的概念30約定：(1) 公式(G)的括號可以省略，即(G)

14、寫成G。(2) 整個公式的最外層括號可以省略。例如(p(qr)可以寫成p(qr)(3)公式中聯(lián)結(jié)詞的優(yōu)先次序為：，。 在公式中，由于命題變元的出現(xiàn)，公式的真值是不確定的。只有將公式中的所有命題變元都解釋成具體的命題時，公式才變成一個有真值的命題。例 下列符號串是否為命題公式。 （1） p(qpr)； （2）(pq)(qr)一 、命題公式的概念31定義1. 8 設(shè)p1，p2，pn是出現(xiàn)在公式G中的全部命題變元。指定p1，p2，pn的一組真值，則稱這組真值為G的一個解釋或賦值。記作I，公式G在I下的真值記作TI(G) 。若TI(G) =1，則稱I為G的成真賦值，否則稱為成假賦值有n個命題變元公式共

15、有的2n個解釋例如： G (pq) r，則I：pqr011是G的一個解釋，在這個解釋下G的真值為1，即TI(G) 1二、賦值32定義1.9 將公式G在其所有解釋下所取的真值列成一個表，稱為G的真值表。公式G真值表的構(gòu)造方法：開始，按二進制順序一次寫出各個賦值，直到(2)列出G的2n個解釋，賦值從為止。然后按從低到高的順序列出G的各層(3)根據(jù)賦值計算各個層次的真值并最終計算出G的真值 (1) 找出公式G中所有的命題變元，并按一定的順序排列成p1，p2，pn 三、真值表33p q rpq(pq)prG=(pq) (pr)0 0 001000 0 101000 1 010010 1 110011

16、0 010011 0 110111 1 010011 1 11011例1.8 求出下列公式的真值表,并說明其所有的成真賦值。(1) G=(pq) (pr) (2) G=(pq) qr解： (1)公式G有3個命題變元，其真值表為：三、真值表34G=(pq) qr有3個命題變元，其真值表為：p q rpq(pq)(pq) qG= (pq) qr0 0 010000 0 110000 1 010000 1 110001 0 001001 0 101001 1 010001 1 11000三、真值表35定義 1.10 設(shè)G為公式:(1) 如果G在所有解釋下都是真的，則稱G是恒真的(或稱G是重言式);(

17、2) 如果G在所有解釋下都是假的，則稱G是恒假的(或稱G是矛盾式);(3) 如果G不是恒假的，則稱G是可滿足的。 注意：(1) 恒真公式的真值表的最后一例全為1，恒假公式的最后一例全為0，可滿足公式的最后一例至少有一個1。(2) 恒真公式一定是可滿足的，可滿足的不一定是恒真的。 四、公式類型36例 判別下列公式的類型。 （1）q( p( pq) （2）(p q) p四、公式類型37總結(jié)公式、賦值和真值表的概念公式的類型38第二章 命題邏輯等值演算392.1 等值式重點等價式的概念基本等價式等價式的判別難點基本等價式等價式的判別40一、等價公式定義2.1 設(shè)G，H是兩個公式，如果G，H在任意解釋

18、下其真值都相同，則稱G，H是等價的（等值的），記作GH。注意：(1) 符號“”與“”的區(qū)別與聯(lián)系。 “”不是聯(lián)結(jié)詞，G H不表示一個公式，它表示兩個公式間的一種關(guān)系，即等價關(guān)系。 “”是聯(lián)結(jié)詞，GH是一個公式。 G H當且僅當GH是永真公式。(2)當G是恒真式時，G 1；當G是恒假式時，則G 0。41例2.1 判斷下列公式是否等價(1) pq與pq(2) p(qr)與(pq)r 解: (1)寫出pq與pq的真值表：p qpqp qpq0 011 110 111 001 000 111 110 01表中第2列與第4列不盡相同，因此pq與pq不等價。一、等價公式42(2)寫出p(qr)與(pq)r

19、的真值表：p q rqrp(qr)pq(pq)r0 0 011010 0 111010 1 001010 1 111011 0 011011 0 111011 1 000101 1 11111表中第3列與第5列完全相同，因此p(qr)與(pq)r等價。一、等價公式431. 雙非律 (p) p 2. 冪等律 ppp ppp 3. 交換律 pqqp pqqp 4. 結(jié)合律 (pq) rp (qr) (pq) rp (qr) 5. 分配律 p (qr) (pq) (pr) p (qr) (pq) (pr) 6. 德摩根律 (pq) pq (pq) pq 二、基本的等價式447. 吸收律 p (pq)

20、 p p (pq) p 8. 零律 p00 p11 9. 同一律 p1p p0p 10. 排中律 pp1 11. 矛盾律 pp0 12. 蘊涵等價式 pqpq 13. 等值等價式 pq(pq) (qp) 14. 假言易位 pq qp 15. 歸謬論 (pq) (pq) p 二、基本的等價式45 例 用真值表方法證明 ： (pq) pq解 令：A= (pq)，B= pq，構(gòu)造A，B以及A B的真值表如下：由于公式AB所標記的列全為1，因此AB。 1、真值表方法pqpq(pq)pqpqAB00110101011110001100101010001111有兩種方法：真值表方法，命題演算方法三、等價式

21、的判別46 (1) 代入規(guī)則 2等值演算方法 例如 F=（pq）（qp）是重言式，若用公式GH代換命題變元p得公式 F1=(GH)q)(q(GH)，F(xiàn)1仍是重言式。注意：因為G H當且僅當G H是重言式。所以，若對于等價式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，則得到的仍是等價式。代入規(guī)則 對于重言式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，得到的仍是重言式。三、等價式的判別47(2) 置 換規(guī)則 例如 設(shè)公式A=(pq)(pq)(rs)。 則pq，pq，(pq)(rs)等均是A的子公式， 但p，p和q等均不是A的子公式。 置換規(guī)則 設(shè)C是公式A的子公式，CD。如果將公式A中

22、的子公式C置換成公式D之后，得到的公式是B，則AB。 定義 設(shè)C是命題公式A的一部分（即C是公式A中連續(xù)的幾個符號），且C本身也是一個命題公式，則稱C為公式A的子公式。三、等價式的判別48(3) 等值演算 等值演算是指利用已知的一些等價式，根據(jù)置換規(guī)則、代入規(guī)則以及等價關(guān)系的可傳遞性推導(dǎo)出另外一些等價式的過程。 由代入規(guī)則知前述的基本等價式，不僅對任意的命題變元陪p，q，r是成立的，而且當p，q，r分別為命題公式時，這些等價式也成立三、等價式的判別49 例2.3 證明命題公式的等價關(guān)系： （pq）（rq）（pr）q；證明 （pq）（rq） （ pq）( rq) (等值等價式) （ p r）q

23、( 分配律) (pr)q (德.摩根定律) (pr) q (等值等價式) 所以（pq）（rq）（pr）q三、等價式的判別50 例2.4 證明下列命題公式的等價關(guān)系 (p q ) ( p ( p q ) ) p q 證明 (pq)( p(pq) (pq)( (p p ) q ) (結(jié)合律) (pq)( pq) (等冪律) (p q ) ( pq ) (交換律) p(q(pq) (結(jié)合律) pq (交換律，吸收律) 三、等價式的判別51例2.5 判別下列公式的類型。 （1） q (p(pq) （2）(pq)p解（1） q（p（pq） q（p（pq） q（pp）（pq） q（1（pq） q（pq）

24、qpq （qq）p 0 所以q (p (pq)是矛盾式。 （2） （pq）p （pq）p p 于是該公式是可滿足式。 三、等價式的判別52 在自動控制和計算機中采用由電子元件組成和用信號控制的開關(guān)我們稱之為門。基本的門電路有三種：非門、或門、與門。其功能完全對應(yīng)于邏輯聯(lián)結(jié)詞， ，。 非門電路有一個輸入端和一個輸出端F=P四、應(yīng)用53或門電路有兩個或兩個以上的輸入端和一個輸出端。 F= PQ 與門電路有兩個或兩個以上的輸入端和一個輸出端。 F= P Q四、應(yīng)用54例 給定如下圖的邏輯線路圖，簡化此邏輯線路圖。四、應(yīng)用55解：由圖知，G=( P QR) (P Q) G( P Q) (R1) P Q

25、因此，原圖的等效圖為： 四、應(yīng)用56 1判斷下列等值式是否成立 （1）(pq) (r q)(pr) q （2）(pq)(p q)(pq)（2）（pq）（pq） (（pq）（qp）) (（pq）（qp）) （pq）解（1）（pq）（rq）（pq） （rq）（pr）q （pr）q（pr）q練習(xí)57總結(jié) 等價式的概念基本等價式等價式的判別真值表法等值演算582.2 析取范式與合取范式重點極小（大）項、范式、主范式的概念范式、主范式的求取難點范式、主范式的求取59 對偶公式：在只含有 ， ，3種聯(lián)結(jié)詞的公式G中，把， 互換，把0，1互換，其它符號不變，得到的新公式稱為G的對偶公式，記作G*。 定理 設(shè)

26、G與G*是一對對偶公式，則(1) G (p1，p2，pn) G*( p1， p2， pn)(2) G( p1， p2， pn) G*( p1，p2，pn)一、對偶原理60例如： (pq) (pq) p( qq) p1p(pq) (pq) p ( qq) p0p 定理(對偶原理) 設(shè)G，H是兩個公式，如果G H，則G* H*一、對偶原理61定義2.2 命題變元及其否定稱為文字；有限個文字的析取式稱為一個簡單析取式(子句)； 有限個文字的合取式稱為一個簡單合取式(短語) 。例如 若p，q，r為命題變元，則p，q，r，p，q，r都是文字，pq， pqr，pqr都為子句， pq ，pqr都為短語。一個

27、文字即是子句也是短語。 二、析取范式與合取范式62定義2.3 有限個簡單合取式的析取式稱為析取范式； 有限個簡單析取式的合取式稱為合取范式。 例如 若p，q，r為命題變元，則(pq)(pqr) (pr)為析取范式；(pq) (pq r) (pr) 為合取范式。二、析取范式與合取范式63二、析取范式與合取范式 定理2.3 (范式存在定理) 任何公式都有與之等價的合取范式和析取范式。 求范式的步驟：(1) 用pqpq及pq(pq) (qp)消去G中的與，使G只含，三種聯(lián)結(jié)詞；(2) 用(p) p及德摩根律把移到命題變元的前面并化簡；(3)反復(fù)使用分配律、交換律與結(jié)合律，得到G的合取與析取范式。64

28、 例2.7 求F1=(p(qr)s的合取范式和析取范式解 F1 (p(qr)s p(qr)s (析取范式)又 F1 p(qr)s (ps)(qr) (psq)(psr) （合取范式）二、析取范式與合取范式65例 求 F2= (pq) (pq)的析取范式、合取范式。解F2 (pq) (pq)(pq) (pq) (pq)(pq)(pq) (pq)(p(q(pq)(pq(pq) (pq)(pq) （合取范式）(p(pq)(q(pq)(pp) (pq)(pq)(qq) (pq)(pq) （析取范式）二、析取范式與合取范式66定義2.4 設(shè)有命題變元p1，p2，pn，稱為p1，p2，pn的極小項，稱為極

29、大項。其中，每一個pi*為pi或pi。注意：(1) n個變元有2n個不同的極小項；任一極小項在2n個解釋下有且僅有一個解釋使該極小項取值為1；在任一解釋下，2n個極小項中有且僅有一個取值為1。 (2) n個變元有2n個不同的極大項，任一極大項在2n個解釋下有且僅有一個解釋使該極大項取值為0；在任一解釋下，2n個極大項中有且僅有一個取值為0。三、極小項與極大項67解釋極小項記法極大項記法0 0 0pqrm0pqrM00 0 1pqrm1pqrM10 1 0pqrm2pqrM20 1 1pqrm3pqrM31 0 0 pqrm4pqrM41 0 1pqrm5pqrM51 1 0pqrm6pqrM6

30、1 1 1pqrm7pqrM7例 寫出命題變元p，q，r的所有的極小項m0，m1，m2，m3，m4，m5，m6，m7與所有的極大項M0，M1，M2，M3，M4，M5，M6，M7。三、極小項與極大項68定義2.5 設(shè)G為公式，p1，p2，pn為所有命題變元，若G的析取范式中的每個短語都是p1，p2，pn的一個極小項，則稱該析取范式為G的主析取范式。恒假公式的主析取范式為0。 定理2.5 對任意的公式G存在唯一與其等價的主析取范式。 四、主析取范式69(1) 列出公式的真值表(2) 將真值表最后一列為1的解釋的二進制數(shù)所對應(yīng)的極小項寫出(3) 將這些極小項析取起來用真值表法求主析取范式的求解步驟：

31、主析取范式的求解方法：等值演算法與真值表法四、主析取范式70例2.8 求(pq)r的主析取范式列出公式的真值表：p q rpq(pq)r對應(yīng)的極小項記號0 0 0100 0 111pqrm10 1 0100 1 111pqrm31 0 001pqrm41 0 1001 1 0101 1 111pqrm7寫出使得G取1的解釋所對應(yīng)的極小項。 G的主析取范式為m1 m3 m4 m7四、主析取范式71四、主析取范式用等值演算法求主析取范式用等值演算法求析取范式把析取范式中的每一個短語化為極小項的析取。例 用等值演算法求公式求pq的主析取范式pqpq(p(qq)(pp)q)(pq)(pq)(pq)(p

32、q)(pq)(pq)(pq) m0m1m372五、主合取范式 定義2.5 設(shè)G為公式，p1，p2，pn為所有命題變元，若G的合取范式中的每個子句都是p1，p2，pn的一個極大項，則稱該合取范式為G的主合取范式。恒真公式的主合取范式為1。 定理2.5 對任意的公式G存在唯一與其等價的主合取范式。 73(1) 列出公式的真值表(2) 將真值表最后一列為0的解釋的二進制數(shù)所對應(yīng)的極大項寫出(3) 將這些極大項合取起來用真值表法求主合取范式的求解步驟：主合取范式的求解方法：等值演算法與真值表法五、主合取范式74例2.8 求(pq)r的主合取范式列出公式的真值表：p q rpq(pq)r對應(yīng)的極大項記號

33、0 0 010pqrM00 0 1110 1 010pqrM20 1 1111 0 0011 0 100pqrM51 1 010pqrM61 1 111寫出使得G取0的解釋所對應(yīng)的極大項。 G的主合取范式為M0M2 M5 M6五、主合取范式75四、主合取范式用等值演算法求主合取范式用等值演算法求合取范式把合取范式中的每一個子句化為極大項的合取。例 用等值演算法求公式pq的主合取范式pq(p(qq)(pp)q)(pq)(pq)(pq)(pq)(pq)(pq)(pq) M0M1M276例2.9 求公式 F1= (pq)(pq)和 F2=p(p(qp)的主析取與合取范式解 F1 (pq)(pq) (

34、pq)(pq) 0 主析取范式 M0M1M2M3 主合取范式解 F2 p(p(qp) (pp) 1 主合取范式m0m1m2m3 主析取范式 五、主合取范式771. 利用主析取范式判定(1) 若公式 F(p1, p2，pn)的主析取范式包含所有2n個極小項，則 F是恒真公式。(2) 若F的主析取范式為0，則 F是恒假公式。(3) 否則，F(xiàn)為可滿足的公式。六、利用主范式判定公式類型78 2 利用主合取范式判定 (1) 若公式F（p1, p2, , pn）的主合取范式包含所有2n個極大項，則F是恒假公式。 (2) 若F的主合取范式為1，則F是恒真公式。 (3) 否則，F(xiàn)為可滿足公式六、利用主范式判定

35、公式類型79 例2.10 求公式F=(q(pq)p的主范式并判定公式的類型.解 (1) 求F的主析取范式F (q(pq)p q (pq)p (q(pp) (pq)(p(qq) （pq)(pq)(pq)(pq)(pq) (pq)(pq)(pq) 由此可知F是可滿足公式。(2) 求F的主合取范式F （q(pq)p pq六、利用主范式判定公式類型80例 張三說李四在說謊，李四說王五在說謊，王五說張三和李四都在說謊。請問3人到底誰在說謊？ 解 設(shè) p：張三說真話。 q：李四說真話。 r： 王五說真話。題意可符號化為： G=(pq) (qr) (r(p q)。構(gòu)造公式G的真值表： 七、應(yīng)用 81p q

36、rpqqrp qr(p q)G0 0 0001000 0 1011100 1 0110110 1 1100001 0 0100101 0 1110001 1 0010101 1 100000 公式G只有在解釋(0,1,0)下為真，即張三說謊話，李四說真話，王五說謊話。 七、應(yīng)用82 例 某單位要從4位甲、乙、丙、丁中挑選兩位職工去外地旅游，由于工作需要，選派時要考慮一下要求：(1) 甲、乙兩人中去且僅去一人；(2) 乙和丁不能都去；(3) 若丙去，則丁必去；(4) 若丁不去，則甲也不去。問該單位派誰去符合要求？ 解 設(shè) p：派甲去旅游。 q：派乙去旅游。 r：派丙去旅游。 s：派丁去旅游。則由

37、條件得到公式 G=(pq) (qs) (rs) ( sp)。 七、應(yīng)用83G (pqrs) (psrs) (pqrs) m4 m9 m11公式G只有在解釋(0,1,0,0) 、(1,0,0,1) 、(1,0,1,1)下為真。所以選派方案有：(1) 派乙去旅游；(2) 派甲、丁去旅游；(3) 派甲、丙、丁去旅游。由于只能派兩人去旅游，所以只有方案(2)可行。 七、應(yīng)用84 1判斷公式F=(pQ)(pQ)是否為重言式或矛盾式？解 F (pQ)(pQ)(QpP) (pQ)(pQ)(Qp) (pq)(p(qp)(q(qp) (pq)(pq)(pp)(qq)(qp) (pq)(pq)(p q) F的主析

38、取范式既非空公式，又未包含22=4個項，故F不是重言式和矛盾式，只是可滿足式。練習(xí)85總結(jié)對偶原理概念文字、句子（簡單析取式）、短語（簡單合取式）析取范式、合取范式極小項、極大項主析取范式、主合取范式范式、主范式的求取主范式的應(yīng)用862.3 聯(lián)結(jié)詞的完備集重點真值函數(shù)的概念聯(lián)結(jié)詞完備集的概念聯(lián)結(jié)詞完備集的證明難點聯(lián)結(jié)詞完備集的證明87一、真值函數(shù)定義 稱F:0,1n 0,1為n元真值函數(shù)。例如 F=pq就是0,12 0,1的2元真值函數(shù)，其定義域為00,01,10,11。n個命題變元共可構(gòu)成 個不同的真值函數(shù)。其實這些個真值函數(shù)與 個不同的主析取范式一一對應(yīng)。88二、聯(lián)結(jié)詞完備集定義 設(shè)S是一

39、個聯(lián)結(jié)詞集合，如果任何n(n1)n元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞完備集。定理 S= , , 是聯(lián)結(jié)詞完備集。推論 以下聯(lián)結(jié)詞集都是完備集。(1) , , , (2) , , , , (3) ,(4) , (5) , 89二、聯(lián)結(jié)詞完備集定義 設(shè)p、q為兩個命題，復(fù)合命題pq稱為p與非q，稱為與非聯(lián)結(jié)詞，并規(guī)定：當且僅當p和q的真值都是1時，pq的真值為0；否則pq的真值為1。定義設(shè)p、q為兩個命題，復(fù)合命題pq稱為p或非q，稱為或非聯(lián)結(jié)詞，并規(guī)定：當且僅當p和q的真值都是0時，pq的真值為1；否則pq的真值為0。定理 , 都是聯(lián)結(jié)詞完備集。90第三章 命題邏輯

40、的推理理論913.1 推理的形式結(jié)構(gòu)重點蘊涵與推理的概念基本蘊涵式蘊涵式的判定難點蘊涵式的判定92一、蘊涵的概念定理 設(shè)G，H是兩個公式，則下列條件等價。(1) 對任意的解釋I均有TI(G)TI(H);(2) 對任意解釋I，若I滿足G，則I滿足H;(3) GH是恒真公式定義 設(shè)G，H是兩個公式，若G，H滿足上述定理的條件之一，則稱G蘊涵H，記作GH。注意：和一樣，不是邏輯聯(lián)結(jié)詞。雖然G，H是公式，但GH不是公式。推理是由前提出發(fā)推出結(jié)論的思維過程。93定義3.1 設(shè)G1，G2，Gn，H是公式，稱H是G1，G2，Gn的邏輯結(jié)果。當且僅當G1G2Gn蘊涵H或(G1G2Gn) H是恒真的，記作(G1

41、G2Gn) H，也稱G1，G2，Gn蘊涵H。此時，稱由前提 G1，G2，Gn推出H的推理是有效的（或正確的），并稱H為有效結(jié)論。說明：由前提G1，G2，Gn推結(jié)論H的推理是否正確與諸前提的排列次序無關(guān)。記G G1G2Gn，對于任意的解釋，只要不出現(xiàn)G=1,H=0的情況，推理就是有效的。推理正確，并不能保證結(jié)論H一定為真。一、蘊涵的概念94一、蘊涵的概念定理3.1 G1，G2，Gn，PQ的充分必要條件是G1，G2，Gn (PQ)。 例3.1 判斷下列推理是否正確(1)、p,pqq(2)、p,qpq(3)、下午馬芳或者去看電影，或者去游泳；她沒有去看電影。所以，她去游泳了。(4)、若下午氣溫超過3

42、0，則王小燕必去游泳；若她去游泳，她就不去看電影了。所以，若王小燕沒去看電影，下午氣溫必超過了30 。95化簡 pqp 附加 ppq 假言推理 p，pqq 拒取式q， pq p 析取三段論 p，pqq 假言三段論 pq， qr pr 等價三段論 pq ， qr pr構(gòu)造性二難 pq ， rs ， pr qs二、基本蘊涵式96判定“G H”是否成立的問題可轉(zhuǎn)化為判定G H是否為重言式，有下述判定方法： （1）真值表； （2）等值演算； （3）假定前件為真 （4）假定后件為假1. 真值表方法例 證明 ：(pq)(p r)(q r) r證明 令公式 F =(pq)(pr)(qr)r， 其真值表如下：

43、三、蘊含式的判別97 公式F對任意的一組真值指派取值均為1，故F是重言式。p q rpqprqr(pq) (pr)(qr)F0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10011111111110101110111010001010111111111三、蘊含式的判別982. 等值演算方法證明 (p(pq) q (p(pq)q (p(pq)q(pp)(pq)q(pq)q 因此 p(pq) q 三、蘊含式的判別例 證明 ：p(pq) q 993. 假定前件為真假定前件G為真，檢查在此情況下，其后件H是否也為真。 例 證明 :q (pq) p證明令前件q(pq)為真

44、，則q為真, 且pq為真。于是q為假，因而p也為假。由此p為真。故蘊含式 成立。GHGH001101011101三、蘊含式的判別1004、 假定后件為假假定后件H為假，檢查在此情況下，其前件G是否也為假. 例 證明蘊含式(pq) (rs) (pr) (qs)證明 令后件(pr)(qs)為假，則pr為真，qs為假,于是p、r均為真，而q和s至少一個為假。由此可知pq與rs中至少一個為假， 因此(pq)(rs)為假。故上述蘊含式成立。三、蘊含式的判別101例 分析下列推理的正確性條件：(1) 香煙有利于健康； (2) 如果香煙有利于健康，那么醫(yī)生就會把香煙作為藥品開給病人。結(jié)論：醫(yī)生把香煙作為藥品

45、開給病人。 解 設(shè) p：香煙有利于健康 q：醫(yī)生把香煙作為藥品開給病人。則條件符號化為：p，pq。q是p，pq的邏輯結(jié)果，因此上述推理正確。四、應(yīng)用102例 分析下列推理的正確性條件：(1) 如果你投資股票，那么你能發(fā)財； (2) 如果你發(fā)財了，你就會過的很幸福。結(jié)論：如果你投資股票，你就會過的很幸福。解 設(shè) p：你投資股票 q：你發(fā)財了 r：你就過的很幸福。則條件可符號化為：pq，qr；結(jié)論符號化為pr。pr為pq，qr的邏輯結(jié)果，上述推理正確。 四、實例1031判定蘊含式p（qr） （pq）（pr）是否成立解假定后件（pq）（pr）為假，則pq為真，pr為假。由pr為假，得p為真，r為假。

46、又pq為真，于是q為真，qr為假。從而 p（qr）為假。因此蘊含式成立。練習(xí)104小結(jié)蘊涵與推理的概念基本蘊涵式蘊涵式的判定1053.2 自然推理系統(tǒng)重點推理規(guī)則及其應(yīng)用形式證明反證法難點形式證明反證法1061. 雙非律 (p) p 2. 冪等律 ppp ppp 3. 交換律 pqqp pqqp 4. 結(jié)合律 (pq) rp (qr) (pq) rp (qr) 5. 分配律 p (qr) (pq) (pr) p (qr) (pq) (pr) 6. 德摩根律 (pq) pq (pq) pq 一、推理規(guī)則基本等價式1077. 吸收律 p (pq) p p (pq) p 8. 零律 p00 p11

47、9. 同一律 p1p p0p 10. 排中律 pp1 11. 矛盾律 pp0 12. 蘊涵等價式 pqpq 13. 等值等價式 pq(pq) (qp) 14. 假言易位 pq qp 15. 歸謬論 (pq) (pq) p 一、推理規(guī)則108一、推理規(guī)則化簡PQP 附加 PPQ 假言推理 P，PQQ 拒取式Q， PQ P 析取三段論 P，PQQ 假言三段論 PQ ， QR PR 合取引入 P， Q PQ 構(gòu)造性二難 PQ ， RS ， PR QS 基本蘊涵式109一、推理規(guī)則規(guī)則P在演繹過程中可以隨便使用前提集合中任一公式。規(guī)則Q在演繹過程中可以隨便使用前面演繹出來的某些公式的邏輯結(jié)果。規(guī)則D如

48、果需要演繹出的公式具有PQ的形式，則可以將P作為附加前提使用，設(shè)法演繹出Q來。110例 證明pq，pr，r蘊涵q。編號公 式依 據(jù)(1)(2)(3)(4)(5)rprppqq規(guī)則P規(guī)則P規(guī)則Q及(1)，(2)規(guī)則P規(guī)則Q及(3)，(4)證明:二、形式證明111例3.3 證明 r(pq)是前提pq，qr，ps ，s的結(jié)論。 所以pq，qr，ps， s r(pq)編號公 式依 據(jù)（1）（2）（3）（4）（5）（6）（7）（8）spsppqqqrrr（pq）規(guī)則P規(guī)則P規(guī)則Q及(1),(2)；規(guī)則P規(guī)則Q及(3),(4)規(guī)則P規(guī)則Q及(5),(6)規(guī)則Q及(4),(7)二、形式證明112證明 編號公

49、 式依 據(jù)(1)(2)(3)(4)(5)rprpp( qs)r(qs)r(qs)規(guī)則P規(guī)則Q及(1)規(guī)則P規(guī)則Q及(2),(3)規(guī)則Q及(4)(6)(7)(8)(9) q(rs)qrsrs規(guī)則Q及(5)規(guī)則P規(guī)則Q及(6),(7)規(guī)則Q及(8)例 試證 p(qs)，rp，q 蘊涵rs二、形式證明113 例 符號化下面語句的推理過程，并指出推理是否正確?！叭绻资枪谲姡瑒t乙或丙將得亞軍；如果乙得亞軍，則甲不能得冠軍；如果丁得亞軍，丙不能得亞軍；事實是甲已得冠軍，可知丁不能得亞軍”。 解 設(shè) p：甲得冠軍；q：乙得亞軍； r：丙得亞軍；s：丁得亞軍。 推理過程符號化為 p（qr），q p，sr，p

50、 s二、形式證明114 推理過程符號化為 p（qr），q p，sr，p s編號公 式依 據(jù)（1）（2）（3）（4）p(qr)pqrqp規(guī)則P規(guī)則P則Q及（1）,（2）規(guī)則P（5）（6）（7）（8）qrs rs則Q及（2）,（4）規(guī)則Q及（3）,（5）規(guī)則P規(guī)則Q及（6）,（7）二、形式證明115編號公 式依 據(jù)(1)rp規(guī)則P(2)r規(guī)則D(附加前提)(3)p規(guī)則Q及(1)，(2)(4)p(qs)規(guī)則P(5)qs規(guī)則Q及(3)，(4)(6)q規(guī)則P(7)s規(guī)則Q及(5)，(6)(8)rs規(guī)則D及(2)，(7)試證 p(qs)，rp，q 蘊涵rs證：三、附加前提證明法116反證法（間接證明法）定

51、義 設(shè)G1，G2，Gn是公式，若至少存在一個解釋I使G1G2Gn在I下的值為1，則稱公式G1，G2，Gn是相容的;若對任意解釋I， G1G2Gn在I下的值為0，則稱公式G1，G2，Gn是不相容的。 定理1 G1G2Gn H當且僅當 G1，G2，Gn ，H是不相容的。定理2 若存在一個公式R，使得 G1G2 Gn R R則公式G1，G2，,Gn是不相容的。四、反證法117思路 為了證明G1、G2、G nH，利用定理1，只需證明G1、G2、Gn、H是不相容的。 利用定理2，只需證明R，使得 G1G2GnH RR。四、反證法118例 證明：p q、qr、rs蘊涵 p 用反證法，將(p)作為附加前提，

52、添加到前提集合中，然后推出矛盾。編號公 式依 據(jù)(1)p規(guī)則D(附加前提)(2)p q規(guī)則P(3)q規(guī)則Q及(1)，(2)(4)qr規(guī)則P(5)r規(guī)則Q及(3)，(4)(6)rs規(guī)則P(7)r規(guī)則Q及 (6)(8)r r規(guī)則Q及(5)，(7)四、反證法119總結(jié)推理規(guī)則基本等價式基本蘊涵式規(guī)則P、Q、D形式證明附加前提法反證法1201.用形式證明方法證明：pq是前提（pq）r，rs，s的結(jié)論。 因此，（pq）r， rs， s p q編號公 式依 據(jù)（1）rs規(guī)則P（2）s規(guī)則P（3）r則Q及(1),(2)（4）(pq）r規(guī)則P（5）（pq）r則Q及(4)（6）（pq）規(guī)則Q及(3),(5)（7

53、）pq規(guī)則Q及(6)練習(xí)1212.張三說李四在說謊，李四說王五在說謊，王五說張三、 李四都在說謊。問張三、李四、王五三人，到底誰說真話，誰說假話？ 解 先將簡單命題符號化。 令p：張三說真話；q：李四說真話； r：王五說真話， 由題意知推理的前提為： p q，pq，qr，qr， r（p q）， r（pq）。下面根據(jù)已知前提進行形式推理。練習(xí)122編號公 式依 據(jù)（1）p q規(guī)則P（2） qr規(guī)則P（3）pr規(guī)則Q及(1),(2)（4）r（pq）規(guī)則P（5）p（p q）則Q及(3),(4)（6）p（p q）規(guī)則Q及(5)（7）p規(guī)則Q及(6)（8）pq規(guī)則P（9）q規(guī)則Q及(7),(8)（10）

54、qr規(guī)則P（11）r規(guī)則Q及(9),(10)（12）pqr規(guī)則Q及(7),(9),(11)p q，pq，qr， qr，r（p q）， r（pq）。練習(xí)因此，由上述推理知張三說假話，王五說假話，只有李四說真話。123第四章 一階邏輯基本概念124一階邏輯（謂詞邏輯）在命題邏輯中就無法表示這種推理過程。 邏輯學(xué)中著名的蘇格拉底三段論 ：大前提p： 凡人都是要死的，小前提q: 蘇格拉底是人，結(jié) 論r： 所以蘇格拉底是要死的125一階邏輯（謂詞邏輯）命題邏輯命題被當作一個基本的，不可分割的單位。研究由原子命題和聯(lián)接詞所組成的復(fù)合命題。無法研究命題的內(nèi)部結(jié)構(gòu)及命題之間內(nèi)在的聯(lián)系。謂詞邏輯對原子命題的成份

55、、結(jié)構(gòu)和原子命題間的共同特性等作進一步分析。引入了個體詞、謂詞、量詞、謂詞公式等概念。研究謂詞公式間的等值關(guān)系和蘊含關(guān)系。對命題邏輯中的推理規(guī)則進行擴充和進行謂詞演算。1264.1 一階邏輯命題符號化 重點謂詞、量詞、個體詞的概念命題符號化難點命題符號化127一、個體詞在謂詞邏輯中，可將原子命題分解為個體詞、謂詞、量詞三部分。例 在命題邏輯中 ，對下述論斷無法判斷其正確性。 蘇格拉底三段論 ： 凡人都是要死的， 蘇格拉底是人， 所以蘇格拉底是要死的。 128一、個體詞定義 個體是指可以獨立存在的客體個體可以是抽象的，也可是具體的。個體通常在一個命題里表示思維對象。將表示具體或特定的客體的個體詞

56、稱作個體常項，一般用小寫英文字母a，b，c表示。將表示抽象或泛指的個體詞稱為個體變項，常用x，y，z表示。稱個體變項的取值范圍為個體域(或稱論域)。有一個特殊的個體域，它是由宇宙間一切事物組成的，稱它為全總個體域。在論述或推理中如沒有指明所采用的個體域，都是使用全總個體域。129二、謂詞定義 用來刻劃個體的性質(zhì)或個體之間關(guān)系的詞稱為謂詞?？虅澮粋€個體性質(zhì)的詞稱為一元謂詞；刻劃n個個體之間關(guān)系的詞稱為n元謂詞。例4.1 （1）李明是學(xué)生； （2）張亮比陳華高； （3）陳華坐在張亮與李明之間。 在這三個命題中，李明、張亮、陳華都是個體；“是學(xué)生”是一元謂詞， “比高”是二元謂詞， “坐與之間”是三

57、元謂詞。130二、謂詞一、通常用大寫字母表示謂詞，小寫字母表示個體。1、Q(x): x是學(xué)生；P(x,y): x比y高；R(x,y,z): x坐y與z之間；a:李明； b:張亮； c:陳華上述命題可分別表示為 Q(a), P(b,c), R(c,b,a)2、一般地，一個由n個個體和n元謂詞所組成的命題可表示為F(a1,a2, ,an)，其中F表示n元謂詞, a1,a2, ,an 分別表示n個個體。 3、注意：a1,a2, ,an的排列次序是重要的。二、謂詞也有常項和變項之分。1、表示具體性質(zhì)或關(guān)系的謂詞稱為謂詞常項。2、表示抽象的、泛指的性質(zhì)或關(guān)系的謂詞稱為謂詞變項。131三、量詞量詞 在命題

58、里表示數(shù)量的詞。對命題 “ 所有的正整數(shù)都是素數(shù) ” 和“ 有些正整數(shù)是素數(shù) ”僅用個體詞和謂詞是很難表達的。 132三、量詞全稱量詞 “x”例4.2 所有人都是要死的。解 個體域為全體人的集合。D(x)：x是要死的。 命題可以表示為x D(x)存在量詞 “x ” 例4.2 有些有理數(shù)是整數(shù)。解 個體域為有理數(shù)集合。令I(lǐng)(x)：x是整數(shù)。命題可以表示為x I(x)133四、命題符號化在命題符號化時，除特殊說明外，均使用全總個體域。而對個體變化的真正取值范圍，用特性謂詞加以限制。特性謂詞 ：把命題的所討論的個體從全總個體域中剝離出來的謂詞。特性謂詞的使用對全稱量詞，特性謂詞作蘊含的前件。對存在量

59、詞，特性謂詞作合取項。134四、命題符號化例4.3 (1) 所有的人都是要死的。 (2) 有的人活百歲以上。當x的個體域E為全體人組成的集合時，符號化上述命題。令D(x)：x是要死的。則(1)可表示為x D(x)。令G(x)：x活百歲以上。則(2)可表示為xG(x)。當取x的個體域為全總個體域時，必須引入一個特性謂詞將人從全宇宙的一切事物中分離出來。 令H(x)：x是人。（1）x( H(x)D(x) ) （2） x( H(x)G(x) ) 135四、命題符號化例4.4 將下列命題符號化，并討論真值。1.所有的人都長著黑頭發(fā)。2.有的人登上過月球。3.沒有人登上過木星。4.在美國留學(xué)的學(xué)生未必都

60、是亞洲人。解：1.所有的人都長著黑頭發(fā)。令 F(x)：x是人。G(x)：x長著黑頭發(fā)。則命題符號化為：x( F(x)G(x) )。2.有的人登上過月球。令 F(x)：x是人。G(x)：x登上過月球。則命題符號化為： x( H(x)G(x) ) 。136四、命題符號化3.沒有人登上過木星。令F(x)：x是人。G(x)：x登上過木星。則命題符號化為： x( H(x)G(x) ) 。4.在美國留學(xué)的學(xué)生未必都是亞洲人。令 F(x)：x在美國留學(xué)。G(x)：x是亞洲人。則命題符號化為：x( F(x)G(x) ) 。137四、命題符號化例4.5 將下列命題符號化。1.兔子比烏龜跑得快。2.有的兔子比所有