命題邏輯1課件

（小）要求

基本要求考核考勤：按大學(xué)生手冊(cè)執(zhí)行（缺席三次取消考試資格，遲到10分鐘不能進(jìn)入教室）作業(yè)獨(dú)立完成期中考試（？）考教分離周三交作業(yè)（按自然班，班長(zhǎng)負(fù)責(zé)），下一個(gè)周三返還平時(shí)成績(jī)30%：作業(yè)+考勤期末成績(jī)70%離散數(shù)學(xué)是數(shù)學(xué)的幾個(gè)分支的總稱，研究基于離散空間而不是連續(xù)的數(shù)學(xué)結(jié)構(gòu)。與微積分和分析等連續(xù)數(shù)學(xué)相對(duì)的。數(shù)理邏輯，集合論，代數(shù)系統(tǒng)，圖論信息論，理論計(jì)算機(jī)科學(xué)，運(yùn)籌學(xué)，概率論，博弈論數(shù)理邏輯的創(chuàng)始人--萊布尼茨

(Leibniz,GottfriedWilhelm)

1646.7.1-1716.11.14

5/34德國(guó)數(shù)學(xué)家、物理學(xué)家、哲學(xué)家等，一個(gè)舉世罕見的科學(xué)天才。研究領(lǐng)域涉及到邏輯學(xué)、數(shù)學(xué)、力學(xué)、地質(zhì)學(xué)、法學(xué)、歷史學(xué)、語(yǔ)言學(xué)、生物學(xué)以及外交、神學(xué)等諸多方面.出生于德國(guó)東部萊比錫的一個(gè)書香之家，父親是萊比錫大學(xué)的道德哲學(xué)教授，母親出生在一個(gè)教授家庭。萊布尼茲的父親在他年僅6歲時(shí)便去世了，給他留下了豐富的藏書。15歲時(shí)，進(jìn)了萊比錫大學(xué)學(xué)習(xí)法律，一進(jìn)校便跟上了大學(xué)二年級(jí)標(biāo)準(zhǔn)的人文學(xué)科的課程，還廣泛閱讀了培根、開普勒、伽利略等人的著作，并對(duì)他們的著述進(jìn)行深入的思考和評(píng)價(jià)。在聽了教授講授歐幾里德的《幾何原本》的課程后，萊布尼茲對(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(1646～1716年)之夢(mèng)：有一天所有的知識(shí)，包括精神和無(wú)形的真理，能夠通過(guò)通用的代數(shù)演算放入一個(gè)單一的演繹系統(tǒng)。1693年，發(fā)現(xiàn)了機(jī)械能的能量守恒定律。與牛頓并稱為微積分的創(chuàng)立者。系統(tǒng)闡述了二進(jìn)制記數(shù)法，并把它和中國(guó)的八卦聯(lián)系起來(lái)。6/34幾何系統(tǒng)（公理）7/341.過(guò)相異兩點(diǎn)，能作且只能作一直線（直線公理）。2.線段(有限直線)可以任意地延長(zhǎng)。3.以任一點(diǎn)為圓心、任意長(zhǎng)為半徑，可作一圓(圓公理)。4.凡是直角都相等(角公理)。5.兩直線被第三條直線所截，如果同側(cè)兩內(nèi)角和小于兩個(gè)直角，則兩直線作延長(zhǎng)時(shí)在此側(cè)會(huì)相交。1.跟同一個(gè)量相等的兩個(gè)量相等；即若a=c且b=c，則a=b（等量代換公理）。2.等量加等量，其和相等；即若a=b且c=d，則a+c=b+d（等量加法公理）。3.等量減等量，其差相等；即若a=b且c=d，則a-c=b-d（等量減法公理）。4.完全疊合的兩個(gè)圖形是全等的（移形疊合公理）。5.全量大於分量，即a+b>a（全量大於分量公理）。公設(shè)：公理：主要內(nèi)容9/34命題、命題邏輯聯(lián)結(jié)詞命題變?cè)?、合式公式重言式、永真蘊(yùn)含、恒等式帶入規(guī)則、替換規(guī)則對(duì)偶原理范式及其判定問(wèn)題命題演算的推理概述10/34現(xiàn)實(shí)語(yǔ)言翻譯判定推理應(yīng)用：計(jì)算機(jī)電路設(shè)計(jì)計(jì)算機(jī)程序構(gòu)造程序正確性證明1.1命題與命題邏輯聯(lián)結(jié)詞一、命題所謂命題，是指具有非真必假的陳述句。而疑問(wèn)句、祈使句和感嘆句等因都不能判斷其真假，故都不是命題。

定義：或者為真，或者為假而不是兩者同時(shí)成立的陳述句被稱為一個(gè)命題?；蛘婊蚣伲荒芗日嬗旨?。例1:判斷下面語(yǔ)句是否是命題華盛頓是美國(guó)的首都。多倫多是加拿大的首都。

1+101=110幾點(diǎn)了？x+1=3真熱呀！坑爹神馬都是浮云11/34或真或假，不能既真又假1.1命題與命題邏輯聯(lián)結(jié)詞2.命題的真值及表示命題用大寫的英文字母，如，，…表示。

P：今天是星期一。命題僅有兩種可能的真值—真和假，且二者只能居其一。如果一個(gè)命題的真值是真，則用1或True(T)來(lái)表示；如果一個(gè)命題的真值是假，則用0或False(F)來(lái)表示。13/34定義：一個(gè)命題不能再分解為更簡(jiǎn)單的命題，這個(gè)命題稱為原子命題。如果下周日下雪，那么我就去滑雪。如果下周日不下雨并且沒有考試，那么我去海邊玩。這次演講比賽，我們班將由趙明或者張強(qiáng)參加。14/34命題原子命題？分子命題（復(fù)合命題）六種邏輯聯(lián)結(jié)詞（1）聯(lián)結(jié)詞“非”，記為“”，表示“否定”的意思。（2）聯(lián)結(jié)詞“合取”，記為“∧”，表示“且”的意思。（3）聯(lián)結(jié)詞“析取”，記為“∨”，表示“或”的意思。（4）聯(lián)結(jié)詞“蘊(yùn)涵”，記為“→”，表示“如果…，則…”的意思。（5）聯(lián)結(jié)詞“等價(jià)”，記為“”，表示“當(dāng)且僅當(dāng)”的意思。（6）聯(lián)結(jié)詞“異或”，記為“”，表示“要么…，要么…”的意思。15/34例：找出命題“熊孩子都是坑爹的”的否定。

“并非所有的熊孩子都是坑爹的?！薄八械男芎⒆佣疾皇强拥摹！狈穸ā獙?duì)整體否定，不是對(duì)局部的否定17/34合取——∧定義：表征意義兩命題合取的真值表18/34或合取——∧19/34析取——∨21/34可兼或不可兼或異或——

定義：表征意義雙條件的真值表22/34或蘊(yùn)涵——→定義：表征意義蘊(yùn)含的真值表23/34或蘊(yùn)涵——→在日常生活中，用條件式表示前提和結(jié)論之間的因果或?qū)嵸|(zhì)關(guān)系，這種條件式稱為形式條件命題。然而在命題邏輯中，一個(gè)條件式的前提并不要求與結(jié)論有任何關(guān)系，這種條件式稱為實(shí)質(zhì)條件命題。25/34等價(jià)——定義：表征意義等價(jià)的真值表26/34或句子到邏輯表達(dá)式的翻譯翻譯下列命題：(1)他既聰明又用功。(2)他雖聰明但不用功。解：原子命題P：他聰明。

Q：他用功。則有：

(1)翻譯成：P∧Q

(2)翻譯成：P∧

?Q29/34句子到邏輯表達(dá)式的翻譯除非有時(shí)間，我才去看電影A：我有時(shí)間。B：我去看電影。翻譯為：B→A我不承認(rèn)你是對(duì)的，除非太陽(yáng)從西邊出來(lái)A：我不承認(rèn)你是對(duì)的。B：太陽(yáng)從西邊出來(lái)。翻譯為：?B→A30/34句子到邏輯表達(dá)式的翻譯如果你和他都不固執(zhí)己見的話，那么不愉快的事情就不會(huì)發(fā)生了。P：你固執(zhí)己見。Q：他固執(zhí)己見。R：不愉快的事情不會(huì)發(fā)生。翻譯為：(?PΛ?Q)→R如果你和他不都是固執(zhí)己見的話，那么不愉快的事情就不會(huì)發(fā)生了。?(PΛQ)→R31/34句子到邏輯表達(dá)式的翻譯P：這個(gè)材料很有趣。Q：這個(gè)習(xí)題很難。R：這門課程使人喜歡。1、這個(gè)材料很有趣，而且這些習(xí)題很難。2、這個(gè)材料無(wú)趣，習(xí)題也不難，那么，這門課程就不會(huì)使人喜歡。3、這個(gè)材料無(wú)趣，習(xí)題也不難，而且這門課程也不使人喜歡。4、這個(gè)材料很有趣意味著這些習(xí)題很難，反之亦然。5、或者這個(gè)材料很有趣，或者這些習(xí)題很難，而且兩者恰具其一。32/34句子到邏輯表達(dá)式的翻譯除非你已滿16周歲，否則只要你的身高不足4英尺就不能乘公園滑行鐵道游樂(lè)車。P：你能乘坐公園滑行鐵道游樂(lè)車。Q：你身高不足4英尺。R：你已滿16周歲。翻譯成：(?RΛ

Q)→?P33/34邏輯難題一個(gè)島上居住著兩類人——騎士和流氓。騎士說(shuō)的都是實(shí)話，而流氓只會(huì)說(shuō)謊。你碰到兩個(gè)人A