離散數(shù)學(xué)課件 第一章 命題邏輯-1st.pdf

離散數(shù)學(xué) 大連理工大學(xué)軟件學(xué)院 陳志奎 教授 辦公室 綜合樓411 Tel 87571525 實(shí)驗(yàn)室 教學(xué)樓A318 A323 Tel 87571620 24 MobileEmail zkchen zkchen00 1 34 引言 離散數(shù)學(xué)是計(jì)算機(jī)專業(yè)的一門重要基礎(chǔ)課 它所研究的 對象是離散數(shù)量關(guān)系和離散結(jié)構(gòu)數(shù)學(xué)結(jié)構(gòu)模型 由于數(shù) 字電子計(jì)算機(jī)是一個(gè)離散結(jié)構(gòu) 它只能處理離散的或離 散化了的數(shù)量關(guān)系 因此 無論計(jì)算機(jī)科學(xué)本身 還是 與計(jì)算機(jī)科學(xué)及其應(yīng)用密切相關(guān)的現(xiàn)代科學(xué)研究領(lǐng)域 都面臨著如何對離散結(jié)構(gòu)建立相應(yīng)的數(shù)學(xué)模型 又如何 將已用連續(xù)數(shù)量關(guān)系建立起來的數(shù)學(xué)模型離散化 從而 可由計(jì)算機(jī)加以處理 離散數(shù)學(xué)課程主要介紹離散數(shù)學(xué) 的各個(gè)分支的基本概念 基本理論和基本方法 這些概 念 理論以及方法大量地應(yīng)用在數(shù)字電路 編譯原理 數(shù)據(jù)結(jié)構(gòu) 操作系統(tǒng) 數(shù)據(jù)庫系統(tǒng) 算法的分析與設(shè)計(jì) 人工智能 計(jì)算機(jī)網(wǎng)絡(luò)等專業(yè)課程中 同時(shí) 該課程所 提供的訓(xùn)練十分有益于學(xué)生概括抽象能力 邏輯思維能 力 歸納構(gòu)造能力的提高 十分有益于學(xué)生嚴(yán)謹(jǐn) 完整 規(guī)范的科學(xué)態(tài)度的培養(yǎng) 2 34 學(xué)習(xí)方法 精確嚴(yán)格地掌握好概念和術(shù)語 正確理解 它們的內(nèi)涵和外延 獨(dú)立完成作業(yè) 自覺歸納基本解題方法 閱讀和復(fù)習(xí)時(shí) 隨時(shí)備好紙筆 以便進(jìn)行 詳細(xì)的推導(dǎo)和計(jì)算 學(xué)習(xí)和理解術(shù)語 給術(shù)語賦予特殊的含 義 加深理解 多做習(xí)題 加深理解 3 34 第一章 命題邏輯 第一章 命題邏輯 數(shù)理邏輯是用數(shù)學(xué)方法研究思維規(guī)律的一門學(xué) 科 所謂數(shù)學(xué)方法是指 用一套數(shù)學(xué)的符號(hào)系統(tǒng) 來描述和處理思維的形式與規(guī)律 因此 數(shù)理 邏輯又稱為符號(hào)邏輯 數(shù)理邏輯和計(jì)算機(jī)的發(fā)展有著密切的聯(lián)系 它為 機(jī)器證明 自動(dòng)程序設(shè)計(jì) 計(jì)算機(jī)輔助設(shè)計(jì)等計(jì) 算機(jī)應(yīng)用和理論研究提供必要的理論基礎(chǔ) 古典數(shù)理邏輯 命題邏輯和謂詞邏輯 是計(jì)算機(jī) 科學(xué)很重要的數(shù)學(xué)基礎(chǔ) 現(xiàn)代數(shù)理邏輯 邏輯演算 證明論 公理集合論 遞歸論和模型論 本章介紹數(shù)理邏輯中最基本的內(nèi)容命題邏輯 首 先引入命題 命題公式等概念 然后 在此基礎(chǔ) 上研究命題公式間的等值關(guān)系和蘊(yùn)含關(guān)系 并給 出推理規(guī)則 進(jìn)行命題演算 5 34 數(shù)理邏輯的創(chuàng)始人數(shù)理邏輯的創(chuàng)始人 萊布尼茨萊布尼茨 Leibniz Gottfried Wilhelm Leibniz Gottfried Wilhelm Leibniz Gottfried Wilhelm Leibniz Gottfried Wilhelm 1646 7 1 1716 11 141646 7 1 1716 11 141646 7 1 1716 11 141646 7 1 1716 11 14 德國數(shù)學(xué)家 物理學(xué)家 哲學(xué)家等 德國數(shù)學(xué)家 物理學(xué)家 哲學(xué)家等 一個(gè)舉世罕見的科學(xué)天才 研究領(lǐng)域涉一個(gè)舉世罕見的科學(xué)天才 研究領(lǐng)域涉 及到邏輯學(xué) 數(shù)學(xué) 力學(xué) 地質(zhì)學(xué) 法及到邏輯學(xué) 數(shù)學(xué) 力學(xué) 地質(zhì)學(xué) 法 學(xué) 歷史學(xué) 語言學(xué) 生物學(xué)以及外交 學(xué) 歷史學(xué) 語言學(xué) 生物學(xué)以及外交 神學(xué)等諸多方面神學(xué)等諸多方面 出生于德國東部萊比錫的一個(gè)書香之出生于德國東部萊比錫的一個(gè)書香之 家 父親是萊比錫大學(xué)的道德哲學(xué)教家 父親是萊比錫大學(xué)的道德哲學(xué)教 授 母親出生在一個(gè)教授家庭 萊布尼授 母親出生在一個(gè)教授家庭 萊布尼 茲的父親在他年僅茲的父親在他年僅6 6歲時(shí)便去世了 給歲時(shí)便去世了 給 他留下了豐富的藏書 他留下了豐富的藏書 6 34 15歲時(shí) 進(jìn)了萊比錫大學(xué)學(xué)習(xí)法律 一進(jìn)校便跟上了大學(xué)二年 級(jí)標(biāo)準(zhǔn)的人文學(xué)科的課程 還廣泛閱讀了培根 開普勒 伽利 略等人的著作 并對他們的著述進(jìn)行深入的思考和評價(jià) 在聽 了教授講授歐幾里德的 幾何原本 的課程后 萊布尼茲對數(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年 之夢 有一天所有的知識(shí) 包括精 神和無形的真理 能夠通過通用的代數(shù)演算放入一個(gè)單一的演 繹系統(tǒng) 1693年 發(fā)現(xiàn)了機(jī)械能的能量守恒定律 與牛頓并稱為微積分的創(chuàng)立者 系統(tǒng)闡述了二進(jìn)制記數(shù)法 并把它和中國的八卦聯(lián)系起來 7 34 主要內(nèi)容 主要內(nèi)容 命題 命題邏輯聯(lián)結(jié)詞 命題變元 合式公式 重言式 永真蘊(yùn)含 恒等式 帶入規(guī)則 替換規(guī)則 對偶原理 范式及其判定問題 命題演算的推理 8 34 1 1概述 目標(biāo) 探索出一套完整的邏輯規(guī)則 這些規(guī)則 給出數(shù)學(xué)語句的準(zhǔn)確定義 按照這些規(guī) 則可以確定任何特定的論證是否有效 應(yīng)用 計(jì)算機(jī)電路設(shè)計(jì) 計(jì)算機(jī)程序構(gòu)造 程序正確性證明 9 34 1 2命題與命題邏輯聯(lián)結(jié)詞 一 命題 所謂命題 是指具有非真必假的陳述句 而疑問句 祈使句和感嘆句等因都不能判斷其真假 故都不是命 題 1 定義 一個(gè)具有真假意義真假意義的陳述句陳述句被稱為一 個(gè)命題 或真或假 不能既真又假 例1 判斷下面語句是否是命題 華盛頓是美國的首都 多倫多是加拿大的首都 1 101 110 幾點(diǎn)了 x 1 3 西安的小吃真多呀 10 34 1 2命題與命題邏輯聯(lián)結(jié)詞 理發(fā)師問題 理發(fā)師給所有不給自己理發(fā)的人理發(fā) 11 34 1 2命題與命題邏輯聯(lián)結(jié)詞 一 命題 2 命題的真值及表示 命題用大寫的英文字母 如 來表示 P 今天是星期二 命題僅有兩種可能的真值 真和假 且二者只能居其 一 如果一個(gè)命題的真值是真 則用1或 Ture 來表 示 如果一個(gè)命題的真值是假 則用0或 False 來 表示 由于命題只有兩種真值 所以稱這種邏輯為二 值邏輯 命題的真值是具有客觀性質(zhì)的 而不是由人 的主觀決定的 原子命題 一個(gè)命題不能再分解為更簡單的命題 這個(gè)命題 稱為原子命題 P Q R 12 34 1 2命題與命題邏輯聯(lián)結(jié)詞 二 邏輯聯(lián)結(jié)詞 復(fù)合命題 分子命題 如果如果下周日下雪 那么那么我就去滑雪 如果下周日不不下雨并且并且沒有考試 那么我去海 邊玩 這次演講比賽 我們班將由趙明或者或者張強(qiáng)參加 13 34 5種邏輯聯(lián)結(jié)詞 否定詞 并非 合取詞 并且 析取詞 或者 蘊(yùn)含詞 如果 那么 單向詞 雙向蘊(yùn)含詞 當(dāng)且僅當(dāng) 雙向詞 14 34 否定 定義 設(shè) 是一個(gè)命題 則 的否定是一個(gè)新的命題 記作 讀作 非 例2 找出命題 所有的素?cái)?shù)都是奇數(shù) 的否定 并非所有的素?cái)?shù)都是奇數(shù) 所有的素?cái)?shù)都不是奇數(shù) 否定詞 的意義如下表 P P P P PP TF FT PP 01 10 或 真值表 利用運(yùn)算對象真值的 所有可能組合判斷命題的真假 15 合取 定義 表征意義 兩命題合取的真值表 PQ 在命題 和 均為真時(shí)為真 否則為假 PQPQPQ 設(shè) 和 是命題 則用表示命題 并且 PQPQ PQPQ FFF FTF TFF TTT 000 010 100 111 或 16 合取 P Q PQ 命題 今天是星期五 命題 今天下雨 找出命題 和 的合取 PQ 解 表示 今天是星期五并且下雨 這一命題在下雨的星期五成真 不下雨 的星期五和不是星期五的日子都為假 17 析取 定義 表征意義 兩命題析取的真值表 PQ 在命題 和 均為假時(shí)為假 否則為真 PQPQPQ 設(shè) 和 是命題 則用表示命題 或者 PQPQ PQPQ FFF FTT TFT TTT 000 011 101 111 或 18 析取 P Q PQ 例 命題 李明在教室 命題 張強(qiáng)是個(gè)好教練 找出命題 和 的析取 PQ 解 表示 李明在教室或張強(qiáng)是個(gè)好教練 P Q 例 命題 李明在教室 命題 李明在網(wǎng)球場 表示命題 李明在教室或在網(wǎng)球場 19 異或 定義 表征意義 雙條件 的真值表 PQ 在 和 中恰有一個(gè)為真時(shí)為真 否則為假 PQP QPQ 設(shè) 和 是命題 則用表示命題 異或 PQP Q PQP Q FFF FTT TFT TTF 000 101 011 110 P Q 或 20 單條件 定義 表征意義 蘊(yùn)含 的真值表 PQ 在 為真而 為假時(shí)為假 否則為真 PQPQPQ 設(shè) 和是命題 則用表示命題 如果那么 PQPQ PQPQ FFT FTT TFF TTT 001 100 011 111 PQ 或 21 單條件 政治家競選時(shí)許諾 如果我當(dāng)選了 那么我將會(huì)減稅 如果今天是星期五 那么2 2 4 與程序設(shè)計(jì)中if p then S語句的區(qū)別 22 單條件 在日常生活中 用條件式表示前提和結(jié)論之間的 因果或?qū)嵸|(zhì)關(guān)系 這種條件式稱為形式條件命題 然而在命題邏輯中 一個(gè)條件式的前提并不要求 與結(jié)論有任何關(guān)系 這種條件式稱為實(shí)質(zhì)條件命 題 采用實(shí)質(zhì)條件式作定義 不單是出于 善意 推斷 主要是因?yàn)榍疤崤c結(jié)論間有無因果和實(shí) 質(zhì)關(guān)系難以區(qū)分 而且實(shí)質(zhì)條件式已包含了形式 條件式 更便于應(yīng)用 23 34 單條件 注意 在使用聯(lián)結(jié)詞 時(shí) 要特別注意以下幾點(diǎn) 1 在自然語言里 特別是在數(shù)學(xué)中 q是p的必要條件 有許多不同的敘述方式 例如 只要p 就q 因?yàn)?p 所以q p僅當(dāng)q 只有q才p 除非q才p 除 非q 否則非p 等等 以上各種敘述方式表面看來有所不 同 但都表達(dá)的是q是p的必要條件 因而所用聯(lián)結(jié)詞均 應(yīng)符號(hào)化為 上述各種敘述方式都應(yīng)符號(hào)化為p q 2 在自然語言中 如果p 則q 中的前件p與后件q往往 具有某種內(nèi)在聯(lián)系 而在數(shù)理邏輯中 p與q可以無任何 內(nèi)在聯(lián)系 3 在數(shù)學(xué)或其它自然科學(xué)中 如果p 則q 往往表達(dá)的 是前件p為真 后件q也為真的推理關(guān)系 但在數(shù)理邏輯 中 作為一種規(guī)定 當(dāng)p為假時(shí) 無論q是真是假 p q 均為真 也就是說 只有p為真q為假這一種情況使得復(fù) 合命題p q為假 24 34 雙條件 定義 表征意義 雙條件 的真值表 PQ 在 和具有相同的真值時(shí)為真 否則為假 PQPQPQ 設(shè) 和 是命題 則用表示命題 等值于 PQPQ PQPQ FFT FTF TFF TTT 001 100 010 111 PQ 或 25 1 2命題與命題邏輯聯(lián)結(jié)詞 注意 由邏輯聯(lián)結(jié)詞聯(lián)結(jié)的命題之間不需要任何關(guān) 系 優(yōu)先次序 PQR PQR 26 句子到邏輯表達(dá)式的翻譯 步驟 確定給定的句子是否為命題 找出各原子命題并確定句子中的連詞為 對應(yīng)的聯(lián)結(jié)詞 用正確的語法把原命題表示成由原子命 題 聯(lián)結(jié)詞和圓括號(hào)組成的公式 27 34 句子到邏輯表達(dá)式的翻譯 翻譯下列命題 1 他既聰明又用功 2 他雖聰明但不用功 解 原子命題 P 他聰明 Q 他用功 則有 1 翻譯成 P Q 2 翻譯成 P Q 28 34 句子到邏輯表達(dá)式的翻譯 除非有時(shí)間 我才去看電影 A 我有時(shí)間 B 我去看電影 翻譯為 B A 我不承認(rèn)你是對的 除非太陽從西邊出來 A 我不承認(rèn)你是對的 B 太陽從西邊出來 翻譯為 B A 29 34 句子到邏輯表達(dá)式的翻譯 如果你和他都不固執(zhí)己見的話 那么不愉 快的事情就不會(huì)發(fā)生了 P 你固執(zhí)己見 Q 他固執(zhí)己見 R 不愉快的事情不會(huì)發(fā)生 翻譯為 P Q R 如果你和他不都是固執(zhí)己見的話 那么不 愉快的事情就不會(huì)發(fā)生了 P Q R 30 34 句子到邏輯表達(dá)式的翻譯 P 這個(gè)材料很有趣 Q 這個(gè)習(xí)題很難 R 這門課程使人喜歡 1 這個(gè)材料很有趣 而且這些習(xí)題很難 2 這個(gè)材料無趣 習(xí)題也不難 那么 這門課程 就不會(huì)使人喜歡 3 這個(gè)材料無趣 習(xí)題也不難 而且這門課程也 不使人喜歡 4 這個(gè)材料很有趣意味著這些習(xí)題很難 反之亦 然 5 或者這個(gè)材料很有趣 或者這些習(xí)題很難 而 且兩者恰具其一 31 34 句子到邏輯表達(dá)式的翻譯 除非你已滿16周歲 否則只要你的身高不 足4英尺就不能乘公園滑行鐵