1、1,離 散 數(shù) 學(xué),第一章 命題邏輯,2,目錄,數(shù)理邏輯引言 1-1 命題與命題的真值 1-2 聯(lián)結(jié)詞 1-3 命題公式及翻譯 1-4 真值表與等價(jià)公式 1-5 重言式與重言蘊(yùn)涵式 1-6 其它聯(lián)結(jié)詞 1-7 對偶與范式 1-8 命題推理理論 小結(jié) 習(xí)題,3,第一篇 數(shù)理邏輯,邏輯-是研究人的思維形式及思維規(guī)律的科學(xué)。 它包含： 1.辯證邏輯：是研究人的思維中的辯證法。 例如：用全面的和發(fā)展的觀點(diǎn)觀察事物； 具體問題具體分析； 實(shí)踐是檢查事物正誤的唯一標(biāo)準(zhǔn)；等等。 2.形式邏輯：是研究人的思維的形式和一般規(guī)律。類似于語法的一門工具性學(xué)科。,4,一 .形式邏輯,人的思維過程： 概念 判斷 推理

2、正確的思維： 概念清楚，判斷正確，推理合乎邏輯。 人們是通過各種各樣的學(xué)習(xí)(理論學(xué)習(xí)和從實(shí)踐中學(xué)習(xí))來掌握許多概念和判斷。 形式邏輯主要是研究推理的。,5,推理方法,推理：是由若干個(gè)已知的判斷(前提)，推出新的 判斷(結(jié)論)的思維過程。 類比推理：由個(gè)別事實(shí)推出個(gè)別結(jié)論。 如：地球上有空氣、水，地球上有生物?；鹦巧嫌锌諝?、水。 火星上有生物。 歸納推理：由若干個(gè)別事實(shí)推出一般結(jié)論。,6,推理方法,如：銅能導(dǎo)電。鐵能導(dǎo)電。錫能導(dǎo)電。鉛能導(dǎo)電。 一切金屬都導(dǎo)電。 演繹推理：由一般規(guī)律推出個(gè)別事實(shí)。 形式邏輯主要是研究演繹推理的。,7,演繹推理 舉例,例1： 如果天下雨，則路上有水。(一般規(guī)律) 天

3、下雨了。 (個(gè)別事實(shí)) 推出結(jié)論：路上有水。 (個(gè)別結(jié)論) 例2： (大前提)：所有金屬都導(dǎo)電。 (一般規(guī)律) (小前提)：銅是金屬。 (個(gè)別事實(shí)) 推出結(jié)論：銅能導(dǎo)電。 (個(gè)別結(jié)論),8,二. 數(shù)理邏輯,數(shù)理邏輯是用數(shù)學(xué)的方法研究形式邏輯。 所謂“數(shù)學(xué)方法”：是建立一套有嚴(yán)格定義的符號，即建立一套形式語言，來研究形式邏輯。所以數(shù)理邏輯也稱為“符號邏輯”。 它與數(shù)學(xué)的其它分支、計(jì)算機(jī)科學(xué)、人工智能、語言學(xué)等學(xué)科均有密切聯(lián)系。 數(shù)理邏輯可分為：證明論、模型論、遞歸論、公理化集合論、邏輯演算，這里只討論“命題邏輯”和“謂詞邏輯”。,9,數(shù)理邏輯把推理符號化之一,下面就前面兩個(gè)例子，說明如何將推理符

4、號化。 設(shè) P表示：天下雨。 設(shè)Q表示：路上有水。 設(shè)表示：如果則 例1的推理過程表示為： 前提1:PQ (如果天下雨,則路上有水。) 前提2：P (天下雨了。) 結(jié) 論：Q (路上有水。),10,數(shù)理邏輯把推理符號化之二,設(shè)M(x): x是金屬 . 設(shè)C(x): x能導(dǎo)電. 設(shè)x 表示: 所有的x . 設(shè) a 表示銅. 例2的推理過程表示為： 前提:x(M(x)C(x) (所有金屬都導(dǎo)電.) 前提:M(a) (銅是金屬.) 結(jié)論:C(a) (銅能導(dǎo)電.) (其中符號M(x)是謂詞，所以這就是第二章“謂詞邏輯”中所討論的內(nèi)容.）,11,第一章 命題邏輯,知識點(diǎn)： 命題的表示、命題的演算 命題演

5、算中的公式，及其應(yīng)用 命題邏輯推理,12,1-1. 命題與命題的真值,本節(jié)主要討論三個(gè)問題： 命題的概念 命題的真值 原子命題與復(fù)合命題 命題的表示,13,一. 命題的概念,命題：是一個(gè)能確定是真的或是假的判斷。（判斷都是用 陳述句表示） 例1-1.1 判定下面這些句子哪些是命題。 2是個(gè)素?cái)?shù)。 雪是黑色的。 2015年人類將到達(dá)火星。 如果 ab且bc，則ac。 x+y5 請打開書！ 您去嗎？,14,是命題 悖論 1、我正在說謊 2、一個(gè)城市里唯一的理發(fā)師只給所有不給自己理發(fā)的人理發(fā),15,二.命題的真值,一個(gè)命題所作的判斷有兩種可能：是正確的判斷或者是錯(cuò)誤的判斷。 一個(gè)命題的真值有兩個(gè)：“

6、真”或“假” 真值為真:一個(gè)命題所作的判斷與客觀一致,則稱該命題的真值為真,記作T (True)。 真值為假:一個(gè)命題所作的判斷與客觀不一致,則稱該命題的真值為假,記作F (False)。 例1-1.1中(1)(4)的真值為真,(2)的真值為假, (3)暫時(shí)不能定，等到2005年確定。,16,三. 原子命題與復(fù)合命題,簡單命題 (原子命題)： 由最簡單的陳述句構(gòu)成的命題 (該句再不能分解成更簡單的句子了)。 復(fù)合命題 (分子命題)：由若干個(gè)原子命題構(gòu)成的命題。,17,四 命題的表示,表示：大寫字母、帶下標(biāo)的大寫字母或數(shù)字 如：A,A3,12,P 命題標(biāo)識符：表示命題的符號 命題常量：一個(gè)命題標(biāo)

7、識符如表示確定的命題 命題變元：命題標(biāo)識符只表示任意命題的位置標(biāo)志。不確定其真值，不是命題 對命題變元的指派：命題變元P用一個(gè)特定命題取代時(shí)，P才能確定真值 原子變元：當(dāng)命題變元表示原子命題時(shí)的變元,18,1-2 聯(lián)結(jié)詞,復(fù)合命題的構(gòu)成：是用“聯(lián)結(jié)詞”將原子命題聯(lián)結(jié)起來構(gòu)成的。 歸納自然語言中的聯(lián)結(jié)詞，定義了六個(gè)邏輯聯(lián)結(jié)詞，分別是： (1) 否定“” (2) 合取“” (3) 析取“” (4) 異或“ ” (5) 蘊(yùn)涵“” (6) 等價(jià)“”,19,一. 否定“”,表示：“不成立”，“不”。 用于：對一個(gè)命題P的否定，寫成P，并讀成“非P”。 P的真值：與P真值相反。 例1-2.1 P：2是素?cái)?shù)

8、。 P：2不是素?cái)?shù)。 P：上海是一個(gè)大城市,P P,T F,F T,20,二. 合取“” 二元運(yùn)算,表示：“并且”、“不但而且.”、“既又 .”“盡管還 ” 例1-2.2 P：小王能唱歌。 Q：小王能跳舞。 PQ：小王能歌善舞。 PQ讀成P合取Q。 PQ的真值為真，當(dāng)且 僅當(dāng)P和Q的真值均為真。,P Q PQ,F F F,F T F,T F F,T T T,21,三. 析取“”、異或“ ”,表示“或者” “或者”有二義性，看下面兩個(gè)例子： 例1-2.3. 燈泡或者線路有故障。 例1-2.4. 第一節(jié)課上數(shù)學(xué)或者上英語。 例3中的或者是可兼取的或。即析取“” 例4中的或者是不可兼取的或，也稱之為

9、異或、排斥或。即“ ”.,22,1. 析取“”,P：燈泡有故障。 Q：線路有故障。 例3中的復(fù)合命題可 表示為：PQ，讀 成P析取Q，P或者Q。 PQ的真值為F，當(dāng) 且僅當(dāng)P與Q均為F。,P Q PQ,F F F,F T T,T F T,T T T,23,2. 異或“ ”,P：第一節(jié)上數(shù)學(xué)。 Q：第一節(jié)上英語。 例4中的復(fù)合命題 可寫成P Q，讀 成P異或Q。 P Q的真值為F， 當(dāng)且僅當(dāng)P與Q的真值相同,F F F,F T T,T F T,T T F,P Q P Q,24,3.異或的另一種表示,異或是表示兩個(gè)命題不可能同時(shí)都成立。 命題“第一節(jié)課上數(shù)學(xué)或者上英語?！笨梢越忉尀椋?“第一節(jié)課上

10、數(shù)學(xué)而沒有上英語或者第一 節(jié)課上英語而沒有上數(shù)學(xué)。” 于是有 P Q 與 (PQ)(QP ) 是一樣的。 實(shí)際應(yīng)用中必須注意“或者”的二義性。,25,四.條件 (蘊(yùn)涵)“”,表示“如果 則 ”， 例1-2.5： P表示：缺少水分。 Q表示：植物會死亡。 PQ：如果缺少水分，植物就會死亡。 PQ：也稱之為蘊(yùn)涵式，讀成“P蘊(yùn)涵Q”，“如果P則Q”。也說成P是PQ 的前件，Q是PQ的后件。還可以說P是Q的充分條件，Q是P的必要條件。,26,PQ的真值,PQ的真值為假，當(dāng)且僅當(dāng)P為真，Q為假。注意：當(dāng)前件P為假時(shí)， PQ為T。,P Q PQ 小王借錢不還 我替他還 （我給小王擔(dān)保）,F F T,F T

11、 T,T F F,T T T,27,書例：,如果某動物為哺乳動物，則它必胎生 如果我得到這本小說，那么我今夜就讀完它 如果雪是黑的，那么太陽從西方出來。,28,關(guān)于充分條件和必要條件的說明：,充分條件：就是只要條件成立，結(jié)論就成立，則該條件就是充分條件。 上例中，“缺少水分”就是“植物會死亡” 的充分條件。在自然語言中表示充分條件的詞有 ： 如果 則 ，只要 就，若則 必要條件：就是如果該條件不成立，那么結(jié)論就不成立, 則該條件就是必要條件。 上例中，“植物死亡”就是“缺少水分”的必要條件(植物未死亡，一定不缺少水分)。 在自然語言中表示必要條件的詞有 ： 只有 才 ； 僅當(dāng)， ; , 僅當(dāng)。

12、,29,舉例：,令：P：天氣好。 Q：我去公園。 1.如果天氣好，我就去公園。 2.只要天氣好，我就去公園。 3.天氣好，我就去公園。 4.僅當(dāng)天氣好，我才去公園。 5.只有天氣好，我才去公園。 6.我去公園，僅當(dāng)天氣好。 命題1.、2.、3.寫成： PQ 命題4.、5.、6.寫成： QP,30,舉例：,可見“”既表示充分條件（即前件是后件的充分條件）； 也表示必要條件（即后件是前件的必要條件）。這一點(diǎn)要特別注意!它決定了哪個(gè)作為前件，哪個(gè)作為后件。,31,五.等價(jià)(雙條件）“”,表示“當(dāng)且僅當(dāng)”、“充分且必要” 例1-2.6： P：ABC是等邊三角形。 Q：ABC是等角三角形。 PQ ：AB

13、C是等邊三角形當(dāng)且僅當(dāng) 它是等角三角形。,32,PQ的真值：,PQ的真值為真，當(dāng)且僅當(dāng)P與Q的真值相同。,P Q PQ,F F T,F T F,T F F,T T T,33,本節(jié)小結(jié)：,要熟練掌握這五個(gè)聯(lián)結(jié)詞在自然語言中所表示的含義以及它們的真值表的定義。,34,本節(jié)小結(jié),特別要注意“或者”的二義性，即要區(qū)分給定的“或”是“可兼取的或”還是“不可兼取的或”。 特別要注意“”的用法，它既表示“充分條件”也表示“必要條件”，即要弄清哪個(gè)作為前件，哪個(gè)作為后件。 作業(yè)：p8 3，4，5,35,本節(jié)小結(jié),練習(xí)：填空 已知PQ為T，則P為( )，Q為( )。 已知PQ為F，則P為( )，Q為( )。 已

14、知P為F，則PQ為( )。 已知P為T，則PQ為( )。 已知PQ為T，且P為F ，則Q為( )。 已知PQ為F，則P為( )，Q為( )。 已知P為F，則PQ為( )。 已知Q為T，則PQ為( )。 已知 PQ為F，則P為( )， Q為( )。,36,本節(jié)小結(jié),已知P為T， PQ為T，則Q為( )。 已知Q為T, PQ為T，則P為( )。 已知PQ為T，P為T , 則Q為( ). 已知PQ為F，P為T , 則Q為( ). PP 的真值為( ). PP 的真值為( )。,37,1-3 命題公式及翻譯,一. 命題常量與命題變元 命題常量：確定的命題。它是有具體含義 (真值)的。例如：“3是素?cái)?shù)。

15、”就是命題常量，也稱常值命題。 命題變元：用大寫的英字母如P、Q等表示任何命題。稱這些字母為命題變元。 對命題變元作指派(給命題變元一個(gè)解釋)：將一個(gè)命題常量賦予命題變元的過程，或者是直接賦給命題變元真值“T”或“F”的過程。 注意：命題變元本身不是命題，只有給它一個(gè)指派，才變成命題。,38,命題公式,設(shè)P和Q是任意兩 個(gè)命題，則P, PQ, PQ, (PQ) (PQ) , P(Q P)等都是復(fù)合命題 若P和Q是命題變元，則上述積各式均稱作命題公式。 P和Q稱作是命題公式的分量。 注：命題公式?jīng)]有真假，僅當(dāng)在一個(gè)公式 中命題變元用確定的命題代入時(shí)，才得到一命題；該命題的真值依賴于代換變元的那些

16、命題的真值；并不是則命題變元，聯(lián)結(jié)詞和一些括號組成的字符串都能成為命題公式,39,命題公式,.二.命題演算合式公式 ( wff ) (well formed formulas) 定義1-3.1： 單個(gè)命題變元是個(gè)合式公式。 若A是合式公式，則A是合式公式。 若A和B是合式公式，則(AB)，(AB)，(AB)和(AB)都是合式公式。 當(dāng)且僅當(dāng)有限次地應(yīng)用，所得到的含有命題變元、聯(lián)結(jié)詞和括號的符號串是合式公式。,40,命題公式,注意這個(gè)定義是遞歸的。(1)是遞歸的基礎(chǔ)，由(1)開始，使用(2)(3)規(guī)則，（4）是界限，可以得到任意的合式公式。 這里所謂的合式公式可以解釋為合法的命題公式之意，也稱之

17、為命題公式，有時(shí)也簡稱公式。 下面的式子不是合式公式： (P Q) (Q)，PR，(PQ)R 下面的式子才是合式公式： (PQ)，(PR)，(PQ)R),41,命題公式,按照合式公式定義最外層括號必須寫。 約定： （1）為方便，最外層括號可以不寫，上面的合式公式可以寫成： PQ，PR，(PQ)R 例： (P(Q)R) (RP)Q),42,命題公式,（2） 五個(gè)聯(lián)結(jié)詞的優(yōu)先次序： 、 、 ，凡符合此優(yōu)先次序的，括號可省略 （3）相同的聯(lián)結(jié)詞按出現(xiàn)的先后次序運(yùn)算，凡符合此要求的，括號可省去。 例： (P(Q)R) (RP)Q) (PQR) RPQ,43,命題公式,判斷下列公式哪些是合式公式，哪些不

18、是合式公式？,(Q RS) (P (RS) (P Q) (Q P) (RST) (P (QR) (P Q) (P R),44,三.命題符號化,所謂命題符號化，就是用命題公式的符號串來表示給定的命題。 命題符號化的方法 （1）.首先要明確給定命題的含義。 （2）.對于復(fù)合命題，找聯(lián)結(jié)詞，用聯(lián)結(jié)詞斷句，分解出各個(gè)原子命題。 （3）.設(shè)原子命題符號，并用邏輯聯(lián)結(jié)詞聯(lián)結(jié)原子命題符號，構(gòu)成給定命題的符號表達(dá)式。,45,三.命題符號化,例1.說離散數(shù)學(xué)無用且枯燥無味是不對的。 P：離散數(shù)學(xué)是有用的。 Q：離散數(shù)學(xué)是枯燥無味的。 該命題可寫成： (PQ) 例2.如果小張與小王都不去，則小李去。 P：小張去。

19、 Q：小王去。 R：小李去。 該命題可寫成： (PQ)R,46,三.命題符號化,例3. 僅當(dāng)天不下雨且我有時(shí)間，才上街。 P：天下雨。Q：我有時(shí)間。R：我上街。 分析：由于“僅當(dāng)”是表示“必要條件”的，既“天不下雨且我有時(shí)間”，是“我上街”的必要條件。所以 該命題可寫成： R(PQ),47,三.命題符號化,例4.人不犯我，我不犯人；人若犯我，我必犯人。 P：人犯我。Q：我犯人。 該命題可寫成：(PQ)(PQ) 或?qū)懗桑?PQ,P是Q的充分條件,P是Q的必要條件,P是Q的充分且必要條件,48,三.命題符號化,例5 .若天不下雨，我就上街；否則在家。 P：天下雨。Q ：我上街。R：我在家。 該命題

20、可寫成： (PQ)(P R). 注意：中間的聯(lián)結(jié)詞一定是“”，而不是“”，也不是“ ”。 因?yàn)樵}表示：“天不下雨時(shí)我做什么，天下雨我又做什么”的兩種作法，其中有一種作法是假的，則我說的就是假話，所以中間的聯(lián)結(jié)詞一定是“ ”。,49,三.命題符號化,如果寫成 (PQ)(P R)，就表明兩種作法都是假的時(shí)候，我說的才是假話。這顯然不對。 若寫成(PQ) (P R)時(shí)，當(dāng)P為F，Q為F時(shí)，即天沒下雨而我沒上街，此時(shí)我說的是假話，但是表達(dá)式 (PQ) (P R) 的真值卻是“T” ，因?yàn)榇藭r(shí)(P R)的真值是“T”。所以這個(gè)表達(dá)式也不對。,50,練習(xí),上海到北京的14次列車是下午五點(diǎn)半或六點(diǎn)半開

21、除非你努力，否則你將失敗,異或,PQ,51,1-4 真值表與等價(jià)公式,一.命題公式的真值表 定義1-4.1 在命題公式中，由對所含命題變元的所有可 能指派和在此指派下公式的真值構(gòu)成的表。 (PQ)Q 的真值表： P Q P PQ (PQ)Q F F T F F F T T T T T F F T T T T F T T,52,1-4 真值表與等價(jià)公式,命題變元P T F N個(gè)命題變元 P1, P2 , Pn T T , T F F , F 命題公式 A(P1,P2,Pn)真值表有2n行 有一類公式不論變元做何種指派，其真值永為真 （假），可將此類公式記為T(F),53,關(guān)于二進(jìn)制數(shù)簡介：,為了

22、有序地列出A(P1,P2,Pn)的真值表，可以將F看成0，將T看成1，按照二進(jìn)制數(shù)000, 0001, 00010, , 1110, 111(即十進(jìn)制的0,1,2,. ,2n -1)的次序進(jìn)行指派列真值表。,54,關(guān)于二進(jìn)制數(shù)簡介：,例如列出P(QR)的真值表,P Q R QR P(QR),000 F F F T T,001 F F T T T,010 F T F F T,011 F T T T T,100 T F F T T,101 T F T T T,110 T T F F F,111 T T T T T,55,二、 等價(jià)公式,P Q PQ PQ QP F F T T T F T T T

23、T T F F F F T T T T T,定義1-4.2 A、B是含有命題變元P1,P2 , Pn的命 題公式，如不論對P1, P2 , , Pn作任何指派，都使 得A和B的真值相同，則稱之為A與B等價(jià)，記作AB。,56,二、 等價(jià)公式,重要的等價(jià)公式 對合律 PP (雙否律) 冪等律 PPP PPP 結(jié)合律 P(QR)(PQ)R P(QR)(PQ)R 交換律 PQQP PQQP,57,二、 等價(jià)公式,分配律 P(QR)(PQ)(PR) P(QR)(PQ)(PR) 吸收律 P(PQ)P P(PQ)P 德-摩根定律 (PQ)PQ (PQ)PQ 同一律 PFP PTP 零律 PTT PFF 互補(bǔ)

24、律 PPT PPF,58,二、 等價(jià)公式, PQPQ PQQP PQ (PQ)(QP) PQ (PQ)(PQ) PQ (PQ)(PQ ) (PQ)R (PQ)(PR) (P Q)R,59,二、 等價(jià)公式, 對合律 AA A表示A的絕對補(bǔ)集 冪等律 AAA AAA 結(jié)合律 A(BC)(AB)C A(BC)(AB)C 交換律 ABBA ABBA 分配律 A(BC)(AB)(AC) A(BC)(AB)(AC),60,二、 等價(jià)公式, 吸收律 A(AB)A A(AB)A 底-摩根定律 (AB)AB (AB)AB 同一律 AA AEA E表示全集 零律 AEE A 否定律 AAE AA,61,4. 等價(jià)

25、公式的證明方法,方法1：用列真值表。 方法2：用公式的等價(jià)變換.(用置換定律) 定義1-4.3 如果X是合式公式A的一部分，且X本身也 是一合式公式，則稱X為公式A的子公式。 定理1-4.1 (置換定律)設(shè)X是合式公式A的子公式，若XY，如果將A中的X用Y來置換，則所得到公式B與公式A等價(jià)，即AB。,62,4. 等價(jià)公式的證明方法,例題1. 求證吸收律 P(PQ)P 證明 P(PQ) (PF)(PQ) (同一律) P(FQ) (分配律) PF (零律) P (同一律),63,4. 等價(jià)公式的證明方法,例題2. 求證 (PQ)(PQ) P 證明 (PQ)(PQ) (PQ)(PQ) (公式E16)

26、 (PQ)(PQ) (摩根定律) (PQ)(PQ) (對合律) P(QQ) (分配律) PT (互補(bǔ)律) P (同一律) 公式E16 ： PQPQ,64,4. 等價(jià)公式的證明方法,例題3.化簡(PQ)(P(PQ) 解 原公式 (PQ)(PP)Q) (E16,結(jié)合) (PQ)(PQ) (對合律，冪等律) (PQ)(QP) (交換律) (PQ)Q)P (結(jié)合律) QP (吸收律) 公式E16 ： PQPQ,65,5. 等價(jià)性質(zhì),1).有自反性：任何命題公式A，有AA。 2).有對稱性：若AB，則BA 3).有傳遞性：若AB且BC，則AC 4).如果A(P1,P2,Pn)B(P1,P2,Pn)，則

27、A(P1,P2,Pn)B(P1,P2,Pn) 例 A(P,Q)PQ B(P,Q)PQ 有 A(P,Q)B(P,Q) A(P,Q)PQ B(P, Q)PQ 可見A(P,Q)B(P, Q),66,5 等價(jià)性質(zhì),試證語句：“不會休息的人也不會工作，沒有豐富知識 的人也不會工作”，與語句“工作得好的人一定會休息 并且有豐富的知識”，具有相同的邏輯含義。 證明：設(shè)P：某人會工作 Q：某人會休息 R：某人有豐富的知識 (QP) (RP) P (QR),67,1-5 重言式與重言蘊(yùn)涵式,P PP PP F T F T T F 可見不論P(yáng)取什么真值PP 的真值總是為真，PP的真值總是為假。PP為重言式(永真式

28、)，稱PP為矛盾式(永假式)。,68,例：,P Q (PQ) PQ (PQ)PQ F F T T T F T T T T T F T T T T T F F T 公式(PQ)PQ，無論對P和Q的何種指派，其真值均為真,69,重言式和矛盾式,定義1-5.1 A(P1,P2,Pn) 是含有命題變元P1,P2, Pn的命題公式，如不論對P1, P2 , , Pn作任何指派，都使得A(P1,P2, Pn) 為真(假)，則稱之為重言式(矛盾式), 也稱之為永真式 (永假式)。 定義1-5.2 一命題公式若至少存在一個(gè)指派使其取真值為T，則稱此公式為可滿足公式。 若至少存在一個(gè)指派使其取真值為假，則稱此公

29、式為非重言式或非永真公式,70,3.相關(guān)性質(zhì)、定理,3.相關(guān)性質(zhì)、定理 （1）重言式的否定是矛盾式；矛盾式的否定是重 言式。 （2）定理1-5.1如果A，B是永真式，則(AB)、(AB)、(AB)和(AB)也都是永真式。 證明：設(shè)A和B為兩個(gè)重言式，則不論A和B分量指派任何真值，總有A為T，B為T，故AB T, AB T.,71,（ 3）定理1-5.2 一個(gè)重言式，對同一分量都用任何合式公式置換，其結(jié)果仍為一重言式 證明：由于重言式的真值與分量的指派無關(guān)，故對同一分量以任何合式公式置換后，重言式的真值仍永為T. 對于矛盾式也有類似于定理1-5.1和定理1-5.2的結(jié)果,3.相關(guān)性質(zhì)、定理,72

30、,定理1-5.2如果A是永真式，則A的置換例式也是永真式。 置換例式： A(P1,P2,Pn) 是含有命題變元P1,P2, Pn 的命題公式，如果用合式公式X替換某個(gè)Pi(如果Pi在 A(P1,P2,Pn) 中多處出現(xiàn)，則各處均用X替換 )， 其余變元不變，替換后得到新的公式B，則稱B是 A(P1,P2,Pn) 的置換例式。,3.相關(guān)性質(zhì)、定理,73,A: P(P(PQ)R) (DE)替換P 置換例式B: (DE)(DE)(DE)Q)R),3.相關(guān)性質(zhì)、定理,74,（4）若兩個(gè)公式的雙條件是重言式，則此兩公式對任何指派存相同真值。反之亦然。即下面的定理1-5.3 定理1-5.3 設(shè)A、B為兩個(gè)

31、命題公式， A B當(dāng)且僅當(dāng)A B為一重言式。 證明：（1）若A B，則A、B有相同的真值，即A B永為T. 2）若A B為重言式，則A B永為T，故A、B的真值相同，即A B,3.相關(guān)性質(zhì)、定理,75,4重言式的證明方法,方法1：列真值表。 方法2：公式的等價(jià)變換，化簡成“T”。 方法3：用公式的主析取范式。,76,4重言式的證明方法,方法1. 列真值表。 例如，證明 (P(PQ)Q 為重言式。,P Q PQ P(PQ) (P(PQ)Q F F T F T F T T F T T F F F T T T T T T,77,二.重言(永真)蘊(yùn)涵式,定義1-5.3：當(dāng)且僅當(dāng)AB是一個(gè)重言式時(shí)，稱A

32、 重言(永真)蘊(yùn)涵 B，記作AB。 上式可以寫成(P(PQ)Q注意符號“”不 是聯(lián)結(jié)詞，它是表示公 式間的“永真蘊(yùn)涵”關(guān) 系，也可以看成是“推導(dǎo)”關(guān)系。即AB可以理 解成由A可推出B，即由A為真，可以推出B也為真。,78,2.重言(永真)蘊(yùn)涵式證明方法,方法1.列真值表。(即列永真式的真值表)這里就不再舉例了。 P Q PQ P(PQ) (P(PQ)Q F F T F T F T T F T T F F F T T T T T T,79,2.重言(永真)蘊(yùn)涵式證明方法,先看一看AB的真值表，如果AB為永真式，則真值表的第三組指派不會出現(xiàn)。于是有下面兩種證明方法。,80,2.重言(永真)蘊(yùn)涵式證

33、明方法,方法2.假設(shè)前件為真，推出后件也為真。 求證：(AB)C)D(CD) AB 證明: 設(shè)前件(AB)C)D(CD) 為真。則(AB)C)、D、(CD)均真， D為T，則D為F (CD)為T (AB)C為T,81,2.重言(永真)蘊(yùn)涵式證明方法,如果A為F，則A為T，所以AB為T。 如果B為F，則B為T，所以AB 為T。 (AB)C)D(CD) AB,82,2.重言(永真)蘊(yùn)涵式證明方法,方法3.假設(shè)后件為假，推出前件也為假。 求證： (AB)C)D(CD) AB 證明:假設(shè)后件AB為F,則A與B均為T。 1.如C為F，則(AB)C為F，所以前件 (AB)C)D(CD) 為F 2.如C為T

34、，則若D為T，則D為F，所以 前件(AB)C)D(CD) 為假 若D為F，則CD為F，所以 前件(AB)C)D(CD) 為假。 (AB)C)D(CD) AB,83,（PQ)(PR)(QR) R,證明：利用的定義 設(shè)前件： (PQ)(PR)(QR) 為T 則P為T， PR為T Q為T，QR為T 都得出R為T 即在前件為T的假定下推出后件R為T 重言蘊(yùn)含式得證,84,3.重要的重言蘊(yùn)涵式,I1.PQP I2. PQQ I3. PPQ I4. QPQ I5. PPQ I6. QPQ I7. (PQ)P I8. (PQ)Q I9. P,Q PQ I10. P(PQ)Q I11. P(PQ)Q I12.

35、 Q(PQ)P I13. (PQ)(QR)PR I14. (PQ)(PR)(QR)R I15. AB (AC)(BC) I16. AB (AC)(BC),85,3.重要的重言蘊(yùn)涵式,等價(jià)式與蘊(yùn)含式之間的關(guān)系 定理1-5.4 設(shè)P、Q為任意兩個(gè)命題公式， PQ的充分必要條件是PQ且 QP。 證明：（1）若PQ，則PQ為重言式，因?yàn)镻Q （PQ）(QP)，故PQ為T，即PQ， QP成立。 （2）若PQ且 QP，則PQ為T且QP也為T，因此PQ 為T, PQ 是重言式，即PQ,86,4.蘊(yùn)含常見的幾個(gè)性質(zhì),1).設(shè)A、B、C為合式公式，若AB且A重言式，則B必是重言式 2).有自反性：對任何命題公式

36、A，有AA 3).有傳遞性：若AB且BC，則AC 4).有反對稱性：若AB且BA，則AB 符號“”表示“等價(jià)”。 5)若AB， AC，那末A（BC) 6)若AB, CB，則AC B 本節(jié)重點(diǎn)掌握：永真式及永真蘊(yùn)涵式的定義、證明方法、以及常用的公式。 作業(yè)：第23頁: (2) b) 、(6)、(8) e),87,1-6.其它聯(lián)結(jié)詞,五個(gè)聯(lián)結(jié)詞： 其它聯(lián)結(jié)詞： P Q ：同為假，異為真（異或） PQ： ( PQ) 僅當(dāng)P為真，Q為假是為T（條件否定） P Q： ( PQ) （與非） P Q： ( PQ) （或非） 共九個(gè)聯(lián)結(jié)詞,c,88,1-6.其它聯(lián)結(jié)詞,P Q 聯(lián)1 聯(lián)2 聯(lián)3 聯(lián)4 聯(lián)5 聯(lián)

37、6 聯(lián)7 聯(lián)8 T T T F T T F F T F T F T F T F F T F T F T T F F T T F F T F F T F F F T T F T,89,1-6.其它聯(lián)結(jié)詞,P Q 聯(lián)9 聯(lián)10 聯(lián)11聯(lián)12 聯(lián)13 聯(lián)14 聯(lián)15 聯(lián)16 T T T F T F T F T F T F T F F T F T T F F T T F T F F T F T F F F T T F T F T F,90,1-6.其它聯(lián)結(jié)詞,命題聯(lián)結(jié)詞在命題演算中是通過真值表定義的。對2個(gè)變元，恰可構(gòu)成16個(gè)不等價(jià)的命題公式，n個(gè)變元，可構(gòu)成 個(gè) 但除常T、F及命題變元本身外，命題聯(lián)

38、結(jié)詞有九個(gè)就夠了，九個(gè)也并非完全必要 最小聯(lián)結(jié)詞組：對任何一個(gè)命題公式，都能由僅含這些聯(lián)結(jié)詞的命題公式等價(jià)代換,91,1-6.其它聯(lián)結(jié)詞,由九個(gè)聯(lián)結(jié)詞組成的命題公式，必可由，或 , 組成的命題公式代替 為方便實(shí)用，命題公式常常同時(shí)包含，,92,1-7.對偶與范式,一、等價(jià)公式的對偶性 從前面列出的等價(jià)公式看出，有很多是成對出現(xiàn)的。這就是等價(jià)公式的對偶性。 定義1-7.1 對偶式：在一個(gè)只含有聯(lián)結(jié)詞 、的公式A中，將換成，換成，T換成F，F(xiàn)換成T，其余部分不變，得到另一個(gè)公式A*，稱A與A*互為對偶式。,93,一、對偶,例如:： A A* P P QR QR (PT)Q (PF)Q 用對偶式求公

39、式的否定,94,一、對偶,定理1-7.1 令A(yù)(P1,P2,Pn)是一個(gè)只含有聯(lián)結(jié)詞 、的命題公式，則 A(P1,P2,Pn)A*(P1,P2,Pn) 此定理可以反復(fù)地使用底-摩根定律得以證明。 證明： 令 A(P,Q)PQ A*(P,Q)PQ A(P,Q)(PQ) A*(P, Q)PQ,95,一、對偶,可見 A(P,Q)A*(P,Q) 推論:A(P1,P2,Pn)A*(P1,P2,Pn) 例1： （1）利用上述求公式的否定公式 求 (PQ)(PQ)R) (PQ)(PQ)R 2）求P Q，P Q的對偶式 3）設(shè)A*(S,W,R)是 S(WR)，證明A*(S,W,R) A (S,W,R),96,

40、一、對偶,對偶原理(定理1-7.2)： 令A(yù)(P1,P2,Pn) 、B(P1,P2,Pn)是只含有聯(lián)結(jié)詞、的命題公式，則如果 A(P1,P2,Pn)B(P1,P2,Pn) 則 A*(P1,P2,Pn)B*(P1,P2, Pn) 證明：因?yàn)?A(P1,P2,Pn)B(P1,P2,Pn) 故 A(P1,P2,Pn)B(P1,P2,Pn),97,一、對偶,而 A(P1,P2,Pn)A*(P1,P2,Pn) B(P1,P2,Pn)B*(P1,P2,Pn) 故 A*(P1,P2,Pn) B*(P1,P2,Pn) 所以 A*(P1,P2,Pn)B*(P1, P2, Pn) 下面我們驗(yàn)證一下對偶原理： P(

41、QR)(PQ)(PR) A B,98,一、對偶,P(QR)(PQ)(PR) A* B* PTT A B PFF A* B* 本節(jié)要求掌握對偶式、及對偶原理的應(yīng)用。 作業(yè)：第39頁 (6),99,二、范式,范式就是命題公式形式的規(guī)范形式。這里約定在范式中 只含有聯(lián)結(jié)詞、和。 (一) 析取范式與合取范式（定義1-7.2/3） 1.合取式與析取式 合取式：是用“”聯(lián)結(jié)命題變元或變元的否定構(gòu)成的式子。如 P 、P 、PQ、PQR 析取式：是用“” 聯(lián)結(jié)命題變元或變元的否定構(gòu)成的式子。,100,二、范式,如 P 、P 、PQ、PQR 注: PPP PPP P是合(析)取式. 2.析取范式 公式A如果寫成

42、如下形式： A1A2.An (n1) 其中每個(gè)Ai (i=1,2.n)是合取式，稱之為A的析取范式。,101,二、范式,3.合取范式 公式A如果寫成如下形式： A1A2.An (n1) 其中每個(gè)Ai (i=1,2.n)是析取式，稱之為A的合取范式。 例如，PQ 的析取范式與合取范式： PQ (PQ)(PQ)-析取范式 PQ (PQ)(PQ)-合取范式,102,二、范式,4.析取范式與合取范式的寫法 先用相應(yīng)的公式去掉和；將公式中的聯(lián)結(jié)詞化歸成包含，,式子 公式E16 PQPQ 公式E21 PQ (PQ)(PQ) 公式E20 PQ (PQ)(QP) 再用E16 PQ (PQ)(PQ),103,二

43、、范式,用公式的否定公式或摩根定律將后移到命題變元之前。 A(P1,P2,Pn)A*(P1,P2,Pn) 底-摩根定律 (PQ)PQ (PQ)PQ 用分配律、冪等律等公式進(jìn)行整理，使之成為所要求析取范式與合取范式。,104,二、范式,一公式的析取范式與合取范式并不唯一，為使任意一個(gè)命題公式，化成唯一的等價(jià)命題的標(biāo)準(zhǔn)形式，采用主范式來統(tǒng)一,例2：求(PQ)R的析取范式與合取范式 (PQ)R (PQ)(PQ)R (PQ)(PQ)R -析取范式 (PQ)R(PQ)(PQ)R (PQ)(PQ)R (PQR)(PQR) -合取范式,105,二、范式,(二) 主析取范式與主合取范式 一個(gè)公式的析取范式與合

44、取范式的形式是不唯一的。下面定義形式唯一的主析取范式與主合取范式。 主析取范式 1.小項(xiàng)(布爾合取) 定義1-7.4：在一個(gè)有n個(gè)命題變元的合取式中，每個(gè)變元與其否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次，稱這個(gè)合取式是個(gè)小項(xiàng)。,106,二、范式,例如，有兩個(gè)變元的小項(xiàng)： PQ、PQ、 PQ、 PQ 小項(xiàng)的性質(zhì) m3 m2 m1 m0 P Q PQ PQ PQ PQ 00 F F F F F T 01 F T F F T F 10 T F F T F F 11 T T T F F F,107,二、范式,a).有n個(gè)變元，則有2n個(gè)小項(xiàng)。 b).每一組指派有且只有一個(gè)小項(xiàng)為T。 為了記憶方便，

45、可將各組指派對應(yīng)的為T的小項(xiàng) 分別記作m0,m1,m2,m2n-1 上例中 m0PQ m1PQ m2PQ m3PQ,108,二、范式,c).三個(gè)命題變元P、Q、R的小項(xiàng) m000PQR m100PQR m001PQR m101PQR m010PQR m110PQR m011PQR m111PQR 每一個(gè)小項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其值為T，在其余 -1種指派情況下均為F,109,二、范式,任意兩個(gè)不同小項(xiàng)的合取式永假 m001m100 (PQR)(PQR) 全體小項(xiàng)的析取式永為真，記為： mi m0 m1 mn-1 T,2,110,二、范式,2.主析取范式定義定義1-7.5 析取范式 A1A

46、2.An, 其中每個(gè)Ai (i=1,2.n)都是小項(xiàng)，稱之為主析取范式。 3.定理1-7.3：在真值表中，一個(gè)公式的真值為T的指派所對應(yīng)的小項(xiàng)為m1 , m2 , , mk ,這些小項(xiàng)的析取式記為B，為此要證AB，即要證A與B在相應(yīng)指派下具有相同真值,111,二、范式,首先對A為T的某一指派，其對應(yīng)的小項(xiàng)為mi，則因mi為T，而m1 , m2 , , mi -1， mi+1， ， mk均為F，故B為T。 其次，對A為F的某一指派，其對應(yīng)的小項(xiàng)不包含在B中，即m1 , m2 , , mk ,均為F，故B為F。 因此AB,112,二、范式,4.主析取范式的寫法 方法：列真值表 列出給定公式的真值表

47、。 找出真值表中每個(gè)“T”對應(yīng)的小項(xiàng)。 (如何根據(jù)一組指派寫對應(yīng)的為“T”的項(xiàng)：如果變元P被指派為T，P在小項(xiàng)中以P形式出現(xiàn)；如變元P被指派為F,P在小項(xiàng)中以P形式出現(xiàn)(因要保證該小項(xiàng)為T)。 用“”聯(lián)結(jié)上述小項(xiàng)，即可。,113,二、范式,例如求 PQ和PQ的主析取范式 P Q PQ PQ F F T T F T T F T F F F T T T T PQ m0m1m3 (PQ)(PQ)(PQ) PQm0m3 (PQ)(PQ),114,二、范式,思考題:永真式的主析取范式是什么樣 ？ 方法：用公式的等價(jià)變換 先寫出給定公式的析取范式 A1A2.An 。 為使每個(gè)Ai都變成小項(xiàng)，對缺少變元的A

48、i補(bǔ)全變元，比如缺變元R，就用聯(lián)結(jié)永真式(RR)形式補(bǔ)R。 用分配律等公式加以整理。,115,二、范式,PQPQ (P(QQ)(P P) Q) (PQ)(PQ)(PQ)(PQ) (PQ)(PQ)(PQ),116,二、范式,主合取范式 1.大項(xiàng) 定義1-7.6:在有n個(gè)命題變元的析取式中，每個(gè)變元必出現(xiàn)且僅出現(xiàn)一次,稱之為大項(xiàng)。 例如，有兩個(gè)變元的大項(xiàng)及其真值表： M0 M1 M2 M3 P Q PQ PQ PQ PQ 0 0 F F F T T T 0 1 F T T F T T 1 0 T F T T F T 1 1 T T T T T F,117,二、范式,大項(xiàng)的性質(zhì) a).有n個(gè)變元，則

49、有 個(gè)大項(xiàng)。 b).每一組指派有且只有一個(gè)大項(xiàng)為F。 為了記憶方便，可將各組指派對應(yīng)的為F的大項(xiàng)分別記作M0,M1,M2,M -1 。 上例中變元為2個(gè)： M0 PQ M1 PQ M2 PQ M3 PQ,118,二、范式,命題變元為三個(gè)P、Q、R的大項(xiàng) M000PQR M100 PQR M001PQR M101 PQR M010PQR M110 PQR M011 PQR M111PQR c).每一個(gè)大項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其值為F ，在其余 -1種指派情況下均為T,119,二、范式,任意兩個(gè)不同大項(xiàng)的析取式永真 M001M100 (PQR )(PQR) 全體大項(xiàng)的合取式必為永假，記為：

50、Mi M0 M1 Mn-1 F,2,120,二、范式,方法：用公式的等價(jià)變換 先寫出給定公式的合取范式 A1A2.An 。 為使每個(gè)Ai變成大項(xiàng)，對缺少變元的析取式Ai補(bǔ)全變元，比如缺變元R，就用聯(lián)結(jié)永假式(RR)形式補(bǔ)R。 用分配律等公式加以整理。,121,二、范式,例如，求(PQ)R的主合取范式 (PQ)R (PQ)R (PQ)R (PR)(QR) (P(QQ)R)(PP)QR) (PQR) (PQR) (PQR)(PQR),122,二、范式,范式應(yīng)用： 例1. 安排課表，教語言課的教師希望將課程安排在第一或第三節(jié)；教數(shù)學(xué)課的教師希望將課程安排在第二或第三節(jié)；教原理課的教師希望將課程安排在

51、第一或第二節(jié)。如何安排課表，使得三位教師都滿意。 令L1、L2、L3分別表示語言課排在第一、第二、第三節(jié)。M1、M2、M3分別表示數(shù)學(xué)課排在第一、第二、第三節(jié)。 P1、P2、P3分別表示原理課排在第一、第二、第三節(jié)。,123,二、范式,三位教師都滿意的條件是： (L1L3)(M2M3)(P1P2 ) 為真。 將上式寫成析取范式(用分配律)得： (L1M2)(L1M3)(L3M2) (L3M3)(P1P2) (L1M2P1)(L1M3P1) (L3M2P1)(L3M3P1) (L1M2P2)(L1M3P2) (L3M2P2)(L3M3P2) 可以取(L3 M2P1)、(L1M3P2)為T， 得到

52、兩種排法。,124,二、范式,本節(jié)要掌握： 析取范式、合取范式、主析取范式、主合取范式的寫法，范式的應(yīng)用。 作業(yè) 第39頁：(2) d) , (3) d) , (4) d) ,(7),125,1-8. 命題推理理論,推理就是根據(jù)一個(gè)或幾個(gè)已知的判斷得出一個(gè)新的判斷的思維過程。稱這些已知的判斷為前提。得到的新的判斷為前提的有效結(jié)論。 定義1-8.1 設(shè)A和C是兩個(gè)命題公式，當(dāng)且僅當(dāng)AC為一重言式，即A C ，稱C是A的有效結(jié)論，或C可由A邏輯地推出。 該定義可推廣到有n個(gè)前提的情況：,126,1-8. 命題推理理論,即令H1，H2，Hn是已知的命題公式(前提)，若有 H1H2.Hn C 則稱C是

53、H1，H2，Hn的有效結(jié)論，簡稱結(jié)論。 實(shí)際上，推理的過程就是證明永真蘊(yùn)含式的過程 推理的嚴(yán)謹(jǐn)描述： （證明） 描述推理過程的命題公式序列，其中的每個(gè)公式或者是已知前提，或是由某些前提應(yīng)用推理規(guī)則得到的結(jié)論。 判別有效結(jié)論的過程是論證過程： 基本方法: 真值表法、證明法。,127,1-8. 命題推理理論,證明法：分 直接證法 間接證法 cp規(guī)則：條件論證 反證法：把結(jié)論的否定作為前提,128,1-8. 命題推理理論,一、真值表法： 設(shè)p1,p2,pn是出現(xiàn)于前提H1，H2，Hn和結(jié)論C中的全部命題變元，假定對p1,p2,pn作全部的真值指派，就能確定H1，H2，Hn和C的所有真值，列出真值表

54、判斷： （1）由前提（前件）為真是否能得到結(jié)論（后件）也為真 （2）由結(jié)論（后件）為假，是否能得到前提（前件）為假 。缺點(diǎn)：變元多時(shí)，列真值表不實(shí)際,129,1-8. 命題推理理論,二、證明法： 如何根據(jù)前提得到結(jié)論，需要有推理的規(guī)則。下面先介紹兩個(gè)推理規(guī)則。 規(guī)則P(引入前提規(guī)則)：在推理過程中，可以隨時(shí)引入前提。 規(guī)則T(引入結(jié)論規(guī)則)：在推理過程中，如果前邊有一個(gè)或幾個(gè)公式永真蘊(yùn)涵公式S，則可將S納入推理過程中。 在推理過程中，還要應(yīng)用教材43頁表1-8.3中的永真蘊(yùn)涵式I1-I16和表1-8.4中等價(jià)公式E1-E22 (常用的公式要熟記) 下面主要介紹三種推理方法：條件論證及反證法,1

55、30,重要的重言蘊(yùn)涵式(如教材第43頁所示),I1.PQP I2. PQQ I3. PPQ I4. QPQ I5. PPQ I6. QPQ I7. (PQ)P I8. (PQ)Q I9. P,Q PQ I10. P(PQ)Q I11. P(PQ)Q I12. Q(PQ)P I13. (PQ)(QR)PR I14. (PQ)(PR)(QR)R I15. AB (AC)(BC) I16. AB (AC)(BC),131,重要的等價(jià)公式:,對合律 E1 PP 交換律 E2 PQQP E3 PQQP 結(jié)合律 E4 P(QR)(PQ)R E5 P(QR)(PQ)R 分配律 E6 P(QR)(PQ)(PR) E7 P(QR)(PQ)(PR) 底-摩根定律 E8 (PQ)PQ E9 (PQ)PQ 冪等律 E10 PPP E11 PPP 同一律 E12 PFP E13 PTP,132,重