命題邏輯PPT精品文檔

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

2、命題的分類,4,定義1-3 如果一個命題標識符代表任意未知命題，則稱該命題標識符為命題變元。如果一個命題標識符代表一個確定的命題，則稱之為命題常元。 命題變元類似代數(shù)中的變量，命題常元類似常量，但兩者有著本質(zhì)的區(qū)別。命題變元或常元代表的是命題元素，而變量和常量代表的是一個數(shù)值,三、命題常元與命題變元,5,1.1.2 命題聯(lián)結(jié)詞 命題聯(lián)結(jié)詞與日常語言中的聯(lián)結(jié)詞類似，例如：“如果,那么”、“不但而且”、“不”、“并且”、“或者”等等。但這些聯(lián)結(jié)詞沒有經(jīng)過嚴格定義，有的在意義上模棱兩可，使用起來不很確切。 在數(shù)理邏輯中，聯(lián)結(jié)詞必須經(jīng)過嚴格定義，它們的含義有時并不完全與日常語言的聯(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,說明】析取又稱為邏輯“或”。它可分為可兼或（inclusive or）和不可兼或（exclusive or）。聯(lián)結(jié)詞 “”代表的是可兼或，還有不可兼或。 例如：命題“小李在看書或聽音樂”，這里的“或”顯然是“可兼或”；而命題“小李正在教室看書或正在圖書館上網(wǎng)” 的“或”是“不可兼或”，因為同一個人不可能同時出現(xiàn)在兩個不同的地方。不可兼或指的是二者不能同時存在。因此，析取聯(lián)結(jié)詞“”只表示“可兼或,10,例1-3將下列命

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

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

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

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

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

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

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