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

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

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