《離散數(shù)學 課件 命題邏輯.ppt》由會員分享，可在線閱讀，更多相關《離散數(shù)學 課件 命題邏輯.ppt（26頁珍藏版）》請在裝配圖網上搜索。

1、1,第2章 命題邏輯,2,實例,某單位要從A,B,C三人中選派若干人出國考察, 需滿足下述條件: (1) 若A去, 則C必須去; (2) 若B去, 則C不能去; (3) A和B必須去一人且只能去一人. 問有幾種可能的選派方案?,3,請根據(jù)下面事實，找出兇手： 1. 清潔工或者秘書謀害了經理。 2. 如果清潔工謀害了經理，則謀害不會發(fā)生在午夜前。 3. 如果秘書的證詞是正確的，則謀害發(fā)生在午夜前。 4. 如果秘書的證詞不正確，則午夜時屋里燈光未滅。 5. 如果清潔工富裕，則他不會謀害經理。 6. 經理有錢且清潔工不富裕。 7. 午夜時屋里燈滅了。,實際推理題：,4,第2章 命題邏輯,2.1 命題

2、邏輯基本概念 2.2 命題邏輯等值演算 2.3 范式 2.4 命題邏輯推理理論,5,2.1 命題邏輯基本概念,2.1.1 命題與聯(lián)結詞 命題與真值(簡單命題, 復合命題) 聯(lián)結詞(, , , , ) 2.2.2 命題公式及其分類 命題公式及其賦值 真值表 命題公式的分類,6,命題及其真值,命題: 判斷結果惟一的陳述句 命題的真值: 判斷的結果,真或假 真命題: 真值為真的命題 假命題: 真值為假的命題 注意: 感嘆句、祈使句、疑問句都不是命題 陳述句中的悖論以及判斷結果不惟一確定的也不是 命題,7,例1 下列句子中那些是命題？ (1) 北京是中華人民共和國的首都. (2) 2 + 5 8. (

3、3) x + 5 3. (4) 你會開車嗎？ (5) 2050年元旦北京是晴天. (6) 這只兔子跑得真快呀！ (7) 請關上門！ (8) 我正在說謊話.,真命題,假命題,真值不確定,疑問句,感嘆句,祈使句,悖論,(1),(2),(5)是命題, (3),(4),(6)(8)都不是命題,真值確定, 但未知,實例,8,簡單命題與復合命題,簡單命題(原子命題):簡單陳述句構成的命題 簡單命題的符號化:用p, q, r, ,pi,qi,ri (i1)表示 用“1”表示真，用“0”表示假 復合命題:由簡單命題通過聯(lián)結詞聯(lián)結而成的陳述句 例如 如果明天天氣好, 我們就出去郊游 設p:明天天氣好, q:我們

4、出去郊游, 如果p, 則q 又如 張三一面喝茶一面看報 設p:張三喝茶, q:張三看報, p并且q,9,聯(lián)結詞與復合命題,定義2.1 設p為命題, 復合命題 “非p”(或 “p的否定”)稱為 p的否定式, 記作p, 符號稱作否定聯(lián)結詞, 并規(guī)定p 為真當且僅當 p為假 例如 p:2是合數(shù), p: 2不是合數(shù), p為假, p為真 定義2.2 設p,q為二命題, 復合命題“p并且q”(或“p與q”)稱 為p與q的合取式, 記作pq, 稱作合取聯(lián)結詞, 并規(guī)定 pq為真當且僅當 p與q同時為真 例如 p:2是偶數(shù), q: 2是素數(shù), pq: 2是偶素數(shù), p為真, q為真, pq為真,10,實例,例

5、2 將下列命題符號化. (1) 王曉既用功又聰明. (2) 王曉不僅聰明，而且用功. (3) 王曉雖然聰明，但不用功. (4) 張輝與王麗都是三好生. (5) 張輝與王麗是同學. 解,記 p:王曉用功, q:王曉聰明,(1) pq,(2) pq,(3) pq,(4) 記 r:張輝是三好生, s:王麗是三好生, rs,(5) 簡單命題, 記 t:張輝與王麗是同學,11,聯(lián)結詞與復合命題(續(xù)),定義2.3 設 p,q為命題, 復合命題“p或q”稱作p與q的析取式, 記作pq, 稱作析取聯(lián)結詞, 并規(guī)定pq為假當且僅當 p與q同時為假. 例如 張三和李四至少有一人會英語 設 p:張三會英語, q:李

6、四會英語, 符號化為pq 相容或與排斥或 例如 這件事由張三和李四中的一人去做 設 p:張三做這件事, q:李四做這件事 應符號化為 (p q) (p q),12,實例,例3 將下列命題符號化 (1) 2或4是素數(shù). (2) 2或3是素數(shù). (3) 4或6是素數(shù). (4) 元元只能拿一個蘋果或一個梨. (5) 王曉紅生于1975年或1976年. 解,記 p:2是素數(shù), q:3是素數(shù), r:4是素數(shù), s:6是素數(shù),(1) pr,(2) pq,(3) rs,(4) 記t:元元拿一個蘋果,u:元元拿一個梨,真值:1,真值: 1,真值: 0,(tu)(tu),(5) 記v:王曉紅生于1975年,w:

7、王曉紅生于1976年,(vw)(vw),又可形式化為 vw,13,聯(lián)結詞與復合命題(續(xù)),定義2.4 設 p,q為二命題, 復合命題 “如果p,則q” 稱作p與q 的蘊涵式, 記作pq, 并稱p是蘊涵式的前件, q為蘊涵式的 后件. 稱作蘊涵聯(lián)結詞, 并規(guī)定, pq為假當且僅當 p為 真且q為假. 例如 如果明天天氣好, 我們就出去郊游 設p:明天天氣好, q:我們出去郊游, 形式化為 pq,14,蘊涵聯(lián)結詞(續(xù)),pq 的邏輯關系: q為p的必要條件, p為q的充分條件 “如果p,則q” 的多種表述方式： 若p,就q 只要p,就q 只有q 才p 除非q, 才p 除非q, 否則非p 當p為假時

8、，pq為真(不管q為真, 還是為假),15,實例,例4 設p:天冷, q:小王穿羽絨服， 將下列命題符號化 (1) 只要天冷，小王就穿羽絨服. (2) 因為天冷，所以小王穿羽絨服. (3) 若小王不穿羽絨服，則天不冷. (4) 只有天冷，小王才穿羽絨服. (5) 除非天冷，小王才穿羽絨服. (6) 除非小王穿羽絨服，否則天不冷. (7) 如果天不冷，則小王不穿羽絨服.,注意： pq 與 qp 等值（真值相同）,pq,pq,qp 或 pq,pq,qp,qp,pq 或 qp,16,聯(lián)結詞與復合命題(續(xù)),定義2.5 設p, q為命題, 復合命題 “p當且僅當q”稱作p與q的 等價式, 記作pq,

9、稱作等價聯(lián)結詞. 并規(guī)定pq為真當 且僅當 p與q同時為真或同時為假. pq 的邏輯關系: p與q互為充分必要條件 例如 這件事張三能做好, 且只有張三能做好 設p:張三做這件事, q:這件事做好了 形式化為: pq,17,實例,例5 求下列復合命題的真值 (1) 2+24 當且僅當 3+36. (2) 2+24 當且僅當 3是偶數(shù). (3) 2+24 當且僅當 太陽從東方升起. (4) 2+25 當且僅當 美國位于非洲. (5) f (x)在x0處可導的充要條件是它在 x0處連續(xù).,1,0,1,1,0,18,聯(lián)結詞與復合命題(續(xù)),聯(lián)結詞優(yōu)先級:( ), , , , 同級按從左到右的順序進行

10、,19,合式公式,命題常項: 簡單命題 命題變項: 真值可以變化的陳述句 定義2.6 合式公式 (命題公式, 公式) 遞歸定義如下： (1) 單個命題常項或變項是合式公式,并稱作原子合式公式 (2) 若A是合式公式, 則 (A)也是合式公式 (3) 若A, B是合式公式, 則(AB), (AB), (AB), (AB)也 是合式公式 (4) 只有有限次地應用(1)(3)形成的符號串才是合式公式 說明:(1) 元語言符號與對象語言符號 (2) 在不影響運算順序時, 括號可以省去 例如 0, p, pq, (pq)(pr), pq r, (pq)r,20,合式公式的層次,定義2.7 (1) 單個命

11、題變項或命題常項是0層公式 (2) 稱A是n+1(n0)層公式是指下面情況之一： (a) A=B, B是n層公式 (b) A=BC, 其中B,C分別為i層和j層公式, 且 n=max(i, j) (c) A=BC, 其中B,C的層次及n同(b) (d) A=BC, 其中B,C的層次及n同(b) (e) A=BC, 其中B,C的層次及n同(b) 例如 p 0層 p 1層 pq 2層 (pq)r 3層 (pq) r)(rs) 4層,21,公式的賦值,定義2.8 設p1, p2, , pn是出現(xiàn)在公式A中全部的命題變項, 給 p1, p2, , pn指定一組真值, 稱為對A的一個賦值或解釋. 使公式

12、為真的賦值稱作成真賦值, 使公式為假的賦值稱作 成假賦值 說明: (1) 賦值記作=12n, i=0或1, 諸i之間不加標 點符號 (2) 通常賦值與命題變項之間按下標或字母順序對應, 即 當A的全部命題變項為p1, p2, , pn時, 給A賦值12n 是指p1=1,p2=2,pn=n; 當A的全部命題變項為p,q,r, 時, 給A賦值123是指p=1, q=2, r=3, ,22,實例,例6 公式A= p1 p2 01是成真賦值, 00是成假賦值 公式B=( p1 p2 p3 )(p1 p2) 000是成真賦值, 001是成假賦值 公式C= (pq)r 000是成假賦值, 001是成真賦值,23,真值表,例7 給出公式的真值表 (1) (qp) qp,真值表: 命題公式在所有可能的賦值下的取值的列表 含n個變項的公式有2n個賦值,24,實例(續(xù)),(2) (pq) q,25,實例(續(xù)),(3) (pq) r,26,命題公式的分類,重言式(永真式): 無成假賦值的命題公式 矛盾式(永假式): 無成真賦值的命題公式 可滿足式: 非矛盾式的命題公式 注意: 重言式是可滿足式，但反之不真. 例如 上例中 (1) (qp)qp為重言式 (2) (pq)q為矛盾式 (3) (pq)r為非重言式的可滿足式,