《離散數(shù)學第一章命題演算基礎-命題和聯(lián)結(jié)詞.ppt》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學第一章命題演算基礎-命題和聯(lián)結(jié)詞.ppt（60頁珍藏版）》請在裝配圖網(wǎng)上搜索。

離散數(shù)學 數(shù)理邏輯集合論圖論代數(shù) 邏輯學 研究推理的科學 早期創(chuàng)始人亞里士多德 公元前384 322 柏拉圖 公元前429 348 首先把邏輯學的思想方法引入幾何學蘇格拉底 前470 前399年 亞里士多德 Aristotole 公元前384 322 亞里士多德有170多部著作 留傳于世的僅47種 他的科學著作構(gòu)成當時的科學知識百科全書 世界古代史上最偉大的哲學家 科學家和教育家 他創(chuàng)立了形式邏輯學 豐富和發(fā)展了哲學的各個分支學科 孔子 前551 479 中國春秋末期偉大的思想家和教育家 儒家學派的創(chuàng)始人 孔子被尊為圣人 無法超越 后代的人們只有沿襲與膜拜 學而不思則罔思而不學則殆 數(shù)理邏輯 數(shù)學化的邏輯學 在17世紀萊布尼茲 Leibniz 已經(jīng)提出仿數(shù)學的方法發(fā)展邏輯的思想 1930年 Godel完全性定理的證明完善了數(shù)理邏輯基礎 建立了邏輯演算 成為現(xiàn)代科學特別是計算機科學不可缺少的基礎理論之一 數(shù)理邏輯發(fā)展史中的代表人物 德國G W Leibniz 1626 1716 把數(shù)學引入形式邏輯 明確提出用數(shù)學方法研究推理 英國G Boole 1815 1864 等創(chuàng)立了邏輯代數(shù) 1847年Boole實現(xiàn)了命題演算 德國G Frege 1848 1925 在1879年建立了第一個謂詞演算系統(tǒng) 英國B Russell 1872 1970 等從邏輯學的基本法則建立了自然數(shù)理論 實數(shù)理論及解析幾何學等 奧地利K Godel 1906 1978 在1931年提出Godel不完全性定理 英國AlanM Turing 1912 1954 在1936年提出一種抽象計算模型 數(shù)學邏輯機 引入圖靈機 一種理想的計算機 數(shù)理邏輯的學習 我現(xiàn)在年紀大了 搞了這么多年的軟件 錯誤不知犯了多少 現(xiàn)在覺悟了 我想 假如我早年在數(shù)理邏輯上好好下點工夫的話 我就不會犯這么多的錯誤 不少東西邏輯學家早就說過了 可是我不知道 要是我能年輕二十歲的話 我就去學邏輯 Edsger W Dijkstra1972年Turing獎獲得者 1930 2002 帶權(quán)圖的最短通路算法 A M TuringAward 姚期智 Dijkstra LeslieValiant HarvardUniversity Valiant sgreatestsinglecontributionmaybehis1984paper ATheoryoftheLearnable whichlaidthefoundationsofcomputationallearningtheory Heintroducedageneralframeworkaswellasconcretecomputationalmodelsforstudyingthelearningprocess includingthefamous probablyapproximatelycorrect PAC modelofmachinelearning Thishasdevelopedintoavibrantresearchareaandhashadenormousinfluenceonmachinelearning artificialintelligence andmanyareasofcomputingpractice suchasnaturallanguageprocessing handwritingrecognition andcomputervision ProfessorofComputerScienceandAppliedMathematicsSchoolofEngineeringandAppliedSciences 目錄 數(shù)理邏輯 第一章命題演算基礎 6學時 第二章命題演算的推理理論 4學時 第三章謂詞演算基礎 5學時 第四章謂詞演算的推理理論 5學時 第五章遞歸函數(shù)論 4學時 第一章命題演算基礎 1 1命題和聯(lián)結(jié)詞1 1 1命題1 1 2聯(lián)結(jié)詞1 1 3合式公式1 2真假性1 3范式及其應用 一 命題定義 定義1 凡是可以判斷真假的陳述句稱為命題 命題 可以判斷真假的陳述句 非經(jīng)典邏輯不接受排中律 例 下列句子都是命題嗎 雪是白的 雪是黑的 好大的雪啊 8大于12 1 101 110 例 下列句子都是命題嗎 上海世博會開幕時天晴 21世紀末 人類將住在月球 大于2的偶數(shù)可表示成兩個素數(shù)之和 哥德巴赫猜想 XB 如果x大于3 則x2大于9 例 下列句子都是命題嗎 8大于12嗎 請勿吸煙 姚明很帥 南京很美 我正在說謊 這種自指謂的語句往往會產(chǎn)生自相矛盾的結(jié)論 即所謂的悖論 具體命題的真假問題 在數(shù)理邏輯的學習中 不能去糾纏各種具體命題的真假問題 而是將命題當成數(shù)學概念來處理 看成一個抽象的形式化的概念 把命題定義成非真必假的陳述句 公説公有理婆説婆有理 帶聯(lián)結(jié)詞的命題 今晚我看書 今晚我玩網(wǎng)絡游戲 今晚我不看書 今晚我不玩網(wǎng)絡游戲 今晚我不看書 我玩網(wǎng)絡游戲 今晚我看書 或者我玩網(wǎng)絡游戲 否定 并且 或者 二 原子命題和復合命題 原子命題 不可剖開或分解為更簡單命題的命題 也稱為簡單命題 本書約定用大寫字母表示 復合命題 由原子命題利用聯(lián)結(jié)詞構(gòu)成的命題 復合命題例子 下列命題都是復合命題 其中紅字為邏輯聯(lián)結(jié)詞 1 雪不是白的 并非雪是白的 2 今晚我看書或者去看電影 3 如果天氣好 那么我去接你 4 偶數(shù)a是質(zhì)數(shù) 當且僅當a 2 a是常數(shù) 5 2是偶數(shù)且3也是偶數(shù) 6 你去了學校 我去了工廠 省略了邏輯聯(lián)結(jié)詞 且 三 命題變元 定義2 如果當P表示任意命題時 P稱為命題變元 字母P表示 命題 具體的 特定的命題 有確定的真值 命題變元 任意命題 沒有確定的真值 第一章命題演算基礎 1 1命題和聯(lián)結(jié)詞1 1 1命題1 1 2聯(lián)結(jié)詞1 1 3合式公式1 2真假性1 3范式及其應用 五種常用的聯(lián)結(jié)詞 否定詞 合取詞 析取詞 蘊含詞 等價詞 P 非P 設P是一個命題 顯然 如下這句話也是命題 P是不對的 稱之為P的否定 P PTFFT 日常語句中有 非 不 并非 真值表 否定詞的例子 例P 上海是中國的城市 P 上海不是中國的城市 例P 雪是黑色的 P 雪不是黑色的 否定聯(lián)結(jié)詞使用的原則 將真命題變成假命題 將假命題變成真命題 但這并不是簡單的隨意加個不字就能完成的 例P 這些都是學生 P 這些不都是學生 這些都不是學生 阿契貝難題 例下述兩命題都是真命題 A 本句是六字句 B 本句不是六字句 看似矛盾的根本原因 在于兩個命題的前提條件是否統(tǒng)一的問題 P Q P合取Q 設P Q是兩個命題 顯然 如下這句話也是命題 P并且Q 稱之為P和Q的合取 日常語句中有 且 與 合取詞的例子 P 2 2 5Q 雪是白的 P Q 2 2 5并且雪是白的 P 今天刮風 Q 今天下雨 P Q 今天刮風并且今天下雨 P Q P析取Q 設P Q是兩個命題 顯然 如下這句話也是命題 P或者Q 稱之為P和Q的析取 PQP QTTTTFTFTTFFF 日常語言中有 或 析取詞的例子 P 2 2 5Q 雪是白的 P Q 2 2 5或者雪是白的 P 今天刮風 Q 今天下雨 P Q 今天刮風或者今天下雨 可兼的 或 PQP QTTTTFTFTTFFF 他會英語或法語 今天刮風或者今天下雨 不可兼的 或 PQP Q P Q P Q TTTFTFTTFTTTFFFF 人固有一死 或重于泰山 或輕于鴻毛 今天晚上我去看電影 或去看球賽 異或XOR P Q P蘊含Q 設P Q是兩個命題 顯然 如下這句話也是命題 如果P則Q 稱之為P蘊含Q 日常語言中有 如果 則 只要 就 PQP QTTTTFFFTTFFT 蘊含詞的例子 P 2 3 6Q 2 3 1 6 2P Q 如果2 3 6 則 2 3 1 6 2 P 天氣不好Q 我去接你P Q 如果天氣不好 那么我去接你 注1 前件為假時 命題為真 如果蘊含前件P是假命題 那么不管Q是什么命題 命題 如果P則Q 在邏輯中都被認為是真命題 例 如果張三能及格 那太陽從西邊升起 注2 前件 后件可以毫不相關(guān) 在日常語言中 如果 則 所聯(lián)結(jié)的句子之間表現(xiàn)的是一種因果關(guān)系 但在數(shù)理邏輯中 盡管說前件蘊涵后件 但兩個命題可以是毫不相關(guān)的 例 P 2 3 5Q 雪是黑色的P Q 如果2 3 5 則雪是黑色的 注3 充分條件 必要條件 p q為真命題的邏輯關(guān)系是 p是q的充分條件 q是p的必要條件 q是p的必要條件 的敘述方式還有 p僅當q 僅當q 則p 只有q才p只要p就q除非q 否則非p 非p 除非q 蘊含詞的例子 用 表示下列命題 1 只要天下雨 我就回家 2 只有天下雨 我才回家 3 除非天下雨 否則我不回家 4 僅當天下雨 我才回家 解設p 天下雨 q 我回家 則 1 符號化為p q 2 符號化為q p 或 p q 3 符號化為q p 或 p q 4 符號化為q p 或 p q P Q P等價于Q 設P Q是兩個命題 顯然 如下這句話也是命題 P當且僅當Q 稱之為P等價于Q PQP QTTTTFFFTFFFT 日常語言中有 當且僅當 等價詞的例子 P 2 2 4Q 雪是白色的 P Q 2 2 4當且僅當雪是白色的 P 2 2 5Q 雪是黑色的 P Q 2 2 5當且僅當雪是黑色 等價詞的例子 三角形 ABC為等腰三角形當且僅當三角形 ABC有兩條邊相等 非復合命題的例子 1 Tom和John是兄弟 2 如果x 0 則x2 0 3 如果兩個三角形全等 則它們的面積相等 4 一個三角形為等腰三角形當且僅當三角形有兩條邊相等 未指定 注4 充要條件 p q為真命題的邏輯關(guān)系是 p是q的充分條件 p是q的必要條件 中學 數(shù)學 選修2 1 四種命題 中學 數(shù)學 選修2 1 充分 必要 真值函項 定義 以真假為定義域并以真假為值域的函數(shù)稱為真值函項 需要集合與映射的知識才能夠講透 T F T F T F T T T F F T F F 一元聯(lián)結(jié)詞的真值表 一元聯(lián)結(jié)詞有一個命題變項P 它取真和假兩種 可定義四個不同的一元聯(lián)結(jié)詞f0 f1 f2 f3 或稱為真值函項 其真假關(guān)系可用下圖表示 Pf0 P f1 P f2 P f3 P TTTFFFTFTF 永真 恒等 否定 P 永假 二元聯(lián)結(jié)詞 PQf0f1f2f3f4f5f6f7f8f9f10f11f12f13f14f15TTTFTTTFFFTTTTFFFFTFTTFTTFTTFFTFTFFFFTTTTFTTFTFTFFFTFFFFTTTTFTTFTFFFFFTF f2為蘊含 f4為析取 f8為等價 f11為合取 三元聯(lián)結(jié)詞共有多少個 28 第一章命題演算基礎 1 1命題和聯(lián)結(jié)詞1 1 1命題1 1 2聯(lián)結(jié)詞1 1 3合式公式1 2真假性1 3范式及其應用 合式公式 Wellformedformulae 合式公式為如下定義的式子 簡稱為公式 任何命題變元均是公式 如果P為公式 則 P為公式 如果為P Q為公式 則P Q P Q P Q P Q為公式 當且僅當經(jīng)過有限次使用 所組成的符號串才是公式 否則不為公式 n元公式 若公式 中有n個不同的命題變元 就說 為n元公式 例一個3元公式 P Q R P Q 命題符號化 將復合命題符號化的步驟是分析出簡單命題 符號化用聯(lián)結(jié)詞聯(lián)結(jié)簡單命題 提示 根據(jù)命題的實際含義 不拘泥于原句形式地確定原子命題和選用聯(lián)結(jié)詞 例1 p5 將下列各命題符號化 只有努力學習 認真復習 才能取得好成績 解 令P表示 努力學習 Q表示 認真復習 R表示 取得好成績 則原句譯為R P Q 該語句能不能譯為 P Q R 例4 p5 已知三個命題 P 今晚我在家上網(wǎng) Q 今晚我去球場看足球比賽 R 今晚我在家上網(wǎng)或去球場看足球比賽 試問P Q和R是否表達同一命題 請用真值表說明之 R P Q P Q 不可兼或 例將下列語句形式化 并表示為命題公式 1 狗急跳墻 令p 狗急了 q 狗跳墻 則可表示為p q 例將下列語句形式化 并表示為命題公式 2 如果他不來 那么他或者是生病了 或者是不在本地 記p 他來 q 他生病 r 他在本地 則可表示為 p q r 例將下列語句形式化 并表示為命題公式 3 如果你和他不都是傻子 那么你們倆都不會去自討沒趣 令p 你是傻子 q 他是傻子 r 你會去自討沒趣 s 他會去自討沒趣 則可表示為 p q r s p q r s 第一章命題演算基礎 1 1命題和聯(lián)結(jié)詞1 1 1命題1 1 2聯(lián)結(jié)詞1 1 3合式公式1 2真假性1 3范式及其應用