離散數(shù)學之命題符號化

1、1,離散數(shù)學,2,主要內(nèi)容,數(shù)理邏輯 集合論 圖論 組合分析初步 代數(shù)系統(tǒng)簡介 形式語言和自動機初步,3,教材與教學參考書,教材： 耿素云、屈婉玲、張立昂，離散數(shù)學（第五版），清華大學出版社, 2013. 教學參考書： 屈婉玲、耿素云、張立昂，離散數(shù)學題解（第五版），清華大學出版社，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é)詞,命題與真值 原子命題 復合命題 命題常項 命題變項

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)成的命題 復合命

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

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

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

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

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

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

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

10、式, 公式) 遞歸定義如下： (1) 單個命題常項或變項 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是單個的命題變項, 則稱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中的命題變項 p1, p2, , pn指定 一組真值稱為對A的一個賦值或解釋 成真賦值: 使公式為真的賦值 成假賦值: 使公式為假的賦值 說明： 賦值=12n之間不加標點符號，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個變項的公式有2n個賦值.,27,真值表,真值表: 公式A在所有賦值下的取值情況列成的表 例 給出公式的真值表 A= (qp) qp 的真值表,28,例 B = (pq) q 的真值表,實例,29,例 C= (pq) r 的真值表,30,公式的類型,定義 設(shè)A為一個命題公式 (1) 若A無成假賦值，則稱A為重言式(也稱永真式) (2) 若A無成真賦值，則稱A為矛盾式(也稱永假式) (3) 若A不是矛盾式，則稱A為可滿足式 注意：重言式是可滿足式，但反之不真. 上例中A為重言式，B為矛盾式，C為可滿足式 A= (qp)qp，B =(pq)q，C= (pq)r,31,真值函數(shù),問題：含n個命題變項的所有公式共產(chǎn)生多少個互 不相同的真值表？ 定義 稱定義域為000, 001, , 111，值域 為0,1的函數(shù)是n元真值函數(shù)，定義域中的元素是 長為n的0,1串. 常用F:0,1n0,1 表示F是n元真值 函數(shù). 共有 個n元真值函數(shù). 例如 F:0,120,1，且F(00)=F(01)=F(1