離散數(shù)學(xué)第一章命題邏輯-1-4節(jié).ppt

《離散數(shù)學(xué)第一章命題邏輯-1-4節(jié).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)第一章命題邏輯-1-4節(jié).ppt（68頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1 離散數(shù)學(xué) 河南工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院 第一章命題邏輯 2 第一篇數(shù)理邏輯 什么是邏輯 學(xué) 研究人類思維的科學(xué) 研究思維形式及思維過程 公元前四世紀(jì)亞里斯多德 工具論 奠定了邏輯學(xué)的理論基礎(chǔ) 中國(guó)最早的一部邏輯專著 墨經(jīng) 也創(chuàng)造了一個(gè)比較完整的邏輯體系 辯證邏輯 形式邏輯 3 什么是數(shù)理邏輯 數(shù)理邏輯是用數(shù)學(xué)的方法研究邏輯 所謂 數(shù)學(xué)方法 就是引進(jìn)一套符號(hào)體系的方法 用數(shù)學(xué)理論 手段和技巧找出研究對(duì)象內(nèi)在聯(lián)系的數(shù)學(xué)表達(dá)式及其規(guī)范的方法 包括使用符號(hào)和公式 已有的數(shù)學(xué)成果和方法 特別是使用形式的公理方法 數(shù)理邏輯即引進(jìn)一套符號(hào)體系的方法來(lái)研究概念 判斷和推理 即對(duì)符號(hào)進(jìn)行判斷和推理 所以數(shù)理邏輯也稱為 符號(hào)邏輯 數(shù)理邏輯屬于形式邏輯 它與數(shù)學(xué)的其它分支 計(jì)算機(jī)科學(xué) 人工智能 語(yǔ)言學(xué)等學(xué)科均有密切聯(lián)系 數(shù)理邏輯的主要內(nèi)容 數(shù)理邏輯內(nèi)容豐富 但其主要包括 兩個(gè)演算 加 四論 即 邏輯演算 包括命題演算和謂詞演算證明論 主要研究數(shù)學(xué)理論系統(tǒng)的相容性 即不矛盾 協(xié)調(diào)性 的證明 遞歸論 能行性理論 自從電子計(jì)算機(jī)發(fā)明后 迫切需要在理論上弄清計(jì)算機(jī)能計(jì)算哪些函數(shù) 遞歸論研究能行可計(jì)算的理論 它為能行可計(jì)算的函數(shù)找出各種理論上精確化的嚴(yán)密類比物 模型論 主要是對(duì)各種數(shù)學(xué)理論系統(tǒng)建立模型 并研究各模型之間的關(guān)系以及模型與系統(tǒng)之間的關(guān)系 公理集合論 主要研究在消除已知集合論悖論的情況下 用公理方法把有關(guān)集合的理論充分發(fā)展下去 5 1 甲在河南工業(yè)大學(xué)上學(xué) 2 甲在鄭州上大學(xué) 如果 甲在河南工業(yè)大學(xué)上學(xué) 真的 則顯然 甲在鄭州上大學(xué) 也是真的 推理形式 如果甲在河南工業(yè)大學(xué)上學(xué) 則甲在鄭州上大學(xué) 甲在河南工業(yè)大學(xué)上學(xué) 則可推出甲在鄭州上大學(xué) 符號(hào)化為 P表示 甲在河南工業(yè)大學(xué)上學(xué) Q表示 甲在鄭州上大學(xué) P Q表示 如果甲在河南工業(yè)大學(xué)上學(xué) 則甲在鄭州上大學(xué) 推理形式可以表示為P Q為真 P為真 則可推出Q為真 可以抽象地寫成 P Q P Q 3 如果甲在河南工業(yè)大學(xué)上學(xué) 則甲在鄭州上大學(xué) 是成立的 例 請(qǐng)根據(jù)下面事實(shí) 找出兇手 1 清潔工或者秘書謀害了經(jīng)理 2 如果清潔工謀害了經(jīng)理 則謀害不會(huì)發(fā)生在午夜前 3 如果秘書的證詞是正確的 則謀害發(fā)生在午夜前 4 如果秘書的證詞不正確 則午夜時(shí)屋里燈光未滅 5 午夜時(shí)屋里燈滅了 問 誰(shuí)是兇手 秘書謀害了經(jīng)理 第一篇數(shù)理邏輯 主要研究?jī)?nèi)容 第一章命題邏輯研究的內(nèi)容 命題邏輯也稱為命題演算研究以命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系 1 1命題與命題的真值1 2聯(lián)結(jié)詞1 3命題公式及翻譯1 4真值表與等價(jià)公式1 5重言式與蘊(yùn)含式1 6其它聯(lián)結(jié)詞 1 7對(duì)偶與范式1 8命題推理理論 第一章命題邏輯學(xué)習(xí)要求 10 1 1 命題與命題的真值 本節(jié)主要討論四個(gè)問題 命題的概念命題的真值原子命題與復(fù)合命題命題的表示 11 一 命題的概念 陳述句 陳述一個(gè)事實(shí)或一個(gè)說(shuō)話人的看法 句末用句號(hào) 祈使句 要求或者希望別人做什么事或者不做什么事時(shí)用的句子 句末用句號(hào)或感嘆號(hào) 疑問句 提出問題的句子 句末用問號(hào) 感嘆句 帶有濃厚感情的句子 句末用感嘆號(hào) 請(qǐng)看下面給出的兩個(gè)陳述句 1 2是個(gè)素?cái)?shù) 2 雪是黑色的 這兩個(gè)陳述句都表示對(duì)事件性質(zhì)的判斷 第一句話表示的判斷是正確的 第二句話表示的判斷是錯(cuò)誤的 像 1 2 這樣能夠唯一確定所表達(dá)的判斷是正確的還是錯(cuò)誤的陳述句稱為命題 13 一 命題的概念 命題是一個(gè)能判斷是真的或是假的陳述句 命題一定是陳述句 但并非一切陳述句都是命題 真值 一個(gè)命題的值叫真值 一個(gè)命題的真值有兩個(gè) 真 或 假 真值為真 一個(gè)命題所作的判斷與客觀一致 則稱該命題的真值為真 記作T True 真命題 真值為假 一個(gè)命題所作的判斷與客觀不一致 則稱該命題的真值為假 記作F False 假命題 命題是具有唯一真值的陳述句 命題可以是真的 或者是假的 但不能同時(shí)為真又為假 例子 例1 1 1 1 中華人民共和國(guó)的首都是北京 2 大于4的偶數(shù)均可分解為兩個(gè)質(zhì)數(shù)的和 哥德巴赫猜想 3 所有質(zhì)數(shù)都是奇數(shù) 4 雪是黑色的 真命題 真命題 假命題 假命題 判斷語(yǔ)句是否為命題要注意的問題 1 目前無(wú)法確定真值 但從本質(zhì)而言 真值存在的語(yǔ)句是命題 例 1 別的星球上有生物 2 2046年世界杯在中國(guó)舉行 2 真值因時(shí)因地而異的判斷性陳述句是命題 例 1 2011年的元旦是晴天 2 今天下雨 3 含有未確定內(nèi)容的代詞 不能判斷真假的語(yǔ)句不是命題 例 1 1 101 110 當(dāng)1和101是二進(jìn)制數(shù) 語(yǔ)句為真 為十進(jìn)制數(shù) 語(yǔ)句為假 2 x y 10 4 悖論不是命題 語(yǔ)句既為真 同時(shí)又包含假的不是命題 這樣的句子稱為 悖論 例 我正在說(shuō)慌 如何判斷一個(gè)句子是否為真命題 1 是否為陳述句 2 其真值是否唯一 3 其真值是否為真 命題 分子命題 原子命題 二 原子命題與復(fù)合命題 簡(jiǎn)單命題 原子命題 由最簡(jiǎn)單的陳述句構(gòu)成的命題 該句再不能分解成更簡(jiǎn)單的句子了 如 我是一位學(xué)生 復(fù)合命題 分子命題 由若干個(gè)原子命題使用適當(dāng)?shù)穆?lián)結(jié)詞所組成的新命題 我是一位學(xué)生 他是一位教師 我是一位學(xué)生和他是一位教師 這些簡(jiǎn)單命題之間是通過如 或者 并且 不 如果 則 當(dāng)且僅當(dāng) 等這樣的關(guān)聯(lián)詞和標(biāo)點(diǎn)符號(hào)復(fù)合而構(gòu)成一個(gè)復(fù)合命題 18 三 命題的表示 大寫的帶或不帶下標(biāo)的英文字母 如 A A3 P例如 P 今天下雨 Q 張三在唱歌 表示命題的符號(hào) 表示確定命題的命題標(biāo)識(shí)符 命題常量真值確定 是命題 可表示任意一個(gè) 原子或復(fù)合 命題的命題標(biāo)識(shí)符 就稱為命題變?cè)?命題標(biāo)識(shí)符只表示任意命題的位置標(biāo)志 注意 命題變?cè)梢员硎救我獾拿} 所以真值不確定 命題變?cè)皇敲} 當(dāng)命題變?cè)狿用一個(gè)特定命題去取代或者是直接賦給命題變?cè)嬷?T 或 F 時(shí) 才能確定P的真值 該過程稱對(duì)P進(jìn)行指派 例 若P是命題變?cè)?P 北京是中國(guó)的首都 指派P為命題北京是中國(guó)的首都 命題標(biāo)識(shí)符 表示方法 對(duì)命題變?cè)髦概?給命題變?cè)粋€(gè)解釋 命題常量 命題變?cè)?19 1 2聯(lián)結(jié)詞 復(fù)合命題的構(gòu)成 是用 聯(lián)結(jié)詞 將原子命題聯(lián)結(jié)起來(lái)構(gòu)成的 歸納自然語(yǔ)言中的聯(lián)結(jié)詞 定義了六個(gè)邏輯聯(lián)結(jié)詞 分別是 1 否定 2 合取 3 析取 4 異或 5 條件 6 雙條件 20 一 否定 一元運(yùn)算 符號(hào) 讀作 非 否定 設(shè)P為命題 在P的前面加否定詞 變?yōu)?P P讀作 非P 或 P的否定 P為一新的命題 定義 用真值表表示 P是P的否定式 例1 2 1P 2是素?cái)?shù) T P 2不是素?cái)?shù) F P 上海是一個(gè)大城市 T P 上海不是一個(gè)大城市 或 上海是個(gè)不大的城市 嚴(yán)格講不建議 21 一 否定 一元運(yùn)算 P 咱班每個(gè)同學(xué)都大于18歲 P 咱班每個(gè)同學(xué)不都大于18歲 咱班每個(gè)同學(xué)都不大于18歲 用真值表來(lái)判斷 P P TF FT P 咱班每個(gè)同學(xué)不都大于18歲 不是每個(gè)同學(xué)不大于18歲 至少有一個(gè)同學(xué)不大于18歲 對(duì)量化命題的否定 需要同時(shí)對(duì)動(dòng)詞和量化詞要加以否定 二 合取 二元運(yùn)算 符號(hào) 設(shè)P Q為兩個(gè)命題 P Q稱為P與Q的合取 讀作 P合取Q P與 并且 Q P與Q的合取 等 P和Q的合取為一個(gè)復(fù)合命題 定義 由真值表給出 P Q的真值為真 當(dāng)且僅當(dāng)P和Q的真值均為真 P和Q是互為獨(dú)立的 地位是相等 P和Q的位置可以互換而不會(huì)影響P Q的結(jié)果 23 二 合取 二元運(yùn)算 相應(yīng)的日常用語(yǔ) 并且 既 又 不但 僅 而且 雖然 但是 盡管 還 例1 2 2P 今天下雨 Q 明天下雨 P Q 今天下雨而且明天下雨 或者 今天與明天都下雨 或者 這兩天都下雨 P 我們?nèi)ナ程贸燥?Q 教室里有三塊黑板 P Q 我們?nèi)ナ程贸燥埐⑶医淌依镉腥龎K黑板 注 復(fù)合命題中的原子命題之間無(wú)需有一般邏輯意義上的關(guān)聯(lián) 下列語(yǔ)句不是合取聯(lián)結(jié)詞組成的命題 1 張麗和王芳是好朋友 2 他打開箱子然后 而后 拿出一件衣服來(lái) 三 析取 異或 二元運(yùn)算1 析取 符號(hào) 設(shè)P Q為兩個(gè)命題 P Q稱為P與Q的析取 讀作 P或者Q P析取Q 等 P和Q的析取為一個(gè)復(fù)合命題 定義 見真值表P Q的真值為F 當(dāng)且僅當(dāng)P與Q均為F 區(qū)分 可兼或 與 不可兼或 例1 2 3燈泡有故障或者線路有故障 今晚寫字或看書 今天下雨或打雷 以上例子為可兼或 析取為可兼或 2 異或 PQ的真值為F 當(dāng)且僅當(dāng)P與Q的真值相同 例1 2 4他通過電視看足球比賽或到體育館看體育比賽 他乘火車去鄭州或乘汽車去鄭州 以上例子為不可兼或 四 雙條件 符號(hào) 設(shè)P Q為兩個(gè)命題 P Q讀作 P當(dāng)且僅當(dāng)Q P是Q的充分必要條件 等 P和Q的雙條件為一個(gè)復(fù)合命題 定義 見真值表P Q的真值為真 當(dāng)且僅當(dāng)P與Q的真值相同 例1 2 4 P ABC是等邊三角形 Q ABC是等角三角形 P Q ABC是等邊三角形當(dāng)且僅當(dāng)它是等角三角形 例 下面均為雙條件聯(lián)結(jié)詞 平面上二直線平行 當(dāng)且僅當(dāng)這二直線不相交 春天來(lái)了 燕子飛回來(lái)了 春天來(lái)了當(dāng)且僅當(dāng)燕子飛回來(lái)了 2 2 4當(dāng)且僅當(dāng)雪是白的 P Q中 P和Q的地位是平等的 P Q交換位置不會(huì)改變真值表的值 30 五 條件 符號(hào) 設(shè)P Q為兩個(gè)命題 P Q讀作 P蘊(yùn)含Q 如果P則Q P條件Q P是Q的充分條件 Q是P的必要條件 P僅當(dāng)Q Q當(dāng)且P 等 P Q為一個(gè)復(fù)合命題 P 稱為前件 條件 前提 假設(shè) Q 稱為后件 結(jié)論 定義 見真值表 P Q的真值 P Q的真值為假 當(dāng)且僅當(dāng)P為真 Q為假 注意 當(dāng)前件P為假時(shí) P Q為T 結(jié)論 P Q中 P和Q的地位是不平等的 P Q交換位置將會(huì)改變真值表的值 前件為假 P Q為真 后件為真 P Q為真 一位父親對(duì)兒子說(shuō) 如果星期天天氣好 就一定帶你去動(dòng)物園 問 在什么情況下父親食言 父親的可能情況有如下四種 1 星期天天氣好 帶兒子去了動(dòng)物園 2 星期天天氣好 卻沒帶兒子去動(dòng)物園 3 星期天天氣不好 卻帶兒子去了動(dòng)物園 4 星期天天氣不好 也沒帶兒子去動(dòng)物園 示例 沒有食言 沒有食言 沒有食言 食言 33 書例 前提與結(jié)論有聯(lián)系的 如果某動(dòng)物為哺乳動(dòng)物 則它必胎生 如果我得到這本小說(shuō) 那么我今夜就讀完它 前提與結(jié)論可以沒有聯(lián)系的 如果雪是黑的 那么太陽(yáng)從西方出來(lái) 舉例 令 P 天氣好 Q 我去公園 1 如果天氣好 我就去公園 P Q 2 只要天氣好 我就去公園 P Q 3 天氣好 我就去公園 P Q 4 只有天氣好 我才去公園 Q P 5 僅當(dāng)天氣好 我才去公園 Q P 6 我去公園 僅當(dāng)天氣好 Q P 7 除非天氣好 否則我不去公園 P Q Q P P Q 這類的聯(lián)結(jié)詞還有 只要P就Q 因?yàn)镻 所以Q P僅當(dāng)Q 只有Q才P 除非Q 否則非P 等等 本節(jié)小結(jié) 要熟練掌握這六個(gè)聯(lián)結(jié)詞在自然語(yǔ)言中所表示的含義以及它們的真值表的定義 均為真 至少一個(gè)為真 相同為真 不同為真 取反 1 復(fù)合命題的真值只取決于構(gòu)成它們的原子命題的真值和命題聯(lián)結(jié)詞的定義 而與它們的內(nèi)容 含義無(wú)關(guān) 與聯(lián)結(jié)詞所連接的兩個(gè)原子命題之間是否有關(guān)系無(wú)關(guān) 2 和 具有可交換性 而 沒有 本節(jié)小結(jié) 聯(lián)結(jié)詞是命題與命題之間的聯(lián)結(jié) 而非單純的名詞 數(shù)詞等地聯(lián)結(jié) 數(shù)理邏輯中的聯(lián)結(jié)詞是自然語(yǔ)言中聯(lián)結(jié)的邏輯抽象 應(yīng)具有準(zhǔn)確的邏輯含義和嚴(yán)格的單義性 使用時(shí)也應(yīng)忠實(shí)地按定義使用 設(shè)P 天不下雨 Q 草木枯黃則 P 天下雨P(guān) Q 天不下雨且草木枯黃 P Q 天不下雨或草木枯黃 P Q 如果天不下雨 那么草木枯黃 P Q 天不下雨當(dāng)且僅當(dāng)草木枯黃 37 本節(jié)小結(jié) 特別要注意 或者 的二義性 即要區(qū)分給定的 或 是 可兼取的或 還是 不可兼取的或 特別要注意 的用法 P Q的邏輯關(guān)系它既表示 充分條件 也表示 必要條件 即要弄清哪個(gè)作為前件 哪個(gè)作為后件 P Q的真值 P Q的靈活的敘述方法作業(yè) p83 4 5 38 練習(xí) 填空 1 已知P Q為T 則P為 Q為 2 已知P Q為F 則P為 Q為 3 已知P為F 則P Q為 4 已知P為T 則P Q為 5 已知P Q為T 且P為F 則Q為 6 已知P Q為F 則P為 Q為 7 已知P為F 則P Q為 8 已知Q為T 則P Q為 9 已知 P Q為F 則P為 Q為 10 已知P為T P Q為T 則Q為 11 已知 Q為T P Q為T 則P為 12 已知P Q為T P為T 則Q為 13 已知P Q為F P為T 則Q為 14 P P的真值為 15 P P的真值為 析取和異或示例 指出下列命題中的 或 是析取還是異或 今晚我去看演出或在家里看電視現(xiàn)場(chǎng)轉(zhuǎn)播 他是一百米冠軍或跳高冠軍 派小王或小趙出差去上海 派小王或小趙中的一個(gè)出差去上海 2 3為析取 1 4為異或 40 1 3命題公式及翻譯 一 命題公式1 原子命題公式 單個(gè)命題變?cè)虺Ｔ?2 命題演算合式公式 wff wellformedformulas 簡(jiǎn)稱命題公式 分子命題公式 由命題變?cè)?常元 聯(lián)結(jié)詞 括號(hào) 以規(guī)定的格式聯(lián)結(jié)起來(lái)的字符串 但并不是由這些符號(hào)任意組成的符號(hào)串都是命題公式 什么樣的符號(hào)串才能表示命題公式 41 1 3命題公式及翻譯 一 命題公式合式公式可以解釋為合法的命題公式之意 也稱之為命題公式 有時(shí)也簡(jiǎn)稱公式 定義1 3 1 單個(gè)的命題變?cè)莻€(gè)合式公式 若A是合式公式 則 A是合式公式 若A和B是合式公式 則 A B A B A B 和 A B 都是合式公式 當(dāng)且僅當(dāng)有限次地應(yīng)用 所得到的含有命題變?cè)?聯(lián)結(jié)詞和括號(hào)的符號(hào)串是合式公式 上述定義方法稱為遞歸定義法 遞歸法定義是離散數(shù)學(xué)中常用的方法 基礎(chǔ) 歸納 界限 例如 P P Q P R P Q R 是合式公式 P Q Q P R P Q R 應(yīng)是二元運(yùn)算符 括號(hào)不匹配 不是合式公式 的位置 命題公式 約定 1 為方便 最外層括號(hào)可以不寫 上面的 P Q P R P Q R 合式公式可以寫成 P Q P R P Q R 2 五個(gè)聯(lián)結(jié)詞的優(yōu)先次序 否定 合取 析取 條件 雙條件 凡符合此優(yōu)先次序的 括號(hào)可省略 P Q R 可以寫成P Q R 3 相同的聯(lián)結(jié)詞按出現(xiàn)的先后次序運(yùn)算 凡符合此要求的 括號(hào)可省去 P Q R 可以寫成P Q RP Q R 不可以寫成P Q R 命題公式的子公式 定義如果X是合式公式A的一部分 且X本身也是一合式公式 則稱X為公式A的子公式 如 A P Q R中P Q R P Q 45 二 命題符號(hào)化 即翻譯 就是用命題公式的符號(hào)串來(lái)表示給定的命題 也稱為翻譯命題 命題符號(hào)化的基本步驟 如何將自然語(yǔ)言符號(hào)化注意 1 分析出各原子命題 并逐個(gè)符號(hào)化 2 找出各聯(lián)結(jié)詞 把原子命題逐個(gè)聯(lián)結(jié)起來(lái) 簡(jiǎn)單命題 復(fù)合命題 句子 段落 篇章 1 必要時(shí)可以進(jìn)行改述 即改變?cè)瓉?lái)的敘述方式 但要保證表達(dá)意思一致 2 需要的括號(hào)不能省略 而可以省略的括號(hào) 在需要提高公式可讀性時(shí)亦可不省略 3 要注意語(yǔ)句的形式化未必是唯一的 46 三 命題符號(hào)化例子 分析并符號(hào)化 強(qiáng)調(diào)在進(jìn)行命題符號(hào)化以前 必須明確含義 刪除歧義 這是命題翻譯的關(guān)鍵之點(diǎn) 教材P10 P11例題1 自學(xué) 例題2 自學(xué) 例題3 自學(xué) 例題4 自學(xué) 例題5 自學(xué) 例題6 自學(xué) 舉例 例1 說(shuō)離散數(shù)學(xué)無(wú)用且枯燥無(wú)味是不對(duì)的 例2 如果小張與小王都不去 則小李去 首先用字母表示原子命題 P 離散數(shù)學(xué)是無(wú)用的 Q 離散數(shù)學(xué)是枯燥無(wú)味的 該命題符號(hào)化為 P Q 首先用字母表示原子命題 P 小張去 Q 小王去 R 小李去 該命題符號(hào)化為 P Q R 48 三 命題符號(hào)化 例3 人不犯我 我不犯人 人若犯我 我必犯人 首先用字母表示原子命題 P 人犯我 Q 我犯人 該命題符號(hào)化為 P Q P Q 或?qū)懗?P Q 49 三 命題符號(hào)化 例4 若天不下雨 我就上街 否則在家 首先用字母表示原子命題 P 天下雨 Q 我上街 R 我在家 該命題符號(hào)化為 P Q P R 注意 中間的聯(lián)結(jié)詞一定是 而不是 因?yàn)樵}表示 天不下雨時(shí)我做什么 天下雨我又做什么 的兩種作法 其中有一種作法是假的 則我說(shuō)的就是假話 所以中間的聯(lián)結(jié)詞一定是 如果寫成 P Q P R 就表明兩種作法都是假的時(shí)候 我說(shuō)的才是假話 這顯然不對(duì) 命題符號(hào)化是很重要的 一定要掌握好 在命題推理中常常最先遇到的就是符號(hào)化一個(gè)問題 解決不好 等于說(shuō)推理的首要前提沒有了 50 練習(xí) 上海到北京的14次列車是下午五點(diǎn)半或六點(diǎn)半開除非你努力 否則你將失敗P 你努力 Q 你成功 異或 Q P或 P Q 51 1 4真值表與等價(jià)公式 一 命題公式的真值表定義1 4 2設(shè)A是命題公式 給所有命題變?cè)概梢唤M真值 稱為對(duì)A的一個(gè)賦值 也稱為一個(gè)解釋 將公式A在所有賦值之下的真值列成一張表 稱為A的真值表 構(gòu)造真值表的步驟 找出給定命題形式中的所有命題變?cè)?列出所有可能的賦值 按計(jì)算從前到后的順序列出命題公式的子公式 計(jì)算各子公式的值 直至最后計(jì)算命題形式的值 命題變?cè)?PQ P P QTTFTTFFTFTTTFFTF 命題公式 命題子公式 例如命題公式 P Q 的真值表如下所示 53 命題變?cè)娜≈到M合 由于對(duì)每個(gè)命題變?cè)梢杂袃蓚€(gè)真值 T F 被指派 所以有n個(gè)命題變?cè)拿}公式A P1 P2 Pn 的真值表有2n行 為了有序地列出公式的真值表 在對(duì)命題變?cè)鲋概蓵r(shí) 可以按照二進(jìn)制數(shù)的次序列表 補(bǔ)充 關(guān)于 二進(jìn)制數(shù) 見下頁(yè) 54 關(guān)于二進(jìn)制數(shù)簡(jiǎn)介 為了有序地列出A P1 P2 Pn 的真值表 可以將F看成0 將T看成1 按照二進(jìn)制數(shù)11 1 11 10 00 010 00 01 00 0 即十進(jìn)制的2n 1 2n 2 2 1 0 的次序進(jìn)行指派列真值表 十進(jìn)制數(shù)0123456789 二進(jìn)制01101110010111011110001001 注 有效數(shù)字前加0不影響數(shù)值 如000 0 001 1 010 10 011 11 55 關(guān)于二進(jìn)制數(shù)簡(jiǎn)介 如A P Q 的真值表可按照如下次序指派 11 T T 10 T F 01 F T 00 F F 如A P Q R 的真值表可按照如下次序指派 111 T T T 110 T T F 101 T F T 100 T F F 011 F T T 010 F T F 001 F F T 000 F F F 56 關(guān)于二進(jìn)制數(shù)簡(jiǎn)介 例如列出P Q R 的真值表 F F T T 57 二 等價(jià)公式 1 例子看下面三個(gè)公式的真值表從真值表可以看出 不論對(duì)P Q作何指派 都使得P Q P Q和 Q P的真值相同 即它們的真值表完全相同 表明它們之間彼此等價(jià)或邏輯相同 58 2 定義1 4 2 A B是含有命題變?cè)狿1 P2 Pn的命題公式 如不論對(duì)P1 P2 Pn作任何指派 都使得A和B的真值相同 則稱之為A與B等價(jià) 記作A B 顯然P Q P Q Q P 59 首先 G H的結(jié)果仍是一個(gè)命題公式 G H的結(jié)果不是命題公式 雙條件詞 是一種命題聯(lián)結(jié)詞 公式G H是命題公式 其中 是一種邏輯運(yùn)算 G H的結(jié)果仍是一個(gè)命題公式 邏輯等價(jià) 則是描述了兩個(gè)公式G與H之間的一種邏輯等價(jià)關(guān)系 G H表示 命題公式G等價(jià)于命題公式H G H的結(jié)果不是命題公式 其次 如果要求用計(jì)算機(jī)來(lái)判斷命題公式G H是否邏輯等價(jià) 即G H那是辦不到的 然而計(jì)算機(jī)卻可 計(jì)算 公式G H是否是永真公式 與 的區(qū)別 60 3 重要的等價(jià)公式 對(duì)合律 P P 雙否律 冪等律P P PP P P 結(jié)合律 P Q R P Q R P Q R P Q R 交換律P Q Q PP Q Q P 下面給出一些常用的等值式 其中很多是通常所說(shuō)的布爾代數(shù)或邏輯代數(shù)的主要組成部分 61 二 等價(jià)公式 分配律P Q R P Q P R P Q R P Q P R 吸收律P P Q PP P Q P 德 摩根定律 P Q P Q P Q P Q 同一律P F PP T P 零律P T TP F F 互補(bǔ)律P P TP P F P 今天下雨 Q 今天刮風(fēng) P Q 今天下雨或刮風(fēng)的否定 P Q 今天不下雨且今天不刮風(fēng) P Q 今天下雨且刮風(fēng)的否定 P Q 今天不下雨或今天不刮風(fēng) 62 二 等價(jià)公式 P43 P Q P Q P Q Q P P Q P Q Q P P Q P Q P Q P Q P Q P Q P Q R P Q R P Q P R 63 4 等價(jià)公式的證明方法 怎樣證明公式是等價(jià)的 方法1 用真值表 方法2 用重言式證明 見下一節(jié) 方法3 用公式的等價(jià)變換 定義1 4 3如果X是合式公式A的一部分 且X本身也是一合式公式 則稱X為公式A的子公式 如 A P Q R中P Q R P Q 64 定理1 4 1置換定律 等價(jià)代換定理 設(shè)X是合式公式A的子公式 Y是一命題公式 若X Y 如果將A中的X用Y來(lái)置換 則所得到公式B與公式A等價(jià) 即A B 從定理可見 一個(gè)命題公式A 經(jīng)過多次的置換 所得到的新公式與原公式等價(jià) 等價(jià)代換定理的用途 1 驗(yàn)證兩個(gè)命題公式等價(jià) 2 化簡(jiǎn)命題公式 3 判斷命題公式的類型 見第五節(jié) 65 等價(jià)代換定理用于證明公式的等價(jià) 例題1 求證吸收律P P Q P證明P P Q P F P Q 同一律 P F Q 分配律 P F 零律 P 同一律 66 等價(jià)代換定理用于證明公式的等價(jià) 例題2 求證 P Q P Q P證明 P Q P Q P Q P Q 公式E16 P Q P Q 摩根定律 P Q P Q 對(duì)合律 P Q Q 分配律 P T 互補(bǔ)律 P 同一律 公式E16 P Q P Q 67 補(bǔ)充 等價(jià)代換定理用于化簡(jiǎn)公式 化簡(jiǎn)語(yǔ)句 不會(huì)休息的人也不會(huì)工作 沒有豐富知識(shí)的人也不會(huì)工作 解 設(shè)P 某人會(huì)工作 Q 某人會(huì)休息 R 某人有豐富的知識(shí)語(yǔ)句符號(hào)化為 Q P R P Q P R P Q P R P P Q R P Q R 與語(yǔ)句 工作得好的人一定會(huì)休息并且有豐富的知識(shí) 具有相同的邏輯含義 公式E16 P Q P Q 68 練習(xí) 作業(yè)題 第12頁(yè) 5 7 第17頁(yè) 1 a d 第18頁(yè) 7 b d 8