離散第一章命題邏輯1st

1、離散數(shù)學第一章 命題邏輯2/34 什么是數(shù)理邏輯？數(shù)理邏輯是用數(shù)學方法研究思維規(guī)律的一門學科。所謂數(shù)學方法是指:用一套數(shù)學的符號系統(tǒng)來描述和處理思維的形式與規(guī)律。因此，數(shù)理邏輯又稱為符號邏輯。 數(shù)理邏輯的創(chuàng)始人-萊布尼茨(Leibniz, Gottfried Wilhelm) 1646.7.1-1716.11.14 3/34德國數(shù)學家、物理學家、哲學家等，一個舉世罕見的科學天才。研究領域涉及到邏輯學、數(shù)學、力學、地質學、法學、歷史學、語言學、生物學以及外交、神學等諸多方面.出生于德國東部萊比錫的一個書香之家，父親是萊比錫大學的道德哲學教授，母親出生在一個教授家庭。萊布尼茲的父親在他年僅6歲時便

2、去世了，給他留下了豐富的藏書。15歲時，進了萊比錫大學學習法律，一進校便跟上了大學二年級標準的人文學科的課程，還廣泛閱讀了培根、開普勒、伽利略等人的著作，并對他們的著述進行深入的思考和評價。在聽了教授講授歐幾里德的幾何原本的課程后，萊布尼茲對數(shù)學產生了濃厚的興趣。17歲時他在耶拿大學學習了短時期的數(shù)學，并獲得了哲學碩士學位 。19歲設計出世界第一臺乘法器，被認為是現(xiàn)代機器數(shù)學的先驅者。 Leibniz(16461716年) 之夢：有一天所有的知識，包括精神和無形的真理，能夠通過通用的代數(shù)演算放入一個單一的演繹系統(tǒng)。1693年，發(fā)現(xiàn)了機械能的能量守恒定律。與牛頓并稱為微積分的創(chuàng)立者。系統(tǒng)闡述了二

3、進制記數(shù)法，并把它和中國的八卦聯(lián)系起來。4/34主要內容5/34命題、命題邏輯聯(lián)結詞命題變元、合式公式重言式、永真蘊含、恒等式帶入規(guī)則、替換規(guī)則對偶原理范式及其判定問題命題演算的推理1.1概述6/34現(xiàn)實語言翻譯判定推理應用：計算機電路設計 計算機程序構造 程序正確性證明1.2命題與命題邏輯聯(lián)結詞一、命題 所謂命題，是指具有非真必假的陳述句。而疑問句、祈使句和感嘆句等因都不能判斷其真假，故都不是命題。 1.定義：一個具有真假意義的陳述句被稱為一 個命題。 或真或假，不能既真又假。 例1:判斷下面語句是否是命題華盛頓是美國的首都。多倫多是加拿大的首都。 1+101=110 幾點了？x+1=3真熱

4、呀！7/34或真或假，不能既真又假1.2命題與命題邏輯聯(lián)結詞8/34理發(fā)師問題：理發(fā)師給所有不給自己理發(fā)的人理發(fā)分析：（1）理發(fā)師給自己理發(fā)（2）理發(fā)師不給自己理發(fā)不能給自己理發(fā)需要給自己理發(fā)悖論1.2命題與命題邏輯聯(lián)結詞一、命題 2.命題的真值及表示命題用大寫的英文字母，如 ， ， 表示。 P：今天是星期二。命題僅有兩種可能的真值真和假，且二者只能居其一。如果一個命題的真值是真，則用1或(Ture)來表示；如果一個命題的真值是假，則用0或（False）來表示。9/34定義：一個命題不能再分解為更簡單的命題，這個命題稱為原子命題。 如果下周日下雪，那么我就去滑雪。如果下周日不下雨并且沒有考試，

5、那么我去海邊玩。這次演講比賽，我們班將由趙明或者張強參加。10/34命題原子命題？分子命題（復合命題）5種邏輯聯(lián)結詞否定詞“并非”合取詞“并且”析取詞“或者”蘊含詞“如果，那么”（單向詞）雙向蘊含詞“當且僅當”（雙向詞）11/34定義：設P是一個命題，則P的否定是一個新的命題，記作“ ”，讀作“非P”。 否定詞“”的意義如下表：否定或真值表：利用運算對象真值的所有可能組合判斷命題的真假。12/34例：找出命題“所有的素數(shù)都是奇數(shù)”的否定。 “并非所有的素數(shù)都是奇數(shù)?！?“所有的素數(shù)都不是奇數(shù)?！狈穸▽φw否定，不是對局部的否定13/34合取定義：表征意義兩命題合取的真值表14/34或合取15/

6、34析取定義：表征意義兩命題析取的真值表16/34或析取17/34可兼或不可兼或異或 定義：表征意義雙條件 的真值表18/34或單條件定義：表征意義蘊含 的真值表19/34或單條件政治家競選時許諾“如果我當選了，那么我將會減稅”。如果今天是星期五，那么2+2=4.與程序設計中if p then S語句的區(qū)別。20/34現(xiàn)實世界中無意義的語言也可以翻譯單條件在日常生活中，用條件式表示前提和結論之間的因果或實質關系，這種條件式稱為形式條件命題。然而在命題邏輯中，一個條件式的前提并不要求與結論有任何關系，這種條件式稱為實質條件命題。21/34雙條件定義：表征意義雙條件 的真值表22/34或1.2命題

7、與命題邏輯聯(lián)結詞注意：由邏輯聯(lián)結詞聯(lián)結的命題之間不需要任何關系。優(yōu)先次序：23/34句子到邏輯表達式的翻譯步驟：確定給定的句子是否為命題；找出各原子命題并確定句子中的連詞為對應的聯(lián)結詞；用正確的語法把原命題表示成由原子命題、聯(lián)結詞和圓括號組成的公式。24/34句子到邏輯表達式的翻譯翻譯下列命題：(1)他既聰明又用功。(2)他雖聰明但不用功。解：原子命題 P：他聰明。 Q：他用功。則有： (1)翻譯成： P Q (2)翻譯成： P Q25/34句子到邏輯表達式的翻譯除非有時間，我才去看電影A：我有時間。B：我去看電影。翻譯為： B A我不承認你是對的，除非太陽從西邊出來A：我不承認你是對的。B：

8、太陽從西邊出來。翻譯為： B A26/34句子到邏輯表達式的翻譯如果你和他都不固執(zhí)己見的話，那么不愉快的事情就不會發(fā)生了。P：你固執(zhí)己見。Q：他固執(zhí)己見。R：不愉快的事情不會發(fā)生。翻譯為： (PQ)R如果你和他不都是固執(zhí)己見的話，那么不愉快的事情就不會發(fā)生了。 (PQ)R27/34句子到邏輯表達式的翻譯P：這個材料很有趣。Q：這個習題很難。R：這門課程使人喜歡。1、這個材料很有趣，而且這些習題很難。2、這個材料無趣，習題也不難，那么，這門課程就不會使人喜歡。3、這個材料無趣，習題也不難，而且這門課程也不使人喜歡。4、這個材料很有趣意味著這些習題很難，反之亦然。5、或者這個材料很有趣，或者這些習題很難，而且兩者恰具其一。28/34句子到邏輯表達式的翻譯除非你已滿16周歲，否則只要你的身高不足4英尺就不能乘公園滑行鐵道游樂車。P：你能乘坐公園滑行鐵道游樂車。Q：你身高不足4英尺。R：你已滿16周歲。翻譯成：(R Q) P29/34邏輯難題一個島上居住著兩類人騎士和流氓。騎士說的都是實話，而流氓只會說謊。