《離散數(shù)學(xué) 課件 命題邏輯.ppt》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué) 課件 命題邏輯.ppt（26頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

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

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

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

7、王曉紅生于1976年,(vw)(vw),又可形式化為 vw,13,聯(lián)結(jié)詞與復(fù)合命題(續(xù)),定義2.4 設(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為假. 例如 如果明天天氣好, 我們就出去郊游 設(shè)p:明天天氣好, q:我們出去郊游, 形式化為 pq,14,蘊(yùn)涵聯(lián)結(jié)詞(續(xù)),pq 的邏輯關(guān)系: q為p的必要條件, p為q的充分條件 “如果p,則q” 的多種表述方式： 若p,就q 只要p,就q 只有q 才p 除非q, 才p 除非q, 否則非p 當(dāng)p為假時(shí)

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

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

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

11、題變項(xiàng)或命題常項(xiàng)是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 設(shè)p1, p2, , pn是出現(xiàn)在公式A中全部的命題變項(xiàng), 給 p1, p2, , pn指定一組真值, 稱為對A的一個(gè)賦值或解釋. 使公式

12、為真的賦值稱作成真賦值, 使公式為假的賦值稱作 成假賦值 說明: (1) 賦值記作=12n, i=0或1, 諸i之間不加標(biāo) 點(diǎn)符號 (2) 通常賦值與命題變項(xiàng)之間按下標(biāo)或字母順序?qū)?yīng), 即 當(dāng)A的全部命題變項(xiàng)為p1, p2, , pn時(shí), 給A賦值12n 是指p1=1,p2=2,pn=n; 當(dāng)A的全部命題變項(xiàng)為p,q,r, 時(shí), 給A賦值123是指p=1, q=2, r=3, ,22,實(shí)例,例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個(gè)變項(xiàng)的公式有2n個(gè)賦值,24,實(shí)例(續(xù)),(2) (pq) q,25,實(shí)例(續(xù)),(3) (pq) r,26,命題公式的分類,重言式(永真式): 無成假賦值的命題公式 矛盾式(永假式): 無成真賦值的命題公式 可滿足式: 非矛盾式的命題公式 注意: 重言式是可滿足式，但反之不真. 例如 上例中 (1) (qp)qp為重言式 (2) (pq)q為矛盾式 (3) (pq)r為非重言式的可滿足式,