命題邏輯PPT精品文檔

1、1,第一章 命題邏輯,第二講,2,定義1-1 在數(shù)理邏輯中，把能惟一判斷真假的陳述句 稱為命題(proposition)，以命題作為研究對(duì)象的邏輯 稱為命題邏輯(proposition logic,回 顧,要判斷一個(gè)句子是否為命題，應(yīng)首先判斷它是否為 陳述句，再判斷它是否有惟一的真值；若它是具有 惟一真值的陳述句，則為命題,一、命題,3,定義1-2 凡不能再分解的命題稱為原子命題 (atomic proposition)。由原子命題和聯(lián)結(jié)詞 聯(lián)結(jié)而成的命題稱為復(fù)合命題(compound pr oposition,原子命題是命題邏輯的基本單位，是一個(gè)不可 再分的個(gè)體，其真假性獨(dú)立于其他命題,二、

2、命題的分類(lèi),4,定義1-3 如果一個(gè)命題標(biāo)識(shí)符代表任意未知命題，則稱該命題標(biāo)識(shí)符為命題變?cè)?。如果一個(gè)命題標(biāo)識(shí)符代表一個(gè)確定的命題，則稱之為命題常元。 命題變?cè)?lèi)似代數(shù)中的變量，命題常元類(lèi)似常量，但兩者有著本質(zhì)的區(qū)別。命題變?cè)虺Ｔ淼氖敲}元素，而變量和常量代表的是一個(gè)數(shù)值,三、命題常元與命題變?cè)?5,1.1.2 命題聯(lián)結(jié)詞 命題聯(lián)結(jié)詞與日常語(yǔ)言中的聯(lián)結(jié)詞類(lèi)似，例如：“如果,那么”、“不但而且”、“不”、“并且”、“或者”等等。但這些聯(lián)結(jié)詞沒(méi)有經(jīng)過(guò)嚴(yán)格定義，有的在意義上模棱兩可，使用起來(lái)不很確切。 在數(shù)理邏輯中，聯(lián)結(jié)詞必須經(jīng)過(guò)嚴(yán)格定義，它們的含義有時(shí)并不完全與日常語(yǔ)言的聯(lián)結(jié)詞一致，為了區(qū)別，

3、我們把命題演算中的聯(lián)結(jié)詞稱為命題聯(lián)結(jié)詞或邏輯聯(lián)結(jié)詞,四、命題聯(lián)結(jié)詞,6,7,0,0,0,0,0,0,0,1,1,1,1,1,8,0,0,0,0,0,1,1,1,1,1,1,1,9,說(shuō)明】析取又稱為邏輯“或”。它可分為可兼或（inclusive or）和不可兼或（exclusive or）。聯(lián)結(jié)詞 “”代表的是可兼或，還有不可兼或。 例如：命題“小李在看書(shū)或聽(tīng)音樂(lè)”，這里的“或”顯然是“可兼或”；而命題“小李正在教室看書(shū)或正在圖書(shū)館上網(wǎng)” 的“或”是“不可兼或”，因?yàn)橥粋€(gè)人不可能同時(shí)出現(xiàn)在兩個(gè)不同的地方。不可兼或指的是二者不能同時(shí)存在。因此，析取聯(lián)結(jié)詞“”只表示“可兼或,10,例1-3將下列命

4、題符號(hào)化： （1）小李在看書(shū)或聽(tīng)音樂(lè)。 （2）小李正在教室看書(shū)或正在圖書(shū)館上網(wǎng)。 解（1）設(shè)p ：小李在看書(shū)， Q ：小李在聽(tīng)音樂(lè)； 則該命題符號(hào)化為：P Q 。 （2）設(shè)R ：小李正在教室看書(shū)， S ：小李正在圖書(shū)館上網(wǎng)；此命題必須使用多個(gè)聯(lián)結(jié)詞，命題符號(hào)化為：,11,0,0,0,0,0,1,1,1,1,1,1,1,12,在真值表中，除了前件為真，后件為假時(shí)為假，其余都為真,前件為假不是我們考慮的對(duì)象，所以不管后件是真還是假，都有為真。這種情況邏輯學(xué)上稱為“善意推定,正是因?yàn)檫@個(gè)“善意推定”，阿基米德才會(huì)說(shuō)：“給我一個(gè)支點(diǎn)，我能把地球撬起來(lái)?！保@句話永遠(yuǎn)是對(duì)的，因?yàn)闆](méi)有誰(shuí)能給他這樣一個(gè)支點(diǎn)

5、，前件總為假，不管他能否把地球撬起來(lái)，他都是對(duì)的,13,0,0,0,0,0,1,1,1,1,1,0,1,14,1.1.3 邏輯聯(lián)結(jié)詞的優(yōu)先級(jí) 為了使命題的符號(hào)化變得清晰而簡(jiǎn)潔，需要給命題聯(lián)結(jié)詞規(guī)定優(yōu)先級(jí)次序，5種聯(lián)結(jié)詞也稱為邏輯運(yùn)算符，其優(yōu)先級(jí)次序規(guī)定為：“ ”、“”、“”、“ ”、“ ”。其中 “ ”的優(yōu)先級(jí)最高，“”的優(yōu)先級(jí)最低。 如果有括號(hào)，括號(hào)最優(yōu)先。在同一括號(hào)層并列兩個(gè)以上相同的聯(lián)結(jié)詞，則按從左到右的順序運(yùn)算。例如： pqr的含義與(p (q) r 相同， 而與p(q) r)或p ( (qr)的含義不同,15,1.2 命題公式,不包含聯(lián)結(jié)詞的命題叫做原子命題,至少包含一個(gè)聯(lián)結(jié)詞的命題

6、稱為復(fù)合命題。若命題表達(dá)式中包含具體命題，或者命題變?cè)?，則稱之為命題公式。命題變?cè)Q為命題公式的分量。 并非由命題常元、變?cè)?、?lián)結(jié)詞和括號(hào)組成的字符串都是命題公式。在此給出一個(gè)嚴(yán)謹(jǐn)?shù)亩x，在給出定義之前先介紹遞歸定義（Inductive definition）的方法,16,遞歸定義一般用于定義集合的元素，整個(gè)過(guò)程分為三步： （1）基礎(chǔ)：確定某個(gè)對(duì)象在集合中。 （2）遞歸：確定構(gòu)造集合元素的方法。 （3）界限：確定集合元素的范圍。 例如：定義一個(gè)非負(fù)偶數(shù)集合E。 解：（1）基礎(chǔ)： （2）遞歸： （3）界限：除非有限次地應(yīng)用基礎(chǔ)和遞歸步造成的數(shù)是偶數(shù)外，其余均不是偶數(shù),17,121 命題公式 命題

7、公式也稱命題演算的合式公式(Well form formula,簡(jiǎn)寫(xiě)為wff)。 定義1-6 命題公式的遞歸定義如下： (1)單個(gè)的命題常元或命題變?cè)敲}公式； (2)如果A是一個(gè)命題公式，則 (A)也是命題公式； (3)如果A和B都是命題公式，則(AB)、(AB)、(AB)、(AB)也是命題公式； (4)當(dāng)且僅當(dāng)有限次地應(yīng)用（1）、(2)、（3）所得到的符號(hào)串是命題公式,18,例如下列不是命題公式: pq、p q、(pq) r、B 、（AB）。 而 、 、 是命題公式。 根據(jù)邏輯聯(lián)結(jié)詞的優(yōu)先級(jí)別可省略一些圓括號(hào)，如上述命題公式可寫(xiě)成： 、 、 。 【說(shuō)明】在命題公式的定義中，引進(jìn)了A、B等

8、符號(hào)，它們代表任意的公式，本書(shū)以后出現(xiàn)的A、B等符號(hào)除特別說(shuō)明外，均表示公式,19,122 命題公式的翻譯 一、把自然語(yǔ)言描述的命題抽象為形式命題(即形式化) 形式化時(shí)應(yīng)注意聯(lián)結(jié)詞的選擇，確定聯(lián)結(jié)詞時(shí)除根據(jù)自然語(yǔ)言的聯(lián)結(jié)詞外，還要考慮語(yǔ)句的實(shí)際含義。 例如：大家要取得好成績(jī)，除非努力學(xué)習(xí)。 其中“除非”是“只有”，除此之外沒(méi)有其它條件。因此努力學(xué)習(xí)是取得好成績(jī)的必要條件。 設(shè) P：大家要取得好成績(jī)； Q：大家要努力學(xué)習(xí)。 則命題形式化為,20,例1-6將下列命題符號(hào)化 （1）8能被2整除，但不能被6整除。 （2）林強(qiáng)學(xué)過(guò)英語(yǔ)或法語(yǔ)。 （3）方梅出生于1956年或1957年。 （4）凡進(jìn)機(jī)房者必

9、須換拖鞋、穿工作服，否則罰款10元。 解（1）設(shè)p ：8能被2整除， q ：8能被6整除； 則該命題符號(hào)化為： （2）設(shè)p ：林強(qiáng)學(xué)過(guò)英語(yǔ)， q ：林強(qiáng)學(xué)過(guò)法語(yǔ)。 由于林強(qiáng)既可能學(xué)過(guò)其中一種語(yǔ)言，也可同時(shí)學(xué)這兩種語(yǔ)言，所以這是可兼或。 則該命題符號(hào)化為,21,3）設(shè)p ：方梅出生于1956年， q ：方梅出生于1957年。 由于方梅可能出生于1956年，也可能出生于1957年，還可能出生于其它年份，但不可能既出生于1956年又出生于1957年。所以這是不可兼或。 該命題應(yīng)符號(hào)化為： （4）設(shè)p:進(jìn)機(jī)房者換拖鞋, q:進(jìn)機(jī)房者穿工作服， r:進(jìn)機(jī)房者被罰款10元。 則該命題應(yīng)符號(hào)化為,22,例1

10、-7 設(shè) P: 明天下雨。 Q: 明天下雪。 R: 我去學(xué)校。 試把下列命題符號(hào)化: 1) 如果明天不是雨夾雪, 我就去學(xué)校。 2) 如果明天既不下雨又不下雪, 我就去學(xué)校。 3) 明天下雨或者下雪, 我就不去學(xué)校。 解： 1) (PQ)R 2) (PQ)R 3) (PQ)R,23,二、把符號(hào)命題翻譯成自然語(yǔ)言命題 這種翻譯比較簡(jiǎn)單，只要求用詞準(zhǔn)確，力求保持原命題的意思。 例 設(shè) A: 今天下雨。 B: 今天下雪。 C: 今天天晴。試把下列形式語(yǔ)言翻譯成自然語(yǔ)言: 1) (AB) 2) C (AB) 3) ABC 解 :1) 說(shuō)今天下雨且下雪是不對(duì)的。 2) 今天天晴當(dāng)且僅當(dāng)今天既不下雨又不下雪。 3) 如果今天下雨或者下雪, 今天就不是晴天,24,堂上練習(xí),1. 將下列命題符號(hào)化： (1) 3不是偶數(shù)。 (2) 小強(qiáng)雖聰明，但不用功。 (3) 派小王或小李出差。 (4) 如果天下雨，他就乘公共汽車(chē)上班。 (5) 只有天下雨，他才乘公共汽車(chē)上班。 (6) 我既不看電