離散數(shù)學(xué)-命題邏輯-1-左孝凌.pdf

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