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

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

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