湖南大學離散數(shù)學教案-命題邏輯.ppt

《湖南大學離散數(shù)學教案-命題邏輯.ppt》由會員分享，可在線閱讀，更多相關(guān)《湖南大學離散數(shù)學教案-命題邏輯.ppt（84頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第一章命題邏輯 楊圣洪yangshenghong8 13007432216 引言邏輯學是推理的基礎(chǔ) 在社會學 自然科學尤其計算機學科中得到普遍應(yīng)用 數(shù)理邏輯是邏輯學的一個分支 也是數(shù)學的分支 它用數(shù)學方法研究推理規(guī)律 它采用符號的方法來描述和處理思維形式 思維過程和思維規(guī)律 它在程序設(shè)計 數(shù)字電路設(shè)計 計算機原理 人工智能等計算機課程得到了廣泛應(yīng)用 命題邏輯是數(shù)理邏輯的基礎(chǔ)部分 但究竟什么是命題 如何表示命題 如何構(gòu)造出復(fù)雜的命題 在本章將討論這些問題 1 1命題及聯(lián)結(jié)詞對錯確定的陳述語句稱為命題 如 1 湖南大學是一本學校 2 命題邏輯是計算機科學的基礎(chǔ)課程 3 命題及聯(lián)結(jié)詞是命題邏輯的最基礎(chǔ)的內(nèi)容 4 4是素數(shù) 5 湖南大學坐落于湘江以東 6 2011年湖南長沙輕軌通車 其中 1 2 3 與事實相符 是對的 正確的 稱為真命題 或者稱命題的值為 真 簡記為T或數(shù)字1 而 4 5 明顯與事實不相符 是錯的 不正確 稱為假命題 或稱命題的值為 假 簡記為F或數(shù)字0 陳述句 6 的正確性 到2011年12月時能確定的 若屆時開通了則它是對的 為真命題 否為假命題 1 1命題及聯(lián)結(jié)詞對錯確定的陳述語句稱為命題 如 7 x與y之和為100 其中x為整數(shù) y為整數(shù) 8 1加1等于10 7 的對錯不確定的 當x為50 y為50時是對的 當x為51 y為52時是錯的 8 的對錯是不確定的 為二進制時正確 當為八進制 十進制時是錯的 因此這兩個陳述句不是命題 9 岳麓山的紅葉真美呀 10 動作快點 11 你是離散數(shù)學老師嗎 這三個語句不是陳述語句 因此不是命題 1 1命題及聯(lián)結(jié)詞對錯確定的陳述語句稱為命題 如 12 我在說假話 13 我只給自己不能理發(fā)的人理發(fā) 14 派出所說 必須先房子再能上戶口單位后勤說 必須先有戶口才能分房你能上到戶口與要到房子嗎 這是一個悖論 其真值不能確定 故不是命題 1 1命題及聯(lián)結(jié)詞對錯確定的陳述語句稱為命題 如 13 我既要學程序設(shè)計 又要學離散數(shù)學 14 我們早餐在公寓食堂或外面早點攤上吃 15 我不是數(shù)學院的學生這三個陳述句都與事實相符 是對的 是真命題 其值為真 T 1 其中 13 與 14 可分解為另外二句話的組合 而 15 是對 我是數(shù)學院學生 的否定 這些語句稱為 復(fù)合命題 不能再分解的語句稱為 簡單命題 或 原子命題 為了便于推理與書寫 常用小寫字母表示簡單命題或原子命題 1 1命題及聯(lián)結(jié)詞簡單命題組合成復(fù)雜命題時所使用的輔助詞稱為 聯(lián)結(jié)詞 命題邏輯中的聯(lián)結(jié)詞歸納為以下5種 合取 C語言中 and并且析取 C語言中 or或否定 C語言中 not非 不是 否定條件式 C語言中if 如果 那么如p則q雙條件式 如p則q且如q則p 當且僅當 1 1命題及聯(lián)結(jié)詞定義1 1合取 當p q都對 即取值為真 T或1 時 p合取q 的值為真 1 1命題及聯(lián)結(jié)詞定義1 1合取 當p q都對 即取值為真 T或1 時 p合取q 的值為真 其他情況為假 邏輯運算符 合取 與漢語中 并且 而且 同時 含義相當 1 1命題及聯(lián)結(jié)詞定義1 2析取 當p q都不對 即取值為假 F或0 時 p析取q 的值為假 其他情況為真 邏輯運算符 析取 與漢語中 或 含義相當 但有細微的區(qū)別 1 1命題及聯(lián)結(jié)詞邏輯運算符 析取 與漢語的 或 幾乎一致但有區(qū)別 16 講離散數(shù)學的老師是楊老師或劉老師 可以表示為 講離散數(shù)學的老師是楊老師 講離散數(shù)學的老師是劉老師 這兩個原子命題有可能都是對的 這種 或 稱為 可同時為真的或 或簡稱為 可兼或 17 離散數(shù)學的教室是102或302 不可以表示為 離散數(shù)學的教室是102 離散數(shù)學的教室是302 因為這兩個原子命題不可能都對 只能這二種情況之一 這種 或 稱為 不可同時為真的或 或簡稱為 不可兼或 排斥或 這種 或 表示不能簡單表示為 析取 需要聯(lián)合使用下面將要介紹的 否定 與 析取 符號 才能準確表達 1 1命題及聯(lián)結(jié)詞定義1 3否定 當p是1 p的否定 p即為0 邏輯運算符 否定 與漢語中 否定 含義相當 我不是數(shù)學院的學生 可表示為 我是數(shù)學院的學生 離散數(shù)學的教室是102或302 表示離散數(shù)學的教室是102不是302 或 離散數(shù)學的教室是302不是102 p 離散數(shù)學的教室是102q 離散數(shù)學的教室是302上面的語句表示 p q p q 1 1命題及聯(lián)結(jié)詞定義1 4條件 當p是1 q是0時 p q為0 即1 0為0 其他情況為1 邏輯運算符 如果 那么 它是用單個運算符表示一個復(fù)合語句 如老媽說 如果期終考了年級前10名 那么獎勵1000元 p 期終考了年級前10名q 獎勵1000元則上面的語句表示為p q 當p為1即 期終考了年級前10 且q為0即 沒有獎勵1000元 這時老媽的話是假話空話 故p q為0 1 1命題及聯(lián)結(jié)詞定義1 4條件式 蘊含式 當p是1 q是0時 p q為0 即1 0為0 其他情況為1 p為前件 q為后件 1 當p為1即 我期終考了年級前10 q為0即 我老媽沒有獎勵1000元 這時老媽的話為假 即p q為0 2 當p為1即 我期終考了年級前10 q為1即 我老媽獎勵1000元 這時媽媽的話就對了 即p q為1 3 至于p為0即 我期終考了年級不是前10 時 無論q為1或為0 即無論 我老媽獎勵1000元 或不獎勵 都不能說老媽的話是假的 故可善意的認為p q為1均為1 1 1命題及聯(lián)結(jié)詞定義1 5雙條件 當p與q值相同0時 p q為1 不同為0 稱p與q的等價式 我明年賺了10萬當且僅當我買彩票中了大獎 可以表示為 我明年賺了10萬 我買彩票中了大獎 1 2公式及其賦值對錯明確的陳述語句稱為命題 其真值確定 又稱為命題常元或命題常項 相當于初等數(shù)學中的 常數(shù) 數(shù)學的運算符號為 加 減 乘x 除 冪 命題邏輯的符號 合取 析取 否定 條件 雙條件 數(shù)學中用變量x表示某些數(shù) 如x2 x 10是代數(shù)式 命題邏輯用變量表示任意一個命題 如p q r 這時由符號與變量所構(gòu)成命題表達式 簡稱為 命題公式 代數(shù)式的書寫有規(guī)律 命題公式也有規(guī)律與約束 稱滿足這些規(guī)則的公式為 合式公式 也稱為 命題公式 簡稱為 公式 1 2公式及其賦值定義1 2 1合式公式的生成規(guī)則 1 單個命題變元 命題常元為合式公式 原子公式 2 若A是合式公式 則 A A 也是合式公式 3 若A B是合式公式 則A B A B A B A B是合式公式 4 有限次使用 2 3 形成的字符串均為合式公式 如 p 1 q是合式公式 因為p 1是合公式 則 p 1 是合式公式 而r是合式公式 故 p 1 q是合式公式 p 1 r 不是合式公式 因為p 1是合公式 則 p 1 是合式公式 而r是合式公式 但 p 1 r 不是合法公式 1 2公式及其賦值對于代數(shù)式x2 y 10 當x與y的值不確定時 該代數(shù)式的值是不確定的 對于公式 p 1 q 由于p與q值不確定時 公式 p 1 q的值不確定 因而不是命題 只有當p與q的值確定后 公式 p 1 q的值才能確定 我們可能像表1 2到表1 5一樣 給出公式在各種情況下的取值 即得到這個公式的真值表 p與q每一種取值稱為p q的一種解釋 1 2公式及其賦值公式 p q p q的真值表如下表 真值表的構(gòu)造方法 1 命題變元的取值從全0開始 依次加1 直到全1 當有n個變元時 則共有2n種不同的取值情況 2 分步驟計算公式的值 3 見黑板上寫 成真賦值 如p q為 0 0 0 1 1 1 成假賦值 如p q為 1 0 1 2公式及其賦值公式 p q q p p q的真值表 無論p q取何值 這兩個公式的值總相等 1 2公式及其賦值公式 p q p q的真值表 無論p q取何值 這兩個公式的值總相等 1 2公式及其賦值公式p q p q的真值表 無論p q取何值 這兩個公式的值總相等 1 1 2公式及其賦值公式p q q p的真值表 無論p q取何值 這兩個公式的值總相等 若前者稱為原命題 后者為逆否命題 1 1 2公式及其賦值公式p q r p q p r 的真值表 無論p q取何值 這兩個公式的值 與前面各例不同 此表是將運算結(jié)果寫在聯(lián)結(jié)詞的下方 1 3等值式一 復(fù)習由前節(jié)可知 p q與 p q q pp q與 p q q p p q p q p q 與 p qp q r p q p r 的真值表完全一樣 稱為等值 定義1 3 1設(shè)A B是兩個合法的命題公式 無論其中的命題變元取何值 這兩個公式的總相等 稱為兩個公式等值 記為A B 由定義及前節(jié)習題有 1 p q p q q p條件式的等值式 2 p q p q q p p q p q 雙條件 3 p p雙重否定律 4 p p p p p冪等律 5 p q q p p q q p交換律 6 p q r p q r結(jié)合律p q r p q r 7 p q r p q p r 分配律p q r p q p r 8 p p r p吸收律 多吃少 p p r p 9 p q p q德摩律 p q p q將以上等值式中的變元換成合式公式仍等值 如 p q p q則有A B A B盡管A B可能很復(fù)雜 但是公式值也只有0 1二種可能 公式A B的組合只有0 0 0 1 1 0 1 1四種 如下表所示 顯然有A B A B 置換規(guī)則 當將公式A中的子公式B換成C得到公式D后 若B C 那么A D 因為A D除了 A中B所在之處 D中C所在之處 外 其他地方均相同 而不同之處的B與C等值 所以公式A 公式D的真值表應(yīng)該完全他相同 故A D 當將一個公式的局部進行等值替換后 仍與原公式等值 這也是數(shù)學中最常見的方法 不斷對局部進行等值替換的操作 稱為 等值演算 利用該規(guī)則及前述的等值式 可進行等值演算 從而推導出新的公式 求證 p q r p r q r p q r p q r條件式的等值式 p q r利用德摩律 r p q 交換律 r p r q 分配律 p r q r 交換律 p r q r 條件式等值式 等值演算的基本套路 1 轉(zhuǎn)換 A B A B 2 恰當轉(zhuǎn)換 A B A B A B A B A B 確保公式只保留 聯(lián)結(jié)詞 3 否定到底 A A B A B 4 恰當使用分配律 吸收律 利用等值演算 判斷公式的類型 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 q p q 結(jié)合律 p q p q 逆用德摩律 A A A p q 1稱為永真式或重言式 即利用等值演算 可以判斷公式的類型 利用等值演算判斷公式類型 p p q r解 p p q r p p q r 條件式的等值式 p p q r 結(jié)合律 1 q r 析取的性質(zhì)即析取定義真值表 1 r 析取的性質(zhì)即析取定義真值表 0 r 否定的定義 0 析取的性質(zhì)即析取定義真值表 永假式或矛盾式 問題 盡管有套路可行 但是隨意性還是比較大 能否有某種方式肯定能成功呢 1 4析取范式與合取范式文字 命題變項 變元 及其否定稱為文字 如 p q r p q r簡單析取式 僅由有限個文字構(gòu)成的析取式 如 p q p q p q p q p q r簡單合取式 僅由有限個文字構(gòu)成的合取式 如 p q p q p q p q p q r定理 簡單析取式與簡單合取式 1 一個簡單析取式Ai是重言式 含有某個命題變元及其否定式 如Ai p p 2 一個簡單合取式Ai是矛盾式 含有某個命題變元及其否定式 如Ai p p 1 4析取范式與合取范式析取范式 由有限個簡單合取式的析取構(gòu)成的命題公式稱為析取范式 總體是析取式 每對括號內(nèi)是合取式A p q p r 合取范式 由有限個簡單析取式的合取構(gòu)成的命題公式稱為合取范式 總體是合取式 每對括號內(nèi)是析取式A p q p r 1 4析取范式與合取范式總體是析取式 每對括號內(nèi)是合取式A p q p r 析取范式總體是合取式 每對括號內(nèi)是析取式A p q p r 合取范式定理 析取范式與合取范式 1 一個析取范式A是矛盾式 每個簡單合取式是矛盾式 A p q p r 2 一個合取范式A是重言式 每個簡單析取式是重言式 A p q p r 1 4析取范式與合取范式 1 轉(zhuǎn)換 A B A B 2 恰當轉(zhuǎn)換 A B A B A B A B A B 3 否定到底 A A B A B 4 適當使用分配律 A B C A B C 經(jīng)過第1步 第2步轉(zhuǎn)換后 公式中只有 三種運算符 經(jīng)過第3步后 從括號外深入到變元的前面 與變元結(jié)合成文文字 文字之間只有 1 4析取范式與合取范式 1 轉(zhuǎn)換 A B A B 2 恰當轉(zhuǎn)換 A B A B A B A B A B 3 否定到底 A A B A B 4 適當使用分配律 A B C A B C 如果外層運算符全部是 而內(nèi)層子公式全部是簡單析取式 則已經(jīng)是合取范式 如果內(nèi)層某子公式形如A B C 不是簡單析取式 則轉(zhuǎn)換為 A B A C 1 4析取范式與合取范式 1 轉(zhuǎn)換 A B A B 2 恰當轉(zhuǎn)換 A B A B A B A B A B 3 否定到底 A A B A B 4 適當使用分配律 A B C A B C 如果外層運算符全部是 而內(nèi)層子公式全部是簡單合取式 則已經(jīng)是析取范式 如果內(nèi)層某子公式形如A B C 不是簡單合取式 則轉(zhuǎn)換為 A B A C 因此有 1 不是永假的命題公式 存在析取范式 2 不是永真的命題公式 存在合取范式 1 4析取范式與合取范式 1 轉(zhuǎn)換 A B A B 2 恰當轉(zhuǎn)換 A B A B A B A B A B 3 否定到底 A A B A B 4 適當使用分配律 A B C A B C 如析取式范式 p q r p q r p q r p q r p r q r p q r 1 4析取范式與合取范式求 p q r的析取范式 合取范式解 1 求析取范式 即外層是 內(nèi)層是 所以 轉(zhuǎn)換模式為A B A B A B p q r p q r p q r 整體為析取 p q r p q r A B A B p q r p q r 德摩律 p r q r p q r 分配律 p r q r p q r 結(jié)合律 1 4析取范式與合取范式解 1 求合取范式 所以 轉(zhuǎn)換模式為A B A B A B p q r p q r p q r 整體為合取 p q r p q r 條件等價式 p q r p q r 德摩律 p r q r p q r 分配律 p r q r p q r 結(jié)合律 1 4析取范式與合取范式小項 在含有n個變元的簡單合取式中 每個命題變元或其否定僅出現(xiàn)一次 且各變元按其字母順序出現(xiàn) 則該簡單合取式為 極 小項 如 p q r p q r p q r p q r p r q r 非小項大項 在含有n個變元的簡單析取式中 每個命題變元或其否定僅出現(xiàn)一次 且各變元按其字母順序出現(xiàn) 則該簡單析取式為 極 大項 如 p q r p q r p q r p q r p r q r 非大項 1 4析取范式與合取范式主析取范式 一個析取范式中 如果所有簡單合取式均為 極 小項 則稱為主析取范式 p q r p r q r p q r 不是 p q r p q r p q r p q r 是主析取范式 1 4析取范式與合取范式主合取范式 一個合取范式中 如果所有簡單析取式均為 極 大項 則稱為主合取范式 p q r p r q r p q r 不是 p q r p q r p q r p q r 是主合取范式 1 4析取范式與合取范式 獲取方法通過轉(zhuǎn)換聯(lián)結(jié)詞 到底 及適當使用分配律 可以得到合取范式與析取范式 這時可能還缺少某個變元 因為p p 1 1 r 1 可在缺少變元的小項中加入形如 p p 的公式 如小項 p r 缺少變元q 加入q q 即 p r p 1 r p q q r p q r p q r 1 4析取范式與合取范式 獲取方法通過轉(zhuǎn)換聯(lián)結(jié)詞 到底 及適當使用分配律 可以得到合取范式與析取范式 這時可能還缺少某個變元 因為p p 1 1 r 1 可在缺少變元的小項中加入形如 p p 的公式 p q r p r q r p q r p q q r p 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 1 4析取范式與合取范式 獲取方法通過轉(zhuǎn)換聯(lián)結(jié)詞 到底 及適當使用分配律 可以得到合取范式與析取范式 這時可能還缺少某個變元 因為p p 0 0 p p 可在缺少變元的大項中加入形如 p p 的公式 如p r p 0 r p q q r p q r p q r 1 4析取范式與合取范式 獲取方法通過轉(zhuǎn)換聯(lián)結(jié)詞 到底 及適當使用分配律 可以得到合取范式與析取范式 這時可能還缺少某個變元 因為p p 0 0 p p 可在缺少變元的大項中加入形如 p p 的公式 p q r p r q r p q r p q q r p 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 1 4析取范式與合取范式當一個公式比較復(fù)雜時 得到其析取范式 合取范式的演算量比較大 再將簡單析取式轉(zhuǎn)換為大項 或簡單合取式轉(zhuǎn)換為小項 又需要進一步演算 能否直接基于原公式 不進行等值演算直接得到 或者能按某種統(tǒng)一的方式得到其主析取范式 主合取范式呢 通過真值表可以實現(xiàn) 為此先研究小項與大項的性質(zhì) 1 4析取范式與合取范式通過真值表可以實現(xiàn) 為此先研究小項與大項的性質(zhì) 下表是各小項的真值表 1 3個變元的小項共有8個 它們各不相同 2 從每一行來看 命題變元的每個指派中 只有一個小項的值為1 3 從每一列來看 每個小項僅在一個指派中值為1 其余7種指派中均為0 4 小項值為1 如 p q r 1 時 p q r均為1 即 p q r 0 0 0 取該值為小項編號 如最后一行 5 根據(jù)小項的編號 可寫出小項的具體形式 如小項m101 其編號為101 表示 p q r 1 0 1 時該小項的值為1 而小項是文字的合取 故小項的各個文字必須為1 則文字只能是p q r 故該小項為p q r 規(guī)則 1對應(yīng)變元本身 如p 0對應(yīng)其否定 如 p 如m00為 p q m01為 p q m10為p q m11為p q 很重要 1 三個變元的大項共有8個 2 每一行 每個指派中 只有一個大項的值為0 3 每一列 每個大項僅在一個指派下值為0 4 大項值為0 如 p q r 0 時 p q r均為0 則 p q r 1 1 1 將其記為大項編號 如表最后行 5 根據(jù)大項的編號 可寫出大項的具體形式 如大項M101 其編號為101 表示 p q r 1 0 1 時該大項的值為0 而大項是文字的析取 故各個文字必須為0 文字只能是 p q r 故該大項為 p q r 規(guī)則 1對應(yīng)變元的否定 如 p 0對應(yīng)變元 如p 如M00為p q M01為p q M10為 p q M11為 p q 1 4析取范式與合取范式 獲取方法1 先轉(zhuǎn)換析取式或合取式 再合取1或析取0 2 先建立真值表 取出所有成真賦值對應(yīng)的小項 析取所有小項得主析取范式 小項與成真賦值對應(yīng) 取出所有成假賦值對應(yīng)的大項 合取所有大項得主合取范式 大項與成假賦值對應(yīng) 如用真值表求主范式 p q r p q p q p q q p p q p q r的主析取范式 主合取范式 主析取范式 公式值為1的指派對應(yīng)小項的析取m001 m011 m100 m1111變元 0變元否定 使小項 1 p q r p q r p q r p q r p q r的主析取范式 主合取范式 主合取式范式 公式值為0的指派對應(yīng)大項的合取 M000 M010 M101 M1101變元否定0變元 使大項 0 p q r p q r p q r p q r p q r 與其主析取范式 主合取范式的真值完全一樣 說明三者互相等值 一般情況下有如下定理 1 不是永假的命題公式 有等值的主析取范式 2 不是永真的命題公式 有等值的主合取范式 由于永假沒有取值為1的解釋 故無相應(yīng)小項 故沒有主析取范式 永真無取值為0的解釋 故沒有主合取范式 設(shè)計一個電子評分系統(tǒng) 3位專家打分 如果有2位以上專家打分為 通過 則總成績?yōu)?通過 對應(yīng)的主析取范式 值為1的指派對應(yīng)的小項的析取 m011 m101 m110 m111 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x1 x2 x3 x1 x2 x3 x3 x1 x2 x1 x2 x3 x1 x2 x1 x2 x1 x2 x3 x1 x2 與非或門表示 某公司要從曹 喬 宋 黎 鄒5人中 選擇一些人承包一項工程 考慮到人與人組合優(yōu)化的問題 需滿足如下約束條件 1 如果曹去 那么喬也去 2 黎 鄒兩人中必有一人去 3 喬 宋兩人中去且僅去一人 4 宋 黎兩人同去或同時不去 5 若鄒去 則曹 喬也同去 解 用小寫字母表示 c 曹去 q 喬去s 宋去l 黎去z 鄒去時 以上5句話可表示為如下的公式 c q l z q s q s s l z q c 5句話同時成立即每句話的值均為1 也即其合取式 c q l z q s q s s l z q c 為1 c q l z q s q s s l z q c c q l z q s q s s l s l z q c c q l z z q c q s s l q s s l q s s l q s s l c q l z z q c q s l q s l c q l z z q s l z q s l q c s l c q z q s l z q c s l c z q s l z q c s l 因 c q l z q s q s s l z q c 為1 故1 c z q s l z q c s l 故1 c z q s l 或1 z q c s l 故方案一是 曹不去 鄒不去 喬不去 宋與黎去 方案二是 曹去 喬去 鄒去 宋與黎均不去 在某班班委的選舉中 該班的甲 乙 丙學生預(yù)言 甲說 王娟為班長 劉強為生活委員 乙說 金鑫為班長 王娟為生活委員 丙說 劉強為班長 王娟為學習委員 結(jié)果公布后 發(fā)現(xiàn)甲 乙 丙三人都恰好對了一半 請問王娟 劉強 金鑫各任何職 解 p1 q1 r1 表示王娟 劉強 金鑫是班長 p2 q2 r2 分別表示王娟 劉強 金鑫是學習委員 p3 q3 r3 分別表示王娟 劉強 金鑫是生活委員 每個人說法對一半 將是一個非常復(fù)雜的公式 p1 q3 r1 p3 q1 p2 p1 q3 r1 p3 q1 p2 p1 q3 r1 p3 q1 p2 p1 q3 r1 p3 q1 p2 p1 q3 r1 p3 q1 p2 p1 q3 r1 p3 q1 p2 p1 q3 r1 p3 q1 p2 p1 q3 r1 p3 q1 p2 要構(gòu)造這9個變元的真值表 將需要29 512行 工作量實在太大了 參考 真值表 設(shè)計如下的判斷表 1 6推理理論從已知條件 假設(shè) 前提或公理出發(fā) 根據(jù)推理規(guī)則推出結(jié)論 定理的過程 稱為推理 定義1設(shè)A與C是兩個命題公式 若A C為永真式 重言式 則稱C是A的有效結(jié)論 或稱A可以邏輯推出C 記為A C 由 的定義可知 當A為假時 A C肯定為真 故只要考慮A為真時C是否為真即可 故有 定義2設(shè)A與C是兩個命題公式 若當A為真時C也為真 則稱C是A的有效結(jié)論 或稱A可以邏輯推出C 記為A C 一般情況下 利用定義2去證明要簡單些 我們在其他學科中遇到的證明都是基于定義2的 判斷A C為永真可用等值演算 真值表等方法 例題求證 A A B B A A B B A A B B 的等值式 A A B B 的等值式 A A A B B 分配律 0 A B B 合取的性質(zhì) A B B 析取的性質(zhì) A B B 德摩律 A B B 結(jié)合律 A 1 析取的性質(zhì) 1 析取的性質(zhì) 所以 A A B B是重言式 真值表也證永真所以A A B B 這是有名的 假言推理 modusponens 或 分離原則 假如我今年進入年級前10名老爸給我買iphone4 期末考試后我為年級第8名 所以老爸應(yīng)該給我買iphone4 這是假言推理 A A B B從形式上看 結(jié)論B是A B的后件 推導的結(jié)果是將后件分離出來 故也稱為分離原則 利用假言推理規(guī)則或分離規(guī)則 結(jié)合析取 合取 否定的定義 只要不歉麻煩 幾乎可推出所有的結(jié)論 為了提高推理效率 還需要學習 掌握某些推理規(guī)則 例題求證A A B采用定義1來證明 即證明A A B為永真式 A A B A A B 的等值式 A A B 結(jié)合律 1 B 析取的性質(zhì) 1 析取的性質(zhì) 所以A A B 例題求證A B AA B A A B A 的等值式 A B A 德摩律 A B A 結(jié)合律 1 B 析取的性質(zhì) 1 析取的性質(zhì) 類似A B B根據(jù) 的定義可知A B為真時 A與B均為真 因此由推理定義2可知A B A A B B 同樣由 的定義可知A為真時A B為真 故由推理定義2可知A A B 然這3個推理式不必記憶 推理定義2效率較高 例題求證 A B B C A C 根據(jù)定義1 要證明下式為永真式 A B B C A C A B B C A C 的等值式 A B B C A C 的等值式 A B B C A C 德摩律 A B A C B B B C A C 分配律 A B A C 1 B C A C 析取的性質(zhì) A B A C B C A C 析取的性質(zhì) A B A C A C A C B C A C 分配律 1 B C 1 C C B A 1 析取的性質(zhì) 1 1 1 析取的性質(zhì) 1 析取的性質(zhì) 判斷公式的類型 除等值演算外 還有真值表與范式等方法 例題求證 A B B C A C 由上表可知 A B B C A C 為重言式 由定義1可知 A B B C A C 這是有名的傳遞律 要記住呀 例題求證 A B C D A C B D利用定義1證明了假言推理規(guī)則 A B A B 傳遞規(guī)則 A B B C A C 有了這2條規(guī)則后 可用定義2來證明推理式了 由于這2條規(guī)則的結(jié)論中沒有析取式 只有條件式 因此將題中結(jié)論 轉(zhuǎn)換為 B D 題設(shè)中 轉(zhuǎn)換為 1 A B C D A C 為真前提條件 定義2的套路 2 A B 為真 1 及合取的性質(zhì) 3 C D 為真 1 及合取的性質(zhì) 4 A C 為真 1 及合取的性質(zhì) 5 B A 為真 2 及 A B B A 6 A C 為真 4 及 A C A C 7 B C 為真 5 6 及推理傳遞律 8 B D 為真 7 3 及推理傳遞律 9 B D為真 8 及 B D B D 例題求證 A B C D B D A C可用傳遞律來證明 還有更高效的方法由定義1只要證 A B C D B D A C 為重言式 而 A B C D B D A C A B C D B D A C A B C D B D A C A B C D B D A C A B C D B D A C故只需證 A B C D B D A C為重言式即只需證明 A B C D B D A CA從結(jié)論中挪到前提中 這種技巧稱為附加條件 CP 法 適合于結(jié)論為條件式的情形 例題求證 A B C D B D A C 1 A B C D B D A為真CP規(guī)則及前提 2 A B為真 1 及合取的性質(zhì) 3 A為真 1 及合取的性質(zhì) 4 B為真 2 3 及假言推理式 A B A B 5 B D為真 1 及合取的性質(zhì) 6 B D為真 5 及 B D B D 7 D為真 4 6 及假言推理式 B D B D 8 C D為真 1 及合取的性質(zhì) 9 D C為真 8 及原命題 逆否命題 10 C為真 7 9 假言推理式 D C D C提示 熟練后可不寫 1 式 直接引用 2 3 5 8 例題求證 A B C D B D A C 1 A B為真前提條件 2 A為真附加前提 3 B為真 1 2 及假言推理式 A B A B 4 B D為真前提條件 5 B D為真 4 及 B D B D 6 D為真 3 5 及假言推理式 B D B D 7 C D為真前提條件 8 D C為真 7 及原命題 逆否命題 9 C為真 6 8 假言推理式 D C D C 求證 W R V V C S S U C U W提示 此處用逗號簡寫前述各例中的合取式 從而鼓勵大家直接引用前提 利用假言推理 傳遞律及前面所學的等值式 可以推出結(jié)論 在黑板上演示一番考慮到本題的結(jié)論是 W 可采用反證法 根據(jù)定義2可知 當前提為真時結(jié)論也為真 反證法是 前提為真時 假設(shè)結(jié)論不為真即結(jié)論的否定為真 即基于前提 結(jié)論否定進行推理 如果推出了一個矛盾的結(jié)論出來 則說明 假設(shè)結(jié)論不為真 是錯誤的 即表示結(jié)論只能為真了 求證 W R V V C S S U C U W 1 W為真假設(shè)結(jié)論 W為0即 W為1 真 2 W為真 1 與否定的性質(zhì) 3 W R 為真 2 與析取的性質(zhì) 4 W R V為真前提條件 5 V為真 4 3 假言推理 W R V W R V 6 V C S 為真前提條件 7 C S 為真 5 6 假言推理 V C S V C S 8 C S為真 7 與條件式的等值式C S C S 9 C為真前提條件 10 S為真 8 9 與假言推理 C S C S 11 S U為真前提條件 12 U為真 10 11 假言推理 S U S U 13 U為真前提條件顯然 12 與 13 矛盾 故假設(shè)有誤 應(yīng)用題天氣情況要么天晴 要么天下雨 如果天晴我去爬山 如果我去爬山那么我回來后不做飯 結(jié)論是 如果我已做飯那么肯定天下雨了 解 用M表示天晴 R表示天下雨 C表示爬山 F表示做飯 則問題可表示為M R M C C F F R M R M R M C C F F R 應(yīng)用題M R M C C F F R 1 F為真附件前提 2 C F為真前提條件 3 F C為真 2 的等值式 4 F C為真 3 的等值式 5 C為真 1 4 的假言推理 6 M C為真前提條件 7 C M為真 6 的等值式 8 M為真 5 7 的假言推理 9 M R為真前提條件 10 M R為真 9 的等值式 11 R為真 8 10 的假言推理 應(yīng)用題M R M C C F F R 1 F為真附件前提 2 C F為真前提條件 3 F C為真 2 的等值式 4 F C為真 3 的等值式 5 C為真 1 4 的假言推理 6 M C為真前提條件 7 C M為真 6 的等值式 8 M為真 5 7 的假言推理 9 M R M R 為真前提條件 10 M R M R 為真 9 的等值式 11 M R M R 為真 10 的等值式 12 M R為真 8 與析取的定義 13 M R 為真 11 12 的假言推理 14 R為真 13 與合取的定義 定義2證明推理式的規(guī)律 1 利用 條件等值式 盡可能將前提 中間結(jié)論及最終結(jié)論中的 析取式 轉(zhuǎn)換為 條件式 以便可引用假言推理 傳遞律 2 如果結(jié)論為條件式 則將條件式的前件做為附加前提 CP原則 3 如果結(jié)論的否定在前提中多次出現(xiàn) 可采用反證法 4 每一步的推理理由可簡化 如 前提條件 簡寫為 P 假言推理 可簡寫 M 等值式只寫 等值 或簡寫 E 5 這種從前提出發(fā) 應(yīng)用已證明的推理式 不斷推出中間結(jié)論 最后推出結(jié)論的方式 稱為自然推理 這是最常見的方式 1 7消解規(guī)則證明 A C B C A B 1 A C 為真前提條件 2 A C為真與 1 等值 3 B C為真前提條件 4 C B為真與 3 等值 5 C B為真與 4 等值 6 A B為真 2 5 傳遞律 7 A B為真與 6 等值因此當 A C B C 為真時 A B為真 由于 A C B C 中互補的公式C C同時消失了 稱 A B 為 A C B C 的消解式 因此在采用定義2進行推理時 只要 A C B C 同時為真 則可直接寫出A B為真 從而節(jié)省大量的中間環(huán)節(jié) 提高了證明效率 1 7消解規(guī)則例題 A B C D B D A C利用條件式的等值式 則此題等價于證明 A B C D B D A C 1 A B 為真前提條件 2 B D 為真前提條件 3 A D為真當 1 2 為真消解式 A D為真 4 C D為真前提條件 5 A C為真當 3 4 為真消解式 A C為真采用假言推理原則時 盡可能將析取轉(zhuǎn)換為條件式 采用消解法時 盡可能將條件式轉(zhuǎn)換為析取 消解法是一種高效的方法 消解法可完成1 6節(jié)中所有推理式 1 7消解規(guī)則采用定傳遞律證明了 A C B C A B因A B A B 故可用假言推理及CP原則證明 1 A為真附加前提 2 A C 為真前提條件 3 A C為真與 1 等值 4 C為真 1 3 假言推理 5 B C為真前提條件 6 C B為真與 4 等值 7 B為真 4 6 假言推理用假言推理證明了消解規(guī)則 反過來用消解規(guī)則可證明假言推理 1 7消解規(guī)則用假言推理證明了消解規(guī)則證明了 A C B C A B反過來 用消解規(guī)則可證明假言推理A A B BA B為真前提條件 A B為真與 1 等值A(chǔ)為真前提條件B為真 2 3 消解得到 假言推理 與 消解規(guī)則 可以互相推出 因此一方推出的結(jié)論另一方也可以推出因此習題三可由消解規(guī)則推導出來呀