01離散數(shù)學(xué)課件資料

1、2020/7/21,離散數(shù)學(xué),1,參考教材：,1、離散數(shù)學(xué)、離散數(shù)學(xué) 理論.分析.題解 左孝凌、李為鑑、劉永才，上?？茖W(xué)技術(shù)文獻(xiàn)出版社 2、離散數(shù)學(xué)（修訂版） 耿素云、屈婉玲，高等教育出版社 3、離散數(shù)學(xué)（第三版） 耿素云、屈婉玲、張立昂，清華大學(xué)出版社 4、離散數(shù)學(xué)及其應(yīng)用（原書第5版） （美）Kenneth H.Rosen著，袁崇義、屈婉玲、王悍貧、 劉田 譯， 機(jī)械工業(yè)署版社,2020/7/21,離散數(shù)學(xué),2,離散數(shù)學(xué)，是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，是計(jì)算機(jī)科學(xué)中基礎(chǔ)理論的核心課程。離散數(shù)學(xué)是以研究離散量的結(jié)構(gòu)和相互間的關(guān)系為主要目標(biāo)，其研究對(duì)象一般地是有限個(gè)或可數(shù)個(gè)元素，因此充分描述了計(jì)算

2、機(jī)科學(xué)離散性的特點(diǎn)。 離散數(shù)學(xué)是隨著計(jì)算機(jī)科學(xué)的發(fā)展而逐步建立的， 它形成于七十年代初，是一門新興的工具性學(xué)科。,2020/7/21,離散數(shù)學(xué),3,邏輯學(xué):研究思維(或推理)的形式結(jié)構(gòu)和規(guī) 律的學(xué)科。利用數(shù)學(xué)方法研究思維(或推理)的形式結(jié)構(gòu)和規(guī)律的學(xué)科，稱作數(shù)理邏輯。,數(shù)理邏輯,數(shù)理邏輯的基本內(nèi)容：命題邏輯(演算)、謂詞邏輯。它們對(duì)電子元件設(shè)計(jì)和性質(zhì)分析，對(duì)邏輯程序設(shè)計(jì)語(yǔ)言的研制具有十分重要的意義。,2020/7/21,離散數(shù)學(xué),4,第一章 命題邏輯 1.1 命題符號(hào)化與聯(lián)結(jié)詞 1.2 命題公式及其賦值 1.3 等值演算 1.4 聯(lián)結(jié)詞的完備集 1.5 對(duì)偶與范式 1.6 推理理論,2020/

3、7/21,離散數(shù)學(xué),5,一、命題的概念,命題：能判斷真假的陳述句。這種判斷只有兩種 可能，一種是正確的判斷，一種是錯(cuò)誤的 判斷。,1.1 命題符號(hào)化及聯(lián)結(jié)詞,命題真值：判斷為正確的命題稱其命題真值為真(1) ； 判斷為錯(cuò)誤的命題稱其命題真值為假(0) ； 命題是具有唯一真值的陳述句。,2020/7/21,離散數(shù)學(xué),6,例1 判斷下列句子中哪些是命題。,(1) 4是素?cái)?shù)。 (2) 2 + 3 = 5。 (3) 雪是黑色的。 (4) 3能被2整除。 (5) 2050年元旦是晴天。 (6) 5x + 1 11。 (7) 這朵花真美麗呀！ (8) 明天下午開(kāi)會(huì)嗎？ (9) 我正在說(shuō)假話。,(是),(是

4、),(是),(是),(是),(否),(否),(否),(否),2020/7/21,離散數(shù)學(xué),7,解題思想：判斷一個(gè)句子是否為命題，首先看它是否為陳述句，,其次看它的真值是否唯一。,2020/7/21,離散數(shù)學(xué),8,二、與命題相關(guān)的幾個(gè)概念,1、簡(jiǎn)單命題(或原子命題)： 命題為簡(jiǎn)單的陳述句，不能分解成更簡(jiǎn)單的句子。一般用小寫的英文字母p, q, r, 表示。,2、命題常項(xiàng)(或命題常元)： 由于簡(jiǎn)單命題的真值確定，故又稱之為命題常項(xiàng) 或命題常元。 如例1中的陳述句(1) (2) (3) (4) (5)。,2020/7/21,離散數(shù)學(xué),9,二、與命題相關(guān)的幾個(gè)概念（續(xù)）,3、命題變項(xiàng)(或命題變?cè)?：

5、真值可以變化的簡(jiǎn)單陳述句，但它不是命題,也可以用p,q,r等表示。 如例1中的陳述句(6) (5x + 1 11)。,4、復(fù)合命題： 由簡(jiǎn)單命題用聯(lián)結(jié)詞聯(lián)結(jié)而成的命題。 命題邏輯主要就是研究復(fù)合命題。,5、命題的符號(hào)化： 用符號(hào)來(lái)表示命題。,2020/7/21,離散數(shù)學(xué),10,三、聯(lián)結(jié)詞,先看一個(gè)例子： 例2：判斷下列命題是否為復(fù)合命題，說(shuō)出其聯(lián)結(jié)詞。 (1) 3不是偶數(shù)。 (2) 2是偶素?cái)?shù)。 (3) 2或4是素?cái)?shù)。 (4) 如果2是素?cái)?shù)，3也是素?cái)?shù)。 (5) 2是素?cái)?shù)當(dāng)且僅當(dāng)4也是素?cái)?shù)。,(非),(且),(或),(如果,則),(當(dāng)且僅當(dāng)),2020/7/21,離散數(shù)學(xué),11,三、聯(lián)結(jié)詞（續(xù)

6、）,常見(jiàn)的基本聯(lián)結(jié)詞： 1、否定聯(lián)結(jié)詞“ ”，讀作“非”。 復(fù)合命題“非p ”稱作p 的否定式，記作“ p ”。 p 為真當(dāng)且僅當(dāng)p 為假。,在命題“3不是偶數(shù)”中，設(shè)p 表示“3是偶數(shù)”，則 p 表示“3不是偶數(shù)”。顯然，p 真值為0， p 真值 為1 。,2020/7/21,離散數(shù)學(xué),12,三、聯(lián)結(jié)詞（續(xù)）,2、合取聯(lián)結(jié)詞“ ”，讀作“合取”。 復(fù)合命題“ p并且q ”稱作p 與q 的合取式，記“ p q ”。 p q 為真當(dāng)且僅當(dāng)p 與q 同時(shí)為真。,在命題“2是偶素?cái)?shù)”中，設(shè) p 表示“2是素?cái)?shù)”， q 表示“2是偶數(shù)”，則 p q 表示“2是偶素?cái)?shù)”。因?yàn)?p和q 的真值均為1， 所

7、以 p q 的真值為1 。,聯(lián)結(jié)詞“既又”，“不但而且”，“雖然但是”等，都可符號(hào)化為 。,2020/7/21,離散數(shù)學(xué),13,三、聯(lián)結(jié)詞（續(xù)）,3、析取聯(lián)結(jié)詞“ ”，讀作“析取”。 復(fù)合命題“ p或q ”稱作 p與q 的析取式，記作“p q ”。 p q 為真當(dāng)且僅當(dāng) p 與 q 中至少一個(gè)為真。,在命題“2或4是素?cái)?shù)”中，設(shè) p 表示“2是素?cái)?shù)”， q 表示“4是素?cái)?shù)”，則 p q 表示“2或4是素?cái)?shù)”。,注意：“或”的二義性。如命題：派小王或小李中 的一人去開(kāi)會(huì)，應(yīng)符號(hào)化為( p q ) ( p q ), 這類“或”表達(dá)的是排斥或。,2020/7/21,離散數(shù)學(xué),14,三、聯(lián)結(jié)詞（續(xù)）,

8、4、蘊(yùn)涵聯(lián)結(jié)詞“ ”，讀作“蘊(yùn)涵”。 復(fù)合命題“ 如果 p，則 q ”稱作p 與q 的蘊(yùn)涵式，記作 “ p q ”。其中 p 稱為蘊(yùn)涵式的前件， q 稱為蘊(yùn)涵 式的后件。 p q 為假當(dāng)且僅當(dāng) p 為真且 q 為假。,在命題“如果2是素?cái)?shù)，3也是素?cái)?shù)”中，設(shè) p 表示“2是素?cái)?shù)”，q 表示“3是素?cái)?shù)”，則 p q 表示“如果2是素?cái)?shù)，則3也是素?cái)?shù)”。,聯(lián)結(jié)詞“只要 p 就 q ”，“ p 僅當(dāng) q ”，“只有q才p ”等，都表示q是p的必要條件,因此都可符號(hào)化為 p q 。,2020/7/21,離散數(shù)學(xué),15,三、聯(lián)結(jié)詞（續(xù)）,5、等價(jià)聯(lián)結(jié)詞“ ”，讀作“等價(jià)”。 復(fù)合命題“ p 當(dāng)且僅當(dāng) q

9、 ”稱作 p 與 q 的等價(jià)式，記 作“ p q ”。 p q 為真當(dāng)且僅當(dāng) p 與 q 真值相同。,在命題“2是素?cái)?shù)當(dāng)且僅當(dāng)4也是素?cái)?shù)”中，設(shè) p 表示“2是素?cái)?shù)”，q 表示“4是素?cái)?shù)”，則 p q 表示“2是素?cái)?shù)當(dāng)且僅當(dāng)4是素?cái)?shù)”,由于p、q的真值分別為1、0，所以p q的真值為0。,2020/7/21,離散數(shù)學(xué),16,真值表,利用以上5種聯(lián)結(jié)詞，可將復(fù)合命題符號(hào)化，進(jìn) 而正確分析出復(fù)合命題的真值?；菊嬷当砣缦拢?p q, p,p q,p q,p q,p q,0 0,0 1,1 0,1 1,1 1 0 0,0 0 0 1,0 1 1 1,1 1 0 1,1 0 0 1,表1.1,2020

10、/7/21,離散數(shù)學(xué),17,(1) 李平不是不聰明，而是不用功。 (2) 李文和李武是兄弟。 (3) 只有不下雨，我才騎自行車上班。 (4) 如果下雨，我就不騎自行車上班。 (5) 我去書店看看，除非我很累。,設(shè)p:我很累,q:我去書店看看,則符號(hào)化為 p q,例3 將下列命題符號(hào)化,設(shè)p:李文和李武是兄弟，則符號(hào)化為p,設(shè)p:天下雨,q:我騎自行車上班, p是q的必要條件則符號(hào)化為q p,設(shè)p:天下雨,q:我騎自行車上班,則符號(hào)化為p q,設(shè)p:李平聰明，q:李平用功,則符號(hào)化為 ( p) q,解題步驟: (1) 分析出各簡(jiǎn)單 命題，并符號(hào)化； (2) 使用合適的聯(lián) 結(jié)詞，把簡(jiǎn)單命題 逐個(gè)聯(lián)

11、結(jié)起來(lái)，組 成一復(fù)合命題的符 號(hào)化形式。,2020/7/21,離散數(shù)學(xué),18,例3 將下列命題符號(hào)化（續(xù)）,(6) 2 + 2 4，當(dāng)且僅當(dāng)3不是奇數(shù)。 (7)小王是游泳冠軍或百米賽跑冠軍。 (8) 小王現(xiàn)在在宿舍或在圖書館。 (9) 選小王或小李中的一人當(dāng)副班長(zhǎng)。,設(shè)p:2 + 2 = 4，q:3是奇數(shù), 則符號(hào)化為 p q,設(shè)p:選小王當(dāng)副班長(zhǎng)，q:選小李當(dāng)副班長(zhǎng),則符號(hào)化為(p q) ( p q),設(shè)p:小王在宿舍，q:小王在圖書館,符號(hào)化為p q,這里的“或”本來(lái)是排斥或，排斥或一般不能直接用“ ”聯(lián)結(jié)，但兩個(gè)命題不能同時(shí)為真時(shí)例外，因此,命題可符號(hào)化為p q ，其中p:小王在宿舍，q

12、:小王在圖書館,設(shè)p:小王是游泳冠軍，q:小王是百米賽跑冠軍,符號(hào)化為p q,2020/7/21,離散數(shù)學(xué),19,例3 將下列命題符號(hào)化（續(xù)）,(10) 如果我上街，我就去書店看看，除非我很累。 (11)王一樂(lè)是計(jì)算機(jī)系的學(xué)生, 他生于1968年或1969 年, 他是三好學(xué)生。,設(shè)p：我上街，q：我去書店看看，r：我很累， r是（pq）的充分條件則符號(hào)化為r (p q),該命題也可敘述為“如果我不累并且我上街，則我就去書店看看?！保虼耍?0）也可符號(hào)化為( r p ) q,設(shè)p：王一樂(lè)是計(jì)算機(jī)系的學(xué)生，q：他生于1968年，r：他生于1969年，s：他是三好學(xué)生，則符號(hào)化為：p (q r)

13、s,2020/7/21,離散數(shù)學(xué),20,合式公式：,一、命題公式的概念,1.2 命題公式及其賦值,(1) 單個(gè)命題常項(xiàng)或變項(xiàng)p, q, , 0, 1是合式公式；,(2) 若A是合式公式，則 A也是合式公式；,(3) 若A, B是合式公式，則(A B), (A B), (A B), (A B)是合式公式;,合式公式即稱為命題公式。,(4) 只有有限次地應(yīng)用(1) (3)組成的符號(hào)串才是 合式公式。,2020/7/21,離散數(shù)學(xué),21,一個(gè)含有命題變項(xiàng)的命題公式的真值是不確定的，只有用指定的命題常項(xiàng)代替后真值才唯一確定。,二、命題公式的解釋或賦值,設(shè)A為一命題公式，p1, p2, , pn為出現(xiàn)在

14、A中的所有的命題變項(xiàng)。給p1, p2, , pn指定一組真值，稱為對(duì)A的一個(gè)賦值或解釋。,若指定的一組真值使命題公式A的真值為1，則 稱這組賦值為A的成真賦值；若使A的真值為0，則 稱這組賦值為A的成假賦值。,將命題公式A在所有賦值下的取值情況列成表， 稱為A的真值表。,2020/7/21,離散數(shù)學(xué),22,(3)對(duì)應(yīng)每個(gè)賦值，計(jì)算命題公式各層次的值，直到 最后計(jì)算出命題公式的值。,二、命題公式的解釋或賦值（真值表）,構(gòu)造真值表的步驟：,命題運(yùn)算的優(yōu)先級(jí)順序：(1)先括號(hào) (2) (3) , (4) (5) (6) 從左至右,(1)找出命題公式中所有命題變項(xiàng)：p1 , p2 , , pn , 列

15、出所有可能的賦值(2n個(gè))。,2020/7/21,離散數(shù)學(xué),23,二、命題公式的解釋或賦值（真值表）,例4：求下列命題的真值表 (1) ( p) q (2) ( p ( p q ) q (3) ( p q ) q,2020/7/21,離散數(shù)學(xué),24,二、命題公式的解釋或賦值（真值表）,(1) ( p) q,2020/7/21,離散數(shù)學(xué),25,二、命題公式的解釋或賦值（真值表）,(2) (p ( p q ) q,表1.3,2020/7/21,離散數(shù)學(xué),26,二、命題公式的解釋或賦值（真值表）,(3) ( p q ) q,2020/7/21,離散數(shù)學(xué),27,三、命題公式的類型,命題公式A在各種賦值

16、下取 值恒為真，則A為重言式。,命題公式A在各種賦值下取 值恒為假，則A為矛盾式。,命題公式A至少存在一組賦值是成真 賦值，則A為可滿足式。,1、重言式(或永真式)： 2、矛盾式(或永假式)： 3、可滿足式：,2020/7/21,離散數(shù)學(xué),28,三、命題公式的類型,3、真值表可以用來(lái)判斷公式的類型： （1）若真值表最后一列全為1，則公式為重言式；,1、可滿足式至少存在一組成真賦值。,2、重言式一定是可滿足式，反之不真。,從以上定義可以看出以下幾點(diǎn)：,（2）若真值表最后一列全為0，則公式為矛盾式；,（3）若真值表最后一列至少有一個(gè)1，則公式為 可滿足式。,2020/7/21,離散數(shù)學(xué),29,一、

17、等值演算的概念,等值關(guān)系是自反的、對(duì)稱的和傳遞的，因而為 等價(jià)關(guān)系。,等值演算：按一定方法尋找某個(gè)復(fù)合命題公式的等 值式的過(guò)程。,1.3 等值演算,等值公式：設(shè)A, B為兩命題公式，若等價(jià)式A B 是重言式，稱A與B等值。記作:A B,用真值表可以驗(yàn)證公式等值。,2020/7/21,離散數(shù)學(xué),30,例5：判斷命題是否等值 ( p q) 與 p q,不 等 值,一、等值演算的概念（續(xù)）,2020/7/21,離散數(shù)學(xué),31,二、常用的重要等值公式表,1、A ( A),2、A A A,3、A A A,4、A B B A,5、A B B A,6、(A B) C A (B C),7、(A B) C A

18、(B C),雙重否定律,結(jié)合律,交換律,等冪律,2020/7/21,離散數(shù)學(xué),32,二、常用的重要等值公式表（續(xù)）,分配律,零律,吸收律,德摩根律,8、A (B C ) (A B) (A C),9、A (B C ) (A B) (A C),10、 (A B) A B,11、 (A B) A B,12、A (A B) A,13、A (A B) A,14、A 1 1,15、A 0 0,2020/7/21,離散數(shù)學(xué),33,二、常用的重要等值公式表（續(xù)）,同一律,歸謬論,蘊(yùn)涵等值式,排中律,16、A 0 A,17、A 1 A,19、A A 0,20、A B A B,21、A B (A B) (B A

19、),22、A B B A,23、A B A B,24、(A B) (A B ) A,18、A A 1,矛盾律,等價(jià)否定等值式,等價(jià)等值式,假言易位,2020/7/21,離散數(shù)學(xué),34,以上24個(gè)等值式必須熟記，并注意其中所含的 A, B, C可以是任意的一個(gè)命題公式，因而每個(gè)公式 是一個(gè)模式，可以代表無(wú)數(shù)多個(gè)同類型的命題公式。,利用24個(gè)基本等值式，不用真值表法也可以推 演出很多等值式。,二、常用的重要等值公式表（續(xù)）,2020/7/21,離散數(shù)學(xué),35,設(shè) (A)是含命題公式A的命題公式, (B)是用B置換了 (A)中的A之后得 到的命題公式。若A B, 則 (A) (B) 。,此外，在進(jìn)行

20、等值演算時(shí)，常常用到：,置換定理,二、常用的重要等值公式表（續(xù)）,如： (A)： p (q r)， A： q r B： q r， (B)： p ( q r),由于： A B，故 (A) (B),2020/7/21,離散數(shù)學(xué),36,例6：驗(yàn)證下列等值式 (1) p (q r) ( p q) r (2) p ( p q) ( p q),解題思想: 可以從左或右的任一個(gè)公式開(kāi)始演算；演算的每一步都要用置換定理。,三、應(yīng)用,2020/7/21,離散數(shù)學(xué),37,例6：驗(yàn)證下列等值式 (1) p (q r) ( p q) r, p ( q r), ( p q) r,蘊(yùn)涵等值式,蘊(yùn)涵等值式,結(jié)合律,德摩根律

21、,蘊(yùn)涵等值式,三、應(yīng)用（續(xù)）,2020/7/21,離散數(shù)學(xué),38,例6：驗(yàn)證下列等值式 (2) p ( p q) (p q), ( p q) ( p q),同一律,排中律,分配律,三、應(yīng)用（續(xù)）,2020/7/21,離散數(shù)學(xué),39,例7：判別下列公式的類型 (1) q ( p q ) p ) (2) ( p p ) (q q) r) (3) ( p q ) p,解題思想: 真值表法和等值演算都可以用來(lái)判別公式的類型，但等值演算更為簡(jiǎn)單快捷。,三、應(yīng)用（續(xù)）,2020/7/21,離散數(shù)學(xué),40,例7：判別下列公式的類型 (1) q ( p q ) p ),解： (1) q ( p p ) (q

22、p), q (0 (q p), q (q p), q ( q p), (q q) p, 1 p, 1,分配律,矛盾律,同一律,德摩根律,結(jié)合律,排中律,零律,重 言 式,三、應(yīng)用（續(xù)）,2020/7/21,離散數(shù)學(xué),41,例7：判別下列公式的類型 (2) ( p p) (q q) r), 1 (0 r), 1 0, 0,矛盾律,零律,排中律,矛 盾 式,三、應(yīng)用（續(xù)）,解： (2) 1 (q q) r),2020/7/21,離散數(shù)學(xué),42,例7：判別下列公式的類型 (3) ( p q) p,解： (3) ( p q) p, p,吸收律,蘊(yùn)涵等值式,可 滿 足 式,三、應(yīng)用（續(xù)）,2020/7/

23、21,離散數(shù)學(xué),43,除了前面我們介紹的5種基本聯(lián)結(jié)詞，這里再給 出邏輯設(shè)計(jì)中常用的3種：,1.4 聯(lián)結(jié)詞的完備集,2020/7/21,離散數(shù)學(xué),44,2、與非：復(fù)合命題“ p與q 的否定”稱作p 與q 的與非 式，記作“ p q ”。 p q為真當(dāng)且僅當(dāng) p, q不同時(shí)為真。,等值關(guān)系：p q ( p q),3、或非：復(fù)合命題“ p或q 的否定”稱作p 與q 的或非 式，記作“ p q ”。 p q為真當(dāng)且僅當(dāng) p, q同時(shí)為假。,等值關(guān)系：p q ( p q),2020/7/21,離散數(shù)學(xué),45,真值表,2020/7/21,離散數(shù)學(xué),46,冗余聯(lián)結(jié)詞和獨(dú)立聯(lián)結(jié)詞：在聯(lián)結(jié)詞集合中, 如果 一

24、個(gè)聯(lián)結(jié)詞可以由集合中其它的聯(lián)結(jié)詞來(lái) 定義，則稱此聯(lián)結(jié)詞為冗余聯(lián)結(jié)詞，否則 稱為獨(dú)立聯(lián)結(jié)詞。 例如: , ， 中的 或是冗余聯(lián)結(jié)詞.,全功能集：如果任一真值函數(shù)(公式)，都可以僅用某一聯(lián) 結(jié)詞集合中的聯(lián)結(jié)詞的命題公式表示，則稱該集合為全功能集。例如: , ， ， , ， , ， ,不含冗余聯(lián)結(jié)詞的全功能集稱為極小全功能集。,2020/7/21,離散數(shù)學(xué),47,常見(jiàn)的全功能集（也是極小全功能集）: , , , , , , , ,2020/7/21,離散數(shù)學(xué),48,又： (p q) 0 的對(duì)偶式： (p q) 1,如： p (q r)的對(duì)偶式是 p (q r),一、對(duì)偶式的概念,在常見(jiàn)的基本等值式中

25、，多數(shù)公式是成對(duì)出現(xiàn)的，它們相互構(gòu)成對(duì)偶式。,對(duì)偶式：在僅含有聯(lián)結(jié)詞 , , 的命題公式A中， 將 換成 ， 換成 ，0換成1，1換成0， 所得命題公式稱為A的對(duì)偶式。記作：A*,顯然，對(duì)偶式是相互的，即(A*)*= A,1.5 對(duì)偶與范式,2020/7/21,離散數(shù)學(xué),49,設(shè)A與A*互為對(duì)偶式，P1, P2, , Pn是出現(xiàn) 在A和A*中的所有命題變?cè)?，如果用n元函 數(shù)的形式表達(dá)，則有 (1) A (P1 , P2 , , Pn ) A*( P1 , P2 , , Pn ) (2) A ( P1 , P2 , , Pn) A*( P1 , P2 , , Pn ),二、關(guān)于對(duì)偶式的兩個(gè)定理,

26、定理,2020/7/21,離散數(shù)學(xué),50,如：設(shè)A (p, q, r) p (q r),二、關(guān)于對(duì)偶式的兩個(gè)定理（續(xù)）,則 A (p, q, r) ( p (q r) ) p ( q r) A*(p, q, r) p (q r) A*( p, q, r) p ( q r),于是有 A (p, q, r) A*( p, q, r),又 A ( p, q, r) p ( q r)， A*(p, q, r) ( p (q r) ) p ( q r)，,于是有 A ( p, q, r) A*( p, q, r),2020/7/21,離散數(shù)學(xué),51,設(shè)A與B為兩命題公式，如果A B， 則A* B*。,二

27、、關(guān)于對(duì)偶式的兩個(gè)定理（續(xù)）,由此可知： A*為重言式 A為矛盾式 A*為矛盾式 A為重言式 A*為可滿足式 A為可滿足式 “兩公式等值” “兩公式的對(duì)偶式等值”,對(duì)偶定理,2020/7/21,離散數(shù)學(xué),52,僅由有限個(gè)命題變?cè)蚱浞穸?gòu)成的 析取式，如 p q， p q。,三、范式的概念,顯然：簡(jiǎn)單析取式是重言式，當(dāng)且僅當(dāng)它同時(shí)含有 一個(gè)命題變項(xiàng)及其否定； 簡(jiǎn)單合取式是矛盾式，當(dāng)且僅當(dāng)它同時(shí)含有 一個(gè)命題變項(xiàng)及其否定。,僅由有限個(gè)命題變?cè)蚱浞穸?gòu)成的 合取式，如 p q。,簡(jiǎn)單析取式： 簡(jiǎn)單合取式：,2020/7/21,離散數(shù)學(xué),53,僅由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式。 如A=A1 A2

28、An , Ai (i =1, 2, , n)為簡(jiǎn)單合取式。,三、范式的概念（續(xù)）,由對(duì)偶的定義知：析取范式的對(duì)偶式為合取范式，合取范式的對(duì)偶式為析取范式。,性質(zhì)：析取范式為矛盾式，當(dāng)且僅當(dāng)構(gòu)成它的每一個(gè)簡(jiǎn)單合取式都是矛盾式；合取范式為重言式，當(dāng)且僅當(dāng)構(gòu)成它的每一個(gè)簡(jiǎn)單析取式都是重言式。,僅由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式。 如A=A1 A2 An , Ai (i =1, 2, , n)為簡(jiǎn)單析取式。,析取范式： 合取范式：,2020/7/21,離散數(shù)學(xué),54,任一命題公式都存在著與之等值 的析取范式和合取范式。,求范式的步驟：,(2) 的消去或內(nèi)移。利用德摩根律或雙重否定律,三、范式的概念（續(xù)）

29、,范式存在定理,(1) 消去對(duì) , , 來(lái)說(shuō)冗余的聯(lián)結(jié)詞。 , , 是全功能集，其他聯(lián)結(jié)詞都可用基本等值式消去,(3) 利用分配律。求析取范式，可利用 對(duì) 的分配 律；求合取范式，可利用 對(duì) 的分配律。,2020/7/21,離散數(shù)學(xué),55,三、范式的概念（續(xù)）,2020/7/21,離散數(shù)學(xué),56,例8：求命題公式( ( p q ) r ) p 的合取范式和 析取范式。,解：(1) 求析取范式 ( ( p q ) r ) p, ( p q ) r ) p, ( p r ) ( q r ) p, p ( q r ),四、應(yīng)用, ( p q ) r ) p, ( p q ) r ) p,2020/7

30、/21,離散數(shù)學(xué),57,例8：求命題公式( ( p q ) r ) p 的合取范式和 析取范式。,四、應(yīng)用（續(xù)）,解： (2) 求合取范式 ( ( p q ) r ) p, ( p q ) r ) p, ( p q p ) ( r p ), ( p q) ( r p ),2020/7/21,離散數(shù)學(xué),58,值得注意的是，任何命題公式的析取范式或合取 范式不唯一，因而不能作為命題公式的標(biāo)準(zhǔn)型。為 此，我們進(jìn)一步引入“主析取范式”、“主合取范式” 的概念。它們是用極小項(xiàng)、極大項(xiàng)來(lái)定義的。,2020/7/21,離散數(shù)學(xué),59,注1：其中 指pi或pi，1 i n 注2：極小項(xiàng)、極大項(xiàng)中必含有n-1個(gè)

31、聯(lián)結(jié)詞 注3： 一定位于第i個(gè)位置，順序不能亂,五、主析取范式與主合取范式,極小項(xiàng)： 極大項(xiàng)：,2020/7/21,離散數(shù)學(xué),60,五、主析取范式與主合取范式（續(xù)）,pqr pqr pqr pqr pqr pqr pqr pqr,成 真 賦 值,極小項(xiàng)的表示（以3個(gè)命題變項(xiàng)為例）：,000 - 0，記作m0 001 - 1，記作m1 010 - 2，記作m2 011 - 3，記作m3 100 - 4，記作m4 101 - 5，記作m5 110 - 6，記作m6 111 - 7，記作m7,2020/7/21,離散數(shù)學(xué),61,五、主析取范式與主合取范式（續(xù)）,極小項(xiàng)的性質(zhì)（以3個(gè)命題變項(xiàng)為例）：,

32、（1）每一個(gè)極小項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為1，在其余7(2n-1)種指派情況下均為0。,（2）任意兩個(gè)不同的極小項(xiàng)的合取式永假。如： m0m3 = (pqr) (pqr) 0,（3）全體極小項(xiàng)的析取式永真,m0 m1 m2n-1 1,2020/7/21,離散數(shù)學(xué),62,五、主析取范式與主合取范式（續(xù)）,成 假 賦 值,極大項(xiàng)的表示（以3個(gè)命題變項(xiàng)為例）：,000 - 0，記作M0 001 - 1，記作M1 010 - 2，記作M2 011 - 3，記作M3 100 - 4，記作M4 101 - 5，記作M5 110 - 6，記作M6 111 - 7，記作M7,pqr pqr pqr

33、pqr pqr pqr pqr pqr,2020/7/21,離散數(shù)學(xué),63,五、主析取范式與主合取范式（續(xù)）,極大項(xiàng)的性質(zhì)（以3個(gè)命題變項(xiàng)為例）：,（1）每個(gè)極大項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其 真值為0，在其余7(2n-1)種指派情況下均為1。,（2）任意兩個(gè)不同的極大項(xiàng)的析取式永真。如： M0 M3 = (pqr) (pqr) 1,（3）全體極大項(xiàng)的合取式永假。,M0 M1 M2n-1 0,2020/7/21,離散數(shù)學(xué),64,五、主析取范式與主合取范式（續(xù)）,任何命題公式的主析取范式和主合取范式 一定存在，并且唯一。,定理,主析取范式： 主合取范式：,命題公式A的析取范式中的簡(jiǎn)單合取式 全是

34、極小項(xiàng)。特別地約定，矛盾式的 主析取范式為0。,命題公式A的合取范式中的簡(jiǎn)單析取式 全是極大項(xiàng)。特別地約定，重言式的主合取范式為1。,2020/7/21,離散數(shù)學(xué),65,(4) 將極小項(xiàng)按從小到大的順序排列，并用表示 如m1 m4 m5 (1, 4, 5),給定命題公式A的主析取范式的求解步驟:,五、主析取范式與主合取范式（續(xù)）,(1) 求A的析取范式A,(2) 若A的某簡(jiǎn)單合取式B中不含命題變項(xiàng)pi 或 pi， 則展開(kāi)B如下： BB 1 B (pi pi)(B pi) (B pi),(3) 消去重復(fù)出現(xiàn)的命題變項(xiàng)、極小項(xiàng)和矛盾式。,2020/7/21,離散數(shù)學(xué),66,(4) 將極大項(xiàng)按從小到

35、大的順序排列，并用表示 如M1 M4 M5 (1, 4, 5),給定命題公式A的主合取范式的求解步驟:,五、主析取范式與主合取范式（續(xù)）,(1) 求A的合取范式A,(2) 若A的某簡(jiǎn)單析取式B中不含命題變項(xiàng)pi 或 pi， 則展開(kāi)B如下： BB 0 B (pi pi)(B pi) (B pi),(3) 消去重復(fù)出現(xiàn)的命題變項(xiàng)、極大項(xiàng)和重言式。,2020/7/21,離散數(shù)學(xué),67,例9：求公式( p r) q) (q p)的主析取范式和 主合取范式。,六、應(yīng)用,解： (1) 求主析取范式 ( p r) q) (q p), ( p r) q) ( q p), ( p r) ( q p) (q (

36、q p),2020/7/21,離散數(shù)學(xué),68,六、應(yīng)用（續(xù)）, ( p q) (r q) (r p) (q p), ( p q r) ( p q r) ( p q r) ( p q r) ( p q r) ( p q r) ( p q r) ( p q r), m0 m1 m5 m6 m7,(0, 1, 5, 6, 7),2020/7/21,離散數(shù)學(xué),69,六、應(yīng)用（續(xù)）,(2) 求主合取范式 (p r) q) (q p), ( p r) q) ( q p), ( p r q) ( q p), ( p q r) (p q r ) (p q r), M4 M3 M2,(2, 3, 4),2020

37、/7/21,離散數(shù)學(xué),70,五、主析取范式與主合取范式（續(xù)）,在真值表中，一個(gè)公式的真值為1的指派（成真賦值）所對(duì)應(yīng)的極小項(xiàng)的析取式，即為公式的主析取范式。,在真值表中，一個(gè)公式的真值為0的指派（成假賦值）所對(duì)應(yīng)的極大項(xiàng)的合取式，即為公式的主合取范式。,定理,定理,真值表法求公式的主析取范式和主合取范式。,2020/7/21,離散數(shù)學(xué),71,五、主析取范式與主合取范式（續(xù)）,例10. 試用真值表法求命題公式(p r) q) (q p) 的成真賦值、成假賦值、主析取范式、主合取范式。,p r (p r) q q p (p r) q) (q p),1 1 1 1 0 1 0 1,1 1 1 1 0

38、 1 1 1,1 1 0 0 1 1 1 1,1 1 0 0 0 1 1 1,2020/7/21,離散數(shù)學(xué),72,五、主析取范式與主合取范式（續(xù)）,解：由真值表可知，公式A的成真賦值為000、001、 101、110、111，其對(duì)應(yīng)的極小項(xiàng)分別為m0、m1、 m5、 m6、m7， 因此公式A的主析取范式為： A m0 m1 m5 m6 m7,由真值表可知，公式A的成假賦值為010、011、100， 其對(duì)應(yīng)的極大項(xiàng)分別為M2 、 M3、 M4， 因此公式A的主合取范式為： A M2 M3 M4,2020/7/21,離散數(shù)學(xué),73,A為重言式，當(dāng)且僅當(dāng)A的主析取范式含所有極小項(xiàng) A為矛盾式，當(dāng)且僅

39、當(dāng)A的主析取范式不含任何極小項(xiàng) A為可滿足式，當(dāng)A的主析取范式中至少含一個(gè)極小項(xiàng),A為重言式，當(dāng)且僅當(dāng)A的主合取范式不含任何極大項(xiàng) A為矛盾式，當(dāng)且僅當(dāng)A的主合取范式含所有極大項(xiàng) A為可滿足式，當(dāng)A的主合取范式中至多含七個(gè)極大項(xiàng),六、應(yīng)用（續(xù)）,主析取范式（主合取范式）的用途：,(2) 判斷兩命題公式是否等值。通過(guò)判斷兩命題公式 的主析取范式（主合取范式）是否相等,(3) 判斷命題公式的類型。,(1) 求命題公式的成真和成假賦值。,2020/7/21,離散數(shù)學(xué),74,例11：判斷下列命題公式的類型 (1) ( p q) q (2) ( p q) p) q,六、應(yīng)用（續(xù)）,解：(1) ( p q

40、) q, ( p q) q, p q q, 0,矛 盾 式,2020/7/21,離散數(shù)學(xué),75,例11：判斷下列命題公式的類型 (1) ( p q) q (2) ( p q) p) q,六、應(yīng)用（續(xù)）, ( p q) p) q,解：(2) ( p q) p) q, ( p q) p q, ( p q) ( p q) ( p q) ( p q),重 言 式, m2 m1 m0 m3,(0, 1, 2, 3),2020/7/21,離散數(shù)學(xué),76,六、應(yīng)用（續(xù)）,設(shè)命題公式含n個(gè)命題變項(xiàng)，其主析取范式中含k個(gè)極小項(xiàng) ，不含極小項(xiàng) ， 則主合取范式中含極大項(xiàng) ,如：A中含3個(gè)命題變項(xiàng)， A m0 m1

41、 m6 m7 (0, 1, 6, 7),主析取范式和主合取范式的關(guān)系：,則A M2 M3 M4 M5 (2, 3, 4, 5),2020/7/21,離散數(shù)學(xué),77,一、推理的概念,推理：從前提推出結(jié)論的思維過(guò)程。,前提指已知的命題公式，結(jié)論是從前提出發(fā)按照一定的推理規(guī)則推出的命題公式。,邏輯結(jié)論（有效結(jié)論）：若( A1 A2 An ) B 為重言式，,則稱A1, A2, , An推結(jié)論B的推理正確， B是A1, A2, , An的邏輯結(jié)論或有效結(jié)論。,并記之為(A1 A2 An ) B,1.6 推理理論,2020/7/21,離散數(shù)學(xué),78,例12：判斷下面各推理是否正確 (1) 如果天氣涼快，

42、小王就不去游泳。天氣涼快, 所以小王沒(méi)去游泳。 (2) 如果我上街，我一定去新華書店。我沒(méi)上街， 所以我沒(méi)去新華書店。,二、應(yīng)用,解題思想: (1) 將命題符號(hào)化； (2) 寫出前提、結(jié)論和推理的形式結(jié)構(gòu)； (3) 用真值表法、等值演算或主析取范式法進(jìn)行判斷。,2020/7/21,離散數(shù)學(xué),79,(1) 如果天氣涼快，小王就不去游泳。天氣涼快, 所以小王沒(méi)去游泳。,二、應(yīng)用（續(xù)）,解：設(shè)p：天氣涼快，q：小王去游泳,前提： p q , p 結(jié)論： q,推理的形式結(jié)構(gòu)為 ( p q) p) q (*),2020/7/21,離散數(shù)學(xué),80,下面判斷(*)式是否為重言式,二、應(yīng)用（續(xù)）,( p q)

43、 p) q, ( p q) p) q, ( p q) p) q, ( ( p q) p) q, ( p q) p q, ( p q) ( p q) ( p q) ( p q), m3 m1 m0 m2,推 理 正 確, (0, 1, 2, 3),2020/7/21,離散數(shù)學(xué),81,(2) 如果我上街，我一定去新華書店。我沒(méi)上街， 所以我沒(méi)去新華書店。,二、應(yīng)用（續(xù)）,解：設(shè)p：我上街，q：我去新華書店,前提： p q , p 結(jié)論： q,推理的形式結(jié)構(gòu)為 (p q) p) q (*),2020/7/21,離散數(shù)學(xué),82,下面判斷(*)式是否為重言式,二、應(yīng)用（續(xù)）,(p q) p) q, (

44、p q) p) q, ( p q) p) q, ( ( p q) p) q, ( p q) p q, ( p q) ( p q) ( p q), m2 m3 m0,推 理 不 正 確, (0, 2, 3),2020/7/21,離散數(shù)學(xué),83,三、構(gòu)造證明法,推理規(guī)則：在推理過(guò)程中，構(gòu)造證明必須在給定的規(guī)則下進(jìn)行，常用的推理如下：,(1) 前提引入規(guī)則: 證明的任何步驟上，都可引入前提；,證明：描述推理過(guò)程的命題公式序列。,(2) 結(jié)論引入規(guī)則：證明的任何步驟上，所證明的結(jié)論都 可作為后續(xù)證明的前提；,(3) 置換規(guī)則：證明的任何步驟上，命題公式中的任何子 命題公式都可以用與之等值的命題公式置換

45、；,2020/7/21,離散數(shù)學(xué),84,(4) 假言推理規(guī)則：A B, A |= B,三、構(gòu)造證明法（續(xù)）,(5) 附加規(guī)則： A |= A B,(8) 假言三段論規(guī)則： A B, B C |= A C,(11) 合取引入規(guī)則： A, B |= A B,(6) 化簡(jiǎn)規(guī)則： A B |= B,(7) 拒取式規(guī)則： A B, B |= A,(10) 構(gòu)造性二難規(guī)則： A B, C D, A C |= B D,(9) 析取三段論規(guī)則： A B, B |= A,2020/7/21,離散數(shù)學(xué),85,例13：構(gòu)造下列推理的證明 (1) 前提：p r, q s, p q 結(jié)論：r s (2) 前提：p q, p r, s t, s r, t 結(jié)論：q,四、應(yīng)用,2020/7/21,離散數(shù)學(xué),86,(1) 前提：p r, q s, p q 結(jié)論：r s,四、應(yīng)用（續(xù)）,證明： p r, q s, p q, r s,前提引入,前提引入,前提引入,構(gòu)造性二難,2020/7/21,離散數(shù)學(xué),87,(2) 前提：p q, p r, s t, s r, t 結(jié)論：q,四、應(yīng)用（續(xù)）,證明： t, s t, s, s r,前提引入,前提引入,拒取式,析取三段論, r, p r, p, p q, q,前提引入,拒取式,前提引入,前提引入,假言