離散數(shù)學(xué)課件：1-4 命題邏輯

1、復(fù)習(xí)思考題3n由p、q構(gòu)成的重言式的主析取范式為_(kāi).n矛盾式的主析取范式為_(kāi)。n已知由三個(gè)變量構(gòu)成的公式A的主合取范式為：A (1,2,4,7)，則 公式公式A的類(lèi)型是的類(lèi)型是_； 公式公式A的成假賦值是的成假賦值是_； 公式公式A的主析取范式是的主析取范式是_。思考題n 有一邏輯學(xué)家誤入某部落，被拘于牢獄，酋長(zhǎng)意欲放行，他對(duì)邏輯學(xué)家說(shuō)：n 邏輯學(xué)家沉思片刻，即向一戰(zhàn)士發(fā)問(wèn)，然后開(kāi)門(mén)從容離去。邏輯學(xué)家應(yīng)如何發(fā)問(wèn)？n 邏輯學(xué)家手指一門(mén)問(wèn)身旁一名戰(zhàn)士，說(shuō)：邏輯學(xué)家手指一門(mén)問(wèn)身旁一名戰(zhàn)士，說(shuō)：“這扇門(mén)是死亡門(mén)，他這扇門(mén)是死亡門(mén)，他（指另一名戰(zhàn)士）（指另一名戰(zhàn)士）將回答將回答是是，對(duì)嗎？，對(duì)嗎？”邏輯

2、學(xué)家手指一門(mén)問(wèn)身旁一名戰(zhàn)士，說(shuō)：邏輯學(xué)家手指一門(mén)問(wèn)身旁一名戰(zhàn)士，說(shuō)：“這扇門(mén)是死亡門(mén)，他這扇門(mén)是死亡門(mén)，他（指另一名戰(zhàn)士）（指另一名戰(zhàn)士）將回答將回答是是，對(duì)嗎？，對(duì)嗎？”n p被問(wèn)戰(zhàn)士是誠(chéng)實(shí)人n q被問(wèn)戰(zhàn)士的回答是“是”n b另一戰(zhàn)士的回答是“是”n s這扇門(mén)是死亡門(mén)所以，當(dāng)被問(wèn)人回答“是”時(shí)，pq0011010010011110為為自由門(mén)自由門(mén)第1章 命題邏輯 1.1 命題符號(hào)化及聯(lián)結(jié)詞1.2 命題公式及分類(lèi)1.3 等值演算1.4 范式1.5 聯(lián)結(jié)詞全功能集1.7 推理理論1.5 聯(lián)結(jié)詞的全功能集n定義定義 設(shè)設(shè)S是一個(gè)是一個(gè)聯(lián)結(jié)詞集合聯(lián)結(jié)詞集合，如果任何，如果任何n(n 1)元元真值真值

3、函數(shù)都函數(shù)都可以用僅可以用僅含含S中的中的聯(lián)結(jié)詞的命題公式聯(lián)結(jié)詞的命題公式表示，表示，則稱(chēng)則稱(chēng)S是是聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集. .n 說(shuō)明說(shuō)明n若若S是聯(lián)結(jié)詞全功能集，則任何命題公式是聯(lián)結(jié)詞全功能集，則任何命題公式都可都可用用S中的聯(lián)結(jié)詞表中的聯(lián)結(jié)詞表示。示。n設(shè)設(shè)S1, S2都是聯(lián)結(jié)詞都是聯(lián)結(jié)詞集合，且集合，且S1 S2. n若若S1是是全功能全功能集，則集，則S2也是全功能集也是全功能集. n反之反之,若若S2不是全不是全功能集功能集，則，則S1也不是全功能集也不是全功能集.聯(lián)結(jié)詞全功能集實(shí)例n定理定理 , , 、 , 、 , 、 , 都是聯(lián)結(jié)詞全功能集都是聯(lián)結(jié)詞全功能集.n證明證明

4、n每一個(gè)真值函數(shù)都可以用一個(gè)主析取范式表示每一個(gè)真值函數(shù)都可以用一個(gè)主析取范式表示,故故 , , 是聯(lián)結(jié)詞全功能集是聯(lián)結(jié)詞全功能集.n p q ( p q)，故，故 , 是全功能是全功能集集.n p q ( p q)，故，故 , 是全功能集是全功能集.n p q p q, p q (p q) 故故 , 也是全功能集也是全功能集.復(fù)合聯(lián)結(jié)詞np q (p q) (與非與非) n性質(zhì)性質(zhì) p (p p) p p p q (p q) (p q) (pq)(pq) p q (p q) (p) (q) (pp)(qq)np q (p q) (或非或非)n性質(zhì)性質(zhì) p (p p) p pp q (p q)

5、 (p q) (p q) (p q)p q (p q) (p) (q) (p p) (q q) , 是是聯(lián)結(jié)詞全功能聯(lián)結(jié)詞全功能集集。聯(lián)結(jié)詞全功能集舉例n例: 用“”和“”分別表示公式 p qn 解解： p q ( (p q) (p ( q) (p (q q) (p (q q) (p (q q) p q ( p q) ( p) q (p p) q1.7 推理理論n 引例: (1) 正項(xiàng)級(jí)數(shù)收斂當(dāng)且僅當(dāng)部分和有上界正項(xiàng)級(jí)數(shù)收斂當(dāng)且僅當(dāng)部分和有上界. (2) 若若A C B D，則，則A B且且C D.n 推理 從從前提前提出發(fā)推出出發(fā)推出結(jié)論結(jié)論的思維過(guò)程。的思維過(guò)程。n上面上面(1)是正確的推

6、理，而是正確的推理，而(2)是錯(cuò)誤的推理是錯(cuò)誤的推理. n 推理的組成n前提前提是推理所根據(jù)的是推理所根據(jù)的已知命題已知命題n結(jié)論結(jié)論是從前提出發(fā)通過(guò)推理而得到的是從前提出發(fā)通過(guò)推理而得到的新命題新命題n 證明 描述推理正確的過(guò)程描述推理正確的過(guò)程. . n 要研究推理，首先應(yīng)該明確什么樣的推理是有效的或正確的。推理的形式結(jié)構(gòu)n 定義定義n 若若 (A1 A2 Ak ) B為為重言式重言式， 則稱(chēng)則稱(chēng)由由 A1, A2, , Ak推出結(jié)論推出結(jié)論B的的推理正確（有推理正確（有效結(jié)論效結(jié)論） , 否則否則推理不正確（錯(cuò)誤）推理不正確（錯(cuò)誤）.n “A1, A2, , Ak 推出結(jié)論B” 的推理正

7、確 當(dāng)且僅當(dāng) A1 A2 AkB為重言式.n 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu): A1 A2 AkB 或或 前提：前提： A1, A2, , Ak 結(jié)論：結(jié)論： B n 若推理正確，則記作：若推理正確，則記作：判斷推理是否正確的方法n真值表法n等值演算法n主析取范式法n構(gòu)造證明法 n說(shuō)明：說(shuō)明：n當(dāng)命題變項(xiàng)比較少時(shí)，用前當(dāng)命題變項(xiàng)比較少時(shí)，用前3 3個(gè)方法比較方便個(gè)方法比較方便, , 此時(shí)采用此時(shí)采用形式結(jié)構(gòu)形式結(jié)構(gòu)“ A1 A2 AkB” . n而在構(gòu)造證明時(shí)，而在構(gòu)造證明時(shí)，采用采用 前提前提: A1, A2, , Ak 結(jié)論結(jié)論: B判斷推理是否正確判斷推理是否正確證明推理正確證明推理正確例

8、：判斷下面推理是否正確?（1）若天氣涼快，小王就不去游泳。天氣涼快，所以小王沒(méi)去游泳。解題方法將命題符號(hào)化將命題符號(hào)化寫(xiě)出前提、結(jié)論和推理的形式結(jié)構(gòu)寫(xiě)出前提、結(jié)論和推理的形式結(jié)構(gòu)進(jìn)行判斷進(jìn)行判斷解： 設(shè) p：天氣涼快，q：小王去游泳. 前提： p q，p 結(jié)論： q 推理的形式結(jié)構(gòu)為： (pq) p) q 判斷上式是否為重言式 例：判斷下面推理是否正確?（1）若天氣涼快，小王就不去游泳。天氣涼快，所以小王沒(méi)去游泳。判斷 (pq) p) q 是否為重言式 方法1：真值表法pqpq(pq) p(pq) p) q00101011011011111001例：判斷下面推理是否正確?（1）若天氣涼快，小王

9、就不去游泳。天氣涼快，所以小王沒(méi)去游泳。判斷 (pq) p) q 是否為重言式 方法2：等值演算法 (pq) p) q ( pq) p)q (p q) p q (p q) (p q) 1例：判斷下面推理是否正確?（1）若天氣涼快，小王就不去游泳。天氣涼快，所以小王沒(méi)去游泳。判斷 (pq) p) q 是否為重言式 方法3：主析取范式法 (pq) p) q ( pq) p)q (p q) p q m11 m0 x mx0 m11 m00 m01 m00 m10 (0,1,2,3) 1例：判斷下面推理是否正確?（2）若我上街，我一定去書(shū)店。我沒(méi)上街，所以我沒(méi)去書(shū)店。解： 設(shè) p：我上街，q：我去書(shū)店

10、. 前提： p q， p 結(jié)論： q 推理的形式結(jié)構(gòu)為： (p q)p) q 判斷上式是否為重言式 (p q)p) q ( p q) p )q (p q) p q m10 m1x mx0 m10 m10 m11 m00 m10 (0,2,3)不是重言式！不是重言式！所以推理不正確所以推理不正確構(gòu)造證明法及推理定律n構(gòu)造證明法n描述推理過(guò)程的命題公式序列。描述推理過(guò)程的命題公式序列。n其中的每個(gè)命題公式可以是其中的每個(gè)命題公式可以是n已知的前提，已知的前提，n或是由前面的命題公式應(yīng)用或是由前面的命題公式應(yīng)用推理規(guī)則推理規(guī)則得到的結(jié)論得到的結(jié)論n重要的推理定律 A (A B) 附加律附加律 (A

11、B) A 化簡(jiǎn)律化簡(jiǎn)律 (AB) A B 假言推理假言推理 (AB)B A 拒取式拒取式構(gòu)造證明法及推理定律n重要的推理定律 (A B)B A 析取三段論析取三段論 (AB) (BC) (AC) 假言三段論假言三段論 (AB) (BC) (AC) 等價(jià)三段論等價(jià)三段論 (AB) (CD) (A C) B D 構(gòu)造性二難構(gòu)造性二難 (AB) (CD) ( BD) AC 破壞性二難破壞性二難說(shuō)明：說(shuō)明： (1) A, B, C, D為元語(yǔ)言為元語(yǔ)言符號(hào)符號(hào) ( (2)2) A B 產(chǎn)生產(chǎn)生兩條推理定律兩條推理定律: : A B 且且 BA常用的推理定律 (1) 前提引入規(guī)則前提引入規(guī)則(2) 結(jié)論

12、引入規(guī)則結(jié)論引入規(guī)則(3) 置換規(guī)則置換規(guī)則(4) 假言推理規(guī)則假言推理規(guī)則 AB A B(5) 附加規(guī)則附加規(guī)則 A A B (6) 化簡(jiǎn)規(guī)則化簡(jiǎn)規(guī)則 A B A (7) 拒取式規(guī)則拒取式規(guī)則 AB B A(8) 假言三段論規(guī)則假言三段論規(guī)則 AB BC AC 常用的推理定律(續(xù)) (11) 破壞性二難推理破壞性二難推理規(guī)則規(guī)則 AB CD BD AC(12) 合取引入規(guī)則合取引入規(guī)則 A B A B (9) 析取三段論規(guī)則析取三段論規(guī)則 A B B A (10)構(gòu)造性二難推理構(gòu)造性二難推理規(guī)則規(guī)則 AB CD A C B D構(gòu)造證明直接證明法構(gòu)造下列推理的證明：前提：前提：p r, q s

13、, p q 結(jié)論：結(jié)論：r s證明證明1： p q 前提前提 置換規(guī)則置換規(guī)則 q s 前提前提 p s 假言三段論規(guī)則假言三段論規(guī)則 s p 置換規(guī)則置換規(guī)則 p r 前提前提 s r 假言三段論規(guī)則假言三段論規(guī)則 r s 置換規(guī)則置換規(guī)則證明2： p r 前提前提 q s 前提前提 p q 前提前提 r s 構(gòu)造性二難構(gòu)造性二難公安人員審查一件盜竊案，已知事實(shí)如下：公安人員審查一件盜竊案，已知事實(shí)如下：甲或甲或乙盜竊了手機(jī)乙盜竊了手機(jī)；若若甲盜竊了甲盜竊了手手機(jī)機(jī)，則作案時(shí)間不能發(fā)生在午夜前；，則作案時(shí)間不能發(fā)生在午夜前；若若乙的證詞正確乙的證詞正確，則，則午夜時(shí)屋里燈光未滅午夜時(shí)屋里燈光

14、未滅；若若乙的證詞不正確，則乙的證詞不正確，則作案時(shí)間發(fā)生在午夜之前作案時(shí)間發(fā)生在午夜之前；午夜時(shí)屋里燈光滅了午夜時(shí)屋里燈光滅了。 解：設(shè) p：甲盜竊甲盜竊手手機(jī)機(jī)。 q：乙盜竊乙盜竊手手機(jī)機(jī)。 r：作案時(shí)間發(fā)生在午夜之前作案時(shí)間發(fā)生在午夜之前。 s：乙的證詞正確乙的證詞正確。 t：午夜時(shí)屋里燈光未滅午夜時(shí)屋里燈光未滅。 前提前提： p q，pr ，st， sr ， t寫(xiě)出對(duì)應(yīng)下面推理的證明P27例28 寫(xiě)出對(duì)應(yīng)下面推理的證明 前提前提： p q，p r, s t, s r, 結(jié)論結(jié)論：?證明：證明： s t 前提前提 t 前提前提 s 拒取式拒取式 s r 前提前提 r 假言推理假言推理 p

15、 r 前提前提 p 拒取式拒取式 p q 前提前提 q 析取三段論析取三段論q：乙乙盜竊盜竊了了手機(jī)手機(jī)。構(gòu)造證明附加前提證明法 欲證明欲證明 前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：CB等價(jià)地證明等價(jià)地證明 前提：前提：A1, A2, , Ak, C 結(jié)論：結(jié)論：B 理由：理由： (A1 A2 Ak) (C B) (A1 A2 Ak) ( C B) ( (A1 A2 Ak ) C) B) (A1 A2 Ak C) B (A1 A2 Ak C) B 例如：證明下列推理。 前提： p (q r)， s p ， q ， 結(jié)論： s r證明證明： s p 前提前提 s 附加前提引入附加前提引入 p 析取析取三段論三段論 p (q r) 前提前提 q r 假言推理假言推理 q 前提前提 r 假言推理假言推理附加前提證明法 舉例構(gòu)造證明歸謬法（反證法） 欲證明欲證明 前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：B將將 B 加入前提，若推出矛盾，則得證推理正確加入前提，若推出矛盾，則得證推理正確.理由理由: A1 A2 Ak B (A1 A2 Ak) B (A1 A2 Ak) ( B) (A1 A2