離散數(shù)學(xué)課件命題邏輯

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

2、午夜如果秘書的證詞是正確的，則謀害發(fā)生在午夜前。前。4. 如果秘書的證詞不正確，則午夜時(shí)屋里燈光未如果秘書的證詞不正確，則午夜時(shí)屋里燈光未滅。滅。5. 如果清潔工富裕，則他不會(huì)謀害經(jīng)理。如果清潔工富裕，則他不會(huì)謀害經(jīng)理。6. 經(jīng)理有錢且清潔工不富裕。經(jīng)理有錢且清潔工不富裕。7. 午夜時(shí)屋里燈滅了。午夜時(shí)屋里燈滅了。實(shí)際推理題實(shí)際推理題：4第第2章章 命題邏輯命題邏輯 2.1 命題邏輯基本概念命題邏輯基本概念 2.2 命題邏輯等值演算命題邏輯等值演算 2.3 范式范式 2.4 命題邏輯推理理論命題邏輯推理理論 52.1 命題邏輯基本概念命題邏輯基本概念 2.1.1 命題與聯(lián)結(jié)詞命題與聯(lián)結(jié)詞 命題

3、與真值命題與真值(簡(jiǎn)單命題簡(jiǎn)單命題, 復(fù)合命題復(fù)合命題) 聯(lián)結(jié)詞聯(lián)結(jié)詞(, , , , ) 2.2.2 命題公式及其分類命題公式及其分類命題公式及其賦值命題公式及其賦值真值表真值表命題公式的分類命題公式的分類 6命題及其真值命題及其真值命題命題: 判斷結(jié)果惟一的陳述句判斷結(jié)果惟一的陳述句命題的真值命題的真值: 判斷的結(jié)果判斷的結(jié)果, ,真或假真或假真命題真命題: 真值為真的命題真值為真的命題假命題假命題: 真值為假的命題真值為假的命題注意注意: 感嘆句、祈使句、疑問句都不是命題感嘆句、祈使句、疑問句都不是命題陳述句中的悖論以及判斷結(jié)果不惟一確定的也不是陳述句中的悖論以及判斷結(jié)果不惟一確定的也不

4、是命題命題 7例例1 1 下列句子中那些是命題？下列句子中那些是命題？ (1) 北京是中華人民共和國(guó)的首都北京是中華人民共和國(guó)的首都.(2) 2 + 5 8.(3) x + 5 3.(4) 你會(huì)開車嗎？你會(huì)開車嗎？(5) 2050年元旦北京是晴天年元旦北京是晴天.(6) 這只兔子跑得真快呀！這只兔子跑得真快呀！(7) 請(qǐng)關(guān)上門！請(qǐng)關(guān)上門！(8) 我正在說謊話我正在說謊話.真命題真命題假命題假命題真值不確定真值不確定疑問句疑問句感嘆句感嘆句祈使句祈使句悖論悖論(1),(2),(5)是命題是命題, (3),(4),(6)(8)都不是命題都不是命題真值確定真值確定, 但未知但未知實(shí)例實(shí)例8簡(jiǎn)單命題與

5、復(fù)合命題簡(jiǎn)單命題與復(fù)合命題簡(jiǎn)單命題簡(jiǎn)單命題( (原子命題原子命題) ): :簡(jiǎn)單陳述句構(gòu)成的命題簡(jiǎn)單陳述句構(gòu)成的命題簡(jiǎn)單命題的符號(hào)化簡(jiǎn)單命題的符號(hào)化: :用用p, q, r, , ,pi, ,qi, ,ri (i1)表示表示 用用“1”表示真，用表示真，用“0”表示假表示假復(fù)合命題復(fù)合命題: :由簡(jiǎn)單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的陳述句由簡(jiǎn)單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的陳述句 例如例如 如果明天天氣好如果明天天氣好, 我們就出去郊游我們就出去郊游設(shè)設(shè)p:明天天氣好明天天氣好, q:我們出去郊游我們出去郊游, 如果如果p, 則則q 又如又如 張三一面喝茶一面看報(bào)張三一面喝茶一面看報(bào)設(shè)設(shè)p:張三喝茶張三喝茶

6、, q:張三看報(bào)張三看報(bào), p并且并且q9聯(lián)結(jié)詞與復(fù)合命題聯(lián)結(jié)詞與復(fù)合命題定義定義2.1 設(shè)設(shè)p為命題為命題, 復(fù)合命題復(fù)合命題 “非非p”(或或 “p的否定的否定”)稱稱為為p的的否定式否定式, 記作記作 p, 符號(hào)符號(hào) 稱作稱作否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞, 并規(guī)定并規(guī)定 p為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng) p為假為假例如例如 p:2是合數(shù)是合數(shù), p: 2不是合數(shù)不是合數(shù), p為假為假, p為真為真定義定義2.2 設(shè)設(shè)p,q為二命題為二命題, 復(fù)合命題復(fù)合命題“p并且并且q”(或或“p與與q”)稱稱為為p與與q的的合取式合取式, 記作記作pq, 稱作稱作合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞, 并規(guī)定并規(guī)定 pq為真當(dāng)且

7、僅當(dāng)為真當(dāng)且僅當(dāng) p與與q同時(shí)為真同時(shí)為真例如例如 p:2是偶數(shù)是偶數(shù), q: 2是素?cái)?shù)是素?cái)?shù), pq: 2是偶素?cái)?shù)是偶素?cái)?shù), p為真為真, q為真為真, pq為真為真10實(shí)例實(shí)例例例2 將下列命題符號(hào)化將下列命題符號(hào)化. (1) 王曉既用功又聰明王曉既用功又聰明.(2) 王曉不僅聰明，而且用功王曉不僅聰明，而且用功.(3) 王曉雖然聰明，但不用功王曉雖然聰明，但不用功.(4) 張輝與王麗都是三好生張輝與王麗都是三好生.(5) 張輝與王麗是同學(xué)張輝與王麗是同學(xué).解解 記記 p:王曉用功王曉用功, q:王曉聰明王曉聰明(1) pq (2) pq(3) p q(4) 記記 r:張輝是三好生張輝是三

8、好生, s:王麗是三好生王麗是三好生, rs(5) 簡(jiǎn)單命題簡(jiǎn)單命題, 記記 t:張輝與王麗是同學(xué)張輝與王麗是同學(xué)11聯(lián)結(jié)詞與復(fù)合命題聯(lián)結(jié)詞與復(fù)合命題(續(xù)續(xù))定義定義2.3 設(shè)設(shè) p,q為命題為命題, 復(fù)合命題復(fù)合命題“p或或q”稱作稱作p與與q的的析取析取式式,記作記作pq, 稱作稱作析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞, 并規(guī)定并規(guī)定pq為假當(dāng)且僅當(dāng)為假當(dāng)且僅當(dāng)p與與q同時(shí)為假同時(shí)為假.例如例如 張三和李四至少有一人會(huì)英語張三和李四至少有一人會(huì)英語設(shè)設(shè) p:張三會(huì)英語張三會(huì)英語, q:李四會(huì)英語李四會(huì)英語, 符號(hào)化為符號(hào)化為pq相容或與排斥或相容或與排斥或例如例如 這件事由張三和李四中的一人去做這件事由張

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

10、一個(gè)梨元元拿一個(gè)梨真值真值:1真值真值: 1真值真值: 0(t u)( tu)(5) 記記v:王曉紅生于王曉紅生于1975年年, ,w:王曉紅生于王曉紅生于1976年年(v w)( vw)又可形式化為又可形式化為 vw13聯(lián)結(jié)詞與復(fù)合命題聯(lián)結(jié)詞與復(fù)合命題(續(xù)續(xù))定義定義2.4 設(shè)設(shè) p,q為二命題為二命題, 復(fù)合命題復(fù)合命題 “如果如果p,則則q” 稱作稱作p與與q的的蘊(yùn)涵式蘊(yùn)涵式, 記作記作pq, 并稱并稱p是蘊(yùn)涵式的是蘊(yùn)涵式的前件前件, q為蘊(yùn)涵式的為蘊(yùn)涵式的后件后件. 稱作稱作蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵聯(lián)結(jié)詞, 并規(guī)定并規(guī)定, pq為假當(dāng)且僅當(dāng)為假當(dāng)且僅當(dāng) p為為真且真且q為假為假.例如例如 如果明

11、天天氣好如果明天天氣好, 我們就出去郊游我們就出去郊游 設(shè)設(shè)p:明天天氣好明天天氣好, q:我們出去郊游我們出去郊游, 形式化為形式化為 pq14蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵聯(lián)結(jié)詞(續(xù)續(xù))pq 的邏輯關(guān)系的邏輯關(guān)系: q為為p的必要條件的必要條件, p為為q的充分條件的充分條件“如果如果p,則則q” 的多種表述方式：的多種表述方式： 若若p,就就q 只要只要p,就就q 只有只有q 才才p 除非除非q, 才才p 除非除非q, 否則非否則非p當(dāng)當(dāng)p為假時(shí)，為假時(shí)，pq為真為真(不管不管q為真為真, 還是為假還是為假)15實(shí)例實(shí)例例例4 設(shè)設(shè)p:天冷天冷, q:小王穿羽絨服，小王穿羽絨服，將下列命題符號(hào)化將下列命

12、題符號(hào)化 (1) 只要天冷，小王就穿羽絨服只要天冷，小王就穿羽絨服.(2) 因?yàn)樘炖?，所以小王穿羽絨服因?yàn)樘炖洌孕⊥醮┯鸾q服.(3) 若小王不穿羽絨服，則天不冷若小王不穿羽絨服，則天不冷.(4) 只有天冷，小王才穿羽絨服只有天冷，小王才穿羽絨服.(5) 除非天冷，小王才穿羽絨服除非天冷，小王才穿羽絨服.(6) 除非小王穿羽絨服，否則天不冷除非小王穿羽絨服，否則天不冷.(7) 如果天不冷，則小王不穿羽絨服如果天不冷，則小王不穿羽絨服.注意：注意： pq 與與 qp 等值（真值相同）等值（真值相同） pqpq qp 或或 pqpqqp qp pq 或或 qp16聯(lián)結(jié)詞與復(fù)合命題聯(lián)結(jié)詞與復(fù)合命題

13、(續(xù)續(xù))定義定義2.5 設(shè)設(shè)p, q為命題為命題, 復(fù)合命題復(fù)合命題 “p當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)q”稱作稱作p與與q的的等價(jià)式等價(jià)式, 記作記作pq, 稱作稱作等價(jià)聯(lián)結(jié)詞等價(jià)聯(lián)結(jié)詞. 并規(guī)定并規(guī)定pq為真當(dāng)為真當(dāng)且僅當(dāng)且僅當(dāng) p與與q同時(shí)為真或同時(shí)為假同時(shí)為真或同時(shí)為假. pq 的邏輯關(guān)系的邏輯關(guān)系: p與與q互為充分必要條件互為充分必要條件例如例如 這件事張三能做好這件事張三能做好, 且只有張三能做好且只有張三能做好 設(shè)設(shè)p:張三做這件事張三做這件事, q:這件事做好了這件事做好了 形式化為形式化為: pq17實(shí)例實(shí)例例例5 求下列復(fù)合命題的真值求下列復(fù)合命題的真值(1) 2+24 當(dāng)且僅當(dāng)當(dāng)且僅

14、當(dāng) 3+36.(2) 2+24 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 3是偶數(shù)是偶數(shù).(3) 2+24 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 太陽從東方升起太陽從東方升起.(4) 2+25 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 美國(guó)位于非洲美國(guó)位于非洲.(5) f (x)在在x0處處可導(dǎo)的充要條件是它在可導(dǎo)的充要條件是它在 x0處連續(xù)處連續(xù).1011018聯(lián)結(jié)詞與復(fù)合命題聯(lián)結(jié)詞與復(fù)合命題(續(xù)續(xù))聯(lián)結(jié)詞優(yōu)先級(jí)聯(lián)結(jié)詞優(yōu)先級(jí):( ),:( ), , , , , 同級(jí)按從左到右的順序進(jìn)行同級(jí)按從左到右的順序進(jìn)行 p q p pq pq pq pq 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1基本

15、復(fù)合命題的真值基本復(fù)合命題的真值19合式公式合式公式命題常命題常項(xiàng)項(xiàng): 簡(jiǎn)單命題簡(jiǎn)單命題 命題變項(xiàng)命題變項(xiàng): 真值可以變化的陳述句真值可以變化的陳述句定義定義2.6 合式公式合式公式 (命題公式命題公式, 公式公式) 遞歸定義如下：遞歸定義如下：(1) 單個(gè)命題常項(xiàng)或變項(xiàng)單個(gè)命題常項(xiàng)或變項(xiàng)是是合式公式合式公式,并稱作并稱作原子合式公式原子合式公式(2) 若若A是合式公式是合式公式, 則則 ( A)也是合式公式也是合式公式(3) 若若A, B是合式公式是合式公式, 則則(A B), (A B), (AB), (AB)也也 是合式公式是合式公式(4) 只有有限次地應(yīng)用只有有限次地應(yīng)用(1)(3)形

16、成的符號(hào)串才是合式公式形成的符號(hào)串才是合式公式說明說明:(1) 元語言符號(hào)與對(duì)象語言符號(hào)元語言符號(hào)與對(duì)象語言符號(hào) (2) 在不影響運(yùn)算順序時(shí)在不影響運(yùn)算順序時(shí), 括號(hào)可以省去括號(hào)可以省去 例如例如 0, p, p q, (p q) ( p r), p q r, (pq)r20合式公式的層次合式公式的層次定義定義2.7 (1) 單個(gè)命題變項(xiàng)或命題常項(xiàng)是單個(gè)命題變項(xiàng)或命題常項(xiàng)是0層公式層公式(2) 稱稱A是是n+1(n0)層公式是指下面情況之一：層公式是指下面情況之一：(a) A= B, B是是n層公式層公式(b) A=B C, 其中其中B,C分別為分別為i層和層和j層公式層公式, 且且 n=ma

17、x(i, j)(c) A=B C, 其中其中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層層 ( p q) r)( r s) 4層層21公式的賦值公式的賦值定義定義2.8 設(shè)設(shè)p1, p2, , pn是出現(xiàn)在公式是出現(xiàn)在公式A中全部的命題變項(xiàng)中全部的命題變項(xiàng), 給給 p1, p2, , pn指定一組真值指定一組真值, 稱為對(duì)稱為對(duì)A的一個(gè)的一個(gè)賦值賦值或或解釋解釋.使公式為真的賦值稱作使公式為真的賦值稱作成真賦值成真賦值

18、, 使公式為假的賦值稱作使公式為假的賦值稱作成假賦值成假賦值說明說明: (1) 賦值記作賦值記作 = 1 2 n, i=0或或1, 諸諸 i之間不加標(biāo)之間不加標(biāo)點(diǎn)符號(hào)點(diǎn)符號(hào)(2) 通常賦值與命題變項(xiàng)之間按下標(biāo)或字母順序?qū)?yīng)通常賦值與命題變項(xiàng)之間按下標(biāo)或字母順序?qū)?yīng), 即即當(dāng)當(dāng)A的全部命題變項(xiàng)為的全部命題變項(xiàng)為p1, p2, , pn時(shí)時(shí), 給給A賦值賦值 1 2 n是指是指p1= 1,p2= 2,pn= n; 當(dāng)當(dāng)A的全部命題變項(xiàng)為的全部命題變項(xiàng)為p,q,r,時(shí)時(shí), 給給A賦值賦值 1 2 3是指是指p= 1, q= 2, r= 3, 22實(shí)例實(shí)例例例6 公式公式A= p1 p2 01是成真賦值是成真賦值, 00是成假賦值是成假賦值 公式公式B=( p1 p2 p3 ) (p1 p2) 000是成真賦值是成真賦值, 001是成假賦值是成假賦值 公式公式C= (pq)r 000是成假賦