《離散數(shù)學(xué)教程》教案與習(xí)題解析 理工學(xué)院 段景輝 第1章 邏輯代數(shù)（上）：命題演算 1.1 邏輯聯(lián)結(jié)詞與命題公式 1.1.1 邏輯聯(lián)結(jié)詞 否定詞(negation)“并非”(not)，用符號(hào) （或 ~ ）表示。設(shè)p表示一命題，那么p表示命題p的否定。當(dāng)p真時(shí)p假，而當(dāng)p假時(shí)p真。p讀作“并非p”或“非p”。用類似表1.1的真值表(truth table)規(guī)定聯(lián)結(jié)詞的意義。 表1.1 p p 0 1 1 0 合取詞(conjunction)“并且”(and)，用符號(hào)∧表示。設(shè)p，q表示兩命題，那么p∧q表示合取p和q所得的命題，即當(dāng)p和q同時(shí)為真時(shí)p∧q真，否則p∧q為假。p∧q讀作“p并且q”或“p且q”。合取詞∧的意義和命題p∧q的真值狀況可由表1.2來刻劃。 表1.2 p q p∧q 0 0 1 1 0 1 0 1 0 0 0 1 析取詞(disjunction)“或”(or)用符號(hào)∨表示。設(shè)p，q表示兩命題，那么p∨q表示p和q的析取，即當(dāng)p和q有一為真時(shí)，p∨q為真，只有當(dāng)p和q均假時(shí)p∨q為假。p∨q讀作“p或者q”，“p或q”。析取詞∨的意義及復(fù)合命題p∨q的真值狀況由表1.3描述。 表1.3 p q p∨q 0 0 1 1 0 1 0 1 0 1 1 1 蘊(yùn)涵詞(implication)“如果……，那么……”(if…then…)，用符號(hào)→表示。設(shè)p，q表示兩命題，那么p→q表示命題“如果p，那么q”，它常被稱作條件命題。當(dāng)p真而q假時(shí)，命題p→q為假，否則均認(rèn)為p→q為真。p→q中的p稱為蘊(yùn)涵前件，q稱為蘊(yùn)涵后件。p→q的讀法較多，可讀作“如果p則q”，“p蘊(yùn)涵q”，“p是q的充分條件”，“q是p的必要條件”，“q當(dāng)p”，“p僅當(dāng)q”等等。數(shù)學(xué)中還常把q→p，p→q，q→p分別叫做p→q的逆命題，否命題，逆否命題。蘊(yùn)涵詞→的意義及復(fù)合命題p→q的真值狀況規(guī)定見表1.4。 表1.4 p q p→q 0 0 1 1 0 1 0 1 1 1 0 1 雙向蘊(yùn)涵詞(two-way implication)“當(dāng)且僅當(dāng)”（if and only if），用符號(hào)表示之。設(shè)p，q為兩命題，那么pq表示命題“p當(dāng)且僅當(dāng)q”，“p與q等價(jià)”，即當(dāng)p與q同真值時(shí)pq為真，否則為假。pq讀作“p雙向蘊(yùn)涵q”，“p當(dāng)且僅當(dāng)q”，“p等價(jià)于q”。由于“當(dāng)且僅當(dāng)”“等價(jià)”常在其它地方使用，因而用第一種讀法更好些。雙向蘊(yùn)涵詞的意義及pq的真值狀況由表1.5給出。 表1.5 p q pq 0 0 1 1 0 1 0 1 1 0 0 1 1.1.2 命題公式 定義1.1 歸納定義命題公式（簡(jiǎn)稱公式proposition formula）： （1）命題常元和命題變?cè)敲}公式，也稱為原子公式或原子。 （2）如果A，B是命題公式，那么(A)，(A∧B)，(A∨B)，(A→B)，(AB)也是命題公式。 （3）只有有限步引用條款（1），（2）所組成的符號(hào)串是命題公式。 定義1.2設(shè)公式A含有命題變?cè)猵1，p2，…，pn（有時(shí)用A(p1，p2，…，pn)表示這一狀況），稱p1，p2，…，pn每一取值狀況為一個(gè)指派(assignments)，用希臘字母a，b等表示，當(dāng)A對(duì)取值狀況 a 為真時(shí)，稱指派a弄真A，或a是A的弄真指派，記為a(A) = 1；反之稱指派a弄假A，或a是A的弄假指派，記為a(A) = 0。 1.1.3 語(yǔ)句形式化 將自然語(yǔ)言表述的命題“翻譯”成命題公式，常稱為語(yǔ)句形式化。語(yǔ)句形式化要注意以下幾個(gè)方面： l 要善于確定原子命題，不要把一個(gè)概念硬拆成幾個(gè)概念，例如“弟兄”是一個(gè)概念，不要拆成“弟”和“兄”、“我和他是弟兄”是一個(gè)原子命題。 l 要注意語(yǔ)句的語(yǔ)用，不同的語(yǔ)用有不同的邏輯含義。例如“狗急跳墻”可能說的是一個(gè)規(guī)律，也可能說的是一個(gè)現(xiàn)象。 l 要善于識(shí)別自然語(yǔ)言中的聯(lián)結(jié)詞（有時(shí)它們被省略）。例如“風(fēng)雨無阻，我去北京”一句，可理解為“不管是否刮風(fēng)、是否下雨我都去北京”。 l 否定詞的位置要放準(zhǔn)確。 l 需要的括號(hào)不能省略；而可以省略的括號(hào)，在需要提高公式可讀性時(shí)亦可不省略。 l 注意“只要，就”“只有，才”的正確理解。因果關(guān)系也常常用蘊(yùn)涵詞來表示，這一點(diǎn)是有爭(zhēng)議的。 l 語(yǔ)句的形式化的結(jié)果未必是唯一的。 練習(xí)1.1題解 1、選擇題 （1）設(shè)P:我將去鎮(zhèn)上，Q:我有時(shí)間。命題“我將去鎮(zhèn)上，僅當(dāng)我有時(shí)間”符號(hào)化為（ ） A．P→Q ； B. Q→P ； C. P?Q ； D. Q∨P.。 【答案】：A （2）設(shè)P:張三可以做這件事，Q李四可以做這件事。命題“張三或李四可以做這件事”符號(hào)化為（ ） A．P∨Q ； B.P∨Q ； C. P?Q ； D. (P∨Q) 【答案】：A （3）設(shè)P:我們劃船，Q:我們跑步。命題“我們不能既劃船又跑步”符號(hào)化為（ ） A．P∧Q ； B.P∨Q ； C.(P?Q) ； D. P?Q 【答案】：B （4）下列語(yǔ)句中哪個(gè)是真命題（ ） A．我正在說謊 B. 如果1+2=3，那么雪是黑的 C. 如果1+2=5，那么雪是黑的 D. 嚴(yán)禁吸煙 【答案】：C （5）P→Q的逆命題是（ ） A .Q→P B. P→Q C.Q→P D.P→Q 【答案】：A （6）下面哪一個(gè)命題是命題“2是偶數(shù)或-3是負(fù)數(shù)”的否定（ ） A．2是偶數(shù)或-3不是負(fù)數(shù) B. 2是奇數(shù)或-3不是負(fù)數(shù) C. 2不是偶數(shù)且-3不是負(fù)數(shù) D. 2是奇數(shù)且-3不是負(fù)數(shù) 【答案】：C 2、填空題 （1）下列句子中，是命題的有 . （a）我是教師。 （b）禁止吸煙。 （c）蚊子是鳥類動(dòng)物。 （d）上課去！ 【答案】：（a），（c） （2）設(shè)P：我生病，Q：我去學(xué)校 （a）命題“我雖然生病但我仍去學(xué)校”可符號(hào)化為 。 （b）命題“只有我生病的時(shí)候，我才不去學(xué)?！?可符號(hào)化為 。 （c）命題“只要我生病，我就不去學(xué)?！?可符號(hào)化為 。 （d）命題“當(dāng)且僅當(dāng)我生病，我才不去學(xué)?！?可符號(hào)化為 。 【答案】：（a）P∧Q；（b）.Q→P；（c）P→Q；（d）P?Q （3）“a≥0”表示a>0 a=0 ；“a是非負(fù)實(shí)數(shù)”表示a≥0 a是實(shí)數(shù)（在空格中填上適當(dāng)?shù)拿}聯(lián)結(jié)詞）。 【答案】：∨；∧ （4）在空格中填上表（表1.6）各列所定義的命題聯(lián)結(jié)詞： 表1.6 P Q P Q P Q 0 0 1 1 0 1 1 0 1 0 0 0 1 1 1 1 【答案】：→；? （5）P，Q為兩個(gè)命題，當(dāng)且僅當(dāng) 時(shí)，P→Q的真值為0。 【答案】：P真且Q假 （6）公式P→Q的否命題為 ，逆否命題為 。 【答案】：﹁P→﹁Q； ﹁Q→﹁P 3．將下列命題形式化： （1）你是博士，但我是碩士。 【答案】：可表示為 (p∧q)， 其中p：你是博士；q：我是碩士 （2）我今天或明天去泰山的說法是謠傳。 【答案】：可表示為 (p∨q)，其中p：我今天去泰山；q：我明天去泰山 （3）如果買不到飛機(jī)票，我不去海南島。 【答案】：可表示為p→q，其中，p：我買到飛機(jī)票，q：我去海南島 （4）只要他出門，他必買書，不管他帶的錢多不多。 【答案】：可表示為(p∧q→r)∧(p∧q→r)或q→r，其中p：他帶的錢多，q：他出門，r：他買書。 （5）除非你陪伴我或代我雇輛車子，否則我不去。 【答案】：可表示為(p∨q) ? r，其中p：你陪伴我，q：你代我雇車，r：我去 （6）只要充分考慮一切論證，就可得到正確見解；必須充分考慮一切論證，才能得到正確見解。 【答案】：可表示為(p→q) ∧(q→p )或p q，其中p：你充分考慮了一切論證，q：你得到了正確見解 （7） 除非你是成年人，否則只要你身高不超過1米3，就能到兒童游樂場(chǎng)玩耍。 r? (s→t)，其中r：你是成年人，s：你身高超過1米3，t: 你到兒童游樂場(chǎng)玩耍 （8）如果只有懂得希臘文才能了解柏拉圖，那么我不了解柏拉圖。 【答案】：可表示為(q→p ) →q，其中p：我懂得希臘文，q：我了解柏拉圖 （9）侈而惰者貧，而力而儉者富。（韓非：《韓非子顯學(xué)》） 【答案】：可表示為((p∧q)→r) ∧((p∧q)→r)，其中p：你奢侈，q：你懶惰，r：你貧困 （10）騏驥一躍，不能十步；駑馬十駕，功在不舍；鍥而舍之，朽木不折；鍥而不舍，金石可鏤。（荀況：《荀子勸學(xué)》） 【答案】：可表示為(p→q) ∧(s→r) ∧(m∧n→o) ∧(m∧n→v)，其中p：騏驥一躍，q：騏驥行十步，r：駑馬行千里，s：駑馬不斷奔跑，m：你雕刻，n：你放棄，o：你將朽木折斷，v：你將金石雕刻 4．根據(jù)命題公式的定義和括號(hào)省略的約定，判定下列符號(hào)串是否為公式，若是，請(qǐng)給出它的真值表，并請(qǐng)注意這些真值表的特點(diǎn)（p,q,r,s為原子命題）： （1） (p) 【答案】： (p) 不是公式 （2）(p∨qr)→s 【答案】：(p∨qr)→s 不是公式 （3）(p∨q)→p 【答案】：(p∨q)→p 是公式，其真值表如表1.7所示： 表1.7 p q p∨q (p∨q)→p 0 0 0 1 0 1 1 0 1 0 1 1 1 1 1 1 （4）p→(p∨q) 【答案】：p→(p∨q) 是公式，其真值表如表1.8所示（恒真）： 表1.8 p q p∨q p→(p∨q) 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 1 （5）p∧(p→q)→q 【答案】：p∧(p→q)→q 是公式，其真值表如表1.9所示（恒真）： 表1.9 p q p→q p∧(p→q) p∧(p→q)→q 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1 （6）p∧(p→q)∧(p→q) 【答案】：p∧(p→q)∧(p→q) 是公式，其真值表如表1.10所示（恒假）： 表1.10 p q ┐q p→q p∧(p→q) p→┐q p∧(p→q)∧(p→q) 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 （7） (p∨q) q∧p 【答案】： (p∨q) q∧p 是公式，其真值表如表1.11所示（恒真）： 表1.11 p q p q p∨q (p∨q) q∧p (p→q) ( q→ p) 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 1 （8） p∨q (p→q) 【答案】： p∨q(p→q) 是公式，其真值表如表1.12所示（恒真）： 表1.12 p q p p∨q p→q p∨q (p→q) 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 （9）(p→q)∧(q→r)→(p→ r ) 【答案】：(p→q)∧(q→r)→(p→r) 是公式，其真值表如表1.13所示（恒真）： 表1.13 p q r p→q q→r p→r (p→q)∧(q→r) (p→q)∧(q→r)→(p→r) 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 （10）(p∨q→r) (p→r)∧(q→r) 【答案】：(p∨q→r) (p→r)∧(q→r) 是公式，其真值表如表1.14所示（恒真）： 表1.14 p q r p∨q p∨q→r p→r q→r (p→r)∧(q→r) (p∨q→r) (p→r)∧(q→r) 0 0 0 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 5．給出弄真下列命題公式的指派： （1）((p→q)∧q)→┐p 【答案】：弄真指派有(0,0)，(0,1)，(1,0) （2）((p→q)→r)→((q→p)→r) 【答案】：弄真指派有(0,0,0)，(0,0,1)，(0,1,0)，(0,1,1)，(1,0,1)，(1,1,0)，(1,1,1) （3）((pq)→r)→((q→p) r) 【答案】：弄真指派有(0,0,0)，(0,0,1)，(0,1,0)， (1,0,1)，(1,1,0)，(1,1,1) （4） ((p∨q)∧r)→(r→p) 【答案】：弄真指派有(0,0,0)，(0,1,0)， (0,1,1)，(1,0,0)，(1,0,1)，(1,1,0)，(1,1,1) 1.2 邏輯等價(jià)式和邏輯蘊(yùn)涵式 1.2.1 重言式 定義1.3 如果對(duì)命題公式A中命題變?cè)囊磺兄概删鍭，那么，稱A為重言式(tautology)；重言式又稱永真式；如果至少有一個(gè)這樣的指派弄真A，那么，稱A為可滿足式(satisfactable formula)，否則稱A為不可滿足式或永假式、矛盾式。 1.2.2 邏輯等價(jià)式和邏輯蘊(yùn)涵式 定義1.4 當(dāng)命題公式AB為永真式時(shí)，稱A邏輯等價(jià)于B，記為A┝┥B，它又稱為邏輯等價(jià)式(logically equivalent)。 以下是一些重要的邏輯等價(jià)式，其中A，B，C表示任意命題公式： E1 A┝┥A 雙重否定律 E2 A∨A┝┥A ，A∧A┝┥A 冪等律 E3 A∨B┝┥B∨A ，A∧B┝┥B∧A 交換律 E4 (A∨B)∨C┝┥A∨(B∨C) 結(jié)合律 (A∧B)∧C┝┥A∧(B∧C) E5 A∧(B∨C)┝┥(A∧B)∨(A∧C) 分配律 A∨(B∧C)┝┥(A∨B)∧(A∨C) E6 (A∨B)┝┥A∧B 德摩根律 (A∧B)┝┥A∨B E7 A∨(A∧B)┝┥A 吸收律 A∧(A∨B)┝┥A E8 A→B┝┥A∨B E9 A B┝┥(A→B)∧(B→A) E10 A∨t┝┥t ， A∧f┝┥f E11 A∨f┝┥A ， A∧t┝┥A E12 A∨A┝┥t ，A∧A┝┥f E13 t┝┥f, f┝┥t E14 A∧B→C┝┥A→(B→C) E15 A∨B→C┝┥(A→C)∧(B→C) E16 A→B┝┥B→A E17 (A→B)∧(A→B)┝┥A E18 A B┝┥(A∧B)∨(A∧B) 定義1.5 當(dāng)命題公式A→B為永真式時(shí)，稱A邏輯蘊(yùn)涵B，記為A┝ B，它又稱為邏輯蘊(yùn)涵式(logically implication)。 一些十分重要的邏輯蘊(yùn)涵式： I1 A┝ A∨B，B┝ A∨B I2 A∧B┝ A，A∧B┝ B I3 B┝A→B I4 A∧(A→B)┝ B I5 (A→B)∧B┝A I6 A∧(A∨B)┝ B，B∧(A∨B)┝ A I7 (A→B)∧(B→C)┝ A→C I8 (A→B)∧(C→D)┝ (A∧C)→(B∧D) I9 (AB)∧(BC)┝ AC I10 A┝ t ； f┝ A 邏輯等價(jià)式與邏輯蘊(yùn)涵式有如下明顯性質(zhì)。 定理1.1 對(duì)任意命題公式A，B，C，A，B， （1）A┝┥B當(dāng)且僅當(dāng)┝ AB （2）A┝ B當(dāng)且僅當(dāng)┝ A→B （3）若A┝┥B，則B┝┥A （4）若A┝┥B，B┝┥C，則A┝┥C （5）若A┝ B，則┐B┝ ┐A （6）若A┝ B，B┝ C，則A┝ C （7）若A┝ B，A┝┥A，B┝┥B，則A┝ B 定理1.2 設(shè)A為永真式，p為A中命題變?cè)?，A(B/p)表示將A中p的所有出現(xiàn)全部代換為公式B后所得的命題公式（稱為A的一個(gè)代入實(shí)例），那么A(B/p)亦為永真式。 定理1.2常被稱為代入原理(rule of substitution)，簡(jiǎn)記為RS 定理1.3 設(shè)A為一命題公式，C為A的子公式，且C┝┥D。若將A中子公式C的某些（未必全部）出現(xiàn)替換為D后得到的公式記為B，那么A┝┥B。 定理1.3常被稱為替換原理(rule of replacement)簡(jiǎn)記為RR。 請(qǐng)注意RS與RR的區(qū)別，詳見表1.15。 表1.15 代入原理 RS 替換原理 RR 使用對(duì)象 任意永真式 任一命題公式 被代換對(duì)象 任一命題變?cè)? 任一子公式 代換對(duì)象 任一命題公式 任一與代換對(duì)象等價(jià)的命題公式 代換方式 代換同一命題變?cè)乃谐霈F(xiàn) 代換子公式的某些出現(xiàn) 代換結(jié)果 仍為永真式 與原公式等價(jià) 當(dāng)然，證明邏輯蘊(yùn)涵式A┝ B不成立的方法只有一個(gè)，那就是：找出一個(gè)指派使得A為真，卻使 B為假。證明邏輯等價(jià)式A┝┥B不成立的方法是：證明A┝ B不成立或者證明B┝A不成立。推而廣之，為證 G┝ B（G 為公式集合）不成立，只要找出一個(gè)指派使得G中所有公式為真，卻使B為假。 1.2.3 對(duì)偶原理 定義1.6 設(shè)公式A僅含聯(lián)結(jié)詞 ，∧，∨，A*為將A中符號(hào)∧，∨，t，f分別改換為∨，∧，f，t后所得的公式，那么稱A*為A的對(duì)偶(dual)。 下面兩定理所描述的事實(shí)常稱為對(duì)偶原理。 定理1.4 設(shè)公式A中僅含命題變?cè)猵1,…,pn，及聯(lián)結(jié)詞，∧，∨，那么 A┝┥A* (p1／p1，…，pn／pn) 這里，A* (p1／p1，…，pn／pn)表示在A*中對(duì)p1,…,pn分別作代入p1,…, pn后所得的公式。 定理1.5 設(shè)A，B為僅含聯(lián)結(jié)詞，∧，∨和命題變?cè)猵1,…,pn的命題公式，且滿足A┝B，那么有B*┝ A*。進(jìn)而當(dāng)A┝┥B時(shí)有A*┝┥B*。 定義1.7 B*┝ A*，A*┝┥B*分別稱為A┝ B和A┝┥B的對(duì)偶式。 1.2.4 應(yīng)用邏輯 命題邏輯的相關(guān)知識(shí)，特別是邏輯等價(jià)式和邏輯蘊(yùn)含式所反映的邏輯思維規(guī)律，如，排中律、矛盾律、雙重否定律、德摩根律等，是人們邏輯推理的基礎(chǔ)，在邏輯訓(xùn)練和實(shí)際生活中有十分廣泛的應(yīng)用。 練習(xí)1.2題解 1．選擇題 （1）K是重言式，那么K的否定是（ ） A.重言式 B.矛盾式 C.可滿足式 D. 不能確定 【答案】：B （2）K不是重言式，那么它是（ ） A.永假式 B.矛盾式 C.可滿足式 D.不能確定 【答案】：C （3）命題公式(P∧(P→Q)) →Q是（ ） A．矛盾式 B. 可滿足式 C. 重言式 D. 不能確定 【答案】：C （4）命題公式(P∧(P∨Q)) ∧Q是（ ） A．矛盾式 B. 可滿足式 C. 重言式 D. 不能確定 【答案】：B （5）如果P→Q為真時(shí)我們稱命題P強(qiáng)于Q，那么最強(qiáng)的命題是（ ），最弱的命題是（ ）。 A．永假式 B. 可滿足式 C. 永真式 D. 不能確定 【答案】：A，C 2．填空題 （1）兩個(gè)重言式的析取是 ，一個(gè)重言式與一個(gè)矛盾式的析取是 。 兩個(gè)重言式的合取是 ，一個(gè)重言式與一個(gè)矛盾式的合取是 。 一個(gè)重言式蘊(yùn)涵一個(gè)矛盾式的是 ，一個(gè)矛盾式蘊(yùn)涵一個(gè)重言式的是 。 【答案】：重言式，重言式，重言式，矛盾式，矛盾式，重言式 （2）在下列各式中，是永真式的有 。 （a）(P∧(P→Q)) →Q （b）P→(P∨Q) （c）Q→(P∧Q) （d）(﹁P∧(P∨Q))→Q （e）(P→Q)→Q 【答案】：(a)，（b），（d） （3）化簡(jiǎn)下列各式： （a）(﹁P∧Q) ∨(﹁P∧﹁Q)可化簡(jiǎn)為 。 （b）Q→(P∨(P∧Q))可化簡(jiǎn)為 。 （c）((﹁P∨Q)?(Q∨﹁P))∧P可化簡(jiǎn)為 。 【答案】：（a）﹁P；（b）Q→P；（c）P （4）公式(P∨Q)→R的只含聯(lián)結(jié)詞，∧的等價(jià)式為 ，它的對(duì)偶式為 。 【答案】：((P∧Q)∧R)；(P∧Q) ∧R 3．試判定以下各式是否為重言式： （1）(p→q)→(q→p) 【答案】：否 （2）﹁p→(p→q) 【答案】：是 （3）q→(p→q) 【答案】：是 （4）p∧q→(pq) 【答案】：是 （5）(p→q)∨(r→q)→((p∨r)→q) 【答案】：否 （6）(p→q)∨(r→s)→((p∨r)→(q∨s)) 【答案】：否 4．試用真值表驗(yàn)證E6，E8，E15，E17。 （1）【答案】： E6 ﹁(A∨B)┝┥﹁A∧﹁B的真值表如表1.16所示： 表1.16 A B A∨B ﹁(A∨B) ﹁A ﹁B ﹁A∧﹁B ﹁(A∨B) ﹁A∧﹁B 0 0 0 1 1 1 1 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 0 0 0 1 ﹁(A∧B)┝┥﹁A∨﹁B的真值表如表1.17所示： 表1.17 A B A∧B ﹁(A∧B) ﹁A ﹁B ﹁A∨﹁B ﹁(A∧B) ﹁A∨﹁B 0 0 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 0 0 1 0 1 1 1 1 1 1 0 0 0 0 1 （2）【答案】： E8 A→B┝┥﹁A∨B的真值表如表1.18所示： 表1.18 A B A→B ﹁A ﹁A∨B A→B﹁A∨B 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 （3）【答案】：E15 A∨B→C┝┥(A→C)∧(B→C) 的真值表如表1.19所示： 表1.19 A B C A∨B A∨B→C A→C B→C (A→C)∧(B→C) (A∨B→C)(A→C)∧(B→C) 0 0 0 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 （4）【答案】：E17 (A→B)∧(A→B)┝┥A的真值表如表1.20所示： 表1.20 A B A→B A→B (A→B)∧(A→B) A (A→B)∧(A→B) A 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 0 1 5．不用真值表，用代入、替換原理證明E16，E17。 （1）E16 A→B┝┥B→A 【答案】： A→B┝┥﹁A∨B 據(jù)E8 ┝┥﹁A∨﹁ (﹁B) 　　　據(jù)E1用RR ┝┥B→A 　　　 對(duì)E8用RS （2）E17 (A→B)∧(A→﹁B)┝┥﹁A 【答案】：(A→B)∧(A→﹁B)┝┥(﹁A∨B) ∧(﹁A∨﹁B) 據(jù)E8用RR ┝┥﹁A∨ (B∧﹁B) 對(duì)E5用RS ┝┥﹁A∨f 據(jù)E12用RR ┝┥﹁A 據(jù)E11用RS 6．試用真值表驗(yàn)證I3，I4，I6，I7。 （1）【答案】： I3 B┝A→B的真值表如表1.21所示： 表1.21 A B A→B B→(A→B) 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 1 （2）【答案】：I4 A∧ (A→B)┝B的真值表如表1.22所示： 表1.22 A B A→B A∧ (A→B) A∧ (A→B) →B 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1 （3）【答案】：I6 ﹁A∧(A∨B) ┝B 的真值表如表1.23所示： 表1.23 A B ﹁A A∨B ﹁A∧(A∨B) ﹁A∧(A∨B)→B 0 0 1 0 0 1 0 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 0 1 ﹁B∧(A∨B) ┝A的真值表如表1.24所示： 表1.24 A B ﹁B A∨B ﹁B∧(A∨B) ﹁B∧(A∨B)→A 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1 0 1 （4）【答案】：I7 (A→B) ∧(B→C) ┝(A→C) 的真值表如表1.25所示： 表1.25 A B C A→B B→C A→C (A→B)∧(B→C) I7 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 7．不用真值表，用代入、替換原理證明I8，I9 。 【答案】：（1）I8：(A→B)∧(C→D)┝ (A∧C)→(B∧D) 證 (A→B)∧(C→D) ∧(A∧C) ┝┥(﹁A∨B)∧(﹁C∨D) ∧(A∧C) ┝┥(﹁A∧﹁C∧A∧C) ∨(B∧﹁C∧A∧C) ∨(﹁A∧D∧A∧C) ∨(B∧D∧A∧C) ┝┥f∨f∨f∨(A∧B∧C∧D) ┝┥A∧B∧C∧D ┝B∧D 因此，(A→B)∧(C→D) ∧(A∧C) →(B∧D)為一重言式 又(A→B)∧(C→D) ∧(A∧C) →(B∧D) ┝┥(A→B)∧(C→D) →((A∧C) →(B∧D)) 所以(A→B)∧(C→D) →((A∧C) →(B∧D)) 為一重言式 即(A→B)∧(C→D)┝ (A∧C)→(B∧D) 【答案】：（2）I9：(AB)∧(BC)┝ (AC) 證 (AB)∧(BC)∧A ┝┥(A→B)∧(B→A)∧(B→C)∧(C→B)∧A ┝ (A→B)∧(B→C)∧A ┝┥(﹁A∨B) ∧(﹁B∨C) ∧A ┝┥(﹁A∧﹁B∧A) ∨(﹁A∧C∧A) ∨(B∧﹁B∧A) ∨(B∧C∧A) ┝┥f∨f∨f∨(A∧B∧C) ┝┥A∧B∧C ┝ C 因此，(AB)∧(BC)∧A →C為一重言式 又(AB)∧(BC)∧A →C ┝┥(AB)∧(BC)→(A →C) 所以(AB)∧(BC)→(A →C) 為一重言式 仿上可證(AB)∧(BC)→(C →A) 為一重言式 又根據(jù)（1），((AB)∧(BC)→(A →C)) ∧((AB)∧(BC)→(C →A)) ┝(AB)∧(BC) →(A →C) ∧(C →A) ┝┥(AB)∧(BC) →(AC) 所以(AB)∧(BC) →(AC)也是重言式， 即(AB)∧(BC)┝ (AC) 8．用三種不同方法證明下列邏輯等價(jià)式和邏輯蘊(yùn)涵式： （1）AB┝┥(A∧B)∨(﹁A∧﹁B) 【答案】證法1：真值表（表1.26）的最后兩列等值，故AB┝┥(A∧B)∨(﹁A∧﹁B) 表1.26 A B A∧B ﹁A ﹁B ﹁A∧﹁B AB (A∧B)∨(﹁A∧﹁B) 0 0 0 1 1 1 1 1 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 證法2：AB┝┥(A→B)∧(B→A) ┝┥(﹁A∨B)∧(﹁B∨A) ┝┥(﹁A∧﹁B)∨(﹁A∧A)∨(B∧﹁B)∨(B∧A) ┝┥(A∧B)∨(﹁A∧﹁B) 證法3： 先證AB┝ (A∧B)∨(﹁A∧﹁B) (a) 設(shè)a為任一指派，使(AB)=1，那么a (A)= a (B)=1或a(A)= a (B)=0，從而 a (A∧B)=1或a (﹁A∧﹁B)=1，即a ((A∧B)∨(﹁A∧﹁B))=1。(a)得證； 再證(A∧B)∨(﹁A∧﹁B)┝ AB (b) 設(shè)a為任一指派，使a (AB)=0，那么a (A)=1，a(B)=0，或者a(A)=0，a a(B)=1，從而a(A∧B)=0且a (﹁A∧﹁B)=0，即a ((A∧B)∨(﹁A∧﹁B))=0。(b)得證。 （2）A→(B→C)┝┥B→(A→C) 【答案】證法1：真值表（表1.27）的最后兩列等值，故A→(B→C)┝┥B→(A→C) 表1.27 A B C B→C A→C A→(B→C) B→(A→C) 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 證法2：A→(B→C)┝┥﹁A∨(﹁B∨C) ┝┥(﹁A∨﹁B)∨C ┝┥(﹁B∨﹁A)∨C ┝┥﹁B∨(﹁A∨C) ┝┥B→(A→C) 證法3：先證A→(B→C)┝ B→(A→C) (a) 設(shè)a為任一指派，使a (A→(B→C))=1，那么 ?。゛ (A)= 0，則a ( A→C)=1，從而a ( B→(A→C))=1 ⅱ）a (A)= 1，a (B)=0，則a ( B→(A→C))=1 ⅲ）a (A)= a (B)=a (C)=1，則a ( B→(A→C))=1 綜上，(a)得證；同理可證B→(A→C)┝ A→(B→C)。 （3）A→(A→B)┝┥A→B 【答案】證法1：真值表（表1.28）的最后兩列等值，故A→(A→B)┝┥A→B 表1.28 A B A→B A→(A→B) 0 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1 證法2：A→(A→B)┝┥A∧A→B ┝┥A→B 證法3：先證A→(A→B)┝ A→B (a) 設(shè)a為任一指派，使a( A→B)=0，那么a (A)=1，a(B)=0，從而 a ( A→(A→B))=0。(a)得證； 再證A→B┝ A→(A→B) (b) 設(shè)a為任一指派，使a (A→(A→B))=0，那么a (A)=1，a (A→B)=0。(b)得證。 （4）A→(B→C)┝┥(A→B)→(A→C) 【答案】證法1：真值表（表1.29）的最后兩列等值，故A→(B→C)┝┥(A→B)→(A→C) 表1.29 A B C B→C A→B A→C A→(B→C) (A→B)→(A→C) 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 1 1 1 1 證法2：(A→B)→(A→C)┝┥﹁(﹁A∨B) ∨ (﹁A∨C) ┝┥(A∧﹁B) ∨ (﹁A∨C) ┝┥( (A∧﹁B)∨﹁A)∨C ┝┥((A∨﹁A)∧(﹁B∨﹁A) )∨C ┝┥(t∧(﹁A∨﹁B) )∨C ┝┥(﹁A∨﹁B)∨C ┝┥﹁A∨(﹁B∨C) ┝┥A→(B→C) 證法3：先證A→(B→C)┝ (A→B)→(A→C) (a) 設(shè)a為任一指派，使a ((A→B)→(A→C))=0，那么a( A→B)=1，a a(A→C)=0，即a(A)=a(B)=1，a(C)=0，從而a(B→C)=0，a a ( A→(B→C))=0。(a)得證； 再證(A→B)→(A→C)┝ A→(B→C) (b) 設(shè)a為任一指派，使a ( A→(B→C))=0，那么a (A)=1，aa (B→C)=0，即 a a(B)=1，a(C)=0，從而a(A→B)=1，a (A→C)=0，a ((A→B)→(A→C))=0。(b)得證。 （5）(A→B)→A┝ A 【答案】證法1：真值表（表1.30）的最后一列均取值1，故(A→B)→A┝ A 表1.30 A B A→B (A→B)→A ((A→B)→A) → A 0 0 1 0 1 0 1 1 0 1 1 0 0 1 1 1 1 1 1 1 證法2：(A→B)→A┝┥ ﹁(﹁A∨B) ∨ A ┝┥ (A∧﹁B) ∨ A ┝┥ (A∨ A)∧(﹁B∨A) ┝┥ A∧(﹁B∨A) ┝ A 證法3：設(shè)a為任一指派，使a(A)=0，則a (A→B)= 1，從而a((A→B)→A)=0。(A→B)→A┝ A得證。 （6）(A∨B)∧(A→C)∧(B→C)┝ C 【答案】證法1：真值表（表1.31）的最后一列均取值1，故(A∨B)∧(A→C)∧(B→C)┝ C 表1.31 A B C A∨B A→C B→C (A∨B)∧(A→C)∧(B→C) ((A∨B)∧(A→C)∧(B→C))→C 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 證法2：(A∨B)∧(A→C)∧(B→C) ┝┥(A∨B)∧(﹁A∨C)∧(﹁B∨C) ┝┥(A∨B∨(C∧﹁C))∧(﹁A∨(B∧﹁B)∨C)∧( (A∧﹁A) ∨﹁B∨C) ┝┥(A∨B∨C)∧(A∨B∨﹁C)∧(﹁A∨B∨C)∧(﹁A∨﹁B∨C)∧(A∨﹁B∨C) ┝ (A∨B∨C)∧(A∨﹁B∨C)∧(﹁A∨B∨C)∧(﹁A∨﹁B∨C) ┝┥(A∨C) ∧(﹁A∨C) ┝┥C 證法3：設(shè)a為任一指派，使a((A∨B)∧(A→C)∧(B→C))=1，則 a(A∨B)=a ( A→C)= a ( B→C)=1。由a (A∨B)=1有兩種情況： （?。゛ (A)=1，由a ( A→C)=1得a (C)=1； （ⅱ）a (B)= 1，由a ( B→C)=1得a (C)=1。 (A∨B)∧(A→C)∧(B→C)┝ C得證。 9．證明下列邏輯蘊(yùn)涵式或推理不成立： （1）AB┝A∧B 【答案】證. 指派a(A)=a(B)=0使得AB為真，而使得A∧B為假，因此邏輯蘊(yùn)涵式AB┝A∧B不成立。 （2）(A→B)→A┝ B 【答案】證. 指派a(A)=1,a(B)=0使得(A→B)→A為真，而使得B為假，因此邏輯蘊(yùn)涵式(A→B)→A┝ B不成立。 （3） 【答案】：令p表示“我有錢”，q表示“我買書”，r表示“我去淮海路”，那么前提是pq，qr和 q， 結(jié)論是 r 。取指派a，使得a(p)=0, a(q)=0, a(r)=1。那么，a(pq)=1，a(qr)=1，a(q)=1, 但a(r)=0。因此，本推理無效。 10．驗(yàn)證下列邏輯等價(jià)式和邏輯蘊(yùn)涵式，并寫出它們的對(duì)偶式： （1）﹁(﹁A∨﹁B)∨﹁(﹁A∨B)┝┥A 【答案】解. ﹁(﹁A∨﹁B)∨﹁(﹁A∨B)┝┥(A∧B)∨(A∧﹁B) ┝┥A∧(B∨﹁B) ┝┥A 對(duì)偶式為 ﹁(﹁A∧﹁B)∧﹁(﹁A∧B)┝┥A （2）(A∨﹁B)∧(A∨B)∧(﹁A∨﹁B)┝┥﹁(﹁A∨B) 【答案】解. (A∨﹁B)∧(A∨B)∧(﹁A∨﹁B)┝┥A∧(B∨﹁B)∧(﹁A∨﹁B) ┝┥A∧(﹁A∨﹁B) ┝┥A∧﹁B ┝┥﹁(﹁A∨B) 對(duì)偶式為 (A∧﹁B)∨(A∧B)∨(﹁A∧﹁B)┝┥﹁(﹁A∧B) （3）B∨﹁((﹁A∨B)∧A)┝┥t 【答案】解. B∨﹁((﹁A∨B)∧A)┝┥B∨((A∧﹁B)∨﹁A) ┝┥B∨(﹁B∨﹁A) ┝┥t 對(duì)偶式為 B∧﹁((﹁A∧B)∨A)┝┥f （4）﹁A∨(﹁B∨C)┝﹁(﹁A∨B)∨(﹁A∨C) 【答案】解.﹁A∨(﹁B∨C)┝ (A∨﹁A∨C) ∧(﹁B∨﹁A∨C) ┝ (A∧﹁B)∨(﹁A∨C) ┝ ﹁(﹁A∨B)∨(﹁A∨C) 對(duì)偶式為 ﹁(﹁A∧B)∧(﹁A∧C)┝﹁A∧(﹁B∧C) （5）﹁(A∨B)∨C┝ A∨(﹁B∨C) 【答案】解.﹁(A∨B)∨C┝ (﹁A∧﹁B)∨C ┝ (﹁A∨C)∧(﹁B∨C) ┝﹁B∨C ┝ A∨(﹁B∨C) 對(duì)偶式為 A∧(﹁B∧C)┝ ﹁(A∧B)∧C （6）﹁(A∨B)┝ A∨(﹁B∨C) 【答案】解. ﹁(A∨B)┝﹁(A∨B)∨C ┝ (﹁A∧﹁B)∨C ┝ (﹁A∨C)∧(﹁B∨C) ┝﹁B∨C ┝ A∨(﹁B∨C) 對(duì)偶式為 A∧(﹁B∧C)┝ ﹁(A∧B) 11．某班級(jí)有位學(xué)員為集體做了一件好事，他是甲、乙、丙、丁四人之一。當(dāng)教員問及時(shí)，他們的回答是： 甲：我沒有做這件好事。 乙：這件好事是丁做的。 丙：我不知道這件好事是誰做的。 ?。哼@件好事不是我做的。 如果他們中只有一個(gè)人說了假話，你能斷定是誰做了好事嗎？ 【答案】解. 根據(jù)排中律，乙和丁之中必有一個(gè)是說假話的。因此，甲說了真話，丙也說了真話，好事必定是乙或丁做的。當(dāng)乙說假話時(shí)，那么這件好事就應(yīng)不是丁做，所以此時(shí)丁說的是真話，那么好事就是乙做的；如果乙說的是真話，那么這件好事就是丁做的，那么丁說的就是假話。僅從四個(gè)人的回答無法判斷出究竟是乙還是丁做的好事。 12．籃球教練按以下原則安排球員上場(chǎng)：如果1號(hào)上場(chǎng)，同時(shí)3號(hào)上場(chǎng)時(shí)，那么5號(hào)，7號(hào)至少有一個(gè)要上場(chǎng)。問：1號(hào)隊(duì)員不上場(chǎng)的充分條件是什么？ 【答案】解. 用1，3，5，7分別表示1號(hào)、3號(hào)、5號(hào)、7上場(chǎng)，那么教練的原則可表示為： (13)(57)，而 (13)(57) ┝┥(57)(13) ┝┥(57)(31) ┝┥(357)1。 因此，1號(hào)隊(duì)員不上場(chǎng)的充分條件是3號(hào)上場(chǎng)、5號(hào)、7號(hào)都不上場(chǎng)。 1.3 范式 1.3.1 析取范式和合取范式 范式中涉及的一些術(shù)語(yǔ)： （1）文字(letters)：指命題常元、變?cè)八鼈兊姆穸?，前者又稱正文字，后者稱負(fù)文字。 （2）析取子句(disjunctive clauses)：指文字或若干文字的析取。例如, p , p∨q , p∨q∨r . （3）合取子句(conjunctive clauses)：指文字或若干文字的合取。例如, p , p∧q , p∧q∧r . （4）互補(bǔ)文字對(duì)(complemental pairs of letters) ：指形如L，L（L為文字）的一對(duì)字符。 定義1.8 命題公式A稱為公式A的析取范式(disjunctive normal form)，如果 （1）A┝┥A （2）A為一合取子句或若干合取子句的析取。 定義1.9 命題公式A稱為公式A的合取范式(conjunctive normal form)，如果 （1）A┝┥A （2）A為一析取子句或若干析取子句的合取。 利用邏輯等價(jià)式和代入、替換原理，可以導(dǎo)出任一公式的析取范式及合取范式，其推演的基本步驟是： l 第一步，消去公式中的聯(lián)結(jié)詞和： 把公式中的A→B化為A∨B； 把公式中的AB化為(A∨B)∧(B∨A)或(A∧B) ∨(A∧B)； l 第二步，將否定聯(lián)結(jié)詞 向內(nèi)深入，使之只作用于命題變?cè)蛎}變?cè)姆穸?，然后將A化為A； l 第三步，利用分配律，將公式進(jìn)一步化為所需要的范式。 l 第四步，據(jù)問題的要求對(duì)已做出的范式作所要求的簡(jiǎn)化。 1.3.2 主析取范式與主合取范式 定義1.10 設(shè)A為恰含命題變?cè)猵1,…,pn的公式。公式A稱為A的主析取范式(major disjunctive normal form)，如果A是A的析取范式，并且其每個(gè)合取子句中p1,…,pn均恰出現(xiàn)一次。公式A稱為A的主合取范式(major conjunctive normal form)，如果A是A的合取范式，并且其每個(gè)析取子句中p1,…,pn均恰出現(xiàn)一次。 利用等價(jià)推演求公式的主析（合）取范式的方法步驟： 第一步：求出該公式的析（合）取范式； 第二步：簡(jiǎn)化各子句，除去范式中所有恒假（真）的合（析）取子句，即化掉含有互補(bǔ)文字對(duì)的合（析）取子句；同時(shí)，將合（析）取子句中同一文字的多個(gè)出現(xiàn)合并為一個(gè)； 第三步：對(duì)并非每一變?cè)汲霈F(xiàn)的析（合）取范式中的合（析）取子句，利用p┝┥p∧t┝┥p∧(q∨┐q)或p┝┥p∨f┝┥p∨(q∧┐q)把未出現(xiàn)的變?cè)╭）補(bǔ)進(jìn)來，并用分配律將其展開，最后得到給定公式的主析（合）取范式。 第四步，對(duì)已做出的范式作必要的簡(jiǎn)化，合并