ch01命題邏輯.ppt

命題邏輯謂詞邏輯非經(jīng)典邏輯 數(shù)理邏輯 數(shù)理邏輯概述 數(shù)理邏輯是用數(shù)學(xué)的方法研究思維規(guī)律的一門學(xué)科 由于它使用了一套符號(hào) 簡(jiǎn)潔的表達(dá)出各種推理的邏輯關(guān)系 因此數(shù)理邏輯一般又稱為符號(hào)邏輯 數(shù)理邏輯和計(jì)算機(jī)的發(fā)展有著密切的聯(lián)系 它為機(jī)器證明 自動(dòng)程序設(shè)計(jì) 計(jì)算機(jī)輔助設(shè)計(jì)等計(jì)算機(jī)應(yīng)用和理論研究提供必要的理論基礎(chǔ) 數(shù)理邏輯的發(fā)展前期 前史時(shí)期 古典形式邏輯時(shí)期 亞里斯多德的直言三段論理論初創(chuàng)時(shí)期 邏輯代數(shù)時(shí)期 17世紀(jì)末 1 資本主義生產(chǎn)力大發(fā)展 自然科學(xué)取得了長(zhǎng)足的進(jìn)步 數(shù)學(xué)在認(rèn)識(shí)自然 發(fā)展技術(shù)方面起到了相當(dāng)重要的作用 2 人們希望使用數(shù)學(xué)的方法來研究思維 把思維過程轉(zhuǎn)換為數(shù)學(xué)的計(jì)算 數(shù)理邏輯的發(fā)展前期 3 萊布尼茲 Leibniz 1646 1716 完善三段論 提出了建立數(shù)理邏輯或者說理性演算的思想 提出將推理的正確性化歸于計(jì)算 這種演算能使人們的推理不依賴于對(duì)推理過程中的命題的含義內(nèi)容的思考 將推理的規(guī)則變?yōu)檠菟愕囊?guī)則 使用一種符號(hào)語言來代替自然語言對(duì)演算進(jìn)行描述 將符號(hào)的形式和其含義分開 使得演算從很大程度上取決與符號(hào)的組合規(guī)律 而與其含義無關(guān) 數(shù)理邏輯的發(fā)展前期 4 布爾 G Boole 1815 1864 代數(shù) 將有關(guān)數(shù)學(xué)運(yùn)算的研究的代數(shù)系統(tǒng)推廣到邏輯領(lǐng)域 布爾代數(shù)既是一種代數(shù)系統(tǒng) 也是一種邏輯演算 數(shù)理邏輯的奠基時(shí)期 弗雷格 G Frege 1848 1925 概念語言 一種按算術(shù)的公式語言構(gòu)成的純思維公式語言 1879 的出版標(biāo)志著數(shù)理邏輯的基礎(chǔ)部分 命題演算和謂詞演算的正式建立 皮亞諾 GiuseppePeano 1858 1932 用一種新的方法陳述的算術(shù)原理 1889 提出了自然數(shù)算術(shù)的一個(gè)公理系統(tǒng) 數(shù)理邏輯的奠基時(shí)期 羅素 BertrandRussell 1872 1970 數(shù)學(xué)原理 與懷特黑合著 1910 1912 1913 從命題演算和謂詞演算開始 然后通過一元和二元命題函項(xiàng)定義類和關(guān)系的概念 建立了抽象的類演算和關(guān)系演算 由此出發(fā) 在類型論的基礎(chǔ)上用連續(xù)定義和證明的方式引出了數(shù)學(xué) 主要是算術(shù) 中的主要概念和定理 數(shù)理邏輯的奠基時(shí)期 邏輯演算的發(fā)展 甘岑 G Gentzen 的自然推理系統(tǒng) NaturalDeductionSystem 邏輯演算的元理論 公理的獨(dú)立性 一致性 完全性等 各種各樣的非經(jīng)典邏輯的發(fā)展 路易斯 Lewis 1883 1964 的模態(tài)邏輯 實(shí)質(zhì)蘊(yùn)含怪論和嚴(yán)格蘊(yùn)含 相干邏輯等 盧卡西維茨的多值邏輯等 第1章命題邏輯 命題邏輯研究的是以原子命題為基本單位的推理演算 其特征在于 研究和考查邏輯形式時(shí) 我們把一個(gè)命題只分析到其中所含的原子命題成分為止 通過這樣的分析可以顯示出一些重要的邏輯形式 這種形式和有關(guān)的邏輯規(guī)律就屬于命題邏輯 第1章命題邏輯 內(nèi)容提要 1 命題邏輯的基本概念 命題聯(lián)結(jié)詞2 命題公式 自然語言的形式化3 命題公式的等值和蘊(yùn)含4 范式5 聯(lián)結(jié)詞的完備集6 推理理論7 命題邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用 1 1命題與聯(lián)結(jié)詞 1 1 1命題與命題變?cè)x1 1能夠分辨真假的陳述句叫做命題 Proposition 該定義有兩層含義 1 命題是陳述句 其他的語句 如疑問句 祈使句 感嘆句均不是命題 2 這個(gè)陳述句表示的內(nèi)容可以分辨真假 而且不是真就是假 不能不真也不假 也不能既真又假 1 1命題與聯(lián)結(jié)詞 作為命題的陳述句所表示的判斷結(jié)果稱為命題的真值 真值只取兩個(gè)值 真或假 凡是與事實(shí)相符的陳述句是真命題 而與事實(shí)不符合的陳述句是假命題 通常用1 或字母T 表示真 用0 或字母F 表示假 1 1命題與聯(lián)結(jié)詞 例1 1判斷下列語句是否為命題 并指出其真值 1 北京是中國的首都 2 5可以被2整除 3 2 2 5 4 請(qǐng)勿吸煙 5 烏鴉是黑色的嗎 6 這個(gè)小男孩多勇敢啊 7 地球外的星球上存在生物 8 我正在說謊 1 1命題與聯(lián)結(jié)詞 注意 一個(gè)語句本身是否能分辨真假與我們是否知道它的真假是兩回事 也就是說 對(duì)于一個(gè)句子 有時(shí)我們可能無法判定它的真假 但它本身卻是有真假的 那么這個(gè)語句是命題 否則就不是命題 悖論不是命題 1 1命題與聯(lián)結(jié)詞 命題的分類原子命題 AutomicProposition 是指不能再分解為更簡(jiǎn)單命題的命題 復(fù)合命題 CompoundProposition 是指由若干命題用聯(lián)結(jié)詞組成的新命題 例如 雪是白的 是原子命題 昨天下雨 而且打雷 如果明天天晴我就去打球或者游泳 都是復(fù)合命題 1 1命題與聯(lián)結(jié)詞 定義1 2真值確定的原子命題稱為命題常元 PropositionalConstant 真值不確定的原子命題稱為命題變?cè)?PropositionalVariable 如果命題符號(hào)P代表命題常元?jiǎng)t意味它是某個(gè)具體命題的符號(hào)化 如果P代表命題變?cè)獎(jiǎng)t意味著它可指代任何具體命題 本書中如果沒有特別指明 通常來說命題符號(hào)P等是命題變?cè)?即可指代任何命題 1 1命題與聯(lián)結(jié)詞 1 1 2命題聯(lián)結(jié)詞及真值表否定詞 或 否定詞 Negation 是一元聯(lián)結(jié)詞 相當(dāng)于自然語言中的 非 不 等 真值表如右圖 1 1命題與聯(lián)結(jié)詞 合取詞 合取詞 Conjunction 是二元聯(lián)結(jié)詞 相當(dāng)于自然語言中的 與 并且 而且 也 等 真值表如右圖 1 1命題與聯(lián)結(jié)詞 析取詞 析取詞 Disjunction 是二元聯(lián)結(jié)詞 相當(dāng)于自然語言中的 或 要么 要么 等 真值表如右圖 1 1命題與聯(lián)結(jié)詞 蘊(yùn)含詞 蘊(yùn)含詞 Implication 是二元聯(lián)結(jié)詞 相當(dāng)于自然語言中的 若 則 如果 就 只有 才 真值表如右圖 1 1命題與聯(lián)結(jié)詞 等價(jià)詞 等價(jià)詞 Equivalence 是二元聯(lián)結(jié)詞 相當(dāng)于自然語言中的 等價(jià) 當(dāng)且僅當(dāng) 充要條件 等 真值表如右圖 我們給聯(lián)結(jié)詞規(guī)定優(yōu)先級(jí)順序 的優(yōu)先級(jí)最高 接著依次是 和 1 2命題公式 1 2 1命題公式與命題符號(hào)化定義1 3命題公式 PropositionalFormula 歸納定義如下 1 命題變?cè)敲}公式 2 如果 是命題公式 則 也是命題公式 3 如果 和 是命題公式 則 均是命題公式 4 只有有限次地利用 1 3 形成的符號(hào)串才是命題公式 1 2命題公式 例如 P Q P P Q 等都是命題公式 而CP Q R P等不是命題公式 命題邏輯里討論的對(duì)象是命題公式 而日常生活中的推理問題是用自然語言描述的 因此要進(jìn)行推理演算必須先把自然語言符號(hào)化 或形式化 成邏輯語言 即命題公式 然后再根據(jù)邏輯演算規(guī)律進(jìn)行推理演算 1 2命題公式 例1 2將下列用自然語言描述的命題符號(hào)化 1 我和他既是弟兄又是同學(xué) 2 我和你之間至少有一個(gè)要去海南島 3 如果他沒來見你 那么他或者是生病了 或者是不在本地 4 n是偶數(shù)當(dāng)且僅當(dāng)它能被2整除 1 2命題公式 從以上例子中可以看出 所謂命題符號(hào)化是指把一個(gè)用自然語言敘述的命題相應(yīng)地寫成由命題變?cè)?聯(lián)結(jié)詞和圓括號(hào)表示的命題公式 符號(hào)化應(yīng)該注意下列事項(xiàng) 確定給定句子是否為命題 句子中連詞是否為命題聯(lián)結(jié)詞 要正確地表示原子命題和適當(dāng)選擇命題聯(lián)結(jié)詞 1 2命題公式 1 2 2命題公式的分類變?cè)M 設(shè)n元公式 中所含有的不同命題元為P1 P2 Pn 我們把這些命題變?cè)M成的變?cè)M P1 P2 Pn 稱為 的變?cè)M 完全指派 的變?cè)M P1 P2 Pn 的任意一組確定的值都稱為該公式 關(guān)于該變?cè)M P1 P2 Pn 的完全指派 1 2命題公式 部分指派 如果僅對(duì)變?cè)M中部分變?cè)x以確定的值 其余變?cè)獩]有賦以確定的值 則這樣的一組值稱為該公式 關(guān)于該變?cè)M P1 P2 Pn 的部分指派 例1 3設(shè) P Q R S 其變?cè)M為 P Q R S P Q R S 1 0 1 1 為 的完全指派 P Q R S 0 0 1 S 為 的部分指派 1 2命題公式 定義1 4對(duì)于任一公式 凡使得 為真的指派 不管是完全指派還是部分指派 都稱為 的成真指派 凡使得 為假的指派 也不管是完全指派還是部分指派 都稱為 的成假指派 例1 4設(shè) P Q R R S 則完全指派 P Q R S 0 1 0 1 和部分指派 P Q R S 0 1 0 S 都是 的成真指派 而指派 P Q R S 1 0 1 0 為 的成假指派 1 2命題公式 子公式 SubFormula 設(shè) 為命題公式 為 中的一個(gè)連續(xù)的符號(hào)串 且 為命題公式 則稱 為 的子公式 例如 設(shè)公式 P Q P Q R 則 P Q Q R P Q R 等都是 的子公式 而 P Q P Q Q R 等都不是 的子公式 因?yàn)樗鼈儽旧聿皇枪?1 2命題公式 用歸納法不難證明 對(duì)于含有n個(gè)命題變?cè)墓?有2n個(gè)完全指派 即在該公式的真值表中有2n行 為方便構(gòu)造真值表 特約定如下 命題變?cè)醋值湫蚺帕?對(duì)每個(gè)指派 以二進(jìn)制數(shù)從小到大或從大到小順序列出 若公式較復(fù)雜 可先列出各子公式的真值 若有括號(hào) 則應(yīng)從里層向外層展開 最后列出所求公式的真值 1 2命題公式 例1 5利用真值表求命題公式 P Q R 的成真指派和成假指派 1 2命題公式 重言式 永真式 Tautology 若公式 的所有完全指派均是成真指派 則公式 稱為重言式或永真式 矛盾式 永假式 Absurdity 若公式 的所有完全指派均是成假指派 則公式 稱為矛盾式或永假式 可滿足式 Contingency 若公式 中有成真指派 則公式 稱為可滿足式 1 2命題公式 對(duì)定義的幾點(diǎn)說明1 是可滿足式的等價(jià)定義是 至少存在一個(gè)成真指派 2 重言式一定是可滿足式 但反之不真 因而 若公式 是可滿足式 且它至少存在一個(gè)成假指派 則稱 為非重言式的可滿足式 1 2命題公式 3 真值表可用來判斷公式的類型 若真值表最后一列全為1 則公式為重言式 若真值表最后一列全為0 則公式為矛盾式 若真值表最后一列中至少有一個(gè)1 則公式為可滿足式 1 2命題公式 例1 6判斷下列公式的類型 1 P Q Q解令 P Q Q 1 2命題公式 2 Q P P Q 解令 Q P P Q 1 2命題公式 3 P Q P Q R 解令 P Q P Q R 1 3等值演算 1 3 1等值式定義1 8設(shè) 是兩個(gè)命題公式 若 構(gòu)成的等價(jià)式 為重言式 則稱公式 與 是等值 Equivalent 的 記作 1 3等值演算 注意 定義中給出的符號(hào) 與 是兩個(gè)完全不同的符號(hào) 不是命題聯(lián)結(jié)詞而是公式間的關(guān)系符號(hào) 不表示一個(gè)公式 即不代表命題 它表示公式 與公式 有等值關(guān)系 而 是命題聯(lián)結(jié)詞 是一個(gè)公式 表示某個(gè)命題 然而這兩者之間有密切的聯(lián)系 即 的充要條件是公式 為重言式 1 3等值演算 判斷兩個(gè)公式 與 是否等值 其中最直接的方法是用真值表法判斷 是否為重言式 例1 7判斷 P Q 與 P Q這兩個(gè)命題公式是否等值 1 3等值演算 下面給出16組重要的等值式 在后面的推理演算中以大寫字母E加以引用 這些等值式也稱作命題定律 其正確性可以用真值表加以證明 1 雙重否定律 2 等冪律 1 3等值演算 3 交換律 4 結(jié)合律 5 分配律 對(duì) 的分配律 對(duì) 的分配律 1 3等值演算 6 德摩根律 7 吸收律 8 零一律 1 1 0 0 1 3等值演算 9 同一律 0 1 10 排中律 1 11 矛盾律 0 12 蘊(yùn)含等值式 1 3等值演算 13 假言易位 14 等價(jià)等值式 15 等價(jià)否定等值式 16 歸謬論 1 3等值演算 例1 8證明蘊(yùn)含等值式 證明 1 3等值演算 1 3 2等值演算及幾個(gè)重要定理由已知的等值式推演出另外一些等值式的過程稱為等值演算 定義1 9設(shè) 是一個(gè)命題公式 P1 P2 Pn是其中出現(xiàn)的所有命題變?cè)?1 用某些公式代換 中的某些命題變?cè)?2 若用公式A代換Pi 則必須用A代換 中所有的Pi 那么 由此而得到的新公式 叫做公式 的一個(gè)代換實(shí)例 1 3等值演算 例如 設(shè)公式 P R P 用Q S代換其中P 可得公式 Q S R Q S 公式 是 的一個(gè)代換實(shí)例 定理1 1 代入定理 對(duì)于重言式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入 得到的仍是重言式 1 3等值演算 于是 若對(duì)于等值式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入 則仍得到等值式 定理1 2 置換定理 設(shè)A是公式 的一個(gè)子公式且A B 如果將公式 中的子公式A置換成公式B之后 得到的公式是 則 1 3等值演算 比較代入定理和置換定理的區(qū)別 1 3等值演算 例1 9用等值演算法證明 P Q R P R Q R 證明 P Q R P Q R 蘊(yùn)含等值式 代入定理 P Q R 德摩根律 置換定理 P R Q R 分配律 代入定理 P R Q R 蘊(yùn)含等值式 置換定理 P R Q R 蘊(yùn)含等值式 置換定理 1 3等值演算 例1 10用等值演算法判斷下列公式的類型 1 P Q P Q解 P Q P Q P Q P Q P Q P Q P Q P Q P Q P Q P P Q P Q 1 Q P Q Q Q P 1 P 1因此該公式是重言式 1 3等值演算 2 P P Q R解 P P Q R P P Q R P P Q R 0 R 0因此該公式是矛盾式 1 3等值演算 3 P P Q P Q 解P P Q P Q P P Q P Q P P P Q P Q P 0 Q P Q P Q P Q P 1 P從最后結(jié)果可以看出該公式既不是重言式 也不是矛盾式 而是可滿足式 1 3等值演算 練習(xí)化簡(jiǎn)公式 P Q P Q 1 3等值演算 例1 11設(shè)有A B C D四人做百米競(jìng)賽 觀眾甲 乙 丙分別對(duì)比賽的名次進(jìn)行了預(yù)測(cè) 甲說C第一 B第二 乙說C第二 D第三 丙說A第二 D第四 比賽結(jié)束后發(fā)現(xiàn)甲 乙 丙每人報(bào)告的情況都是各對(duì)一半 試問實(shí)際名次如何 無并列者 1 3等值演算 解設(shè)Pi Qi Ri Si分別表示A B C D是第i i 1 2 3 4 名 由于甲 乙 丙每人報(bào)告的情況都各對(duì)一半 故有下面三個(gè)等值式 R1 Q2 R1 Q2 1 R2 S3 R2 S3 1 P2 S4 P2 S4 1因?yàn)橹匮允降暮先∪詾橹匮允?所以 1 即1 R1 Q2 R1 Q2 R2 S3 R2 S3 R1 Q2 R2 S3 R1 Q2 R2 S3 R1 Q2 R2 S3 R1 Q2 R2 S3 1 3等值演算 由于C不能既第一又第二 B和C不能并列第二 所以R1 Q2 R2 S3 0 R1 Q2 R2 S3 0于是得 R1 Q2 R2 S3 R1 Q2 R2 S3 1再將 與 合取得 1 即1 P2 S4 P2 S4 R1 Q2 R2 S3 R1 Q2 R2 S3 P2 S4 R1 Q2 R2 S3 P2 S4 R1 Q2 R2 S3 P2 S4 R1 Q2 R2 S3 P2 S4 R1 Q2 R2 S3 1 3等值演算 由于A B不能同時(shí)第二 D不能第三又第四 所以P2 S4 R1 Q2 R2 S3 0 P2 S4 R1 Q2 R2 S3 0 P2 S4 R1 Q2 R2 S3 0于是可得 P2 S4 R1 Q2 R2 S3 1因此C第一 A第二 D第三 B第四 1 3等值演算 定義1 10如果命題公式 中只出現(xiàn)命題變?cè)?命題常元 命題聯(lián)結(jié)詞 和 則稱 為限制性命題公式 定義1 11在限制性公式 中 將聯(lián)結(jié)詞 換成 將 換成 將0換成1 將1換成0 所得到的公式稱為 的對(duì)偶式 記為 1 3等值演算 顯然 和 互為對(duì)偶式 例如 公式 P Q R 與公式 P Q R 互為對(duì)偶式 定理1 3設(shè) 和 是互為對(duì)偶的兩個(gè)公式 P1 P2 Pn是其命題變?cè)?則 P1 P2 Pn P1 P2 Pn 定理1 4 對(duì)偶定理 設(shè) P1 P2 Pn 和 P1 P2 Pn 是兩個(gè)公式 若 則 1 4范式 原子命題 P 及其否定 P 統(tǒng)稱文字 文字或者一些文字的合取稱為質(zhì)合取式 文字或者一些文字的析取稱為質(zhì)析取式 或稱子句 P與 P稱為互補(bǔ)對(duì) 例如 P P P Q P Q R等都是質(zhì)合取式 P Q P Q P Q R等都是質(zhì)析取式 1 4范式 定理1 5 1 質(zhì)合取式為矛盾式的充要條件 它包含有一個(gè)互補(bǔ)對(duì) 2 質(zhì)析取式為重言式的充要條件 它包含有一個(gè)互補(bǔ)對(duì) 1 4范式 1 4 1析取范式與合取范式定義1 12若干個(gè)質(zhì)合取式的析取式稱為析取范式 亦即該公式具有形式 1 2 n 其中 i i 1 2 n 為質(zhì)合取式 定義1 13若干個(gè)質(zhì)析取式的合取式稱為合取范式 亦即該公式具有形式 1 2 n 其中 i i 1 2 n 為質(zhì)析取式 1 4范式 例如 命題公式 P Q P Q 是析取范式 而命題公式 P R P Q R P R 是合取范式 1 4范式 定理1 6 范式存在定理 任一命題公式都存在著與之等值的析取范式和合取范式 下面給出求任一公式的析取范式和合取范式的步驟 1 利用蘊(yùn)含等值式和等價(jià)等值式消去公式中的聯(lián)結(jié)詞 和 2 利用德摩根律和雙重否定律將聯(lián)結(jié)詞 向內(nèi)深入 使之只作用于命題變?cè)?3 利用分配律將公式化為所需要的范式 1 4范式 例1 12求 P Q R P的析取范式和合取范式 解 1 求合取范式 P Q R P P Q R P 消去 P Q R P P Q R P 深入 P Q R P P Q R P P Q P R P 對(duì) 的分配律 再利用交換律和等冪律得 P Q P R P P Q R P 可見 P Q R P 也是原公式的合取范式 這說明與某個(gè)命題公式等值的合取范式不是惟一的 1 4范式 2 析取范式用 對(duì) 的分配律就可得到析取范式 即 P Q R P P Q R P P R Q R P 對(duì) 分配律 最后結(jié)果為原公式的析取范式 利用交換律和吸收律得P Q R 此公式也是原公式的析取范式 由此可見 與命題公式等值的析取范式也不是惟一的 1 4范式 利用析取范式和合取范式可以判定一個(gè)命題公式是重言式還是矛盾式 定理1 7 1 公式 為重言式的充要條件是 的合取范式中每一質(zhì)析取式至少包含一個(gè)互補(bǔ)對(duì) 2 公式 為矛盾式的充要條件是 的析取范式中每一質(zhì)合取式至少包含一個(gè)互補(bǔ)對(duì) 1 4范式 例1 13判別公式 P Q P Q是否為重言式或矛盾式 解 P Q P Q P Q P Q P Q P Q P Q P Q P P Q Q P Q 在公式的合取范式中 每一個(gè)質(zhì)析取式均含有互補(bǔ)對(duì) 因此原式為重言式 1 4范式 1 4 2主析取范式與主合取范式定義1 14在含n個(gè)命題變?cè)馁|(zhì)合取式 質(zhì)析取式 中 若每個(gè)命題變?cè)c其否定不同時(shí)存在 而二者之一必出現(xiàn)且僅出現(xiàn)一次 且第i個(gè)命題變?cè)蚱浞穸ǔ霈F(xiàn)在從左算起的第i位上 若命題變?cè)獰o下標(biāo) 則按字典順序排序 這樣的質(zhì)合取式 質(zhì)析取式 稱為極小項(xiàng) 極大項(xiàng) 1 4范式 n個(gè)命題變?cè)部僧a(chǎn)生2n個(gè)不同的極小項(xiàng) 其中每個(gè)極小項(xiàng)都有且僅有一個(gè)成真指派 若在極小項(xiàng)中 將命題變?cè)闯? 命題變?cè)姆穸闯? 則每個(gè)極小項(xiàng)惟一地對(duì)應(yīng)一個(gè)二進(jìn)制數(shù) 若把該二進(jìn)制數(shù)轉(zhuǎn)化成十進(jìn)制數(shù)為i 并將所對(duì)應(yīng)極小項(xiàng)記作mi 類似地 n個(gè)命題變?cè)部僧a(chǎn)生2n個(gè)不同的極大項(xiàng) 每個(gè)極大項(xiàng)只有一個(gè)成假指派 將其對(duì)應(yīng)的十進(jìn)制數(shù)i做極大項(xiàng)的下標(biāo) 記作Mi 1 4范式 例如 兩個(gè)命題變?cè)狿 Q共可產(chǎn)生4個(gè)極小項(xiàng) 也可以產(chǎn)生4個(gè)極大項(xiàng) 類似地 由三個(gè)命題變?cè)狿 Q R共可產(chǎn)生8個(gè)極小項(xiàng) 也可以產(chǎn)生8個(gè)極大項(xiàng) 定理1 8設(shè)mi和Mi是命題變?cè)狿1 P2 Pn形成的極小項(xiàng)和極大項(xiàng) 則 mi Mi Mi mi 1 4范式 定義1 15設(shè)命題公式 中含n個(gè)命題變?cè)?如果 的析取范式 合取范式 中的質(zhì)合取式 質(zhì)析取式 都是極小項(xiàng) 極大項(xiàng) 則稱該析取范式 合取范式 為 的主析取范式 主合取范式 1 4范式 例1 15求公式 P R P Q 的主析取范式和主合取范式 1 4范式 公式所在的列有三個(gè)1 它們分別對(duì)應(yīng)于編碼001 110 111 因此所求的主析取范式為 m1 m6 m7即 P Q R P Q R P Q R 公式所在的列有五個(gè)0 它們分別對(duì)應(yīng)于編碼000 010 011 100 101 因此所求的主合取范式為 M0 M2 M3 M4 M5即 P Q R P Q R P Q R P Q R P Q R 1 4范式 定理1 9任何一個(gè)不為矛盾式 重言式 的命題公式都存在著與之等值的主析取范式 主合取范式 并且是惟一的 從定理中可看出 矛盾式的主析取范式是空公式 定義它為0 其主合取范式必由所有極大項(xiàng)的合取構(gòu)成 同理重言式的主合取范式也是空公式 定義它為1 其主析取范式必由所有極小項(xiàng)的析取構(gòu)成 因此 利用一個(gè)公式的主范式可以判別這個(gè)公式是否為重言式或矛盾式 1 4范式 求一個(gè)給定公式的主析取范式和主合取范式除了可以用真值表法 還可以用類似于求范式的方法 下面給出求解步驟 1 利用蘊(yùn)含等值式和等價(jià)等值式消去公式中的聯(lián)結(jié)詞 和 2 利用德摩根律和雙重否定律將聯(lián)結(jié)詞 向內(nèi)深入 使之只作用于命題變?cè)?3 利用分配律將公式化為析取范式或合取范式 1 4范式 4 利用同一律消去矛盾的質(zhì)合取式 重言的質(zhì)析取式 5 利用等冪律消去相同的質(zhì)合取式 質(zhì)析取式 以及質(zhì)合取式 質(zhì)析取式 中相同的合取項(xiàng) 析取項(xiàng) 6 利用同一律 分配律將不包含某一命題變?cè)馁|(zhì)合取式 質(zhì)析取式 置換為包含這一命題變?cè)馁|(zhì)合取式 質(zhì)析取式 直到每一質(zhì)合取式 質(zhì)析取式 成為極小項(xiàng) 極大項(xiàng) 為止 例如P Q P Q R R P Q R P Q R 1 4范式 例1 15利用求主范式的方法判別公式 P Q P Q是否為重言式或矛盾式 解求公式的主析取范式為 P Q P Q P Q P Q P Q P Q P Q P Q P Q P Q Q P P Q P Q P Q P Q P Q m0 m1 m2 m3由于公式的主析取范式包含了所有的極小項(xiàng) 因此原公式為重言式 1 4范式 當(dāng)然 利用求主合取范式也可以得到同樣的結(jié)論 即 P Q P Q P Q P Q P Q P Q P Q P Q P P Q Q P Q 1 1 1由于公式的主合取范式是一個(gè)空公式 因此原公式為重言式 1 4范式 例1 16求公式 P R P Q 的主析取范式和主合取范式 解令 P R P Q 1 求主合取范式 P R P Q P Q P Q Q R P Q R R P Q R R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R M0 M2 M3 M4 M5此即 的主合取范式 1 4范式 2 求主析取范式顯然 余下的極大項(xiàng)的合取式便是 的主合取范式 即 P Q R P Q R P Q R 對(duì) 求否定并利用定理1 8 便得到 的主析取范式為 P Q R P Q R P Q R m1 m6 m7由上可以看出 公式 既不是重言式也不是矛盾式 因而是一個(gè)可滿足式 1 4范式 例1 17某單位要在甲 乙 丙三人中選派1 2名出差 選派時(shí)需滿足如下條件 1 若甲去 則丙同去 2 若乙去 則丙不能去 3 若丙不去 則甲或乙可以去 問有幾種選派方案 解設(shè)P 派甲去出差 Q 派乙去出差 R 派丙去出差 由已知條件可得公式 P R Q R R P Q 1 4范式 經(jīng)過演算可得 P R Q R R P Q P Q R P Q R P Q R 該公式主析取范式包含3個(gè)極小項(xiàng) 因此可知有3種選派方案 丙去 甲和乙不去 乙去 甲和丙不去 甲和丙去 乙不去 1 5聯(lián)結(jié)詞的完備集 定義1 16稱F 0 1 n 0 1 為n元真值函數(shù) TruthValueFunction 在這個(gè)定義中 F的自變量為n個(gè)命題變?cè)?定義域 0 1 n 00 0 00 1 11 1 即 0 1 n中元素為由0 1組成的全體長(zhǎng)為n的符號(hào)串 值域?yàn)?0 1 n個(gè)命題變?cè)部蓸?gòu)成22n個(gè)不同的真值函數(shù) 含命題變?cè)狿的1元真值函數(shù)共有4個(gè) 含兩個(gè)命題變?cè)狿 Q的真值函數(shù)共有16個(gè) 1 5聯(lián)結(jié)詞的完備集 定義1 17設(shè)S是一個(gè)聯(lián)結(jié)詞集合 如果任何n n 1 元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示 則稱S是聯(lián)結(jié)詞完備集 AdequateSetofConnectives 定理1 10S 是聯(lián)結(jié)詞完備集 證因?yàn)槿魏蝞 n 1 元真值函數(shù)都與惟一的一個(gè)主析取范式等值 而在主析取范式中僅含聯(lián)結(jié)詞 所以S 是聯(lián)結(jié)詞完備集 1 5聯(lián)結(jié)詞的完備集 推論1 1以下聯(lián)結(jié)詞集都是完備集 1 S1 2 S2 3 S3 4 S4 5 S5 1 5聯(lián)結(jié)詞的完備集 證 1 2 的成立是顯然的 3 由于S 是聯(lián)結(jié)詞完備集 因而任何真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞的公式表示 同時(shí)對(duì)于任意公式A和B A B A B A B 因而任意真值函數(shù)都可以由僅含S3 中的聯(lián)結(jié)詞的公式表示 所以S3是聯(lián)結(jié)詞完備集 1 5聯(lián)結(jié)詞的完備集 可以證明恒取0值的真值函數(shù) 即與矛盾式等值的真值函數(shù) 不能用僅含聯(lián)結(jié)詞集 中的聯(lián)結(jié)詞的公式表示 因而 不是聯(lián)結(jié)詞完備集 由此可知 等也都不是聯(lián)結(jié)詞完備集 所以 的任何子集都不是聯(lián)結(jié)詞完備集 1 5聯(lián)結(jié)詞的完備集 定義1 18設(shè)P Q為兩個(gè)命題 復(fù)合命題 P與Q的否定式 P或Q的否定式 稱為P Q的與非式 或非式 記作P Q P Q 符號(hào) 稱作為與非聯(lián)結(jié)詞 或非聯(lián)結(jié)詞 P Q為真當(dāng)且僅當(dāng)P與Q不同時(shí)為真 P Q為真當(dāng)且僅當(dāng)P與Q同時(shí)為假 由定義不難看出P Q P Q P Q P Q 1 5聯(lián)結(jié)詞的完備集 定理1 11 都是聯(lián)結(jié)詞完備集 證已知 為聯(lián)結(jié)詞完備集 因而只需證明其中的每個(gè)聯(lián)結(jié)詞都可以由 定義即可 而 P P P P P a P Q P Q P Q P Q P Q b P Q P Q P Q P Q P P Q Q c 由 a b 可知 是聯(lián)結(jié)詞完備集 類似可證 是聯(lián)結(jié)詞完備集 1 6命題邏輯的推理演算 推理 也稱論證 由已知的命題得到新命題的思維過程前提 推理所根據(jù)的已知命題結(jié)論 從前提出發(fā)應(yīng)用推理規(guī)則推出的新命題在數(shù)理邏輯中 集中注意的是研究和提供用來從前提導(dǎo)出結(jié)論的推理規(guī)則和論證原理 與這些規(guī)則有關(guān)的理論稱為推理理論 1 6命題邏輯的推理演算 1 6 1推理形式定義1 19設(shè) 1 2 n 都是命題公式 若 1 2 n 是重言式 則稱由前提 1 2 n推出 的推理是有效的或正確的 并稱 是 1 2 n的有效結(jié)論或邏輯結(jié)果 記為 1 2 n 或 1 2 n 記號(hào) 1 2 n 也稱為重言蘊(yùn)含或推理形式 1 6命題邏輯的推理演算 關(guān)于定義1 16還需做以下說明 1 由前提 1 2 n推結(jié)論 的推理是否正確與各前提的排列次序無關(guān) 因而前提中的公式不一定是序列 而是一個(gè)有限公式集合 若推理是正確的 則記為 1 2 n 否則記為 1 2 n 1 6命題邏輯的推理演算 2 符號(hào) 與 是兩個(gè)完全不同的符號(hào) 它們的區(qū)別與聯(lián)系類似于 和 的關(guān)系 不是命題聯(lián)結(jié)詞而是公式間的關(guān)系符號(hào) 而 是命題聯(lián)結(jié)詞 這兩者之間有密切的聯(lián)系 即 的充要條件是公式 為重言式 1 6命題邏輯的推理演算 3 必須把推理的有效性和結(jié)論的真實(shí)性區(qū)別開 有效的推理不一定產(chǎn)生真實(shí)的結(jié)論 產(chǎn)生真實(shí)結(jié)論的推理過程未必一定是有效的 再說 有效的推理中可能包含假的前提 而無效的推理卻可能包含真的前提 1 6命題邏輯的推理演算 可見 推理的有效性是一回事 前提與結(jié)論的真實(shí)與否是另一回事 所謂推理有效 指它的結(jié)論是它的前提的合乎邏輯的結(jié)果 也即 如果它的前提都為真 那么所得結(jié)論也必然為真 而并不是要求前提或結(jié)論一定為真或?yàn)榧?如果推理是有效的話 那么不可能它的前提都為真時(shí)而它的結(jié)論為假 1 6命題邏輯的推理演算 例1 18寫出下述推理關(guān)系的推理形式 下午小王或去看電影或去游泳 他沒去看電影 所以 他去游泳了 解設(shè)P 小王下午去看電影 Q 小王下午去游泳 前提 P Q P結(jié)論 Q推理形式為 P Q P Q 1 6命題邏輯的推理演算 1 6 2推理規(guī)則1 前提引入規(guī)則 P 在推理過程中 可以隨時(shí)引入已知的前提 2 結(jié)論引用規(guī)則 T 在推理過程中 前面已推出的有效結(jié)論都可作為后續(xù)推理的前提引用 1 6命題邏輯的推理演算 3 置換規(guī)則 R 在推理過程中 命題公式中的子公式都可以用與之等值的命題公式置換 得到證明的公式序列的另一公式 4 代入規(guī)則 S 在推理過程中 重言式中的任一命題變?cè)伎梢杂靡幻}公式代入 得到的仍是重言式 1 6命題邏輯的推理演算 1 6 3推理定律定理1 12設(shè) 是兩個(gè)命題公式 當(dāng)且僅當(dāng) 且 定理1 13設(shè) 是命題公式 若 且 則 定理1 14設(shè) 是命題公式 則 的充要條件是 是矛盾式 1 6命題邏輯的推理演算 下面列出一些常用的推理定律 在后面的推理演算中以大寫字母I加以引用 1 化簡(jiǎn)律 2 附加律 3 假言推理 又稱分離規(guī)則 1 6命題邏輯的推理演算 4 假言三段論 5 等價(jià)三段論 6 析取三段論 7 拒取式 8 二難推理 1 6命題邏輯的推理演算 9 10 11 12 13 14 1 6命題邏輯的推理演算 對(duì)于以上推理定律還有幾點(diǎn)需要說明 1 推理定律中出現(xiàn)的 均代表任意的命題公式 2 若一個(gè)推理形式與某條推理定律對(duì)應(yīng)一致 則不用證明就可判定這個(gè)推理是正確的 但需說明依據(jù) 3 根據(jù)定理1 10 在1 3節(jié)中給出的16組等值式中的每一條公式都可以派生出兩條推理定律 例如 雙重否定律 產(chǎn)生兩條推理定律 和 1 6命題邏輯的推理演算 1 6 4推理方法1 真值表法設(shè)P1 P2 Pn是出現(xiàn)于前提 1 2 m和結(jié)論 中的全部命題變?cè)?對(duì)P1 P2 Pn的所有情況作完全指派 這樣能對(duì)應(yīng)地確定 1 2 m和 的所有真值 列出這個(gè)真值表 即可判斷如下推理形式是否成立 1 2 m 或 1 2 m 若從真值表上找出 1 2 m均為1的行 對(duì)應(yīng)的行也為1 則上式成立 或者 若 為0的行 對(duì)應(yīng)的行中 1 2 m至少有一個(gè)0 則上式也成立 1 6命題邏輯的推理演算 例1 20用真值表法證明 P Q P Q P 解列出 P Q P Q P的真值表 1 6命題邏輯的推理演算 從表中可以看出P Q與 P Q 均為1的行是第一 二行 此兩行 P也為1 所以該推理形式正確 當(dāng)然也可以從另外一個(gè)方面來判斷 表中 P為0的行是第三 四行 此兩行中P Q與 P Q 至少有一個(gè)為0 從而也可以判斷出該推理形式正確 1 6命題邏輯的推理演算 2 直接證法直接證法就是由一組前提 利用前面的四條推理規(guī)則 根據(jù)已知的命題等值公式 1 3節(jié)中的16組公式 和推理定律 推演而得到有效的結(jié)論 1 6命題邏輯的推理演算 例1 21證明 P Q P R Q S S R證明 1 P QP 2 P QR E 1 3 Q SP 4 P ST I 2 3 5 S PR E 4 6 P RP 7 S RT I 5 6 8 S RR E 7 1 6命題邏輯的推理演算 3 間接證法間接證法主要有兩種 一種就是我們經(jīng)常用的反證法 另外一種稱之為CP規(guī)則 1 反證法要證明推理形式 1 2 m 成立 記作 根據(jù)定理1 14可知 只須證明 是矛盾式 因此 只須把 作為附加前提加入推理過程中 推出矛盾即可 1 6命題邏輯的推理演算 例1 22證明P Q Q R R S P證明用反證法 把 P 作為附加前提加入到前提的集合中去 證明由此導(dǎo)致矛盾 1 P P 附加 2 PR E 1 3 P QP 4 QT I 2 3 5 Q RP 6 RT I 4 5 7 R SP 8 RT I 7 9 R RT I 6 8 矛盾因此 假設(shè)不成立 原推理形式正確 1 6命題邏輯的推理演算 2 CP規(guī)則欲證 即證 亦即 永真 因?yàn)?所以若將 作為附加前提 證明 成立 即得證 成立 這一證明方法稱為CP規(guī)則 1 6命題邏輯的推理演算 例1 23驗(yàn)證下述推理是否正確 或者邏輯學(xué)難學(xué) 或者有許多學(xué)生喜歡它 如果數(shù)學(xué)容易學(xué) 那么邏輯學(xué)并不難學(xué) 因此如果許多學(xué)生不喜歡邏輯 那么數(shù)學(xué)并不容易學(xué) 解求解上述類型的推理問題 應(yīng)先將命題符號(hào)化 然后寫出前提 結(jié)論和推理形式 最后進(jìn)行判斷 令P 邏輯學(xué)難學(xué) Q 有許多學(xué)生喜歡邏輯學(xué) R 數(shù)學(xué)容易學(xué) 1 6命題邏輯的推理演算 前提 P Q R P結(jié)論 Q R推理形式 P Q R P Q R 1 QP 附加 2 P QP 3 PT I 1 2 4 R PP 5 RT I 3 4 6 Q RCP因此整個(gè)推理正確 1 7命題邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用 邏輯難題可以用邏輯推理解決的難題稱為邏輯難題 求解邏輯難題是實(shí)踐邏輯規(guī)則的一種好方法 同樣 涉及用于執(zhí)行邏輯推理的計(jì)算機(jī)程序通常也使用著名的邏輯難題來演示它們的能力 許多人對(duì)求解邏輯難題感興趣 有許多書和雜志也登載邏輯難題以供娛樂 1 7命題邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用 這是著名物理學(xué)家愛因斯坦出過的一道題 一個(gè)土耳其商人 想找一個(gè)十分聰明的助手協(xié)助他經(jīng)商 有兩個(gè)人前來應(yīng)聘 這個(gè)商人為了試一試哪一個(gè)聰明些 就把兩個(gè)人帶進(jìn)一間漆黑的屋子里 他打開電燈后說 這張桌子上有五頂帽子 兩頂是紅色的 三頂是黑色的 現(xiàn)在 我把燈關(guān)掉 而且把帽子擺的位置弄亂 然后我們?nèi)齻€(gè)人每人摸一頂帽子戴在頭上 在我開燈后 請(qǐng)你們盡快地說出自己頭上戴的帽子是什么顏色的 說完之后 商人將電燈關(guān)掉 然后三人都摸了一頂帽子戴在頭上 同時(shí)商人將余下的兩頂帽子藏了起來接著把電燈打開 這時(shí)那兩個(gè)應(yīng)試者看到商人頭上戴的是一頂紅帽子 過了一會(huì)兒 其中一個(gè)人便喊到