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

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

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

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

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

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

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

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

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

9、 ”稱作 p 與 q 的等價式，記 作“ p q ”。 p q 為真當且僅當 p 與 q 真值相同。,在命題“2是素數(shù)當且僅當4也是素數(shù)”中，設 p 表示“2是素數(shù)”，q 表示“4是素數(shù)”，則 p q 表示“2是素數(shù)當且僅當4是素數(shù)”,由于p、q的真值分別為1、0，所以p q的真值為0。,2020/7/21,離散數(shù)學,16,真值表,利用以上5種聯(lián)結詞，可將復合命題符號化，進 而正確分析出復合命題的真值?；菊嬷当砣缦拢?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ù)學,17,(1) 李平不是不聰明，而是不用功。 (2) 李文和李武是兄弟。 (3) 只有不下雨，我才騎自行車上班。 (4) 如果下雨，我就不騎自行車上班。 (5) 我去書店看看，除非我很累。,設p:我很累,q:我去書店看看,則符號化為 p q,例3 將下列命題符號化,設p:李文和李武是兄弟，則符號化為p,設p:天下雨,q:我騎自行車上班, p是q的必要條件則符號化為q p,設p:天下雨,q:我騎自行車上班,則符號化為p q,設p:李平聰明，q:李平用功,則符號化為 ( p) q,解題步驟: (1) 分析出各簡單 命題，并符號化； (2) 使用合適的聯(lián) 結詞，把簡單命題 逐個聯(lián)

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

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

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

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

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

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

17、等值演算的概念,等值關系是自反的、對稱的和傳遞的，因而為 等價關系。,等值演算：按一定方法尋找某個復合命題公式的等 值式的過程。,1.3 等值演算,等值公式：設A, B為兩命題公式，若等價式A B 是重言式，稱A與B等值。記作:A B,用真值表可以驗證公式等值。,2020/7/21,離散數(shù)學,30,例5：判斷命題是否等值 ( p q) 與 p q,不 等 值,一、等值演算的概念（續(xù)）,2020/7/21,離散數(shù)學,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),雙重否定律,結合律,交換律,等冪律,2020/7/21,離散數(shù)學,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ù)學,33,二、常用的重要等值公式表（續(xù)）,同一律,歸謬論,蘊涵等值式,排中律,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,矛盾律,等價否定等值式,等價等值式,假言易位,2020/7/21,離散數(shù)學,34,以上24個等值式必須熟記，并注意其中所含的 A, B, C可以是任意的一個命題公式，因而每個公式 是一個模式，可以代表無數(shù)多個同類型的命題公式。,利用24個基本等值式，不用真值表法也可以推 演出很多等值式。,二、常用的重要等值公式表（續(xù)）,2020/7/21,離散數(shù)學,35,設 (A)是含命題公式A的命題公式, (B)是用B置換了 (A)中的A之后得 到的命題公式。若A B, 則 (A) (B) 。,此外，在進行

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

21、,蘊涵等值式,三、應用（續(xù)）,2020/7/21,離散數(shù)學,38,例6：驗證下列等值式 (2) p ( p q) (p q), ( p q) ( p q),同一律,排中律,分配律,三、應用（續(xù)）,2020/7/21,離散數(shù)學,39,例7：判別下列公式的類型 (1) q ( p q ) p ) (2) ( p p ) (q q) r) (3) ( p q ) p,解題思想: 真值表法和等值演算都可以用來判別公式的類型，但等值演算更為簡單快捷。,三、應用（續(xù)）,2020/7/21,離散數(shù)學,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,分配律,矛盾律,同一律,德摩根律,結合律,排中律,零律,重 言 式,三、應用（續(xù)）,2020/7/21,離散數(shù)學,41,例7：判別下列公式的類型 (2) ( p p) (q q) r), 1 (0 r), 1 0, 0,矛盾律,零律,排中律,矛 盾 式,三、應用（續(xù)）,解： (2) 1 (q q) r),2020/7/21,離散數(shù)學,42,例7：判別下列公式的類型 (3) ( p q) p,解： (3) ( p q) p, p,吸收律,蘊涵等值式,可 滿 足 式,三、應用（續(xù)）,2020/7/

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

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

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

26、定理,2020/7/21,離散數(shù)學,50,如：設A (p, q, r) p (q r),二、關于對偶式的兩個定理（續(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ù)學,51,設A與B為兩命題公式，如果A B， 則A* B*。,二

27、、關于對偶式的兩個定理（續(xù)）,由此可知： A*為重言式 A為矛盾式 A*為矛盾式 A為重言式 A*為可滿足式 A為可滿足式 “兩公式等值” “兩公式的對偶式等值”,對偶定理,2020/7/21,離散數(shù)學,52,僅由有限個命題變元或其否定構成的 析取式，如 p q， p q。,三、范式的概念,顯然：簡單析取式是重言式，當且僅當它同時含有 一個命題變項及其否定； 簡單合取式是矛盾式，當且僅當它同時含有 一個命題變項及其否定。,僅由有限個命題變元或其否定構成的 合取式，如 p q。,簡單析取式： 簡單合取式：,2020/7/21,離散數(shù)學,53,僅由有限個簡單合取式構成的析取式。 如A=A1 A2

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

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

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

31、聯(lián)結詞 注3： 一定位于第i個位置，順序不能亂,五、主析取范式與主合取范式,極小項： 極大項：,2020/7/21,離散數(shù)學,60,五、主析取范式與主合取范式（續(xù)）,pqr pqr pqr pqr pqr pqr pqr pqr,成 真 賦 值,極小項的表示（以3個命題變項為例）：,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ù)學,61,五、主析取范式與主合取范式（續(xù)）,極小項的性質（以3個命題變項為例）：,

32、（1）每一個極小項當其真值指派與編碼相同時，其真值為1，在其余7(2n-1)種指派情況下均為0。,（2）任意兩個不同的極小項的合取式永假。如： m0m3 = (pqr) (pqr) 0,（3）全體極小項的析取式永真,m0 m1 m2n-1 1,2020/7/21,離散數(shù)學,62,五、主析取范式與主合取范式（續(xù)）,成 假 賦 值,極大項的表示（以3個命題變項為例）：,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ù)學,63,五、主析取范式與主合取范式（續(xù)）,極大項的性質（以3個命題變項為例）：,（1）每個極大項當其真值指派與編碼相同時，其 真值為0，在其余7(2n-1)種指派情況下均為1。,（2）任意兩個不同的極大項的析取式永真。如： M0 M3 = (pqr) (pqr) 1,（3）全體極大項的合取式永假。,M0 M1 M2n-1 0,2020/7/21,離散數(shù)學,64,五、主析取范式與主合取范式（續(xù)）,任何命題公式的主析取范式和主合取范式 一定存在，并且唯一。,定理,主析取范式： 主合取范式：,命題公式A的析取范式中的簡單合取式 全是

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

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

36、q p),2020/7/21,離散數(shù)學,68,六、應用（續(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ù)學,69,六、應用（續(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ù)學,70,五、主析取范式與主合取范式（續(xù)）,在真值表中，一個公式的真值為1的指派（成真賦值）所對應的極小項的析取式，即為公式的主析取范式。,在真值表中，一個公式的真值為0的指派（成假賦值）所對應的極大項的合取式，即為公式的主合取范式。,定理,定理,真值表法求公式的主析取范式和主合取范式。,2020/7/21,離散數(shù)學,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ù)學,72,五、主析取范式與主合取范式（續(xù)）,解：由真值表可知，公式A的成真賦值為000、001、 101、110、111，其對應的極小項分別為m0、m1、 m5、 m6、m7， 因此公式A的主析取范式為： A m0 m1 m5 m6 m7,由真值表可知，公式A的成假賦值為010、011、100， 其對應的極大項分別為M2 、 M3、 M4， 因此公式A的主合取范式為： A M2 M3 M4,2020/7/21,離散數(shù)學,73,A為重言式，當且僅當A的主析取范式含所有極小項 A為矛盾式，當且僅

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

40、) q, ( p q) q, p q q, 0,矛 盾 式,2020/7/21,離散數(shù)學,75,例11：判斷下列命題公式的類型 (1) ( p q) q (2) ( p q) p) q,六、應用（續(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ù)學,76,六、應用（續(xù)）,設命題公式含n個命題變項，其主析取范式中含k個極小項 ，不含極小項 ， 則主合取范式中含極大項 ,如：A中含3個命題變項， A m0 m1

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

42、小王就不去游泳。天氣涼快, 所以小王沒去游泳。 (2) 如果我上街，我一定去新華書店。我沒上街， 所以我沒去新華書店。,二、應用,解題思想: (1) 將命題符號化； (2) 寫出前提、結論和推理的形式結構； (3) 用真值表法、等值演算或主析取范式法進行判斷。,2020/7/21,離散數(shù)學,79,(1) 如果天氣涼快，小王就不去游泳。天氣涼快, 所以小王沒去游泳。,二、應用（續(xù)）,解：設p：天氣涼快，q：小王去游泳,前提： p q , p 結論： q,推理的形式結構為 ( p q) p) q (*),2020/7/21,離散數(shù)學,80,下面判斷(*)式是否為重言式,二、應用（續(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ù)學,81,(2) 如果我上街，我一定去新華書店。我沒上街， 所以我沒去新華書店。,二、應用（續(xù)）,解：設p：我上街，q：我去新華書店,前提： p q , p 結論： q,推理的形式結構為 (p q) p) q (*),2020/7/21,離散數(shù)學,82,下面判斷(*)式是否為重言式,二、應用（續(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ù)學,83,三、構造證明法,推理規(guī)則：在推理過程中，構造證明必須在給定的規(guī)則下進行，常用的推理如下：,(1) 前提引入規(guī)則: 證明的任何步驟上，都可引入前提；,證明：描述推理過程的命題公式序列。,(2) 結論引入規(guī)則：證明的任何步驟上，所證明的結論都 可作為后續(xù)證明的前提；,(3) 置換規(guī)則：證明的任何步驟上，命題公式中的任何子 命題公式都可以用與之等值的命題公式置換

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