1、離散數(shù)學(xué),Discrete Mathematics,什么是離散數(shù)學(xué)？ 為什么要學(xué)習(xí)離散數(shù)學(xué)？ 離散數(shù)學(xué)主要學(xué)習(xí)那些內(nèi)容？,什么是離散數(shù)學(xué)？ 研究離散量的結(jié)構(gòu)及關(guān)系的一門科學(xué)。,研究離散結(jié)構(gòu)的數(shù)學(xué)分科。 （辭海）,培養(yǎng)個人理解和構(gòu)造數(shù)學(xué)證明的能力 為學(xué)習(xí)計算機科學(xué)課程提供必要的數(shù)學(xué)基礎(chǔ),為什么學(xué)習(xí)離散數(shù)學(xué)？,后繼課程： 數(shù)據(jù)結(jié)構(gòu)、編譯技術(shù)、算法分析與設(shè)計、 人工智能、數(shù)據(jù)庫、,離散數(shù)學(xué)的內(nèi)容：,數(shù)理邏輯（Mathematics Logic) 集合論(Sets),圖論（Graph Theory) 代數(shù)結(jié)構(gòu)（Algbra Structure),線性代數(shù)(Linear Algbra ) 概率論(離散部

2、分)（Propobility Theory),組合論（Combination),學(xué)習(xí)方法: 理解概念、掌握方法、注重應(yīng)用,課程特點：邏輯性、抽象性,1、離散數(shù)學(xué)（左孝琳、李為檻、劉永才，上?？萍嘉墨I版） 2、離散數(shù)學(xué)-計算機數(shù)學(xué)基礎(chǔ)學(xué)習(xí)（陳德人，浙大版） 3、Discrete Mathematics（ Forth Edition: Richard Johnsonbaugh) 4、 Discrete Mathematics（ Revised Edition:Biggs ) 5、Discrete Math. Elements（ Liu Chuang Laung),邏輯學(xué)：研究人的思維形式及規(guī)律的學(xué)

3、科。 分為形式邏輯、辯證邏輯、數(shù)理邏輯。,數(shù)理邏輯的提出：,17世紀(jì)，有人提出計算的方法代替人們思維中的推理過程。 萊布尼茲 ：“通用的科學(xué)語言”，把推理過程變成象 數(shù)學(xué)一樣利用公式計算，得出正確結(jié)論。 現(xiàn)代數(shù)理邏輯部分內(nèi)容的萌芽。,1847年，數(shù)學(xué)家布爾（英）發(fā)表邏輯的數(shù)學(xué)分析， 建立”布爾代數(shù)“，創(chuàng)建了一套符號體系，和一套運算 規(guī)則，利用代數(shù)的方法研究邏輯問題。 奠定了數(shù)理邏輯的基礎(chǔ)。,1884年，數(shù)學(xué)家弗雷格（德）出版數(shù)論的基礎(chǔ)一書， 引入量詞符號，使得數(shù)理邏輯中的符號體系更加完備， 皮爾斯（美），又引入邏輯符號。 數(shù)理邏輯理論基礎(chǔ)逐漸形成，稱為一門獨立的學(xué)科。,“兩個演算”+“四論”,

4、命題演算，謂詞演算,遞歸論，證明論，模型論，公理集合論,數(shù)理邏輯是應(yīng)用數(shù)學(xué)方法研究推理中前提與結(jié)論之間的形式關(guān)系的科學(xué)。 數(shù)理邏輯的核心是把邏輯推理符號化，即把推理變成象數(shù)學(xué)演算一樣完全形式化。 數(shù)理邏輯又叫符號邏輯，因為它的主要工具是 符號體系。,第1篇 數(shù)理邏輯,Mathematics Logic,- 一套符號體系 + 一組規(guī)則,第1-1章 命題邏輯,1-1-1 命題、邏輯聯(lián)結(jié)詞與真值表 1-1-2 命題公式與真值函數(shù),Proposition Logic,1-1-1 命題、邏輯聯(lián)結(jié)詞與真值表,一、命題的基本概念 能判斷真假而不是可真可假的陳述句。 真值：命題表達的判斷結(jié)果。真值只取兩個值：

5、真或假。 真值為真的命題稱為真命題，真值為假的命題稱為假命題。 真命題表達的判斷正確，假命題表達的判斷錯誤。 任何命題的真值都是唯一的。,例1 判斷下列句子是否為命題。 (1) 人總是要死的。 (4) 中國人民是勤勞和勇敢的。 (7) 今天沒有下雨。 (9) 太陽系以外的星球上有人。 (10) 他喜歡讀書也喜歡運動。 (11) 他在機房里或在圖書館里。 (13) 如果a和b都是正數(shù)，則ab也是正數(shù)。 (14) xy0當(dāng)且僅當(dāng)x和y都大于0。,陳述句，真值唯一。,(16) 天氣多好?。?(17) 他來了嗎？ (21) 我正在說假話。,不是命題,不是命題,不是命題,若(21)的真值為真，即“我正在

6、說假話”為真， 表明我說的是假話，則又推出(21)的真值應(yīng)為假；反之，若(21)的真值為假，即“我正在說假話”為假，表明我說的是真話，則又推出(21)的真值應(yīng)為真。于是(21)既不為真又不為假，因此它不是命題。,像(21)這樣由真推出假，又由假推出真的陳述句稱為 悖論。,命題符號化,用大寫英文字母P,Q,R，Pi ,Qi ,Ri 表示命題 用“1”表示真，用“0”表示假,如： P: 人總是要死的。 真值為1 Q: 是有理數(shù)。 真值為0,不能再被分解的命題為簡單命題（原子命題）。,命題標(biāo)識符,命題標(biāo)識符代表一個確定的命題，稱為命題常元； 代表一個非確指的命題，稱為命題變元。,用一個確定的命題代入

7、命題標(biāo)識符P，稱為對P 的指派（賦值，或解釋）。,3是素數(shù)是不對的。 他喜歡讀書也喜歡運動。 他在機房里或在圖書館里。 如果a和b都是正數(shù)，則ab也是正數(shù)。 xy0當(dāng)且僅當(dāng)x和y都大于0。,復(fù)合命題,P：3是素數(shù)。,非P,Q：他喜歡讀書。 R：他喜歡運動,Q并且R,S：他在機房。 T：他在圖書館。,S或者T,U：a和b都是正數(shù)。V： ab是正數(shù)。,如果U則V。,W：xy0。 Z：x和y都大于0。,W當(dāng)且僅當(dāng)Z。,聯(lián)結(jié)詞,定義1.3 設(shè)P為命題，復(fù)合命題“非P”(或“P的否定”) 稱為P的否定式,記作P，符號稱作否定聯(lián)結(jié)詞 。并規(guī)定P為真當(dāng)且僅當(dāng)p為假。,是有理數(shù)是不對的；,0,1,“2是偶素數(shù)

8、” 。,定義1.4 設(shè)P,Q二命題，復(fù)合命題“P并且Q”(或“P與Q”)稱為P與Q的合取式，記作PQ，稱作合取聯(lián)結(jié)詞。并規(guī)定PQ為真當(dāng)且僅當(dāng)P與Q同時為真。,P: 2是偶數(shù) Q: 2是素數(shù),PQ,1 1,1,“2或4是素數(shù)”,定義1.5 設(shè)P，Q為二命題，復(fù)合命題“P或Q”稱作 P與Q的析取式，記作PQ，稱作析取聯(lián)結(jié)詞。 并規(guī)定PQ為假當(dāng)且僅當(dāng)P與Q同時為假。,P: 2是素數(shù) Q: 4是素數(shù),PQ,1 0,1,張紅喜歡唱歌或者跳舞。,張紅是安徽人或者江蘇人。,(13) 如果a和b都是正數(shù)，則ab也是正數(shù)。,定義1.6 設(shè)P，Q為二個命題，復(fù)合命題“如果P，則Q” 稱作P與Q的條件式，記作PQ，

9、稱作條件聯(lián)結(jié)詞。 稱P為前件，Q為后件。 并規(guī)定PQ為假當(dāng)且僅當(dāng)P為真Q為假。,PQ的邏輯關(guān)系:P是Q的充分條件，Q是P的必要條件。,注意： 在使用聯(lián)結(jié)詞時，要特別注意以下幾點：,1在自然語言里，特別是在數(shù)學(xué)中，Q是P的必要 條件有許多不同的敘述方式。,例如：“只要P，就Q”，“因為P，所以Q”，“P僅當(dāng)Q”， “只有Q才p”，“除非Q才P”，“除非Q，否則非P”等等。,上述各種敘述方式都應(yīng)符號化為PQ.,2在自然語言中，“如果P，則Q”中的前件P與后件Q往往具有某種內(nèi)在聯(lián)系。而在數(shù)理邏輯中，P與Q可以無任何內(nèi)在聯(lián)系。,若河水泛濫，則周圍的莊稼被毀。,P:河水泛濫。 Q：周圍的莊稼被毀。,PQ

10、,若23，則今天陽光明媚。,A：23。 B：今天陽光明媚。,AB,只有天下大雨，他才乘班車上班。,3在數(shù)學(xué)或其它自然科學(xué)中，“如果P，則Q”往往表 達的是前件P為真，后件Q也為真的推理關(guān)系。但在數(shù) 理邏輯中，作為一種規(guī)定:當(dāng)P為假時，無論Q是真是 假，PQ均為真。,“xy0當(dāng)且僅當(dāng)x和y都大于0。 ”,定義1.5 設(shè)P，Q為二個命題，復(fù)合命題“p當(dāng)且僅當(dāng)q” 記作P Q， 稱作雙條件聯(lián)結(jié)詞。 并規(guī)定PQ為真當(dāng)且僅當(dāng)P與Q同時為真或同時為假。,P Q的邏輯關(guān)系為P與Q互為充分必要條件。,例1.6 將下列命題符號化，并討論它們的真值,(1) 是無理數(shù)當(dāng)且僅當(dāng)加拿大位于亞洲 2+3=5的充要條件是是

11、 無理數(shù) 若兩圓O1，O2的面積相等，則它們的半徑相等， 反之亦然。,解：令p: 是無理數(shù)，真值為1 q: 加拿大位于亞洲，真值為0,則(1)符號化為p q，真值為0,令r:2+3=5，真值為1， 則(2)符號化為r p，真值為1,令 s:兩圓O1，O2的面積相等 t:兩圓O1，O2的半徑相等 則(3)符號化為s t,真值為1,以上定義了五種最基本、最常用、也是最重要的聯(lián)結(jié)詞， ，將它們組成一個集合， ，稱為一個聯(lián)結(jié)詞集。其中為一元聯(lián)結(jié)詞，其余的都是二元聯(lián)結(jié)詞。,說明： 1.由聯(lián)結(jié)詞集， 中的一個聯(lián) 結(jié)詞聯(lián)結(jié)一個或兩個原子命題組成的復(fù)合命題是最簡 單的復(fù)合命題，稱為基本復(fù)合命題。,基本復(fù)合命題

12、的真值,2. 多次使用聯(lián)結(jié)詞集中的聯(lián)結(jié)詞，可以組成更為 復(fù)雜的復(fù)合命題，求復(fù)雜復(fù)合命題的真值時，還要規(guī)定聯(lián)結(jié)詞的優(yōu)先順序，將括號也算在內(nèi)，本書規(guī)定的聯(lián)結(jié)詞優(yōu)先順序為,（），,例 令 P:北京比天津人口多 Q: 2+2=4 R: 烏鴉是白色的 求下列復(fù)合命題的真值： (1) (PQ) (P Q) R (2) (QR) (P R) (3) (PR) (P R),1,1,0,1-1-2 命題公式與真值函數(shù),一、命題演算公式,定義2.1 由命題變元、聯(lián)結(jié)詞、括號按下列規(guī)則 形成的符號串。命題合式公式（WFF）,(1)單個原子命題變元是WFF(原子命題公式)。 (2)若A是WFF，則(A)也是WFF。

13、(3)若A，B是WFF，則(AB)，(AB)，(AB)， (A B)也是WFF。 (4)只有有限次地應(yīng)用(1)(3)形式的符號串才是WFF。,如：(PQ)(QR)，(PQ)R，P(QR),PQR，（P(RQ) 不是WFF。,注意：合式公式的定義方式稱為歸納定義方式， 本書中還將多次出現(xiàn)這種定義方式。,公式的賦值,例如，公式(PQ)R,P,Q,R,(PQ)R,0,0,0,1,0,1,0,0,定義2.2 設(shè)P1,P2,Pn是出現(xiàn)在公式A中的全部命題符號，給P1,P2,Pn各指定一個真值，稱為對A的一個指派（賦值或解釋）。若指定的一組值使A的真值為1，則稱這組值為A的成真賦值；若使A的真值為0，則稱

14、這組值為A的成假賦值。,(P1P2P3)(P1P2) 000(P10，P20，P30)，110(P11，P21，P30)都是成真賦值; 001(P10，P20，P31)，011(P10，P21，P31)都是成假賦值。,含n(n1)個命題變項的公式共有 組不同的賦值。,2n,構(gòu)造真值表的步驟： (1) 找出公式中所含的全體命題變項P1,P2,Pn (若無下角標(biāo)就按字典順序排列)，列出2n個賦值。規(guī)定，賦值從000開始，然后按二進制加法依次寫出各賦值，直到111為止。,(2) 計算出公式在每個賦值下的真值。,例2.1 求下列公式的真值表，并求成真賦值和成假賦值。,(1)（PQ）（QP） (2)（P

15、Q）PQ (3)（PQ）（P Q）,1,1,0,0,1,1,1,1,0,0,0,0,公式(1)成真賦值：00，11，成假賦值：01，10,公式(2)所有賦值都是成真賦值，無成假賦值。,公式(3)所有賦值都是成假賦值，無成真賦值。,重言式（永真式）,矛盾式（永假式）,公式分類,根據(jù)公式的取值情況對公式進行如下分類:,定義2.4 設(shè)A為任一命題公式。,若A在它的各種賦值下取值均為真,則稱A是重言式或永真式，記為T。 (2) 若A在它的各種賦值下取值均為假,則稱A是矛盾式或永假式，記為F。 (3) 若A不是矛盾式,則稱A是可滿足式。,說明： 1. A是可滿足式的等價定義是：A至少存在一個成真賦值。

16、2. 重言式一定是可滿足式，但反之不真。因而，若公式A是可滿足式，且它至少存在一個成假賦值，則稱A為非重言式的可滿足式。,3. 真值表可用來判斷公式的類型: (1) 若真值表最后一列全為1，則公式為重言式。 (2) 若真值表最后一列全為0，則公式為矛盾式。 (3) 若真值表最后一列中至少有一個1，則公式為可滿足式。,定理2.1 任意兩個重言式（矛盾式）的合取或析取仍是 重言式（矛盾式）。,下列各公式均含兩個命題變元P與Q，列出它們的真值表。,(1) PQ (2) PQ (3) (PQ)(4) (PQ)(QP)(5) PQ,公式形式不同， 真值表可能相同,公式(1)(3)(5)真值表相同 公式(

17、2)(4)真值表相同,等價式,二、真值函數(shù),定義2.3 以真，假為定義域和值域的函數(shù)為真值函數(shù) 。,所有的WFF都是真值函數(shù)。,一個WFF對應(yīng)一個真值表，反之， 由真值表也可以寫出對應(yīng)的真值函數(shù),例2.4 設(shè)f (P,Q,R) 是3個包含命題變元P，Q，R的真值函數(shù)（WFF），它們的真值表如下， 請確定它們的表達式。,f1(P,Q,R)= (PQR) (PQ R) (PQ R)(PQR),f2(P,Q,R)= (PQ R)(PQR),f1(P,Q,R)和f2(P,Q,R)的形式是否唯一？,由真值表確定的真值函數(shù)不一定是最簡單的WFF， 也不一定只對應(yīng)一個表達式。,1,1,1,1,0,0,0,0

18、,等價式,f3(P,Q,R)= (PQR) (PQ R)(Q P),例 下列公式中,哪些具有相同的真值表?,(1) PQ(2) QR(3) (PQ)(PR)P)(4) (QR)(PP),公式(1)(3)真值表相同 公式(2)(4)真值表相同,f (P,Q,R)=,形式是否唯一？,(PQ)R,(P Q) R,(P R) (Q R),由同一個真值表確定的真值函數(shù)的形式不唯一。,等價式,問：關(guān)于n個命題變元P1,P2,Pn,可以構(gòu)造多少個真值表不同的命題公式呢?,n個命題變元共產(chǎn)生2n個不同賦值,在每個賦值下,公式的值只有0和1兩個值。于是n個命題變元構(gòu)造的公式的真值表共有 種不同情況。,1-1-3

19、 公式的等價與蘊涵,PQ PQ (PQ),(PQ)(QP) 與 P Q,公式形式不同，但真值表相同。,等價式,定義3.1 設(shè)P1,P2,Pn是出現(xiàn)在兩個WFFA和B中的原子命題變元，如果對P1,P2,Pn的任意真值指派，A和B的真值都相同，則稱A和B邏輯相等或A和B等價。,記為 AB (A=B),AB 是重言式,定理3.3 公式A和B等價當(dāng)且僅當(dāng)AB 是重言式。,基本等價式,P P (對合律),(2) PP P PP P (冪等律),(3) PQ QP PQ QP (交換律),(4) P(Q R) (PQ) R P(Q R) (P Q) R (結(jié)合律),(5) P(Q R) (PQ)(PR)

20、P(Q R) (PQ)(PQ) (分配律),(6) P(P Q) P P(P Q) P (吸收律),(7) (P Q) P Q (P Q) P Q (德摩根律),(8) PF P PT P (同一律),(9) PT T PF F (零一律),(10) PP T PP F (否定律),(11) PQ PQ (條件等價式),(12) PQ (PQ) (QP) (雙條件等價式),等價可看做是兩個公式之間的關(guān)系，此關(guān)系具有 自反性、對稱性、傳遞性,(1)自反性 A A,(2)對稱性 若AB，則 BA,(3)傳遞性 若AB且 BC，則有AC,定義3.2 子公式,若WFFX是WFFA的子串，則稱是的子公式

21、。,P(Q R),Q R是子公式,因為 QR QR,所以 P(Q R) P (QR),定理3.1 替換規(guī)則,設(shè)是WFFA的一個子公式，且YX，則將A中 X用Y取代后得到的公式與A等價。,例1 Q(P (PQ),P,吸收律, QP,等價演算,例2 證明 (P (PQ) Q T,例4 證明: PQ QP,等價演算證明公式等價關(guān)系,例5 證明: P(Q R) (PQ)R,重言式，真值始終為1，與公式中變元取值無關(guān)。,等價演算判斷公式類型,證明 (AB) (BC) (CA) (AB)(BC)(CA),證明：(AB) (BC) (CA), (B(AC), (BC)(BA)(ACC) (ACA),(CA)

22、, (BC)(BA)(AC) (AC), (AB)(BC)(CA),等價演算解決實際邏輯判斷問題,例2.12 某科研所要從3名科研骨干A,B,C中挑選12 名出國進修,選派時要滿足以下條件: (1) 若A去,則C同去. (2) 若B去,則C不能去. (3) 若C不去,則A或B可以去. 問所里應(yīng)如何選派他們?nèi)?,解: 設(shè) P:派A去 Q:派B去 R: 派C去,由已知條件可得此問題的邏輯表達式為 (PR) (QR) (R (PQ),問題轉(zhuǎn)換為求該式的成真賦值,001，010，101,所以選派方案有三種:,(1) C去,而A,B都不去 (2) B去,而A,C都不去 (3) A,C同去,而B不去,定義

23、3.3 設(shè)P1,P2,Pn是出現(xiàn)在兩個WFFA和B中的原子命題變元，如果對P1,P2,Pn的任意真值指派，都不會出現(xiàn)A為1而B為0的情況，則稱A蘊涵B（B是A的邏輯結(jié)果）。,記為 A B,AB是重言式,定理3.4 公式 A B 當(dāng)且僅當(dāng)AB是重言式。,判斷公式間蘊含關(guān)系的問題轉(zhuǎn)換為判斷公式類型問題。,例6 證明 P PQ,用定義（采用真值表）,例7 證明 (PQ) (QR) PR,例8 證明 Q(PQ) P,舉例證明蘊涵關(guān)系,用定理3.4 (PQ) (QR) (PR) T,性質(zhì)：自反性、反對稱性、傳遞性,若A B且A C，則A BC,若A B且C B，則AC B,A(BC),A (BC),(A

24、B) (AC),(AB) (AC),蘊涵也可以看做公式間的一種關(guān)系。,證明蘊涵關(guān)系常借助基本蘊涵式,基本蘊涵式,(1) PQ P PQ Q 化簡律,(2) P PQ Q PQ 附加律,(3) P PQ,(4) Q PQ,(5) (PQ) P (PQ) Q,(6) P (PQ) Q 分離規(guī)則（假言推理）,(7) Q (PQ) P 拒取式,(8) P (PQ) Q 析取三段論,(9) (PQ) (QR) PR 假言三段論,(10) (PQ) (PR) (QR) R,(11) (PQ) (RS) (PR)(QS),(12) (PQ) (Q R) P R 等價三段論,2.不構(gòu)造真值表證明下列蘊涵式,(

25、PQ)QPQ PQPS (6) (QP)(R(RP) R(PQ),3.若 AC BC，是否有A B,錯誤。,C取1，A取0，B取1時， AC BC， 但 A B,若 AC BC，是否有A B,1-1-4 命題邏輯的推理理論,什么樣的推理是有效的？,由給定的前提經(jīng)過有效的推理得出的結(jié)論， 稱為有效結(jié)論。,定義4.1 A1，A2， An和B為合式公式，若 A1A2 AnB，則稱B為前提A1，A2， An 的有效結(jié)論，或說 B為前提A1，A2， An 的邏輯結(jié)果，或說A1，A2， An 共同蘊涵B。,注意：推理的有效性與結(jié)論的真實性不是等同的。,有效的推理不一定產(chǎn)生真實的結(jié)論。,推理有效指結(jié)論是所給

26、前提的合乎邏輯的結(jié)果。,例1 證明 RS是P(QS)， RP，Q的有效 結(jié)論。,(P(QS) (RP) Q RS,(P(QS)(RP)Q( RS)是重言式,真值表，等價演算,(P(QS)(RP)Q( RS),(P(QS)(RP)Q(RS),(P(QS)(RP)Q)(RS),(P(QS) (RP) QRS,(P(QS) (RP) (QS)R,(P (QS) P R,T,麻煩,(P Q S) P R,證明 RS是P(QS)， RP，Q的有效 結(jié)論。,R P,P(QS),R P, R(QS),RQS,(RS) Q,Q, RS,RS,中間結(jié)論,演繹法,基本蘊涵式 等價式,證明過程分解成一步一步，以基本

27、蘊涵式或等價式 作為推理依據(jù)，中間結(jié)論作為前提使用。,定義4.2 設(shè)S為若干公式的集合(稱為前提集合)， 如果有公式的有限序列A1，A2， An ，其中 AiS或Ai是A1，A2， Ai-1中某些公式的有效 結(jié)論,且An=B，則稱B是S的邏輯結(jié)果或有效結(jié)論, 或者說S演繹出B。,基本蘊涵式、基本等價式是演繹方法論證的根據(jù)， 除此之外還必須遵循下列推理規(guī)則：,P規(guī)則：在推演過程中可以隨時使用前提。,T規(guī)則：在推演過程中可以任意使用前面演繹的 某些公式的邏輯結(jié)果（中間結(jié)論），當(dāng)借助于 等價式時記為TE，當(dāng)借助于蘊涵式時記為TI。,CP規(guī)則：如果需要演繹的公式為BC，那么將 B作為附加前提，設(shè)法演繹

28、出C來。,附加前提證明法，定理4.1證明其正確性,例1 證明 RS是P(QS)， RP，Q的有效結(jié)論。,證明：, P(QS), R P, R(QS), RQS,(RS)Q, Q, RS, RP,P,TE,P,TI,假言三段論,TE,P,TI,析取三段論, RS,TE,定理4.1 若A1A2 An B C，則 A1A2 An B C,當(dāng)且僅當(dāng),若(A1A2 An B) C是重言式,則(A1A2 An ) (B C)也是重言式,(A1A2 An B) C,(A1A2 An ) (B C),(P(QS) (RP) Q RS,(P(QS) (RP) Q R S,例1 證明 RS是P(QS)， RP，Q

29、的有效結(jié)論。,證明：, P(QS), P, QS, Q, S, RP,P,TI,P,TI,分離規(guī)則,P,TI, RS,CP, R,P（附加前提）,分離規(guī)則,附加前提證明法,例1 證明 RS是P(QS)， RP，Q的有效 結(jié)論。,令 S=P(QS)， RP，Q,證明S演繹出RS,R P,P(QS),R P, R(QS),RQS,(RS) Q,Q, RS,RS,中間結(jié)論,S演繹出RS 的過程,演繹法與證明 (P(QS) (RP) Q RS 是等價的。,基本蘊涵式 等價式,定理4.2 設(shè)S為公式集，B是一個公式，S能演繹 出B的充要條件是：B是S的邏輯結(jié)果。,定理4.3 設(shè)S為前提公式集合，B和C是

30、兩個公式， 若SB能演繹C，則S演繹出B C。,設(shè)S=A1，A2， An ，則 SB= =A1，A2， ，An ，B，,說明如果證明的結(jié)論是一個條件式，則可以將 前件作為前提之一，后件作為結(jié)論。,前件B稱為附加前提，附加前提引入,反證法（歸謬法）,定義4.3 設(shè)A1，A2， An是n個命題公式，若A1A2 An 是矛盾式，則稱A1，A2， ，An是不相容的。否則，稱其為相容的。,取結(jié)論的否定作為前提引入到證明中，希望推出 矛盾的結(jié)論。,定理4.4 A1A2 AnB當(dāng)且僅當(dāng) A1，A2， ，An ，B是不相容的。,A1A2 AnB T,A1A2 An B F,反證法（歸謬法）的理論依據(jù), (A1

31、A2 An)B, (A1A2 An B), T, T,例3 證明 S=AB， (BC)演繹出A,采用反證法（歸謬法）,證明：, AB,P, A,P(否定結(jié)論引入), B,TI,(BC),P,BC,TE,B,TI, BB F,TE,A,定理4.4,例2 證明 (PQ) (PR) (QS) SR, PQ,證明：, PQ,P,TE, QS,P, PS,TI,假言三段論, SP,TE, PR,P, SR,TI,假言三段論, SR,TE,使用反證法, (SR),P, S R,TE, P R,P, S, R, QS,P, P,T I, Q,TI,TI,TI, P Q, (P Q), P Q, (P Q)

32、P Q F,例2 反證法證明 (PQ) (PR) (QS) SR,論證的方法可以分為：真值表法，直接法，間接法,直接法：由一組前提經(jīng)P規(guī)則，T規(guī)則演繹出有效結(jié)論,間接法: (1)附加前提證明法 (2)反證法（歸謬法）,定義4.3 設(shè)P1,P2,Pn是A1，A2， Am中出現(xiàn)的原子命題變元，若A1A2 Am 是矛盾式，則稱A1，A2， ，Am是不相容的。否則，稱其為相容的。, PR,P, PQRQ,TI, QS,P, RQRS,TI, PQRS,TI, PQ,P, RS,TI,例2 證明 (PQ) (PR) (QS) SR,證明:,例5 “如果天下雨，春游就改期，如果沒有球賽， 春游就不改期。結(jié)

33、果沒有球賽，所以沒有下雨?！?證明這是有效的論斷。,證明： 令 A:天下雨； B：春游改期； C：沒有球賽,符號化前提和結(jié)論， 前提： AB， CB，C 結(jié)論： A,例6 “如果學(xué)生學(xué)習(xí)努力，他們的父親或母親就 高興。若母親高興，學(xué)生就不努力學(xué)習(xí)。若老師 只表揚學(xué)生，則父親就不高興。故如果學(xué)生學(xué)習(xí) 努力，老師就不只是表揚學(xué)生。” 證明這是有效的論斷。,證明： 令 A:學(xué)生學(xué)習(xí)努力； B:學(xué)生的父親高興； C:學(xué)生的母親高興；D:老師只表揚學(xué)生,符號化前提和結(jié)論， 前提： A(BC)， CA， DB 結(jié)論： AD,前提： A(BC)， CA， DB 結(jié)論： AD,證明：, A,P(附加前提),

34、A(BC),P, BC,TI, CA,P, C,TI, B,TI, DB,P,D,TI,例7 證明下列命題是不容的：“如果他因病缺課， 那么他考試不及格。如果他考試不及格，他就受 不到教育。若他讀了許多書，則他受到了教育， 但是，雖然他因病缺課，他還是讀了許多書?！?證明： 令 P:他因病缺課； Q:他考試不及格； R:他就受不到教育；S:他讀了許多書,問題符號化為,PQ,QR,SR,PS,不相容,(PQ) (QR) (SR) (PS)F,(PQ) (QR) (SR) (PS)T,(PQ) (QR) (SR) (PS),1-1-5 對偶與范式,定義5.1 在只含有邏輯聯(lián)結(jié)詞, 的公式A 中，將

35、換成， 換成，如果A中有T或F 就分別換成F或T，所得到的公式記為A*,稱為 A的對偶式。,A*和A互為對偶式,(A*)*=A,P(Q R),P(Q R),例5.1 求 (1) (PQ)F (2) P(QT) (3) (PQ) R 的對偶式。,對偶性質(zhì),定理5.1 設(shè)P1,P2,Pn是公式A和A*中出現(xiàn)的原子命題變元，分別記為A(P1,P2,Pn)和 A*(P1,P2,Pn)，則,A(P1,P2,Pn) A*(P1,P2,Pn),A(P1,P2,Pn)A*(P1,P2,Pn),A=P(Q R),A*=P(Q R),A=P (Q R),A*()= P(QR),定理5.2 設(shè)A，B為兩個合式公式，

36、若AB， 則A*B*,P(Q R) (PQ)(PR),P(Q R) (PQ)(PQ),(P Q) P Q,(P Q) P Q,PQ ， PQ ， (PQ) ，QP,找出一種統(tǒng)一的形式表示一組等價式，希望 這種形式惟一化。,主范式（正則范式）,定義5.2 文字（句節(jié)） 原子命題公式或它的否定。,定義5.3 子句，短語 子句：有限個文字（句節(jié)）的析取式（簡單析取式） 短語：有限個文字（句節(jié)）的合取式（簡單合取式）,一個文字既是子句又是短語。,P1 ，P2 ，Q,子句：P1P2P3 ，PQ ，R,短語：P1P2P3 ，PQ ，R,定義5.4 范式 合取范式：有限個子句（簡單析取式）的合取式。 析取范

37、式：有限個短語（簡單合取式）的析取式。,(P1P2P3) (PQ) R,(P1P2P3) (PQ) R,一個子句（短語）既是合取范式，又是析取范式。,定理5.3 （范式存在定理） 任一命題公式都有與之等價的合取范式和析取范式。,證明:范式中出現(xiàn)的聯(lián)結(jié)詞只能是， ，,設(shè)A為任一個命題公式,若A中含有，可以通過等價式消去,PQ PQ,PQ (PQ) (QP), (PQ) (QP),再對A使用分配、結(jié)合、交換、德摩根律化成范式。,例： 求 (P Q ) R 的合取(析取)范式,解： (P Q ) R,(PQ)R, (PQ) R, (P Q) R, (PR) (Q R),合取范式,析取范式,公式 C=

38、 (PQR) (PQR) (PQR) (PQR),析取范式,C(PQR) (PQR) (PQR) (PQR) (PQR) (PQR),C(PQ) (PR)(QR),析取范式,析取范式不惟一,范式并不是惟一的,定義5.5 （極大項，極小項） 按順序取n個原子命題變元中每一個句節(jié)一次 且僅一次 構(gòu)成的子句（短語），稱為關(guān)于這 n個變元的極大項（極小項）。,例如:3個命題變元P，Q，R,短語： PQR , PQ, PQR Q,極小項,子句： PQ, PQP , PQRQ， PQ R,極大項,寫出兩個原子命題變元P,Q能夠成的所有極大項、 極小項,兩個原子命題變元能構(gòu)成的所有極大項、極小項,每一個極大

39、項有且只有一組成假賦值；不同極大項成假賦值不同。,每一個極小項有且只有一組成真賦值；不同極小項成真賦值不同。,PQ,PQ,PQ,PQ,極大項：,極小項：,PQ,PQ,PQ,PQ,任兩個極大項的析取式為重言式。 全體極大項的合取式為矛盾式。,任兩個極小項的合取式為矛盾式。 全體極小項的析取式為重言式。,n個命題變元能構(gòu)成 多少 個極大項（極小項）？,2n,PQ R,PQR,PQR,P QR,寫出3個命題變元P、Q、R構(gòu)成的所有極大項,P QR,PQR,PQR,PQR,000,001,010,011,100,101,110,111,M0,M1,M2,M3,M4,M5,M6,M7,定義5.6，5.7

40、 主范式（正則范式）,設(shè)A是包含原子命題變元P1,P2,Pn的公式，若A的一個合取范式中每個子句都是極大項，則稱該合取范式是A的主合取范式（正則合取范式）。若A的一個析取范式中每個短語都是極小項，則稱該析取范式是A的主析取范式（正則析取范式）。,A=(PQ) (QR) (PR),是合取范式， 不是主合取范式,能否求出A的主范式？,等價演算法求主范式,例6 求A=(PQ) (QR) (PR)的 主合取范式和主析取范式。,A=(PQ) (QR) (PR),(Q(PR) )(PR),(QP)(QR)(PRP)(PRR), (QP)(QR)(PR),合取范式,析取范式,與主合取范式的差異在哪里？,與主

41、析取范式的差異在哪里？,m2 m3 m5 m7,M0 M1 M4 M6,主合取范式：,主析取范式：,A=(PQ) (QR) (PR),A有且只有4組成假賦值： 000，001，100，110,A有且只有4組成真賦值： 010，011，101，111,從主范式可以得出公式 的成真、成假賦值,反之呢？,主范式與真值表之間的關(guān)系：,定理5.4 在公式A的真值表中，使A的成假賦值 所對應(yīng)的A的極大項的合取式就是A的主合取范式。,定理5.8 在公式A的真值表中，使A的成真賦值 所對應(yīng)的A的極小項的析取式就是A的 主析取范式。,例 真值表法求A= (P Q ) R的 主合取范式和主析取范式。,真值表法求主

42、范式,解：列真值表，找出成假賦值和成真賦值 。,A(PQR)(PQR)(PQR),成假賦值(PQR)： 000,010,110,對應(yīng)極大項： M000=PQR,=M0,M010=PQR,=M2,M110=PQR,=M6,A M0 M2 M6,A m1 m3 m4 m5 m7,A= (P Q ) R,主合取范式,主析取范式,定理5.5,5.7，5.9 （主范式存在惟一性） 任何公式都有與之等價的主合?。ㄎ鋈。┓妒?， 且惟一。,矛盾式和重言式的主合取范式、主析取范式。,矛盾式的主合取范式包含每一個極大項,A(P1,P2,Pn) F M0 M1 M2 M2n-1,重言式的主析取范式包含每一個極小項,A(P1,P2,Pn) T m0 m1 m2 m2n-1,矛盾式無成真賦值，其主析取范式不包含極小項， 記做F。,重言式無成假賦值，其主合取范式不包含極大項， 記做T。,1-1-6 其他邏輯聯(lián)結(jié)詞,定義 6.1 不可兼或