離散數學-命題邏輯-1-左孝凌.pdf

離散數學 一 大連理工大學電信學部計算機學院 內容 數理邏輯 命題邏輯 謂詞邏輯 集合論 集合 關系 函數 代數系統(tǒng) 圖論 說明 學時 32 教材 左孝凌 李為鑑 劉永才 離散數學 上?？茖W 技術文獻出版社 作業(yè) 兩周交一次作業(yè) 考試 100 范圍 80 書上 60 課堂內容 成績 平時成績 考試成績 加分 課堂表現活躍 作業(yè)完成認真 完整 以及 其它體現該課程學習努力的行為 加分上限8分 第一篇 數理邏輯 第1章 命題邏輯 命題及其表示法 聯(lián)結詞 命題公式與翻譯 真值表和等價公式 重言式與蘊含式 全功能聯(lián)結詞集 對偶與范式 推理理論 1 1 命題及其表示法 在數理邏輯中把能判斷真假的陳述句稱為命題 一般 用大寫英文字母或大寫英文字母帶下標表示 命題的概念包含了以下3個要素 只有陳述句才有可能成為命題 而其它的語句 如 感嘆句 祈使句 疑問句等都不是命題 一個語句雖是陳述句 但不能判斷真假不是命題 雖然要求命題能判斷真假 但不要求現在就能確定 真假 將來可以確定真假也可以 命題的真值 一個命題表達的判斷結果稱為命題的真值 命題的真值有 真 和 假 兩種 分別用 True T 1 真 和False F 0 假 來表示 真 值為真的命題稱為真命題 真值為假的命題稱為 假命題 任何命題的真值是惟一的 判斷以下語句是否為命題 若是命題 確定其真值 解 命題 F 命題 待定 不是命題 祈使句 命題 T 命題 F 不是命 題 疑問句 命題 由上下文確定 不是 命題 悖論 上海是個小村莊 存在外星人 禁止吸煙 北京是中國的首都 4是素數或6是素數 今天你吃了嗎 11 1 100 我正在說謊 命題常元 命題變元 原子命題 復合命題 表示命題的小寫英文字母或帶下標的小寫英文字母常稱為命 題標識符 如果命題標識符表示一個具體 確定的命題 稱為命 題常元 命 題常元 如果命題標識符表示任意一個命題 稱為命題變元命題變元 命 題變元無確定的真值 命題是能判斷真假的陳述句 而命題變元代表任意的命題 其真值是不確定的 因而不是命題 如果一個命題不能再分解成更簡單的命題 則稱該命題為原 子命題 原 子命題 如果一個命題不是原子命題 稱該命題為復合命題復合命題 如果命題變元表示原子命題時 該命題變元稱為原子變元 1 2 命題聯(lián)結詞 在自然語言中 可以通過 如果 那么 不但 而且 這樣的連詞將簡單的陳述句聯(lián)結 成復合語句 同樣在命題邏輯當中 也可以通過命題 聯(lián)結詞將原子變元聯(lián)結起來表示復合命題 常用的邏輯聯(lián)結詞有五種 否定聯(lián)結詞 合取聯(lián) 結詞 析取聯(lián)結詞 條件聯(lián)結詞和雙條件聯(lián)結詞 1 否定聯(lián)結詞 定義1 2 1 設P為命題 則P的否定是一個 復合命題 記作 P 讀作 非P 或 P的否定 定義為 若P為T 則 P為F 若P為F 則 P的真值為T 表1 2 1 P P FT TF P和 P的關系如表1 2 1所示 叫做聯(lián)結詞 的真值表 聯(lián)結詞 也可以看作邏輯運算 它是一元運算 例 否定下列命題 P 王強是一名大學生 P 王強不是一名大學生 2 合取聯(lián)結詞 定義1 2 2 設P和Q均為命題 則P和Q的 合取是一個復合命題 記作P Q 讀 作 P與Q 或 P合取Q 定義為 當 且僅當P和Q均為T時 P Q的才為T 聯(lián)結詞 的真值表如表1 2 2所示 聯(lián)結詞 也可以看成邏輯 運算 它是二元邏輯運算 表1 2 2 PQP Q FFF FTF TFF TTT 例1 P 今天下雨 Q 明天下雨 則P Q 今天下雨并且明天下 雨 或 P Q 今天與明天都下雨 例2 P 我們去看電影 Q 房間里有桌子 則P Q 我們去看電影且房間里有 桌子 3 析取聯(lián)結詞 定義1 2 3 設P和Q均為命題 則 P和Q的析取是一個復合命題 記作P Q 讀作 P或Q 或者 P析取Q 定義為 當且僅 當P和Q均為F時 P Q才為F 表1 2 3 PQP Q FFF FTT TFT TTT 聯(lián)結詞 的真值表如表1 2 3所示 聯(lián)結詞 也可以看成邏輯運算 它是二元邏輯運算 析取聯(lián)結詞 與漢語中的 或 相似 但又不相 同 漢語中的或有可兼或與不可兼或 排斥或 的區(qū)分 例 在電視上看這場雜技或在劇場里看這場雜 技 不可兼 燈泡有故障或開關有故障 可兼 是可兼或 4 條件聯(lián)結詞 定義1 2 4 設P和Q均為命題 其條 件命題是個復合命題 記為 P Q 讀作 如果P 那么Q 或 若P 則Q 定義為 當且僅 當P為T Q為F時 P Q才為F P 稱為條件命題P Q的前件 Q稱 為條件命題P Q的后件 聯(lián)結詞 真值表如表1 4所示 聯(lián)結詞 也可以 看成邏輯運算 它是二元邏輯運算 表1 2 4 PQP Q FFT FTT TFF TTT 條件聯(lián)結詞 例1 如果某動物為哺乳動物 則它必為胎生 例2 如果我得到這本小說 那么我今夜就讀完它 例3 如果雪是黑的 那么太陽從西方出來 它們都可以表示為P Q的形式 5 雙條件聯(lián)結詞 定義1 2 5 設P和Q均為命題 其 復合命題P Q稱為雙條件命 題 讀作 P雙條件Q 或者 P當且僅當Q 定義為 當 且僅當P和Q的真值相同時 P Q為T 表1 2 5 PQP Q FFT FTF TFF TTT 聯(lián)結詞 的真值表如表1 2 5所示 聯(lián)結詞 也可以理解成邏輯運算 它是二元邏輯運算 雙條件聯(lián)結詞 雙條件聯(lián)結詞表示的是一個充分必要關系 與前面所 述相同 也可以不必顧及其前因后果 而只根據聯(lián)結 詞的定義來確定其真值 例1 兩個三角形全等 當且僅當它們的三組對應邊相等 例2 燕子飛回南方 春天來了 例3 2 2 4當且僅當雪是白的 它們都可以表示為P Q 1 3 命題公式與翻譯 把命題常量 命題變量按照一定的邏輯順序用命題聯(lián)結詞連接起來 就構成了命題演算的合式公式 也叫命題公式 當使用聯(lián)結詞集 時 合式公式定義如下 定義1 3 1 按下列規(guī)則構成的符號串稱為命題演算的合式公式 也稱為 命題公式 簡稱公式 單個命題變元和常元是合式公式 如果A是合式公式 那么 A是合式公式 如果A和B是合式公式 那么 A B A B A B 和 A B 是合 式公式 當且僅當有限次地應用了 所得到的符號串是合式公式 說明 命題公式一般的用大寫的英文字母A B C 表示 依照這個定義 下列符號串是合式公式 p q p q p p q p q q r s t 下列符號串不是合式公式 p q q p q p q q 定義1 3 1給出合式公式定義的方法稱為歸納定義 它包括三部分 基礎 歸納和界限 定義1 3 1中的 是基礎 和 是歸納 是 界限 下文中還將多次出現這種形式的定義 一般地說 命題公式中包含命題變元 因而無法計算其真值 所以不 是命題 命題公式中的命題變元 也叫命題公式的分量 優(yōu)先級 為方便起見 對命題公式約定如下 最外層括號可以省略 規(guī)定聯(lián)結詞的優(yōu)先級由高到低依次為 按此優(yōu)先級別 如果去掉括號 不改變原 公式運算次序 也可以省掉這些括號 符號化 翻譯 例1 他或者騎自行車去學校 或者乘公共汽車去學 校 解 令P 他騎自行車去學校 Q 他乘公共汽車去學校 此命題中的或是不可兼或 所以不能符號化為 P Q 而要符號化為 P Q 或 P Q P Q 符號化 翻譯 例2 符號化下列命題 只要天下雨 我就回家 只有天下雨 我才回家 除非天下雨 否則我不回家 僅當天下雨 我才回家 設P 天下雨 Q 我回家 則 符號化為P Q 均符號化為 Q P 或等價形式 P Q 符號化 翻譯 練習 自然語言形式化舉例 如果天不下雨并且不刮風 我就去書店 小王邊走邊唱 除非a能被2整除 否則a不能被4整除 此時 小綱要么在學習 要么在玩游戲 如果天不下雨 我們去打籃球 除非班上有 會 練習解答練習解答 設P 今天天下雨 Q 今天天刮風 R 我去書店 則原命 題符號化為 P Q R 設P 小王走路 Q 小王唱歌 則原命題符號化為 P Q 設P a能被2整除 Q a能被4整除 則原命題符號化 為 P Q 或者Q P 設P 小剛在學習 Q 小剛在玩游戲 則原命題符號化 為 P Q P Q 或 P Q P Q 設P 今天天下雨 Q 我們去打籃球 R 今天班上有 會 則原命題符號化為 R P Q