離散數(shù)學(xué)-耿素云PPT(第5版)1.1-2.ppt

1、1,離散數(shù)學(xué),2,主要內(nèi)容,數(shù)理邏輯 集合論 圖論 組合分析初步 代數(shù)系統(tǒng)簡介 形式語言和自動機(jī)初步,3,教材與教學(xué)參考書,教材： 耿素云、屈婉玲、張立昂，離散數(shù)學(xué)（第五版），清華大學(xué)出版社, 2013. 教學(xué)參考書： 屈婉玲、耿素云、張立昂，離散數(shù)學(xué)題解（第五版），清華大學(xué)出版社，2013.,4,數(shù)理邏輯部分,第1章 命題邏輯 第2章 一階邏輯,5,第1章 命題邏輯,1.1 命題符號化及聯(lián)結(jié)詞 1.2 命題公式及分類 1.3 等值演算 1.4 范式 1.5 聯(lián)結(jié)詞全功能集 1.6 組合電路 1.7 推理理論,6,1.1 命題符號化及聯(lián)結(jié)詞,命題與真值 原子命題 復(fù)合命題 命題常項(xiàng) 命題變項(xiàng)

2、聯(lián)結(jié)詞,7,命題與真值,命題: 判斷結(jié)果惟一的陳述句 命題的真值: 判斷的結(jié)果 真值的取值: 真與假 真命題: 真值為真的命題 假命題: 真值為假的命題 注意: 感嘆句、祈使句、疑問句都不是命題 陳述句中的悖論以及判斷結(jié)果不惟一確定的也不是 命題,8,例 下列句子中那些是命題？ (1) 是無理數(shù). (2) 2 + 5 8. (3) x + 5 3. (4) 你有鉛筆嗎？ (5) 這只兔子跑得真快呀！ (6) 請不要講話！ (7) 我正在說謊話.,真命題,假命題,真值不確定,疑問句,感嘆句,祈使句,悖論,(3)(7)都不是命題,9,命題的分類,簡單命題(原子命題)： 簡單陳述句構(gòu)成的命題 復(fù)合命

3、題： 由簡單命題與聯(lián)結(jié)詞按一定規(guī)則復(fù)合 而成的命題,10,簡單命題符號化,用小寫英文字母 p, q, r, ,pi,qi,ri (i1）表示 簡單命題 用“1”表示真，用“0”表示假 例如，令 p： 是有理數(shù)，則 p 的真值為 0 q：2 + 5 = 7，則 q 的真值為 1,11,聯(lián)結(jié)詞與復(fù)合命題,1.否定式與否定聯(lián)結(jié)詞“” 定義 設(shè)p為命題，復(fù)合命題 “非p”(或 “p的否定”)稱 為p的否定式，記作p. 符號稱作否定聯(lián)結(jié)詞，并規(guī) 定p 為真當(dāng)且僅當(dāng)p為假. 2.合取式與合取聯(lián)結(jié)詞“” 定義 設(shè)p,q為二命題,復(fù)合命題“p并且q”(或“p與q”)稱 為p與q的合取式，記作pq. 稱作合取聯(lián)

4、結(jié)詞，并規(guī) 定 pq為真當(dāng)且僅當(dāng)p與q同時(shí)為真 注意：描述合取式的靈活性與多樣性 分清簡單命題與復(fù)合命題,12,例 將下列命題符號化. (1) 王曉既用功又聰明. (2) 王曉不僅聰明，而且用功. (3) 王曉雖然聰明，但不用功. (4) 張輝與王麗都是三好生. (5) 張輝與王麗是同學(xué). 解 令 p：王曉用功，q：王曉聰明，則 (1) pq (2) pq (3) pq.,13,例 (續(xù)),令 r : 張輝是三好學(xué)生，s :王麗是三好學(xué)生 (4) rs. (5) 令 t : 張輝與王麗是同學(xué)，t 是簡單命題 .,說明: (1)(4)說明描述合取式的靈活性與多樣性. (5) 中“與”聯(lián)結(jié)的是兩個(gè)

5、名詞，整個(gè)句子是一個(gè)簡單命題.,14,聯(lián)結(jié)詞與復(fù)合命題(續(xù)),定義 設(shè) p,q為二命題，復(fù)合命題“p或q”稱作p與q 的析取式，記作pq. 稱作析取聯(lián)結(jié)詞，并規(guī)定pq為假當(dāng)且僅當(dāng)p與q同時(shí)為假.,例 將下列命題符號化 (1) 2或4是素?cái)?shù). (2) 2或3是素?cái)?shù). (3) 4或6是素?cái)?shù). (4) 小元元只能拿一個(gè)蘋果或一個(gè)梨. (5) 王曉紅生于1975年或1976年.,3.析取式與析取聯(lián)結(jié)詞“”,15,解 令 p:2是素?cái)?shù), q:3是素?cái)?shù), r:4是素?cái)?shù), s:6是素?cái)?shù), 則 (1), (2), (3) 均為相容或. 分別符號化為: pr , pq, rs, 它們的真值分別為 1, 1, 0

6、. (4), (5) 為排斥或. 令 t :小元元拿一個(gè)蘋果，u:小元元拿一個(gè)梨， 則 (4) 符號化為 (tu) (tu). 令v :王曉紅生于1975年,w:王曉紅生于1976年,則 (5) 既可符號化為 (vw)(vw), 又可符號化為 vw .,16,聯(lián)結(jié)詞與復(fù)合命題(續(xù)),定義 設(shè) p,q為二命題，復(fù)合命題 “如果p,則q” 稱作p與q的蘊(yùn)涵式，記作pq，并稱p是蘊(yùn)涵式的前件，q為蘊(yùn)涵式的后件. 稱作蘊(yùn)涵聯(lián)結(jié)詞，并規(guī)定，pq為假當(dāng)且僅當(dāng) p 為真 q 為假.,4.蘊(yùn)涵式與蘊(yùn)涵聯(lián)結(jié)詞“”,17,pq 的邏輯關(guān)系：q 為 p 的必要條件 “如果 p，則 q ” 的不同表述法很多： 若 p

7、，就 q 只要 p，就 q p 僅當(dāng) q 只有 q 才 p 除非 q, 才 p 或 除非 q, 否則非 p. 當(dāng) p 為假時(shí)，pq 為真 常出現(xiàn)的錯誤：不分充分與必要條件,聯(lián)結(jié)詞與復(fù)合命題(續(xù)),18,例 設(shè) p:天冷，q:小王穿羽絨服， 將下列命題符號化 (1) 只要天冷，小王就穿羽絨服. (2) 因?yàn)樘炖洌孕⊥醮┯鸾q服. (3) 若小王不穿羽絨服，則天不冷. (4) 只有天冷，小王才穿羽絨服. (5) 除非天冷，小王才穿羽絨服. (6) 除非小王穿羽絨服，否則天不冷. (7) 如果天不冷，則小王不穿羽絨服. (8) 小王穿羽絨服僅當(dāng)天冷的時(shí)候.,注意： pq 與 qp 等值（真值相同）

8、,pq,pq,pq,pq,qp,qp,qp,qp,19,聯(lián)結(jié)詞與復(fù)合命題(續(xù)),定義 設(shè)p，q為二命題，復(fù)合命題 “p當(dāng)且僅當(dāng)q”稱作p與q的等價(jià)式，記作pq. 稱作等價(jià)聯(lián)結(jié)詞.并規(guī)定pq為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假. 說明: (1) pq 的邏輯關(guān)系:p與q互為充分必要條件 (2) pq為真當(dāng)且僅當(dāng)p與q同真或同假,5. 等價(jià)式與等價(jià)聯(lián)結(jié)詞“”,20,例 求下列復(fù)合命題的真值 (1) 2 + 2 4 當(dāng)且僅當(dāng) 3 + 3 6. (2) 2 + 2 4 當(dāng)且僅當(dāng) 3 是偶數(shù). (3) 2 + 2 4 當(dāng)且僅當(dāng) 太陽從東方升起. (4) 2 + 2 4 當(dāng)且僅當(dāng) 美國位于非洲. (5)

9、函數(shù) f (x) 在x0 可導(dǎo)的充要條件是它在 x0 連續(xù).,1,1,0,0,0,例,21,聯(lián)結(jié)詞與復(fù)合命題(續(xù)),以上給出了5個(gè)聯(lián)結(jié)詞：, , , , ，組成 一個(gè)聯(lián)結(jié)詞集合, , , , ， 聯(lián)結(jié)詞的優(yōu)先順序?yàn)椋? , , , ; 如果出 現(xiàn)的聯(lián)結(jié)詞同級，又無括號時(shí)，則按從左到右 的順序運(yùn)算; 若遇有括號時(shí)，應(yīng)該先進(jìn)行括號 中的運(yùn)算. 注意: 本書中使用的 括號全為園括號.,22,1.2 命題公式及分類,命題變項(xiàng)與合式公式 公式的賦值 真值表 命題的分類 重言式 矛盾式 可滿足式 真值函數(shù),23,命題變項(xiàng)與合式公式,命題常項(xiàng)：簡單命題 命題變項(xiàng)：真值不確定的陳述句 定義 合式公式 (命題公

10、式, 公式) 遞歸定義如下： (1) 單個(gè)命題常項(xiàng)或變項(xiàng) p,q,r,pi ,qi ,ri ,0,1 是合式公式 (2) 若A是合式公式，則 (A)也是合式公式 (3) 若A, B是合式公式，則(AB), (AB), (AB), (AB)也是合式公式 (4) 只有有限次地應(yīng)用(1)(3)形成的符號串才是合式公式 說明: 外層括號可以省去,24,合式公式的層次,定義 (1) 若公式A是單個(gè)的命題變項(xiàng), 則稱A為0層公式. (2) 稱A是n+1(n0)層公式是指下面情況之一： (a) A=B, B是n層公式； (b) A=BC, 其中B,C分別為i層和j層公式，且 n=max(i, j)； (c)

11、 A=BC, 其中B,C的層次及n同(b)； (d) A=BC, 其中B,C的層次及n同(b)； (e) A=BC, 其中B,C的層次及n同(b).,25,合式公式的層次 (續(xù)),例如 公式 p 0層 p 1層 pq 2層 (pq)r 3層 (pq) r)(rs) 4層,26,公式的賦值,定義 給公式A中的命題變項(xiàng) p1, p2, , pn指定 一組真值稱為對A的一個(gè)賦值或解釋 成真賦值: 使公式為真的賦值 成假賦值: 使公式為假的賦值 說明： 賦值=12n之間不加標(biāo)點(diǎn)符號，i=0或1. A中僅出現(xiàn) p1, p2, , pn，給A賦值12n是 指 p1=1, p2=2, , pn=n A中僅出

12、現(xiàn) p, q, r, , 給A賦值123是指 p=1,q=2 , r=3 含n個(gè)變項(xiàng)的公式有2n個(gè)賦值.,27,真值表,真值表: 公式A在所有賦值下的取值情況列成的表 例 給出公式的真值表 A= (qp) qp 的真值表,28,例 B = (pq) q 的真值表,實(shí)例,29,例 C= (pq) r 的真值表,30,公式的類型,定義 設(shè)A為一個(gè)命題公式 (1) 若A無成假賦值，則稱A為重言式(也稱永真式) (2) 若A無成真賦值，則稱A為矛盾式(也稱永假式) (3) 若A不是矛盾式，則稱A為可滿足式 注意：重言式是可滿足式，但反之不真. 上例中A為重言式，B為矛盾式，C為可滿足式 A= (qp)qp，B =(pq)q，C= (pq)r,31,真值函數(shù),問題：含n個(gè)命題變項(xiàng)的所有公式共產(chǎn)生多少個(gè)互 不相同的真值表？ 定義 稱定義域?yàn)?00, 001, , 111，值域 為0,1的函數(shù)是n元真值函數(shù)，定義域中的元素是 長為n的0,1串. 常用F:0,1n0,1 表示F是n元真值 函數(shù). 共有 個(gè)n元真值函數(shù). 例如 F:0,120,1，且F(00)=F(01)=F(1