離散第一章命題邏輯1st

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

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

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

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

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

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

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

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