離散數(shù)學(xué)命題邏輯.ppt

1、第一章 命 題 邏 輯,命題與聯(lián)結(jié)詞,邏輯,研究人類思維的科學(xué)。公元前四世紀亞里斯多德工具論奠定了邏輯學(xué)的理論基礎(chǔ)。中國最早的一部邏輯專著墨經(jīng)也創(chuàng)造了一個比較完整的邏輯體系。,形式邏輯,辨證邏輯,數(shù)理邏輯,數(shù)理邏輯,數(shù)理邏輯是一門用數(shù)學(xué)方法來研究推理規(guī)律的科學(xué)。 所謂數(shù)學(xué)方法主要是指引進一套符號體系的方法，所以數(shù)理邏輯也稱做符號邏輯。,（創(chuàng)始人：十七世紀，德國數(shù)學(xué)家萊布尼茲）,形式符號體系,由于自然語言存在模棱兩可、含糊的特性，所以有必要引入形式化語言。形式化語言在數(shù)理邏輯中稱為目標語言。 例如：今天晚上八點中央一臺播放連續(xù)劇或紀錄片。 我吃蘋果或雪梨。 定義目標語言：具有單一、明確的含義的語

2、言。（基本元素是命題） 定義形式符號體系：由目標語言和一些規(guī)定的公式與符號構(gòu)成的體系,為何學(xué)習(xí)數(shù)理邏輯,程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu) 算法 = 邏輯 + 控制,數(shù)理邏輯的主要內(nèi)容,數(shù)理邏輯內(nèi)容豐富，但其主要包括“兩個演算” 加“四論”，即： 邏輯演算。包括命題演算和謂詞演算 證明論。主要研究數(shù)學(xué)理論系統(tǒng)的相容性（即不矛盾、協(xié)調(diào)性）的證明。 遞歸論（能行性理論）。自從電子計算機發(fā)明后，迫切需要在理論上弄清計算機能計算哪些函數(shù)。遞歸論研究能行可計算的理論，它為能行可計算的函數(shù)找出各種理論上精確化的嚴密類比物。 模型論。主要是對各種數(shù)學(xué)理論系統(tǒng)建立模型，并研究各模型之間的關(guān)系以及模型與系統(tǒng)之間的關(guān)系

3、。 公理集合論。主要研究在消除已知集合論悖論的情況下，用公理方法把有關(guān)集合的理論充分發(fā)展下去。,命題邏輯研究的內(nèi)容,命題邏輯也稱為命題演算 研究以命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系. (1) 什么是命題？ (2) 如何表示命題？ (3) 如何由一些前提推導(dǎo)出一些結(jié)論?,命題與聯(lián)結(jié)詞,命題 聯(lián)結(jié)詞,命題的概念,具有判斷內(nèi)容（非真即假）的陳述句稱為命題。 能夠確定或分辨其真假的陳述句。 命題有一個值，稱為真值，真值只有“真”和“假”兩種，分別用“T”（或“1”）和“F”（或“0”）表示。 命題中的判斷正確，其真值為真，稱為真命題，命題中的判斷錯誤，真值為假，稱為假命題。,命題示例1,中

4、華人民共和國的首都是北京。 我們在學(xué)習(xí)離散數(shù)學(xué)的數(shù)理邏輯部分。 所有素數(shù)都是奇數(shù)。 雪是黑色的。,命題示例2,某些感嘆句、祈使句、疑問句等沒有真假之分，所以不是命題。 明天開會嗎？ 多美妙??！ 請進來。 全體立正。,判斷語句是否為命題要注意的問題：,目前無法確定真值，但從本質(zhì)而言，真值存在的語句是命題。 例： (1) 別的星球上有生物。 (2) 2046年世界杯在中國舉行。 真值因時因地而異的判斷性陳述句是命題。 例：(1) 現(xiàn)在是上午。 (2) 今天下雨。 含有未確定內(nèi)容的代詞，不能判斷真假的語句不是命題。 例： (1) 1+101=110。 當1和101是二進制數(shù)，語句為真，為十進制數(shù)，語

5、句為假。 (2) x+y10。 悖論不是命題。 例：我正在說慌。,命題的分類,根據(jù)命題的構(gòu)成形式，可以將命題分為： 定義原子命題：不包含任何聯(lián)結(jié)詞的命題。 定義復(fù)合命題：由原子命題和聯(lián)結(jié)詞組成的命題。連接詞一般譯為：“或者”、“并且”、“不”、“如果則”、“僅當”、“當且僅當”等。 例如：“明天下雪”、“9是素數(shù)”都是原子命題， “2不是素數(shù)”是復(fù)合命題 “明天下雪或明天下雨”是復(fù)合命題。 “中國獲得2008奧運的主辦權(quán)并且加入了WTO”是復(fù)合命題。 “如果A和B是對頂角，則角A等于角B”是復(fù)合命題。,命題的表示,定義命題標識符：表示命題的符號，通常是大寫英文字母。 定義命題符號化：將表示命題

6、的符號放在該命題的前面。 例：P：北京是中國的首都。 Q：北京承辦2008年奧運。,命題的表示（續(xù)）,定義命題常量：表示確定命題的命題標識符。 定義命題變元：可表示任意一個（原子或復(fù)合）命題的命題標識符，就稱為命題變元。當命題變元表示原子命題時，該變元稱為原子變元。 當命題變元P用一個特定命題去取代時， 才能確定P的真值，這時也稱對P進行指派。 例： 若P是命題變元， P：北京是中國的首都。（指派P為命題北京是中國的首都）,命題小結(jié),判斷一句話是否是命題的步驟： 1）看它是否是陳述句，如果是疑問句、感嘆句和祈使句則不是命題； 2）看它是否是悖論，悖論不是命題，如“我正在說謊”； 3）看它真值是

7、否唯一，如果不唯一，則不是命題。,命題與聯(lián)結(jié)詞,命題 聯(lián)結(jié)詞,命題聯(lián)結(jié)詞,1. 否定： 2. 合取： 3. 析?。?4. 排斥析取： 5. 條件（蘊含）： 6. 雙條件：,否定,設(shè)P為命題，P的否定也是一個命題，記作 P 當P為T時， P為F 當P為F時， P為T P與P的關(guān)系如右表 例：設(shè)P：上海是個大城市。 則P：上海不是一個大城市。 或：上海是個不大的城市。,合取,設(shè)P、Q是命題，P和Q的合取也是個命題，記作PQ 當且僅當P、Q同時為T時，PQ為T 其他情況下，PQ的真值都是F 讀作“P并且（與）Q”,合取示例,(1) P: 我富有。 Q: 我快樂。 PQ：我富有并且快樂。 (2) P:

8、 我們?nèi)ナ程贸燥垺?Q: 教室里有三塊黑板。 PQ: 我們?nèi)ナ程贸燥埐⑶医淌依镉腥龎K黑板。 注：復(fù)合命題中的原子命題之間無需有一般邏輯意義上的關(guān)聯(lián)，如(2)。,析取,設(shè)P、Q是命題，則P和Q的析取也是個命題，記作PQ。 當且僅當P、Q同時為F時，PQ為F 其他情況下， PQ的真值都是T 讀作“P或Q” （與自然語言中的“或”不完全相同，是兼并或）,析取例子,例：(1) P：猴子吃香蕉。 Q：猴子吃橘子。 猴子吃香蕉或者吃橘子 ？ PQ (2) P：他明天早上吃蛋糕。 Q：他明天早上喝牛奶。 PQ？ 他明天早上吃蛋糕或者喝牛奶 。 (3) P: 我明天早上9點在家看書。 Q: 我明天早上9點出去

9、打球。 我明天早上9點在家看書或出去打球 PQ？,排斥析取,設(shè)P、Q是命題，P和Q的排斥析取也是個命題，記作 PQ 當且僅當P和Q的真值不相同時， PQ為T， 其他情況下,PQ的真值都是F 讀作“P或Q” （排斥或）,排斥析取示例,指出下列命題中的“或”是析取還是排斥析取 今晚我去看演出或在家里看電視現(xiàn)場轉(zhuǎn)播。 他是一百米冠軍或跳高冠軍。 派小王或小趙出差去上海。 派小王或小趙中的一個出差去上海。 2、3為析取，1、 4為排斥析取,條件/蘊含,設(shè)P、Q是命題，P對于Q的條件命題記為PQ，或稱為P蘊含Q 。 當且僅當P的真值為T，Q的真值為F時，PQ的真值為F， 其他情況， PQ的真值為T。 讀

10、作“如果（若）P，則Q”、“Q是P的必要條件” 、“僅當Q為真時，P為真” 稱P為前件，Q為后件。,條件示例,P：天不下雨 Q：我去看電影 如果天不下雨，那么我去看電影： PQ 。 P：我不到學(xué)校去。 Q：我生病。 PQ：如果我不到學(xué)校去，那么我生病。 P：我去踢足球。 Q：我有時間。 僅當我有時間，我去踢足球。,PQ,雙條件,P、Q是命題，P和Q的雙條件命題記作：P Q 當P和Q的真值相同時，P Q的真值為T， 否則PQ的真值為F 翻譯為：“P當且僅當Q” 或者“若P則Q，否則，則Q”,雙條件示例,P：整數(shù)a能被2整除 Q：a是偶數(shù)。 當且僅當整數(shù)a能被2整除，a才是偶數(shù)：P Q 。 P：天

11、不下雨 Q：我去看足球 P Q：如果天不下雨，我就去看足球，否則，我就不去看足球。 P：224 Q：雪是白的 224當且僅當雪是白的： P Q 注：復(fù)合命題中的原子命題之間無需有一般邏輯意義上的關(guān)聯(lián)。如此例中P和Q并無因果關(guān)系，P Q仍是命題，其真值根據(jù)聯(lián)結(jié)詞定義以及P和Q的真值來確定。,綜合示例,設(shè)P表示命題“天下雪”。 Q表示命題“我去看電影”。 R表示命題“我有時間”。 試以符號形式表示下列命題：,P PQ Q R (QR) P,天不下雪。 如果天不下雪，那么我去看電影。 我去看電影，僅當我有時間。 如果我去看電影且我有時間，那么天不下雪。,聯(lián)結(jié)詞小結(jié),1. 復(fù)合命題的真值只取決于構(gòu)成它

12、們的原子命題的真值和命題聯(lián)結(jié)符的定義，而與它們的內(nèi)容、含義無關(guān)，與聯(lián)結(jié)詞所連接的兩個原子命題之間是否有關(guān)系無關(guān)。 2. ，和具有可交換性，而，沒有。,聯(lián)結(jié)詞小結(jié),1.“只要(若、當)A成立，則B成立” ：AB 2.“僅當A成立時,B成立”和“只有A成立時，B成立”： BA 3. “A成立,否則B成立”：AB。 4. 遇到“或”，就需要考察兩件事情可否同時發(fā)生，若不能同時，則是，否則用“”。,聯(lián)結(jié)詞運算順序,優(yōu)先級從高到底排列： 、/、 、 ,命題（合式）公式,定義命題合式公式： (1) 單個命題變元本身是一個命題合式公式。 (2) 如果A是合式公式，則A是命題合式公式。 (3) 如果 A和B是合式公式，則AB,AB、AB、AB、AB都是命題合式公式。 (4) 當且僅當能夠有限次應(yīng)用(1)、(2)、(3)所得到的包含命題變元，聯(lián)結(jié)詞和括號的符號串是命題合式公式。,命題（合式）公式舉例,設(shè)P、Q、R、S、T都是命題變元，判斷下列字符串哪些是合式公式： (1) (P Q) (2)(PQ) (Q R ) (S T) (3) (PQ) (Q) (4) (PQ)，