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

景曉軍景曉軍 1 1 Discrete Mathematics 景曉軍景曉軍 制作時(shí)間制作時(shí)間 制作時(shí)間制作時(shí)間 2012201220122012年年年年2 2 2 2月月月月 景曉軍景曉軍 2 2 景曉軍景曉軍 北京郵電大學(xué)北京郵電大學(xué)280信箱信箱 Tel 62283790 MobileE mail jxiaojun 聯(lián)系方式聯(lián)系方式 景曉軍景曉軍 3 3 課程安排 總學(xué)時(shí)總學(xué)時(shí) 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é)方法來(lái)來(lái)研究推理的形式結(jié)研究推理的形式結(jié) 構(gòu)和推理規(guī)律構(gòu)和推理規(guī)律的數(shù)學(xué)科學(xué)的數(shù)學(xué)科學(xué) 數(shù)理邏輯的內(nèi)容大體為數(shù)理邏輯的內(nèi)容大體為 邏輯演算邏輯演算 證明論證明論 公理集合論公理集合論 遞歸論和模型論遞歸論和模型論 本書重點(diǎn)講授本書重點(diǎn)講授命題邏輯和一階邏輯命題邏輯和一階邏輯的邏輯的邏輯 演算演算 景曉軍景曉軍 5 5 騎士與無(wú)賴騎士與無(wú)賴 騎士騎士 說(shuō)真話說(shuō)真話 無(wú)賴無(wú)賴 說(shuō)假話說(shuō)假話 現(xiàn)有倆人現(xiàn)有倆人 問(wèn)話判斷問(wèn)話判斷 1 你是騎士嗎 2 你是無(wú)賴嗎 3 你們倆人中有騎士嗎 4 你們倆人中有無(wú)賴嗎 景曉軍景曉軍 6 6 邏輯判斷邏輯判斷 長(zhǎng)官命令長(zhǎng)官命令 理發(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對(duì)偶與范式對(duì)偶與范式 1 6 推理理論推理理論 景曉軍景曉軍 8 8 什么是什么是命題命題 數(shù)理邏輯數(shù)理邏輯研究的中心問(wèn)題是研究的中心問(wèn)題是推理推理 而推理而推理 的的前提前提和和結(jié)論結(jié)論都是表達(dá)判斷的都是表達(dá)判斷的命題命題 命題命題 能判斷真假的能判斷真假的陳述句陳述句 真值真值 命題的命題的判斷結(jié)果判斷結(jié)果 也稱為也稱為值值 真真 假假 命題命題真值真值的的兩種可能兩種可能 命題的三要素命題的三要素 1 1 是是陳述句陳述句 2 2 真值真值只能有只能有真真和和假假兩種結(jié)果兩種結(jié)果 3 3 真值真值必須必須唯一唯一 景曉軍景曉軍 9 9 判斷下面句子是否是命題判斷下面句子是否是命題 2是素?cái)?shù)是素?cái)?shù) 雪是黑色的雪是黑色的 2 3 5 明年十月一日是晴天明年十月一日是晴天 這朵花多好看呀這朵花多好看呀 明天下午有會(huì)嗎明天下午有會(huì)嗎 請(qǐng)關(guān)上門請(qǐng)關(guān)上門 x y 5 地球外的星球上也有人地球外的星球上也有人 我寫了錯(cuò)字我寫了錯(cuò)字 是是1 是是0 是是1 是是 否否 否否 否否 否否真值不唯一真值不唯一 是是 否否真值不唯一真值不唯一 整個(gè)句子有整個(gè)句子有 二義性二義性 悖論不是命題悖論不是命題 景曉軍景曉軍10 10 簡(jiǎn)單命題與復(fù)合命題簡(jiǎn)單命題與復(fù)合命題 簡(jiǎn)單命題簡(jiǎn)單命題 命題不能分成更簡(jiǎn)單的句子的命題命題不能分成更簡(jiǎn)單的句子的命題 又稱為又稱為 命題常項(xiàng)命題常項(xiàng) 2是素?cái)?shù)是素?cái)?shù) 雪是黑色的雪是黑色的 2 3 5 明年十月一日是晴天明年十月一日是晴天 復(fù)合命題復(fù)合命題 由簡(jiǎn)單命題用聯(lián)結(jié)詞聯(lián)結(jié)而成的命題由簡(jiǎn)單命題用聯(lián)結(jié)詞聯(lián)結(jié)而成的命題 3不是偶數(shù)不是偶數(shù) 2是素?cái)?shù)和偶數(shù)是素?cái)?shù)和偶數(shù) 林芳學(xué)過(guò)英語(yǔ)或日語(yǔ)林芳學(xué)過(guò)英語(yǔ)或日語(yǔ) 如果角如果角A和角和角B是對(duì)頂角是對(duì)頂角 則角則角A等于角等于角B 景曉軍景曉軍11 11 命題變項(xiàng)命題變項(xiàng) 命題變?cè)}變?cè)?命題變項(xiàng)命題變項(xiàng) 命題變?cè)}變?cè)?真值可以變真值可以變 化的陳述句化的陳述句 如如 x yx y 5 5 命題變項(xiàng)命題變項(xiàng)不是命題不是命題 命題常項(xiàng)命題常項(xiàng) 命題常元命題常元 真值唯一確真值唯一確 定的陳述句定的陳述句 如如 2 2是偶數(shù)是偶數(shù) 命題常項(xiàng)命題常項(xiàng)是命題是命題 景曉軍景曉軍12 12 簡(jiǎn)單命題簡(jiǎn)單命題 命題變項(xiàng)的符號(hào)化命題變項(xiàng)的符號(hào)化 簡(jiǎn)單命題符號(hào)化簡(jiǎn)單命題符號(hào)化 p 2是素?cái)?shù)是素?cái)?shù) 命題常項(xiàng)命題常項(xiàng) q 雪是白的雪是白的 命題常項(xiàng)命題常項(xiàng) 命題變項(xiàng)命題變項(xiàng)符號(hào)化符號(hào)化 P x y 5 命題變項(xiàng)命題變項(xiàng) 不是命題不是命題 命題的真值表示命題的真值表示 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é)詞 蘊(yùn)涵蘊(yùn)涵聯(lián)結(jié)詞聯(lián)結(jié)詞 等價(jià)等價(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為兩個(gè)命題為兩個(gè)命題 復(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同同 時(shí)為真時(shí)為真 合取聯(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為兩個(gè)命題為兩個(gè)命題 復(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中至少一個(gè)為真中至少一個(gè)為真 析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞是是邏輯邏輯 或或 的意思的意思 王燕學(xué)過(guò)英語(yǔ)王燕學(xué)過(guò)英語(yǔ) p 或法語(yǔ)或法語(yǔ) q p q 或或 具有具有 相容性相容性 和和 相斥性相斥性 兩重意兩重意 義義 派小王或小李中的一人去開會(huì)派小王或小李中的一人去開會(huì) p q p q 景曉軍景曉軍17 17 蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵聯(lián)結(jié)詞 設(shè)設(shè)p p q q為兩個(gè)命題為兩個(gè)命題 復(fù)合命題復(fù)合命題 如果如果p p 則則q q 稱作稱作p p與與q q的的蘊(yùn)涵式蘊(yùn)涵式 記作記作p q p p為蘊(yùn)涵為蘊(yùn)涵 式的式的前件前件 q q為蘊(yùn)涵式的為蘊(yùn)涵式的后件后件 為為蘊(yùn)涵蘊(yùn)涵 聯(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 則太陽(yáng)就從東方升起則太陽(yáng)就從東方升起 p q 景曉軍景曉軍18 18 等價(jià)聯(lián)結(jié)詞等價(jià)聯(lián)結(jié)詞 設(shè)設(shè)p p q q為兩個(gè)命題為兩個(gè)命題 復(fù)合命題復(fù)合命題 p p當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)q q 稱作稱作 p p與與q q的的等價(jià)式等價(jià)式 記作記作p q 為為等價(jià)聯(lián)結(jié)詞等價(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)班長(zhǎng)選小王或小李中的一人當(dāng)班長(zhǎng) p q p q 如果我上街如果我上街 我就去書店看看我就去書店看看 除非我很累除非我很累 r p q r p q 王一樂(lè)是計(jì)算機(jī)系的學(xué)生王一樂(lè)是計(jì)算機(jī)系的學(xué)生 他生于他生于68年或年或69年年 他是三好學(xué)生他是三好學(xué)生 p q r q r s 景曉軍景曉軍20 20 聯(lián)結(jié)詞運(yùn)算規(guī)則聯(lián)結(jié)詞運(yùn)算規(guī)則 我們所學(xué)的我們所學(xué)的5 5種基本聯(lián)結(jié)詞種基本聯(lián)結(jié)詞也稱為也稱為邏輯邏輯 運(yùn)算符運(yùn)算符 其其運(yùn)算順序運(yùn)算順序?yàn)闉?如果出現(xiàn)的如果出現(xiàn)的基本聯(lián)結(jié)詞基本聯(lián)結(jié)詞相同相同 又又無(wú)括號(hào)無(wú)括號(hào) 時(shí)時(shí) 則按則按從左到右從左到右的的運(yùn)算順序運(yùn)算順序 如果遇有如果遇有括號(hào)括號(hào)時(shí)時(shí) 不管出現(xiàn)的不管出現(xiàn)的基本聯(lián)結(jié)基本聯(lián)結(jié) 詞詞如何如何 都先進(jìn)行都先進(jìn)行括號(hào)中括號(hào)中的的運(yùn)算運(yùn)算 景曉軍景曉軍21 21 1 命題符號(hào)化及聯(lián)結(jié)詞命題符號(hào)化及聯(lián)結(jié)詞 2 命題公式及分類命題公式及分類 3 等值演算等值演算 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 5 對(duì)偶與范式對(duì)偶與范式 6 推理理論推理理論 第一章第一章 命題邏輯命題邏輯 景曉軍景曉軍22 22 什么是命題公式或公式什么是命題公式或公式 命題公式命題公式是由命題常項(xiàng)是由命題常項(xiàng) 命題變項(xiàng)命題變項(xiàng) 聯(lián)結(jié)詞聯(lián)結(jié)詞 括號(hào)等組括號(hào)等組 成的符號(hào)串成的符號(hào)串 遞歸定義遞歸定義 1 單個(gè)命題常項(xiàng)或變項(xiàng)單個(gè)命題常項(xiàng)或變項(xiàng)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 組成的符號(hào)串才是組成的符號(hào)串才是合式公式合式公式 合式公式合式公式稱為稱為命題公式命題公式 簡(jiǎn)稱簡(jiǎn)稱公式公式 p q r p q r p q r p q r p q r p q r 景曉軍景曉軍23 23 命題公式的層次定義命題公式的層次定義 若若A是單個(gè)命題是單個(gè)命題 常項(xiàng)或變項(xiàng)常項(xiàng)或變項(xiàng) 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)在 中中 的所有的的所有的命題變項(xiàng)命題變項(xiàng) 給給p1 p2 pn指定一組指定一組 真值真值 稱為對(duì)稱為對(duì) 的一個(gè)的一個(gè)賦值賦值 若指定的這若指定的這 一組真值使一組真值使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 個(gè)個(gè)命題變項(xiàng)命題變項(xiàng)的命題公式的命題公式 共有共有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 如計(jì)算如計(jì)算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 命題符號(hào)化及聯(lián)結(jié)詞命題符號(hào)化及聯(lián)結(jié)詞 2 命題公式及分類命題公式及分類 3 等值演算等值演算 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 5 對(duì)偶與范式對(duì)偶與范式 6 推理理論推理理論 第一章第一章 命題邏輯命題邏輯 景曉軍景曉軍28 28 等值演算等值演算 設(shè)設(shè)A B是兩個(gè)命題是兩個(gè)命題 若等價(jià)式若等價(jià)式A B是是重言式重言式 則則A與與B是是等值等值的的 記為記為AB 注意和注意和 的關(guān)系的關(guān)系 A B是重言式是重言式 說(shuō)明只出現(xiàn)說(shuō)明只出現(xiàn)A與與B 的值的值 同時(shí)為真同時(shí)為真或或同時(shí)為假同時(shí)為假的的兩種情況兩種情況 所所 以肯定以肯定A B 注意和注意和 的關(guān)系的關(guān)系 如如A B 則則A B必是重言式必是重言式 若若A B 未必未必A B 因?yàn)橐驗(yàn)锳 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 定律定律等值式等值式序號(hào)序號(hào) 不要死記不要死記 理解記憶理解記憶 景曉軍景曉軍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 定律定律等值式等值式序號(hào)序號(hào) 景曉軍景曉軍34 34 判斷類別法判斷類別法 等值式等值式 3 輸出律輸出律A B C A B C24 蘊(yùn)涵等式蘊(yùn)涵等式 真值表真值表 A B 7AVB20 等價(jià)等值等價(jià)等值A(chǔ) B A B B A 21 假言易位假言易位 逆否命題逆否命題 A B 7B 7A22 等價(jià)否定等值等價(jià)否定等值A(chǔ)B 7A7B23 歸繆論歸繆論 A B A 7B 7A25 刁難人刁難人 定律定律等值式等值式序號(hào)序號(hào) 景曉軍景曉軍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時(shí)時(shí) A 0 能使能使 A 1 B 1 也能使也能使 B 1 顯然此時(shí)顯然此時(shí)A B不等值不等值 根據(jù)上述等值式根據(jù)上述等值式 不用真值表不用真值表法就可以推出更多的等法就可以推出更多的等 值式值式 這個(gè)過(guò)程為這個(gè)過(guò)程為等值演算等值演算 景曉軍景曉軍36 36 習(xí)題習(xí)題 驗(yàn)證下列等式驗(yàn)證下列等式 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í)題 驗(yàn)證下列等式驗(yàn)證下列等式 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 命題符號(hào)化及聯(lián)結(jié)詞命題符號(hào)化及聯(lián)結(jié)詞 2 命題公式及分類命題公式及分類 3 等值演算等值演算 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 5 對(duì)偶與范式對(duì)偶與范式 6 推理理論推理理論 第一章第一章 命題邏輯命題邏輯 景曉軍景曉軍39 39 聯(lián)結(jié)詞的擴(kuò)展聯(lián)結(jié)詞的擴(kuò)展 異或異或聯(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為兩個(gè)命題為兩個(gè)命題 復(fù)合命題復(fù)合命題 p q中中恰有恰有 一個(gè)成立一個(gè)成立 稱為稱為p與與q的的排斥或排斥或或或異或異或記作記作 p q 稱作稱作排斥或排斥或或或異或異或聯(lián)結(jié)詞聯(lián)結(jié)詞 p q為為真真當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)p q中中恰有一個(gè)為真恰有一個(gè)為真 0 1 If and only if 景曉軍景曉軍41 41 與非聯(lián)結(jié)詞與非聯(lián)結(jié)詞 設(shè)設(shè)p q兩個(gè)命題兩個(gè)命題 復(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不同時(shí)為真不同時(shí)為真 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兩個(gè)命題兩個(gè)命題 復(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同時(shí)為假同時(shí)為假 p q 7 p V q p q p V q 0 p q p V q 1 景曉軍景曉軍43 43 n元真值函數(shù)元真值函數(shù) 一個(gè)一個(gè)n n 1 維卡氏積維卡氏積 0 1 n到到 0 1 的函數(shù)稱為一的函數(shù)稱為一 個(gè)個(gè)n元元真值函數(shù)真值函數(shù) 設(shè)設(shè)F是一個(gè)是一個(gè)n元真值函數(shù)元真值函數(shù) 則可記為則可記為 F 0 1 n 0 1 0 1 x x x 1 0 n個(gè)命題變項(xiàng)個(gè)命題變項(xiàng) 共有共有2n個(gè)可能的賦值個(gè)可能的賦值 橫行橫行 有有 個(gè)不同的真值函數(shù)個(gè)不同的真值函數(shù) 豎列豎列 其中其中 一個(gè)真值一個(gè)真值 函數(shù)函數(shù)對(duì)應(yīng)著對(duì)應(yīng)著一個(gè)真值相同的命題公式一個(gè)真值相同的命題公式 而這個(gè)命題而這個(gè)命題 公式又和許多命題公式彼此間是等值的公式又和許多命題公式彼此間是等值的 即即 n個(gè)命個(gè)命 題變項(xiàng)題變項(xiàng) 必有且僅有必有且僅有個(gè)不同真值的命題公式個(gè)不同真值的命題公式 其其 余的命題公式必然與這余的命題公式必然與這個(gè)命題公式中的一個(gè)是等個(gè)命題公式中的一個(gè)是等 值的值的 n 2 2 n 2 2 n 2 2 景曉軍景曉軍44 44 兩個(gè)變?cè)恼嬷岛瘮?shù)兩個(gè)變?cè)恼嬷岛瘮?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ù)寫出對(duì)應(yīng)的命題公式由真值函數(shù)寫出對(duì)應(yīng)的命題公式 n個(gè)命題變?cè)獋€(gè)命題變?cè)?個(gè)個(gè)真值函數(shù)真值函數(shù) 出現(xiàn)出現(xiàn)k個(gè)個(gè) 1 的真值函數(shù)為的真值函數(shù)為個(gè)個(gè) n 2 2 2 1 n k n C nk 現(xiàn)有現(xiàn)有p q 2個(gè)命題變?cè)獋€(gè)命題變?cè)?則則 0個(gè)個(gè) 1 的公式的公式1個(gè)個(gè) 1個(gè)個(gè) 1 的公式的公式4個(gè)個(gè) 2個(gè)個(gè) 1 的公式的公式6個(gè)個(gè) 3個(gè)個(gè) 1 的公式的公式4個(gè)個(gè) 4個(gè)個(gè) 1 的公式的公式1個(gè)個(gè) 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é)詞 獨(dú)立聯(lián)結(jié)詞獨(dú)立聯(lián)結(jié)詞 在一個(gè)聯(lián)結(jié)詞的集合中在一個(gè)聯(lián)結(jié)詞的集合中 如果一個(gè)聯(lián)結(jié)詞可由集如果一個(gè)聯(lián)結(jié)詞可由集 合中的其他聯(lián)結(jié)詞表示合中的其他聯(lián)結(jié)詞表示 則稱此聯(lián)接詞為則稱此聯(lián)接詞為冗余聯(lián)冗余聯(lián) 結(jié)詞結(jié)詞 否則稱為否則稱為獨(dú)立聯(lián)結(jié)詞獨(dú)立聯(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 為為獨(dú)立聯(lián)結(jié)詞獨(dú)立聯(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 命題符號(hào)化及聯(lián)結(jié)詞命題符號(hào)化及聯(lián)結(jié)詞 2 命題公式及分類命題公式及分類 3 等值演算等值演算 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 5 對(duì)偶與范式對(duì)偶與范式 6 推理理論推理理論 景曉軍景曉軍50 50 對(duì)偶式對(duì)偶式 在含有聯(lián)結(jié)詞在含有聯(lián)結(jié)詞7 V的命題公式的命題公式A中中 將將V換換 成成 換成換成V 若若A中含中含0或或1 將將0換成換成1 1 換成換成0 所得到命題公式稱為所得到命題公式稱為A的的對(duì)偶式對(duì)偶式 記作記作A p q 與與 pvq是對(duì)偶式是對(duì)偶式 7 p q 與與 7 pvq 是對(duì)偶式是對(duì)偶式 景曉軍景曉軍51 51 性質(zhì)性質(zhì)1 設(shè)設(shè)A和和A 互為對(duì)偶式互為對(duì)偶式 p1 p2 pn是出現(xiàn)在是出現(xiàn)在A和和A 中的全部的命題變項(xiàng)中的全部的命題變項(xiàng) 若將若將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 對(duì)偶原理對(duì)偶原理 設(shè)設(shè)A B為兩命題公式為兩命題公式 若若A B 則則A B 其中其中 A B 分別為分別為A B的對(duì)偶式的對(duì)偶式 例如例如 p q V 7pV 7pVq 7pVq p q V 7pV 7pVq p q v 7pvq pv 7pvq qv 7pvq 1 7pvq 7pVq 對(duì)偶式對(duì)偶式 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 簡(jiǎn)單析取式簡(jiǎn)單析取式 簡(jiǎn)單合取式簡(jiǎn)單合取式 僅有限個(gè)命題變項(xiàng)或其否定構(gòu)成的析取式僅有限個(gè)命題變項(xiàng)或其否定構(gòu)成的析取式 稱為稱為簡(jiǎn)單析取式簡(jiǎn)單析取式 僅有限個(gè)命題變項(xiàng)或其否僅有限個(gè)命題變項(xiàng)或其否 定構(gòu)成的合取式稱為定構(gòu)成的合取式稱為簡(jiǎn)單合取式簡(jiǎn)單合取式 簡(jiǎn)單析取式簡(jiǎn)單析取式 pvq 7pvq 7pv7q 簡(jiǎn)單合取式簡(jiǎn)單合取式 p q 7p q 7p 7q 一個(gè)簡(jiǎn)單析取式為一個(gè)簡(jiǎn)單析取式為重言式重言式 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)同時(shí)含有同時(shí)含有 一個(gè)命題變項(xiàng)及其否定一個(gè)命題變項(xiàng)及其否定 一個(gè)簡(jiǎn)單合取式為一個(gè)簡(jiǎn)單合取式為矛盾式矛盾式 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)同時(shí)含有同時(shí)含有 一個(gè)命題變項(xiàng)及其否定一個(gè)命題變項(xiàng)及其否定 景曉軍景曉軍54 54 析取范式析取范式 合取范式合取范式 僅由僅由有限個(gè)簡(jiǎn)單合取式有限個(gè)簡(jiǎn)單合取式構(gòu)成的構(gòu)成的析取式析取式稱為稱為析取范析取范 式式 A A1VA2VA3 一個(gè)析取范式一個(gè)析取范式為為矛盾式矛盾式 當(dāng)且僅當(dāng)含有的當(dāng)且僅當(dāng)含有的每個(gè)簡(jiǎn)單合每個(gè)簡(jiǎn)單合 取式為假取式為假 僅由僅由有限個(gè)簡(jiǎn)單析取式有限個(gè)簡(jiǎn)單析取式構(gòu)成的構(gòu)成的合取式合取式稱為稱為合取范合取范 式式 A A1 A2 A3 一個(gè)合取范式一個(gè)合取范式為為重言式重言式 當(dāng)且僅當(dāng)含有的當(dāng)且僅當(dāng)含有的每個(gè)簡(jiǎn)單析每個(gè)簡(jiǎn)單析 取式為真取式為真 景曉軍景曉軍55 55 范式存在定理范式存在定理 任一命題公式都存在與之等值的任一命題公式都存在與之等值的析取范式析取范式 與與合取范式合取范式 但不唯一但不唯一 如如 7pvp 7qvq 由于由于 7 V 是全功能集是全功能集 因而可以用這因而可以用這 些聯(lián)結(jié)詞來(lái)代替些聯(lián)結(jié)詞來(lái)代替 V 目的是 變成合取或析取范式 p q 7pvq p q 7pvq pv7q 景曉軍景曉軍56 56 極小項(xiàng)極小項(xiàng) 在含有在含有n個(gè)命題的簡(jiǎn)單合取式中個(gè)命題的簡(jiǎn)單合取式中 若若每個(gè)命題變項(xiàng)與其否定每個(gè)命題變項(xiàng)與其否定 不同時(shí)存在不同時(shí)存在 而而兩者之一必出現(xiàn)且僅出現(xiàn)一次兩者之一必出現(xiàn)且僅出現(xiàn)一次 且且第第i個(gè)命題個(gè)命題 變項(xiàng)或其否定出現(xiàn)在從左起的第變項(xiàng)或其否定出現(xiàn)在從左起的第i位上位上 若命題變項(xiàng)無(wú)角標(biāo)若命題變項(xiàng)無(wú)角標(biāo) 則按字典順序排序則按字典順序排序 這樣的這樣的簡(jiǎn)單合取式簡(jiǎn)單合取式稱為稱為極小項(xiàng)極小項(xiàng) 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個(gè)命題變項(xiàng)個(gè)命題變項(xiàng) 如果如果A的的析取析取 范式范式中的中的簡(jiǎn)單合取式簡(jiǎn)單合取式全是極小項(xiàng)全是極小項(xiàng) 則則A稱稱為為主析取主析取 范式范式 任何命題公式的任何命題公式的主析取范式主析取范式是是存在的存在的 且唯一且唯一 求解步驟求解步驟 求求A的析取范式的析取范式 對(duì)命題中不含某個(gè)變項(xiàng)的采用對(duì)命題中不含某個(gè)變項(xiàng)的采用 B B 1 B p V B 7p 消去消去 重復(fù)出現(xiàn)的命題變項(xiàng)重復(fù)出現(xiàn)的命題變項(xiàng) 矛盾式及極小矛盾式及極小 項(xiàng)項(xiàng) 景曉軍景曉軍58 58 命題公式命題公式A中含有中含有n個(gè)命題變項(xiàng)個(gè)命題變項(xiàng) 如果如果A是重言是重言 式式 永真式永真式 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A的主析取范式中的主析取范式中 含全部的含全部的2n個(gè)極小項(xiàng)個(gè)極小項(xiàng) 命題公式命題公式A中含有中含有n個(gè)命題變項(xiàng)個(gè)命題變項(xiàng) 如果如果A是矛盾是矛盾 式式 永假式永假式 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A的主析取范式中的主析取范式中 不含任何極小項(xiàng)不含任何極小項(xiàng) 命題公式命題公式A中含有中含有n個(gè)命題變項(xiàng)個(gè)命題變項(xiàng) 如果如果A是可滿是可滿 足式足式 協(xié)調(diào)式協(xié)調(diào)式 則則A的主析取范式中的主析取范式中至少至少 含一個(gè)極小項(xiàng)含一個(gè)極小項(xiàng) 主析取范式主析取范式 判斷命題公式類型法判斷命題公式類型法 景曉軍景曉軍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 極大項(xiàng)極大項(xiàng) 在含有在含有n個(gè)命題的簡(jiǎn)單析取式中個(gè)命題的簡(jiǎn)單析取式中 若若每個(gè)命題變項(xiàng)與其否定每個(gè)命題變項(xiàng)與其否定 不同時(shí)存在不同時(shí)存在 而而兩者之一必出現(xiàn)且僅出現(xiàn)一次兩者之一必出現(xiàn)且僅出現(xiàn)一次 且且第第i個(gè)命題個(gè)命題 變項(xiàng)或其否定出現(xiàn)在從左起的第變項(xiàng)或其否定出現(xiàn)在從左起的第i 位上位上 若命題變項(xiàng)無(wú)角標(biāo)若命題變項(xiàng)無(wú)角標(biāo) 按字典順序排序按字典順序排序 這樣的這樣的簡(jiǎn)單析取式簡(jiǎn)單析取式稱為稱為極大項(xiàng)極大項(xiàng) 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個(gè)命題變項(xiàng)個(gè)命題變項(xiàng) 如果如果A的的合取合取 范式范式中的中的簡(jiǎn)單析取式簡(jiǎn)單析取式全是極大項(xiàng)全是極大項(xiàng) 則則A稱稱為為主合取主合取 范式范式 任何命題公式的任何命題公式的主合取范式主合取范式是是存在的存在的 且唯一且唯一 求解方式求解方式 求求A的合取范式的合取范式 對(duì)命題中不含某個(gè)變項(xiàng)的采用對(duì)命題中不含某個(gè)變項(xiàng)的采用 B BV0 BVp BV7p 消去消去 重復(fù)出現(xiàn)的命題變項(xiàng)重復(fù)出現(xiàn)的命題變項(xiàng) 重言式及極大重言式及極大 項(xiàng)項(xiàng) 景曉軍景曉軍63 63 命題公式命題公式A中含有中含有n個(gè)命題變項(xiàng)個(gè)命題變項(xiàng) 如果如果A是重言是重言 式式 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A的的主合取范式主合取范式中中不含任何極大不含任何極大 項(xiàng)項(xiàng) 命題公式命題公式A中含有中含有n個(gè)命題變項(xiàng)個(gè)命題變項(xiàng) 如果如果A是矛盾是矛盾 式式 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A的的主合取范式主合取范式中中含全部的含全部的2n個(gè)個(gè) 極大項(xiàng)極大項(xiàng) 命題公式命題公式A中含有中含有n個(gè)命題變項(xiàng)個(gè)命題變項(xiàng) 如果如果A是可滿是可滿 足式足式 協(xié)調(diào)式協(xié)調(diào)式 則則A的的主合析取范式主合析取范式中中至少至少 含一個(gè)極大項(xiàng)含一個(gè)極大項(xiàng) 主合取范式主合取范式 判斷命題公式類型法判斷命題公式類型法 景曉軍景曉軍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 因真值表的寫法是一樣的因真值表的寫法是一樣的 所以所以 同一個(gè)真值函數(shù)同一個(gè)真值函數(shù) 對(duì)對(duì) 應(yīng)唯一的一個(gè)主析取范式應(yīng)唯一的一個(gè)主析取范式 且對(duì)應(yīng)唯一的主合取范式且對(duì)應(yīng)唯一的主合取范式 即即 一個(gè)主析取范式唯一一個(gè)主析取范式唯一 的對(duì)應(yīng)一個(gè)主合取范式的對(duì)應(yīng)一個(gè)主合取范式 景曉軍景曉軍66 66 主析取范式與主合取范式的關(guān)系主析取范式與主合取范式的關(guān)系 存在存在7mi Mi關(guān)系關(guān)系 單個(gè)單個(gè) 所以所以 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 命題符號(hào)化及聯(lián)結(jié)詞命題符號(hào)化及聯(lián)結(jié)詞 2 命題公式及分類命題公式及分類 3 等值演算等值演算 4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 5 對(duì)偶與范式對(duì)偶與范式 6 推理理論推理理論 景曉軍景曉軍68 68 什么是推理什么是推理 推理推理是從前提推出結(jié)論的思是從前提推出結(jié)論的思 維過(guò)程維過(guò)程 前提前提是已知的命題公是已知的命題公 式式 結(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 判斷推理是否正確的方法就是重言蘊(yùn)涵式的 方法 我們已學(xué)過(guò)三種方法 1 1 真值表法真值表法 2 2 等值演算等值演算 3 3 主析取范式主析取范式 下面介紹第四種方法下面介紹第四種方法 構(gòu)造證明法構(gòu)造證明法 構(gòu)造證明法構(gòu)造證明法 判斷命題公式類型法判斷命題公式類型法 景曉軍景曉軍71 71 例題例題 1 判斷下面各推理是否正確判斷下面各推理是否正確 如果天氣涼快如果天氣涼快 小王就不去游泳小王就不去游泳 天氣涼快天氣涼快 所以小王