離散數(shù)學(xué)北郵內(nèi)部資料.pdf

景曉軍景曉軍 1 1 Discrete Mathematics 景曉軍景曉軍 制作時間制作時間 制作時間制作時間 2012201220122012年年年年2 2 2 2月月月月 景曉軍景曉軍 2 2 景曉軍景曉軍 北京郵電大學(xué)北京郵電大學(xué)280信箱信箱 Tel 62283790 MobileE mail jxiaojun 聯(lián)系方式聯(lián)系方式 景曉軍景曉軍 3 3 課程安排 總學(xué)時總學(xué)時 3232 考核原則考核原則 以學(xué)有所得為目的以學(xué)有所得為目的 以掌握方法和思以掌握方法和思 路為要求路為要求 摒棄死記硬背摒棄死記硬背 考核方式考核方式 閉卷考試閉卷考試 教材教材 離散數(shù)學(xué)離散數(shù)學(xué) 耿素云耿素云 屈婉玲屈婉玲 張立昂張立昂 清華大學(xué)出版社清華大學(xué)出版社 離散數(shù)學(xué)離散數(shù)學(xué) 景曉軍景曉軍 孫松林孫松林 陸月明陸月明 北京郵電大學(xué)出版社北京郵電大學(xué)出版社 景曉軍景曉軍 4 4 什么是數(shù)理邏輯什么是數(shù)理邏輯 數(shù)理邏輯數(shù)理邏輯 用用數(shù)學(xué)方法數(shù)學(xué)方法來來研究推理的形式結(jié)研究推理的形式結(jié) 構(gòu)和推理規(guī)律構(gòu)和推理規(guī)律的數(shù)學(xué)科學(xué)的數(shù)學(xué)科學(xué) 數(shù)理邏輯的內(nèi)容大體為數(shù)理邏輯的內(nèi)容大體為 邏輯演算邏輯演算 證明論證明論 公理集合論公理集合論 遞歸論和模型論遞歸論和模型論 本書重點講授本書重點講授命題邏輯和一階邏輯命題邏輯和一階邏輯的邏輯的邏輯 演算演算 景曉軍景曉軍 5 5 騎士與無賴騎士與無賴 騎士騎士 說真話說真話 無賴無賴 說假話說假話 現(xiàn)有倆人現(xiàn)有倆人 問話判斷問話判斷 1 你是騎士嗎 2 你是無賴嗎 3 你們倆人中有騎士嗎 4 你們倆人中有無賴嗎 景曉軍景曉軍 6 6 邏輯判斷邏輯判斷 長官命令長官命令 理發(fā)兵給所有不自己剃胡子的人刮理發(fā)兵給所有不自己剃胡子的人刮 胡子胡子 違抗命令者關(guān)禁閉違抗命令者關(guān)禁閉 理發(fā)兵剃也不是理發(fā)兵剃也不是 不剃也不是不剃也不是 景曉軍景曉軍 7 7 第一章第一章 命題邏輯命題邏輯 1 1命題與聯(lián)結(jié)詞命題與聯(lián)結(jié)詞 1 2命題公式及其分類命題公式及其分類 1 3 等值演算等值演算 1 4聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 1 5對偶與范式對偶與范式 1 6 推理理論推理理論 景曉軍景曉軍 8 8 什么是什么是命題命題 數(shù)理邏輯數(shù)理邏輯研究的中心問題是研究的中心問題是推理推理 而推理而推理 的的前提前提和和結(jié)論結(jié)論都是表達判斷的都是表達判斷的命題命題 命題命題 能判斷真假的能判斷真假的陳述句陳述句 真值真值 命題的命題的判斷結(jié)果判斷結(jié)果 也稱為也稱為值值 真真 假假 命題命題真值真值的的兩種可能兩種可能 命題的三要素命題的三要素 1 1 是是陳述句陳述句 2 2 真值真值只能有只能有真真和和假假兩種結(jié)果兩種結(jié)果 3 3 真值真值必須必須唯一唯一 景曉軍景曉軍 9 9 判斷下面句子是否是命題判斷下面句子是否是命題 2是素數(shù)是素數(shù) 雪是黑色的雪是黑色的 2 3 5 明年十月一日是晴天明年十月一日是晴天 這朵花多好看呀這朵花多好看呀 明天下午有會嗎明天下午有會嗎 請關(guān)上門請關(guān)上門 x y 5 地球外的星球上也有人地球外的星球上也有人 我寫了錯字我寫了錯字 是是1 是是0 是是1 是是 否否 否否 否否 否否真值不唯一真值不唯一 是是 否否真值不唯一真值不唯一 整個句子有整個句子有 二義性二義性 悖論不是命題悖論不是命題 景曉軍景曉軍10 10 簡單命題與復(fù)合命題簡單命題與復(fù)合命題 簡單命題簡單命題 命題不能分成更簡單的句子的命題命題不能分成更簡單的句子的命題 又稱為又稱為 命題常項命題常項 2是素數(shù)是素數(shù) 雪是黑色的雪是黑色的 2 3 5 明年十月一日是晴天明年十月一日是晴天 復(fù)合命題復(fù)合命題 由簡單命題用聯(lián)結(jié)詞聯(lián)結(jié)而成的命題由簡單命題用聯(lián)結(jié)詞聯(lián)結(jié)而成的命題 3不是偶數(shù)不是偶數(shù) 2是素數(shù)和偶數(shù)是素數(shù)和偶數(shù) 林芳學(xué)過英語或日語林芳學(xué)過英語或日語 如果角如果角A和角和角B是對頂角是對頂角 則角則角A等于角等于角B 景曉軍景曉軍11 11 命題變項命題變項 命題變元命題變元 命題變項命題變項 命題變元命題變元 真值可以變真值可以變 化的陳述句化的陳述句 如如 x yx y 5 5 命題變項命題變項不是命題不是命題 命題常項命題常項 命題常元命題常元 真值唯一確真值唯一確 定的陳述句定的陳述句 如如 2 2是偶數(shù)是偶數(shù) 命題常項命題常項是命題是命題 景曉軍景曉軍12 12 簡單命題簡單命題 命題變項的符號化命題變項的符號化 簡單命題符號化簡單命題符號化 p 2是素數(shù)是素數(shù) 命題常項命題常項 q 雪是白的雪是白的 命題常項命題常項 命題變項命題變項符號化符號化 P x y 5 命題變項命題變項 不是命題不是命題 命題的真值表示命題的真值表示 1 T 表示真表示真 0 F 表示假表示假 景曉軍景曉軍13 13 基本聯(lián)結(jié)詞基本聯(lián)結(jié)詞 否定否定聯(lián)結(jié)詞聯(lián)結(jié)詞 合取合取聯(lián)結(jié)詞聯(lián)結(jié)詞 析取析取聯(lián)結(jié)詞聯(lián)結(jié)詞 蘊涵蘊涵聯(lián)結(jié)詞聯(lián)結(jié)詞 等價等價聯(lián)結(jié)詞聯(lián)結(jié)詞 景曉軍景曉軍14 14 否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞 設(shè)設(shè)p p為任一命題為任一命題 復(fù)合命題復(fù)合命題 非非p p 或或 p p的否定的否定 稱作稱作p p的的否定式否定式 記作記作 P P 為為否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞 p p為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p p為假為假 p p 3 3是偶數(shù)是偶數(shù) p p 3 3不是偶數(shù)不是偶數(shù) 景曉軍景曉軍15 15 合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞 設(shè)設(shè)p p q q為兩個命題為兩個命題 復(fù)合命題復(fù)合命題 p p并且并且q q 或或 p p 和和q q 稱作稱作p p與與q q的的合取式合取式 記作記作p q 為為合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞 p q為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p p與與q q同同 時為真時為真 合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞是是邏輯邏輯 與與 的意思的意思 李平既聰明李平既聰明 p 又用功又用功 q p q 李平雖然聰明李平雖然聰明 但不用功但不用功 p q 李平不但聰明李平不但聰明 p 而且用功而且用功 q p q 李平不是不聰明李平不是不聰明 p 而是不用功而是不用功 q p q 不是所有的不是所有的 和和 與與 都可用都可用 表示表示 李文和李武是兄弟李文和李武是兄弟 p 景曉軍景曉軍16 16 析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞 設(shè)設(shè)p q為兩個命題為兩個命題 復(fù)合命題復(fù)合命題 p或或q 稱稱 作作p與與q的的析取式析取式 記作記作p q 為為 析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞 p q為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p與與 q中至少一個為真中至少一個為真 析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞是是邏輯邏輯 或或 的意思的意思 王燕學(xué)過英語王燕學(xué)過英語 p 或法語或法語 q p q 或或 具有具有 相容性相容性 和和 相斥性相斥性 兩重意兩重意 義義 派小王或小李中的一人去開會派小王或小李中的一人去開會 p q p q 景曉軍景曉軍17 17 蘊涵聯(lián)結(jié)詞蘊涵聯(lián)結(jié)詞 設(shè)設(shè)p p q q為兩個命題為兩個命題 復(fù)合命題復(fù)合命題 如果如果p p 則則q q 稱作稱作p p與與q q的的蘊涵式蘊涵式 記作記作p q p p為蘊涵為蘊涵 式的式的前件前件 q q為蘊涵式的為蘊涵式的后件后件 為為蘊涵蘊涵 聯(lián)結(jié)詞聯(lián)結(jié)詞 p q為假當(dāng)且僅當(dāng)為假當(dāng)且僅當(dāng)p p為真為真q q為假為假 p p是是q q的充分條件的充分條件 q q是是p p的必要條件的必要條件 只要不下雨只要不下雨 我就騎自行車上班我就騎自行車上班 p q 只有不下雨只有不下雨 我才騎自行車上班我才騎自行車上班 q p 若若2 2 4 2 2 4 則太陽就從東方升起則太陽就從東方升起 p q 景曉軍景曉軍18 18 等價聯(lián)結(jié)詞等價聯(lián)結(jié)詞 設(shè)設(shè)p p q q為兩個命題為兩個命題 復(fù)合命題復(fù)合命題 p p當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)q q 稱作稱作 p p與與q q的的等價式等價式 記作記作p q 為為等價聯(lián)結(jié)詞等價聯(lián)結(jié)詞 p q為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p p與與q q真值相同真值相同 P P當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)q q 2 2 42 2 4當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)3 3是奇數(shù)是奇數(shù) p p q q 2 2 42 2 4當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)3 3不是奇數(shù)不是奇數(shù) p p q q 2 22 2 4 4當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)3 3是奇數(shù)是奇數(shù) p p q q 景曉軍景曉軍19 19 習(xí)題習(xí)題 小王是游泳冠軍或百米賽跑冠軍小王是游泳冠軍或百米賽跑冠軍 p q 小王現(xiàn)在在宿舍或在圖書館小王現(xiàn)在在宿舍或在圖書館 p q p q 選小王或小李中的一人當(dāng)班長選小王或小李中的一人當(dāng)班長 p q p q 如果我上街如果我上街 我就去書店看看我就去書店看看 除非我很累除非我很累 r p q r p q 王一樂是計算機系的學(xué)生王一樂是計算機系的學(xué)生 他生于他生于68年或年或69年年 他是三好學(xué)生他是三好學(xué)生 p q r q r s 景曉軍景曉軍20 20 聯(lián)結(jié)詞運算規(guī)則聯(lián)結(jié)詞運算規(guī)則 我們所學(xué)的我們所學(xué)的5 5種基本聯(lián)結(jié)詞種基本聯(lián)結(jié)詞也稱為也稱為邏輯邏輯 運算符運算符 其其運算順序運算順序為為 如果出現(xiàn)的如果出現(xiàn)的基本聯(lián)結(jié)詞基本聯(lián)結(jié)詞相同相同 又又無括號無括號 時時 則按則按從左到右從左到右的的運算順序運算順序 如果遇有如果遇有括號括號時時 不管出現(xiàn)的不管出現(xiàn)的基本聯(lián)結(jié)基本聯(lián)結(jié) 詞詞如何如何 都先進行都先進行括號中括號中的的運算運算 景曉軍景曉軍21 21 1 命題符號化及聯(lián)結(jié)詞命題符號化及聯(lián)結(jié)詞 2 命題公式及分類命題公式及分類 3 等值演算等值演算 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 5 對偶與范式對偶與范式 6 推理理論推理理論 第一章第一章 命題邏輯命題邏輯 景曉軍景曉軍22 22 什么是命題公式或公式什么是命題公式或公式 命題公式命題公式是由命題常項是由命題常項 命題變項命題變項 聯(lián)結(jié)詞聯(lián)結(jié)詞 括號等組括號等組 成的符號串成的符號串 遞歸定義遞歸定義 1 單個命題常項或變項單個命題常項或變項p q r pi qi ri 0 1是是合式公式合式公式 2 如果如果 是合式公式是合式公式 則則 是是合式公式合式公式 3 如果如果 B是合式公式是合式公式 則則 A B A B A B A B 是是 合式公式合式公式 4 4 只有有限次地應(yīng)用只有有限次地應(yīng)用 1 1 3 3 組成的符號串才是組成的符號串才是合式公式合式公式 合式公式合式公式稱為稱為命題公式命題公式 簡稱簡稱公式公式 p q r p q r p q r p q r p q r p q r 景曉軍景曉軍23 23 命題公式的層次定義命題公式的層次定義 若若A是單個命題是單個命題 常項或變項常項或變項 p q r pi qi ri 0 1 則稱則稱A為為 0層公式層公式 稱稱A是是n 1 n 0 層公式是指層公式是指A符合下列情況之一符合下列情況之一 A 7B B是是n層公式層公式 A B C 其中其中B C分別為分別為i層公式和層公式和j層公式層公式 且且n max i j A B C 其中其中B C分別為分別為i層公式和層公式和j層公式層公式 且且n max i j A B C 其中其中B C分別為分別為i層公式和層公式和j層公式層公式 且且n max i j A B C 其中其中B C分別為分別為i層公式和層公式和j層公式層公式 且且n max i j 若若 的最高層次為的最高層次為 則稱則稱 是是K層公式層公式 7p q 2 p q r 2 7 7p q r s 7 7p q r s 3 4 景曉軍景曉軍24 24 成真賦值成真賦值 成假賦值成假賦值 設(shè)設(shè)A為一命題公式為一命題公式 p1 p2 pn為出現(xiàn)在為出現(xiàn)在 中中 的所有的的所有的命題變項命題變項 給給p1 p2 pn指定一組指定一組 真值真值 稱為對稱為對 的一個的一個賦值賦值 若指定的這若指定的這 一組真值使一組真值使A的值為真的值為真 則稱這組值為則稱這組值為A的的 成真賦值成真賦值 若使若使A的值為假的值為假 則稱這組值則稱這組值 為為A的的成假賦值成假賦值 A p q r 1 1 0 A 0 成假賦值成假賦值 1 1 1 0 1 1 0 1 0 A 1 成真賦值成真賦值 景曉軍景曉軍25 25 真值表真值表 含含n n 1 個個命題變項命題變項的命題公式的命題公式 共有共有2n組賦值組賦值 將命題將命題 公式公式A在在所有的賦值之下取值所有的賦值之下取值的情況列成表的情況列成表 稱為稱為A的的真真 值表值表 1101 1 1 1111 1 0 0001 0 1 1111 0 0 0100 1 1 0110 1 0 0000 0 1 0110 0 0 p q r q r r p qr 0 1 2 3 4 5 6 7 如計算如計算p p q q r r 的的真值表真值表 景曉軍景曉軍26 26 真值表真值表 判斷命題公式類型法判斷命題公式類型法 p q r 有有成真賦值成真賦值 也有也有成假賦值成假賦值 P7 表表1 1 p p q q 全是全是成真賦值成真賦值 P7 表表1 2 p q q 全是全是成假賦值成假賦值 P7 表表1 3 重言式重言式 A在它的在它的各種賦值各種賦值下下取值取值均為均為真真 矛盾式矛盾式 A在它的在它的各種賦值各種賦值下下取值取值均為均為假假 可滿足式可滿足式 A至少有至少有一組一組賦值賦值是是成真賦值成真賦值 重言式重言式一定是一定是可滿足式可滿足式 但但可滿足式可滿足式未必是未必是重重言式言式 充分條件充分條件 Sufficient condition 必要條件必要條件 Necessary condition 景曉軍景曉軍27 27 1 命題符號化及聯(lián)結(jié)詞命題符號化及聯(lián)結(jié)詞 2 命題公式及分類命題公式及分類 3 等值演算等值演算 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 5 對偶與范式對偶與范式 6 推理理論推理理論 第一章第一章 命題邏輯命題邏輯 景曉軍景曉軍28 28 等值演算等值演算 設(shè)設(shè)A B是兩個命題是兩個命題 若等價式若等價式A B是是重言式重言式 則則A與與B是是等值等值的的 記為記為AB 注意和注意和 的關(guān)系的關(guān)系 A B是重言式是重言式 說明只出現(xiàn)說明只出現(xiàn)A與與B 的值的值 同時為真同時為真或或同時為假同時為假的的兩種情況兩種情況 所所 以肯定以肯定A B 注意和注意和 的關(guān)系的關(guān)系 如如A B 則則A B必是重言式必是重言式 若若A B 未必未必A B 因為因為A B有有4種情況種情況 景曉軍景曉軍29 29 判斷下列命題公式是否判斷下列命題公式是否等值等值 7 pvq 與與 7pV7q 7 pvq 與與 7p 7q 景曉軍景曉軍30 30 真值表法真值表法 1 001001 1 101101 0 101010 1 110110 0 7pv7q7 pvq pvq7q7pp q 7 pvq 與與 7pV7q 不等值不等值 景曉軍景曉軍31 31 真值表法真值表法 2 001001 1 001101 0 001010 1 110110 0 7p 7q7 pvq pvq7q7pp q 7 pvq 與與 7p 7q 等值等值 景曉軍景曉軍32 32 判斷類別法判斷類別法 等值式等值式 1 分配律分配律 一樣一樣 A BVC A B V A C 9 分配律分配律 互換互換 AV B C AVB AVC 8 結(jié)合律結(jié)合律 A B C A B C 7 結(jié)合律結(jié)合律 AVB VC AV BVC 6 交換律交換律A B B A5 交換律交換律AVB BVA4 等冪律等冪律A A A3 等冪律等冪律A AVA2 雙重否定雙重否定A 77A1 定律定律等值式等值式序號序號 不要死記不要死記 理解記憶理解記憶 景曉軍景曉軍33 33 判斷類別法判斷類別法 等值式等值式 2 德德 摩根律摩根律7 AVB 7A 7B10 德德 摩根律摩根律7 A B 7AV7B11 吸收律吸收律AV A B A12 吸收律吸收律A AVB A13 零律零律A V1 114 零律零律A 0 015 同一律同一律AV0 A16 同一律同一律A 1 A17 排中律排中律AV7A 118 矛盾律矛盾律A 7A 019 定律定律等值式等值式序號序號 景曉軍景曉軍34 34 判斷類別法判斷類別法 等值式等值式 3 輸出律輸出律A B C A B C24 蘊涵等式蘊涵等式 真值表真值表 A B 7AVB20 等價等值等價等值A(chǔ) B A B B A 21 假言易位假言易位 逆否命題逆否命題 A B 7B 7A22 等價否定等值等價否定等值A(chǔ)B 7A7B23 歸繆論歸繆論 A B A 7B 7A25 刁難人刁難人 定律定律等值式等值式序號序號 景曉軍景曉軍35 35 等值演算等值演算 判斷命題公式類型法判斷命題公式類型法 置換定理置換定理 設(shè)設(shè) A 是含命題公式是含命題公式A的命題公式的命題公式 B 是命題公式是命題公式B置換了置換了 A 中中A之后得到的命題公式之后得到的命題公式 如如 果果A B 則則 A B 例如例如 P 7 q r P 7qV7r 注意注意 A B A B 反之不然反之不然 設(shè)設(shè) A A B B B B 1 如果如果A B 有有 A B B 則則 A B 但當(dāng)?shù)?dāng) A B 1時時 A 0 能使能使 A 1 B 1 也能使也能使 B 1 顯然此時顯然此時A B不等值不等值 根據(jù)上述等值式根據(jù)上述等值式 不用真值表不用真值表法就可以推出更多的等法就可以推出更多的等 值式值式 這個過程為這個過程為等值演算等值演算 景曉軍景曉軍36 36 習(xí)題習(xí)題 驗證下列等式驗證下列等式 p q r p q r P10例例1 9 1 p q r p q r p q r p q r p q r p q r p q r q p r q p r q p r q p r q p r q p r 景曉軍景曉軍37 37 習(xí)題習(xí)題 驗證下列等式驗證下列等式 p p q p q P10例例1 9 2 p p 1 p q q p q p q 講解講解P11 例例11 p A q B r C s D 景曉軍景曉軍38 38 1 命題符號化及聯(lián)結(jié)詞命題符號化及聯(lián)結(jié)詞 2 命題公式及分類命題公式及分類 3 等值演算等值演算 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 5 對偶與范式對偶與范式 6 推理理論推理理論 第一章第一章 命題邏輯命題邏輯 景曉軍景曉軍39 39 聯(lián)結(jié)詞的擴展聯(lián)結(jié)詞的擴展 異或異或聯(lián)結(jié)詞聯(lián)結(jié)詞 與非與非聯(lián)結(jié)詞聯(lián)結(jié)詞 或非或非聯(lián)結(jié)詞聯(lián)結(jié)詞 景曉軍景曉軍40 40 異或聯(lián)結(jié)詞異或聯(lián)結(jié)詞 設(shè)設(shè)p q為兩個命題為兩個命題 復(fù)合命題復(fù)合命題 p q中中恰有恰有 一個成立一個成立 稱為稱為p與與q的的排斥或排斥或或或異或異或記作記作 p q 稱作稱作排斥或排斥或或或異或異或聯(lián)結(jié)詞聯(lián)結(jié)詞 p q為為真真當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)p q中中恰有一個為真恰有一個為真 0 1 If and only if 景曉軍景曉軍41 41 與非聯(lián)結(jié)詞與非聯(lián)結(jié)詞 設(shè)設(shè)p q兩個命題兩個命題 復(fù)合命題復(fù)合命題 p與與q的否的否 定定 稱為稱為p與與q的的與非式與非式 記作記作p q 稱作稱作與非與非聯(lián)結(jié)詞聯(lián)結(jié)詞 p q為為真真當(dāng)且當(dāng)且 僅當(dāng)僅當(dāng)p q不同時為真不同時為真 p q 7 p q p q p q 0 p q p q 1 景曉軍景曉軍42 42 或非聯(lián)結(jié)詞或非聯(lián)結(jié)詞 設(shè)設(shè)p q兩個命題兩個命題 復(fù)合命題復(fù)合命題 p或或q的否定的否定 稱稱 為為p與與q的的或非式或非式 記作記作p q 稱作稱作或非或非 聯(lián)結(jié)詞聯(lián)結(jié)詞 p q為為真真當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)p q同時為假同時為假 p q 7 p V q p q p V q 0 p q p V q 1 景曉軍景曉軍43 43 n元真值函數(shù)元真值函數(shù) 一個一個n n 1 維卡氏積維卡氏積 0 1 n到到 0 1 的函數(shù)稱為一的函數(shù)稱為一 個個n元元真值函數(shù)真值函數(shù) 設(shè)設(shè)F是一個是一個n元真值函數(shù)元真值函數(shù) 則可記為則可記為 F 0 1 n 0 1 0 1 x x x 1 0 n個命題變項個命題變項 共有共有2n個可能的賦值個可能的賦值 橫行橫行 有有 個不同的真值函數(shù)個不同的真值函數(shù) 豎列豎列 其中其中 一個真值一個真值 函數(shù)函數(shù)對應(yīng)著對應(yīng)著一個真值相同的命題公式一個真值相同的命題公式 而這個命題而這個命題 公式又和許多命題公式彼此間是等值的公式又和許多命題公式彼此間是等值的 即即 n個命個命 題變項題變項 必有且僅有必有且僅有個不同真值的命題公式個不同真值的命題公式 其其 余的命題公式必然與這余的命題公式必然與這個命題公式中的一個是等個命題公式中的一個是等 值的值的 n 2 2 n 2 2 n 2 2 景曉軍景曉軍44 44 兩個變元的真值函數(shù)兩個變元的真值函數(shù) 101010101 1 110011001 0 111100000 1 111111110 0 F16F15F14F13F12F11F10F9p q 101010101 1 110011001 0 111100000 1 000000000 0 F8F7F6F5F4F3F2F1p q0 1 景曉軍景曉軍45 45 由真值函數(shù)寫出對應(yīng)的命題公式由真值函數(shù)寫出對應(yīng)的命題公式 n個命題變元個命題變元 個個真值函數(shù)真值函數(shù) 出現(xiàn)出現(xiàn)k個個 1 的真值函數(shù)為的真值函數(shù)為個個 n 2 2 2 1 n k n C nk 現(xiàn)有現(xiàn)有p q 2個命題變元個命題變元 則則 0個個 1 的公式的公式1個個 1個個 1 的公式的公式4個個 2個個 1 的公式的公式6個個 3個個 1 的公式的公式4個個 4個個 1 的公式的公式1個個 0 p q p q 7 p q 7 p q p q 7p 7q p q 7 p q p q p q p q p q 1p 7p 景曉軍景曉軍46 46 冗余聯(lián)結(jié)詞冗余聯(lián)結(jié)詞 獨立聯(lián)結(jié)詞獨立聯(lián)結(jié)詞 在一個聯(lián)結(jié)詞的集合中在一個聯(lián)結(jié)詞的集合中 如果一個聯(lián)結(jié)詞可由集如果一個聯(lián)結(jié)詞可由集 合中的其他聯(lián)結(jié)詞表示合中的其他聯(lián)結(jié)詞表示 則稱此聯(lián)接詞為則稱此聯(lián)接詞為冗余聯(lián)冗余聯(lián) 結(jié)詞結(jié)詞 否則稱為否則稱為獨立聯(lián)結(jié)詞獨立聯(lián)結(jié)詞 現(xiàn)給定聯(lián)結(jié)詞現(xiàn)給定聯(lián)結(jié)詞 7 v p q 7pvq 7 p 7q p q p q q p 7pvq 7qvp 7 p 7q 7 q 7p pvq 77 pvq 7 7p 7q 所以所以 v 為為冗余聯(lián)結(jié)詞冗余聯(lián)結(jié)詞 7 為為獨立聯(lián)結(jié)詞獨立聯(lián)結(jié)詞 景曉軍景曉軍47 47 全功能集全功能集 極小功能集極小功能集 若任一真值函數(shù)都可以用含某一聯(lián)結(jié)詞集中的聯(lián)若任一真值函數(shù)都可以用含某一聯(lián)結(jié)詞集中的聯(lián) 結(jié)詞的命題公式表示結(jié)詞的命題公式表示 則稱該聯(lián)結(jié)詞集為則稱該聯(lián)結(jié)詞集為全功能全功能 集集 若一聯(lián)結(jié)詞的全功能集中不含冗余的聯(lián)結(jié)若一聯(lián)結(jié)詞的全功能集中不含冗余的聯(lián)結(jié) 詞詞 則稱它為則稱它為極小全功能集極小全功能集 7 v 7 v 7 v 7 V 7 為為全功能集全功能集 7 V 7 為為極小全功能集極小全功能集 景曉軍景曉軍48 48 用用 表示下列命題公式表示下列命題公式 極小功能集例題極小功能集例題 1 p q p q p q p p q q p p q q 2 p q p q p q p q p q 3 p q p q p p q A q A q q A q q p p q q p p q q p p A 景曉軍景曉軍49 49 第一章第一章 命題邏輯命題邏輯 1 命題符號化及聯(lián)結(jié)詞命題符號化及聯(lián)結(jié)詞 2 命題公式及分類命題公式及分類 3 等值演算等值演算 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 5 對偶與范式對偶與范式 6 推理理論推理理論 景曉軍景曉軍50 50 對偶式對偶式 在含有聯(lián)結(jié)詞在含有聯(lián)結(jié)詞7 V的命題公式的命題公式A中中 將將V換換 成成 換成換成V 若若A中含中含0或或1 將將0換成換成1 1 換成換成0 所得到命題公式稱為所得到命題公式稱為A的的對偶式對偶式 記作記作A p q 與與 pvq是對偶式是對偶式 7 p q 與與 7 pvq 是對偶式是對偶式 景曉軍景曉軍51 51 性質(zhì)性質(zhì)1 設(shè)設(shè)A和和A 互為對偶式互為對偶式 p1 p2 pn是出現(xiàn)在是出現(xiàn)在A和和A 中的全部的命題變項中的全部的命題變項 若將若將A和和A 寫成寫成n元函數(shù)形元函數(shù)形 式式 則則 1 7A p1 p2 pn A 7p1 7 p2 7pn 2 7A p1 p2 pn A 7p1 7 p2 7pn 例如例如 A p q r p 7qvr 7A p q r 7 p 7qVr 7pV q 7r A p q r pv 7q r A 7p 7q 7r 7pv q 7r 7A p q r 7 pv 7q r 7p qV7r A 7p 7q 7r 7p qv7r 就是就是德德 摩摩 根律根律 景曉軍景曉軍52 52 性質(zhì)性質(zhì)2 對偶原理對偶原理 設(shè)設(shè)A B為兩命題公式為兩命題公式 若若A B 則則A B 其中其中 A B 分別為分別為A B的對偶式的對偶式 例如例如 p q V 7pV 7pVq 7pVq p q V 7pV 7pVq p q v 7pvq pv 7pvq qv 7pvq 1 7pvq 7pVq 對偶式對偶式 pvq 7p 7p q 7p q pvq 7p 7p q pvq 7p q p 7p q v q 7p q 0v 7p q 7p q 景曉軍景曉軍53 53 簡單析取式簡單析取式 簡單合取式簡單合取式 僅有限個命題變項或其否定構(gòu)成的析取式僅有限個命題變項或其否定構(gòu)成的析取式 稱為稱為簡單析取式簡單析取式 僅有限個命題變項或其否僅有限個命題變項或其否 定構(gòu)成的合取式稱為定構(gòu)成的合取式稱為簡單合取式簡單合取式 簡單析取式簡單析取式 pvq 7pvq 7pv7q 簡單合取式簡單合取式 p q 7p q 7p 7q 一個簡單析取式為一個簡單析取式為重言式重言式 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)同時含有同時含有 一個命題變項及其否定一個命題變項及其否定 一個簡單合取式為一個簡單合取式為矛盾式矛盾式 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)同時含有同時含有 一個命題變項及其否定一個命題變項及其否定 景曉軍景曉軍54 54 析取范式析取范式 合取范式合取范式 僅由僅由有限個簡單合取式有限個簡單合取式構(gòu)成的構(gòu)成的析取式析取式稱為稱為析取范析取范 式式 A A1VA2VA3 一個析取范式一個析取范式為為矛盾式矛盾式 當(dāng)且僅當(dāng)含有的當(dāng)且僅當(dāng)含有的每個簡單合每個簡單合 取式為假取式為假 僅由僅由有限個簡單析取式有限個簡單析取式構(gòu)成的構(gòu)成的合取式合取式稱為稱為合取范合取范 式式 A A1 A2 A3 一個合取范式一個合取范式為為重言式重言式 當(dāng)且僅當(dāng)含有的當(dāng)且僅當(dāng)含有的每個簡單析每個簡單析 取式為真取式為真 景曉軍景曉軍55 55 范式存在定理范式存在定理 任一命題公式都存在與之等值的任一命題公式都存在與之等值的析取范式析取范式 與與合取范式合取范式 但不唯一但不唯一 如如 7pvp 7qvq 由于由于 7 V 是全功能集是全功能集 因而可以用這因而可以用這 些聯(lián)結(jié)詞來代替些聯(lián)結(jié)詞來代替 V 目的是 變成合取或析取范式 p q 7pvq p q 7pvq pv7q 景曉軍景曉軍56 56 極小項極小項 在含有在含有n個命題的簡單合取式中個命題的簡單合取式中 若若每個命題變項與其否定每個命題變項與其否定 不同時存在不同時存在 而而兩者之一必出現(xiàn)且僅出現(xiàn)一次兩者之一必出現(xiàn)且僅出現(xiàn)一次 且且第第i個命題個命題 變項或其否定出現(xiàn)在從左起的第變項或其否定出現(xiàn)在從左起的第i位上位上 若命題變項無角標(biāo)若命題變項無角標(biāo) 則按字典順序排序則按字典順序排序 這樣的這樣的簡單合取式簡單合取式稱為稱為極小項極小項 3要素要素 7p 7q 7r 000 0記為記為m0 7p 7q r 001 1記為記為m1 7p q 7r 010 2記為記為m2 7p q r 011 3記為記為m3 p 7q 7r 100 4記為記為m4 p 7q r 101 5記為記為m5 p q 7r 110 6記為記為m6 p q r 111 7記為記為m7 取取p q rp q r本身為本身為 1 1 否定為否定為0 0 景曉軍景曉軍57 57 主析取范式主析取范式 判斷命題公式類型法判斷命題公式類型法 設(shè)命題公式設(shè)命題公式A中含有中含有n個命題變項個命題變項 如果如果A的的析取析取 范式范式中的中的簡單合取式簡單合取式全是極小項全是極小項 則則A稱稱為為主析取主析取 范式范式 任何命題公式的任何命題公式的主析取范式主析取范式是是存在的存在的 且唯一且唯一 求解步驟求解步驟 求求A的析取范式的析取范式 對命題中不含某個變項的采用對命題中不含某個變項的采用 B B 1 B p V B 7p 消去消去 重復(fù)出現(xiàn)的命題變項重復(fù)出現(xiàn)的命題變項 矛盾式及極小矛盾式及極小 項項 景曉軍景曉軍58 58 命題公式命題公式A中含有中含有n個命題變項個命題變項 如果如果A是重言是重言 式式 永真式永真式 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A的主析取范式中的主析取范式中 含全部的含全部的2n個極小項個極小項 命題公式命題公式A中含有中含有n個命題變項個命題變項 如果如果A是矛盾是矛盾 式式 永假式永假式 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A的主析取范式中的主析取范式中 不含任何極小項不含任何極小項 命題公式命題公式A中含有中含有n個命題變項個命題變項 如果如果A是可滿是可滿 足式足式 協(xié)調(diào)式協(xié)調(diào)式 則則A的主析取范式中的主析取范式中至少至少 含一個極小項含一個極小項 主析取范式主析取范式 判斷命題公式類型法判斷命題公式類型法 景曉軍景曉軍59 59 例題例題 求求 pvq r p的主析取范式的主析取范式 pvq r p 7 pVq r vp 7 7 pvq vr vp pvq 7r vp p 7r v q 7r vp p q 7r v p 7q 7r V p q 7r v 7p q 7r v p q r v p 7q r v p q 7r v p 7q 7r p q 7r v p 7q 7r v 7p q 7r v p q r v p 7q r m6v m4v m2v m7v m5 2 4 5 6 7 景曉軍景曉軍60 60 例題例題 A pvq r p 2 4 5 6 7 p q r A 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 B 7p 7q 7r V 7p q 7r V 7p q r V p 7q r V p q 7r 0 2 3 5 6 0 0 1 0 1 1 1 1 B 1 0 1 1 0 1 1 0 景曉軍景曉軍61 61 極大項極大項 在含有在含有n個命題的簡單析取式中個命題的簡單析取式中 若若每個命題變項與其否定每個命題變項與其否定 不同時存在不同時存在 而而兩者之一必出現(xiàn)且僅出現(xiàn)一次兩者之一必出現(xiàn)且僅出現(xiàn)一次 且且第第i個命題個命題 變項或其否定出現(xiàn)在從左起的第變項或其否定出現(xiàn)在從左起的第i 位上位上 若命題變項無角標(biāo)若命題變項無角標(biāo) 按字典順序排序按字典順序排序 這樣的這樣的簡單析取式簡單析取式稱為稱為極大項極大項 3要素要素 pVqVr 000 0記為記為M0 pVqV7r 001 1記為記為M1 pV7qVr 010 2記為記為M2 pV7qV7r 011 3記為記為M3 7pVqVr 100 4記為記為M4 7pVqV7r 101 5記為記為M5 7pV7qVr 110 6記為記為M6 7pV7qV7r 111 7記為記為M7 取取p q rp q r本身為本身為 0 0 否定為否定為1 1 景曉軍景曉軍62 62 主合取范式主合取范式 判斷命題公式類型法判斷命題公式類型法 設(shè)命題公式設(shè)命題公式A中含有中含有n個命題變項個命題變項 如果如果A的的合取合取 范式范式中的中的簡單析取式簡單析取式全是極大項全是極大項 則則A稱稱為為主合取主合取 范式范式 任何命題公式的任何命題公式的主合取范式主合取范式是是存在的存在的 且唯一且唯一 求解方式求解方式 求求A的合取范式的合取范式 對命題中不含某個變項的采用對命題中不含某個變項的采用 B BV0 BVp BV7p 消去消去 重復(fù)出現(xiàn)的命題變項重復(fù)出現(xiàn)的命題變項 重言式及極大重言式及極大 項項 景曉軍景曉軍63 63 命題公式命題公式A中含有中含有n個命題變項個命題變項 如果如果A是重言是重言 式式 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A的的主合取范式主合取范式中中不含任何極大不含任何極大 項項 命題公式命題公式A中含有中含有n個命題變項個命題變項 如果如果A是矛盾是矛盾 式式 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A的的主合取范式主合取范式中中含全部的含全部的2n個個 極大項極大項 命題公式命題公式A中含有中含有n個命題變項個命題變項 如果如果A是可滿是可滿 足式足式 協(xié)調(diào)式協(xié)調(diào)式 則則A的的主合析取范式主合析取范式中中至少至少 含一個極大項含一個極大項 主合取范式主合取范式 判斷命題公式類型法判斷命題公式類型法 景曉軍景曉軍64 64 例題例題 求求 p q vr的主合取范式的主合取范式 p q vr pvr qvr pvqvr pv7qvr pvqvr 7pvqvr pvqvr pv7qvr 7pvqvr M0 M2 M4 0 2 4 景曉軍景曉軍65 65 例題例題 A p q vr 0 2 4 p q r A 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 B pVqV7r 1 4 7 0 1 0 1 0 1 1 1 B 1 0 1 1 0 1 1 0 7pVqVr 7pV7qV7r 7p 7q 7r V 7p q 7r V 7p q r V p 7q r V p q 7r 0 2 3 5 6 1 3 5 6 7 因真值表的寫法是一樣的因真值表的寫法是一樣的 所以所以 同一個真值函數(shù)同一個真值函數(shù) 對對 應(yīng)唯一的一個主析取范式應(yīng)唯一的一個主析取范式 且對應(yīng)唯一的主合取范式且對應(yīng)唯一的主合取范式 即即 一個主析取范式唯一一個主析取范式唯一 的對應(yīng)一個主合取范式的對應(yīng)一個主合取范式 景曉軍景曉軍66 66 主析取范式與主合取范式的關(guān)系主析取范式與主合取范式的關(guān)系 存在存在7mi Mi關(guān)系關(guān)系 單個單個 所以所以 A m0Vm1Vm5Vm7 0 1 5 7 7M0V7M1V7M5V7M7 7 M0 M1 M5 M7 M2 M3 M4 M6 2 3 4 6 7 A E A E是全集是全集 景曉軍景曉軍67 67 第一章第一章 命題邏輯命題邏輯 1 命題符號化及聯(lián)結(jié)詞命題符號化及聯(lián)結(jié)詞 2 命題公式及分類命題公式及分類 3 等值演算等值演算 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 5 對偶與范式對偶與范式 6 推理理論推理理論 景曉軍景曉軍68 68 什么是推理什么是推理 推理推理是從前提推出結(jié)論的思是從前提推出結(jié)論的思 維過程維過程 前提前提是已知的命題公是已知的命題公 式式 結(jié)論結(jié)論是從前提出發(fā)是從前提出發(fā) 應(yīng)用推應(yīng)用推 理規(guī)則推出的命題公式理規(guī)則推出的命題公式 景曉軍景曉軍69 69 邏輯結(jié)論邏輯結(jié)論 若若 A1 A2 AK B為重言式為重言式 則則 稱稱A1 A2 AK推結(jié)論推結(jié)論B的的推理正推理正 確確 B是是A1 A2 AK的的邏輯結(jié)論邏輯結(jié)論或或 有效結(jié)論有效結(jié)論 稱稱 A1 A2 AK B為為 由前提由前提A1 A2 AK推結(jié)論推結(jié)論B的推的推 理的形式結(jié)構(gòu)理的形式結(jié)構(gòu) 景曉軍景曉軍70 70 同用 AB 表示 A B 是重言式類似 用 A B 表示 A B 是重言式 因而 若由 前提 A1 A2 AK 推結(jié)論 B 的推理 正確 也記為 A1 A2 AK B 判斷推理是否正確的方法就是重言蘊涵式的 方法 我們已學(xué)過三種方法 1 1 真值表法真值表法 2 2 等值演算等值演算 3 3 主析取范式主析取范式 下面介紹第四種方法下面介紹第四種方法 構(gòu)造證明法構(gòu)造證明法 構(gòu)造證明法構(gòu)造證明法 判斷命題公式類型法判斷命題公式類型法 景曉軍景曉軍71 71 例題例題 1 判斷下面各推理是否正確判斷下面各推理是否正確 如果天氣涼快如果天氣涼快 小王就不去游泳小王就不去游泳 天氣涼快天氣涼快 所以小王