第九章離散數(shù)學(xué)PPT學(xué)習(xí)教案

1、會計學(xué)1第九章離散數(shù)學(xué)第九章離散數(shù)學(xué) 9.1 命題和命題聯(lián)結(jié)詞命題和命題聯(lián)結(jié)詞 一、一、 命題的概念命題的概念 命題命題：是能分辨真假的陳述句。是能分辨真假的陳述句。 例例1 判斷下列語句是否是命題。判斷下列語句是否是命題。 （1）空氣是人生存所必需的。）空氣是人生存所必需的。 （2）請把門關(guān)上。）請把門關(guān)上。 （3）南京是中國的首都。）南京是中國的首都。 （4）你吃飯了嗎？）你吃飯了嗎？ （5）x=3。（。（6）啊，真美呀?。┌?，真美呀！ (7) 明年春節(jié)是個大晴天。明年春節(jié)是個大晴天。 解解 語句（語句（1）,（3）,（5），），(7)(7)是陳述句是陳述句 （1）、（）、（3）、）、(7

2、)(7)是命題是命題 用真值來描述命題是用真值來描述命題是“真真” 還是還是“假假”。分別用。分別用“1”和和“0 0”表示表示 命題用大寫的拉丁字母命題用大寫的拉丁字母A、B、C、P、Q、或者帶下標(biāo)的大寫的字母來表示?；蛘邘聵?biāo)的大寫的字母來表示。 例例2 判斷下列陳述句是否是命題。判斷下列陳述句是否是命題。 P：地球外的星球上也有人；：地球外的星球上也有人； Q：小王是我的好朋友；：小王是我的好朋友； 解解 P、Q是命題是命題 第1頁/共80頁 二、命題聯(lián)結(jié)詞二、命題聯(lián)結(jié)詞 原子命題原子命題 ：由簡單句形成的命題。由簡單句形成的命題。 復(fù)合命題：復(fù)合命題：由一個或幾個原子命題通過聯(lián)結(jié)詞的由

3、一個或幾個原子命題通過聯(lián)結(jié)詞的聯(lián)接而構(gòu)成的命題。聯(lián)接而構(gòu)成的命題。 例例3 A：李明既是三好學(xué)生又是足球隊員。：李明既是三好學(xué)生又是足球隊員。 B：張平或者正在釣魚或者正在睡覺。：張平或者正在釣魚或者正在睡覺。 C：如果明天天氣晴朗，那么我們舉行運(yùn)動會：如果明天天氣晴朗，那么我們舉行運(yùn)動會。第2頁/共80頁定義五種聯(lián)結(jié)詞（或稱命題的五種運(yùn)算）定義五種聯(lián)結(jié)詞（或稱命題的五種運(yùn)算）。1. 否定否定“” 定義定義9-1 設(shè)設(shè)P是一個命題，利用是一個命題，利用“”和和P組成的復(fù)合命題稱為組成的復(fù)合命題稱為P的否命題，記作的否命題，記作“P” (讀作讀作“非非P”)。命題命題P P取值為真時，命題取值為

4、真時，命題P P取值為假；命題取值為假；命題P P取值為假時，命題取值為假時，命題P P取值為真。取值為真。 例例4 設(shè)設(shè)P：上海是一個城市；：上海是一個城市；Q：每個自然數(shù)都是偶數(shù)。則有：每個自然數(shù)都是偶數(shù)。則有 P：上海不是一個城市：上海不是一個城市; Q：并非每個自然數(shù)都是偶數(shù)。：并非每個自然數(shù)都是偶數(shù)。 P P P 1 0 0 1第3頁/共80頁 2合取合取“” 定義定義9-2 設(shè)設(shè)P和和Q是兩個命題，由是兩個命題，由P、Q利用利用“”組成的復(fù)合命題，稱為合取式復(fù)合命題，記作組成的復(fù)合命題，稱為合取式復(fù)合命題，記作“P Q”（讀作（讀作“P且且Q”）。）。 當(dāng)且僅當(dāng)命題當(dāng)且僅當(dāng)命題P

5、P和和Q Q均取值為真時，均取值為真時，P P Q Q才取值為真。才取值為真。 例例5 5 設(shè)設(shè)P P：我們?nèi)タ措娪?。：我們?nèi)タ措娪?。Q Q：房間里有十張桌子。則：房間里有十張桌子。則P P Q Q表示表示“我們?nèi)タ措娪安⑶曳块g里有十張桌子。我們?nèi)タ措娪安⑶曳块g里有十張桌子?！?PQPQ000010100111第4頁/共80頁3. 析取析取“” 定義定義9-39-3 由命題由命題P P和和Q Q利用利用“”組成的復(fù)合命題，稱為析取式復(fù)合命題，記作組成的復(fù)合命題，稱為析取式復(fù)合命題，記作“PQPQ”（讀作（讀作“P P或或Q Q”）。）。 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)P P和和Q Q至少有一個取值為真時，至

6、少有一個取值為真時，PQPQ取值為真。取值為真。 PQPQ000011101111例例6 將命題將命題“他可能是他可能是100米或米或400米賽跑的冠軍。米賽跑的冠軍。”符號化。符號化。解解令令 P：他可能是：他可能是100米賽跑冠軍；米賽跑冠軍； Q Q：他可能是：他可能是400400米賽跑冠軍。米賽跑冠軍。 則命題可表示為則命題可表示為PQ。第5頁/共80頁設(shè)設(shè)P P、Q Q是兩個命題，是兩個命題，P P異或異或Q Q是一個復(fù)合命題，記作是一個復(fù)合命題，記作PQPQ。 例例7 今天晚上我在家看電視或去劇場看戲。今天晚上我在家看電視或去劇場看戲。 令令P：今天晚上我在家看電視。：今天晚上我在

7、家看電視。Q：今天晚上我去劇場看戲：今天晚上我去劇場看戲 例例7中的命題可表示為中的命題可表示為P Q，或者表示為（，或者表示為（PQ(PQ)。 由于由于“ ”可用可用“”，“ ”和和“ ”表示，故我們不把它當(dāng)作表示，故我們不把它當(dāng)作基本基本聯(lián)結(jié)詞。聯(lián)結(jié)詞。 PQP Q000011101110第6頁/共80頁 4. 蘊(yùn)含蘊(yùn)含“” 定義定義9-49-4由命題由命題P P和和Q Q利用利用“”組成的復(fù)合命題，稱為蘊(yùn)含式復(fù)合命題，記作組成的復(fù)合命題，稱為蘊(yùn)含式復(fù)合命題，記作“PQPQ”（讀作（讀作“如果如果P P，則，則Q Q”）。）。 當(dāng)當(dāng)P為真，為真，Q為假時，為假時，PQ為假，否則為假，否則

8、PQPQ為真。為真。 PQPQ001011100111 例例8 將命題將命題“如果我得到這本小說，那么我今夜就讀完它。如果我得到這本小說，那么我今夜就讀完它。”符號化。符號化。解解 令令P：我得到這本小說；：我得到這本小說；Q：我今夜就讀完它。：我今夜就讀完它。 于是上述命題可表示為于是上述命題可表示為PQPQ。 例例9 若若P：雪是黑色的；：雪是黑色的；Q：太陽從西邊升起；：太陽從西邊升起；R：太陽從東邊升起。：太陽從東邊升起。則則PQPQ和和PRPR所表示的命題都是真的所表示的命題都是真的. . 第7頁/共80頁5等值等值“” 定義定義9-5 由命題由命題P和和Q，利用，利用“”組成的復(fù)合

9、命題，稱為等值式復(fù)合命題，記作組成的復(fù)合命題，稱為等值式復(fù)合命題，記作“PQ” （讀作（讀作“P當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)Q”）。）。 當(dāng)當(dāng)P P和和Q Q的真值相同時的真值相同時,P,PQ Q取真取真, ,否則取假。否則取假。 PQP Q001010100111 例例10 非本倉庫工作人員，一律不得入內(nèi)。非本倉庫工作人員，一律不得入內(nèi)。解解 令令P：某人是倉庫工作人員；：某人是倉庫工作人員； Q Q：某人可以進(jìn)入倉庫。：某人可以進(jìn)入倉庫。 則上述命題可表示為則上述命題可表示為PQ。第8頁/共80頁 例例1111 黃山比喜馬拉雅山高，當(dāng)且僅當(dāng)黃山比喜馬拉雅山高，當(dāng)且僅當(dāng)3 3是素數(shù)是素數(shù) 令令P P：黃

10、山比喜馬拉雅山高；：黃山比喜馬拉雅山高；Q Q：3 3是素數(shù)是素數(shù) 本例可符號化為本例可符號化為P PQ Q 從漢語的語義看，從漢語的語義看，P與與Q之間并無聯(lián)系，但就聯(lián)結(jié)之間并無聯(lián)系，但就聯(lián)結(jié)詞詞的定義來看，因為的定義來看，因為P的真值為假，的真值為假，Q的真值為真，的真值為真，所以所以PQ的真值為假。的真值為假。 對于上述五種聯(lián)結(jié)詞，應(yīng)注意到：對于上述五種聯(lián)結(jié)詞，應(yīng)注意到： 復(fù)合命題的真值只取決于構(gòu)成它的各原子命題的真復(fù)合命題的真值只取決于構(gòu)成它的各原子命題的真值，而與這些原子命題的內(nèi)容含義無關(guān)。值，而與這些原子命題的內(nèi)容含義無關(guān)。第9頁/共80頁 三、命題符號化三、命題符號化 利用聯(lián)結(jié)詞

11、可以把許多日常語句符號化?；静襟E如下：利用聯(lián)結(jié)詞可以把許多日常語句符號化。基本步驟如下： （1 1）從語句中分析出各原子命題，將它們符號化；）從語句中分析出各原子命題，將它們符號化； （2）使用合適的命題聯(lián)結(jié)詞，把原子命題逐個聯(lián)結(jié)起來，組成復(fù)合命題的符號化表示。）使用合適的命題聯(lián)結(jié)詞，把原子命題逐個聯(lián)結(jié)起來，組成復(fù)合命題的符號化表示。 例例12 用符號形式表示下列命題。用符號形式表示下列命題。 （1）如果明天早上下雨或下雪，那么我不去學(xué)校）如果明天早上下雨或下雪，那么我不去學(xué)校 （2）如果明天早上不下雨且不下雪，那么我去學(xué)校。）如果明天早上不下雨且不下雪，那么我去學(xué)校。 （3）如果明天早上不

12、是雨夾雪，那么我去學(xué)校。）如果明天早上不是雨夾雪，那么我去學(xué)校。 （4）只有當(dāng)明天早上不下雨且不下雪時，我才去學(xué)校。）只有當(dāng)明天早上不下雨且不下雪時，我才去學(xué)校。 解解 令令P：明天早上下雨；：明天早上下雨； Q：明天早上下雪；：明天早上下雪； R：我去學(xué)校。：我去學(xué)校。 （2）（）（P P Q Q）R； （1）（）（PQ） R；（4 4）RR（P P Q Q） （3）(PQ）R；第10頁/共80頁 例例13 將下列命題符號化將下列命題符號化 （1） 派小王或小李出差；派小王或小李出差； （2） 我們不能既劃船又跑步；我們不能既劃船又跑步； （3） 如果你來了，那么他唱不唱歌將看你是否伴奏而定

13、；如果你來了，那么他唱不唱歌將看你是否伴奏而定； （4） 如果李明是體育愛好者，但不是文藝愛好者，那么如果李明是體育愛好者，但不是文藝愛好者，那么 李明不是文體愛好者；李明不是文體愛好者； （5） 假如上午不下雨，我去看電影，否則就在家里看書。假如上午不下雨，我去看電影，否則就在家里看書。解解 （1） 令令P：派小王出差；：派小王出差；Q：派小李出差。：派小李出差。 命題符號化為命題符號化為PQ。 （2） 令令P：我們劃船；：我們劃船；Q：我們跑步。則命題可：我們跑步。則命題可 表示為表示為( (PQ）。 （3） 令令P：你來了；：你來了；Q：他唱歌；：他唱歌；R：你伴奏。：你伴奏。 則命題可

14、表示為則命題可表示為 P（QR） （4） 令令P：李明是體育愛好者；：李明是體育愛好者；Q：李明是文藝愛好者。：李明是文藝愛好者。 則命題可表示為則命題可表示為（P Q）（P Q） （5） 令令P：上午下雨；：上午下雨；Q：我去看電影；：我去看電影；R：我在家讀書。：我在家讀書。 則命題可表示為則命題可表示為（P Q）（PR）。 第11頁/共80頁練習(xí)練習(xí)7-1 1. 判斷下列語句哪些是命題，若是命題，則指出其真值。判斷下列語句哪些是命題，若是命題，則指出其真值。 （1） 只有小孩才愛哭。只有小孩才愛哭。 （2） X+6=Y （3） 銀是白的。銀是白的。 （4） 起來吧，我的朋友。起來吧，我的

15、朋友。( 是是 假假 ) ( 不是不是 )( 是是 真真 ) ( 不是不是 ) 2 將下列命題符號化將下列命題符號化 （1 1）我看見的既不是小張也不是老李。）我看見的既不是小張也不是老李。 解解 令令P：我看見的是小張；：我看見的是小張；Q：我看見的是老李。：我看見的是老李。 則該命題可表示為則該命題可表示為PQ （2）如果晚上做完了作業(yè)并且沒有其它的事，他就會看電視或聽音樂。如果晚上做完了作業(yè)并且沒有其它的事，他就會看電視或聽音樂。 解解 令令 P：他晚上做完了作業(yè)；：他晚上做完了作業(yè)；Q：他晚上有其它的事；：他晚上有其它的事； R：他看電視；：他看電視； S：他聽音樂。：他聽音樂。 則該

16、命題可表示為則該命題可表示為（PQ）（RS）第12頁/共80頁 9.2 命題公式命題公式 一一 、 命題公式的概念命題公式的概念 1. 命題常元命題常元 一個表示確定命題的大寫字母。一個表示確定命題的大寫字母。 2命題變元命題變元 一個沒有指定具體內(nèi)容的命題符號。一個沒有指定具體內(nèi)容的命題符號。 一個命題變元當(dāng)沒有對其賦予內(nèi)容時，它的真一個命題變元當(dāng)沒有對其賦予內(nèi)容時，它的真值不能確定，一旦用一個具體的命題代入，它值不能確定，一旦用一個具體的命題代入，它的真值就確定了。的真值就確定了。 第13頁/共80頁3. 命題公式命題公式 命題公式（或簡稱公式）是由命題公式（或簡稱公式）是由0、1和命題變

17、元以及命題聯(lián)結(jié)詞按一定的規(guī)則產(chǎn)生的符號串。和命題變元以及命題聯(lián)結(jié)詞按一定的規(guī)則產(chǎn)生的符號串。 定義定義9-6 （命題公式的遞歸定義。）（命題公式的遞歸定義。） （1） 0，1是命題公式；是命題公式； （2） 命題變元是命題公式；命題變元是命題公式； （3） 如果如果A是命題公式，則是命題公式，則A是命題公式；是命題公式； （4） 如果如果A和和B是命題公式，則（是命題公式，則（AB），）， （AB）,(AB）,(A B）也是命題公式；）也是命題公式； 有限次地利用上述（有限次地利用上述（1）（4）而產(chǎn)生的符號串是命題公式。）而產(chǎn)生的符號串是命題公式。 例例1 下列符號串是否為命題公式。下列符號

18、串是否為命題公式。 （1） P(QPR）；）； （2）（）（PQ）（QR） 解解 （1） 不是命題公式。不是命題公式。 （2 2） 是命題公式。是命題公式。 第14頁/共80頁二、真值指派二、真值指派 命題公式代表一個命題，但只有當(dāng)公式中的每一個命題變元都用一個確定的命題代入時，命題公式才有確定的真值，成為命題。命題公式代表一個命題，但只有當(dāng)公式中的每一個命題變元都用一個確定的命題代入時，命題公式才有確定的真值，成為命題。 定義定義97 設(shè)設(shè)F F為含有命題變元為含有命題變元P P1 1，P P2 2，,P,Pn n的命題公式，對的命題公式，對P P1 1，P P2 2，,P,Pn n分別指定

19、一個真值分別指定一個真值, ,稱為對公式稱為對公式F F的一組的一組真值指派真值指派。 公式與其命題變元之間的真值關(guān)系，可以用真值表的方法表示出來。公式與其命題變元之間的真值關(guān)系，可以用真值表的方法表示出來。 第15頁/共80頁 例例2 給給出公式出公式 F=(F=(（PQPQ）（QRQR）) ) (P (PR R）的真值表。）的真值表。 解解 公式公式F F的真值表如下：的真值表如下：PQRRPQQR(PQ)(QR)PRF0 0 00 0 00 0 10 0 10 1 00 1 00 1 10 1 11 0 01 0 01 0 11 0 11 1 01 1 01 1 11 1 11 10 0

20、1 10 01 10 01 10 00 00 01 11 11 11 11 11 10 00 00 01 10 00 00 01 11 11 10 01 10 00 00 01 10 00 00 00 01 10 01 10 00 00 01 10 01 11 11 10 0第16頁/共80頁 三、公式類型三、公式類型 定義定義9-8 如果對于命題公式如果對于命題公式F所包含的命題變元的任何一組真值指派，所包含的命題變元的任何一組真值指派，F(xiàn)的真值恒為真，則稱公式的真值恒為真，則稱公式F為為重言式重言式（或（或永真公式永真公式），常用），常用“1”表示。相反地，若對于表示。相反地，若對于F所包

21、含的命題變元的任何一組真值指派，所包含的命題變元的任何一組真值指派，F(xiàn)的真值恒為假，則稱公式的真值恒為假，則稱公式F為為矛盾式矛盾式（或（或永假公式永假公式），常用），常用“0”表示。如果至少有一組真值指派使公式表示。如果至少有一組真值指派使公式F的真值為真，則稱的真值為真，則稱F為為可滿足公式可滿足公式 。 例例3 構(gòu)造下列命題公式的真值表，并判斷它們是何種類型的公式構(gòu)造下列命題公式的真值表，并判斷它們是何種類型的公式 （1）（）（PQ） （PQ）；）； （2）（）（QP）（PQ）；）； （3 3）（）（PQPQ）（QRQR）（PPR R）。）。 第17頁/共80頁 解解 令令F F1 1=

22、 =（P PQ Q）（P P Q Q），），F(xiàn) F2 2= =（Q QP P）（ PQ PQ） F F1 1和和F F2 2的真值表如下：的真值表如下：P QPPQP Q(PQ)F1QPPQF20 0101011000 1110110101 0010111001 100101100由上可知：由上可知： F F1 1是是重言式重言式 , F F2 2是是矛盾式。矛盾式。 (3)的真值表如第的真值表如第4頁所示，它是可滿足公式。頁所示，它是可滿足公式。第18頁/共80頁9.3 命題公式的等值關(guān)系和蘊(yùn)含關(guān)系命題公式的等值關(guān)系和蘊(yùn)含關(guān)系一、命題公式的等值關(guān)系一、命題公式的等值關(guān)系 定義定義9-9 設(shè)設(shè)

23、A和和B是兩個命題公式是兩個命題公式, P1, P2, , Pn 是所有出現(xiàn)于是所有出現(xiàn)于A和和B中的命題變元，如果對于中的命題變元，如果對于P1, P2, , Pn 的任一組真值指派，的任一組真值指派，A和和B的真值都相同的真值都相同,則稱公式則稱公式A和和B等值等值，記為，記為A B,稱稱 AB為等值式為等值式。注意注意：（1 1）符號）符號“”與與“”的區(qū)別與聯(lián)系。的區(qū)別與聯(lián)系。 “”不是聯(lián)結(jié)詞，不是聯(lián)結(jié)詞，A AB B不表示一個公式，它表示兩個公式間的一種關(guān)系，即等值關(guān)系。不表示一個公式，它表示兩個公式間的一種關(guān)系，即等值關(guān)系。 “”是聯(lián)結(jié)詞，是聯(lián)結(jié)詞，A AB B是一個公式。是一個公

24、式。 AB當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)AB是永真公式。是永真公式。第19頁/共80頁 （2） 可以驗證等值關(guān)系是等價關(guān)系?？梢则炞C等值關(guān)系是等價關(guān)系。 即即自反性自反性：對任意公式：對任意公式A，有，有AA。 對稱性對稱性：對任意公式：對任意公式A，B，若，若AB，則則BA。 可傳遞性可傳遞性：對任意公式：對任意公式A A、B B、C C，若，若A AB B，B BC C，則，則A AC C。 （3）當(dāng)）當(dāng)A是重言式時，是重言式時，A1；當(dāng)；當(dāng)A是矛盾式是矛盾式時，則時，則A0。第20頁/共80頁二、基本的等值式二、基本的等值式 設(shè)設(shè)P、Q、R是命題變元，下表中列出了是命題變元，下表中列出了24個最基本的

25、等值式個最基本的等值式:編號 公公 式式E1E1E2E2E3E3E4E4E5E5E6E6E7E7 PQQP 交換律 PQQP 交換律 (PQ)R P(QR) 結(jié)合律 (PQ)R P(QR) 結(jié)合律 P(QR) (PQ)(PR) 分配律 P(QR) (PQ)(PR) 分配律 P0P 同一律 P1P 同一律 PP1 互否律 PP0 互否律 （P）P 雙重否定律 PPP 等冪律 PP P 等冪律 第21頁/共80頁編號 公公 式式E8E8E9E9E10E10E11E12E13E14E15P11 零一律 P00 零一律P（PQ）P 吸收律P（PQ）P 吸收律 （PQ）PQ 德.摩根定律 （PQ）PQ

26、德.摩根定律PQPQPQ (PQ)(PQ)P (QR) (PQ) RPQ (PQ)(QP) PQQP第22頁/共80頁三、等值式的判別三、等值式的判別 有兩種方法：真值表方法，命題演算方法有兩種方法：真值表方法，命題演算方法 1、真值表方法、真值表方法 例例1 用真值表方法證明用真值表方法證明 E10： (P Q) PQ 解解 令：令：A= (P Q)，B= PQ，構(gòu)造，構(gòu)造A，B 以及以及A B的真值表如下：的真值表如下： PQP Q (P Q) P Q PQAB000111110110100111100101 由于公式由于公式AB所標(biāo)記的列全為所標(biāo)記的列全為1，因此，因此AB。 10100

27、001第23頁/共80頁例例2 2 用真值表方法證明用真值表方法證明E E1111：P PQ QP P Q Q解解 令令A(yù)=PA=PQ Q，B=B= P P Q Q 構(gòu)造構(gòu)造A A，B B以及以及A AB B的真值表如下：的真值表如下：PQ P P QPQAB001111011111100001 由于公式由于公式AB所標(biāo)記的列全為所標(biāo)記的列全為1，因此，因此AB.110111第24頁/共80頁 例例3 用真值表方法判斷用真值表方法判斷PQPQ是否成立是否成立. 解解 令令A(yù)=PA=PQ Q，B=B= P PQ Q 構(gòu)造構(gòu)造A A，B B以及以及A AB B的真值表的真值表PQ P Q PQPQ

28、AB0011111011001001100 由于公式由于公式A AB B所標(biāo)記的列不全為所標(biāo)記的列不全為1 1，A AB B不是永真公式，因此不是永真公式，因此A AB B不成立。不成立。101100111第25頁/共80頁 (1) 代入規(guī)則代入規(guī)則 代入規(guī)則代入規(guī)則 對于重言式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，得到的仍是重言式。對于重言式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，得到的仍是重言式。2等值演算方法等值演算方法 例如例如 F=（PQ）（ QP）是重言式，若）是重言式，若用公式用公式AB代換命題變元代換命題變元P得公式得公式 F1=（AB）Q）（ Q（AB）

29、，）， F1仍是重言式。仍是重言式。注意：因為注意：因為A B當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A B是重言式。所以，若對于等值式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，則得到的仍是等值式。是重言式。所以，若對于等值式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，則得到的仍是等值式。第26頁/共80頁(2) 置置 換規(guī)則換規(guī)則 定義定義9-109-10 設(shè)設(shè)C C是命題公式是命題公式A A的一部分（即的一部分（即C C是公式是公式A A中連續(xù)的幾個符號），且中連續(xù)的幾個符號），且C C本身也是一個命題公式，則稱本身也是一個命題公式，則稱C C為公式為公式A A的的子公式。子公式。 例如例如 設(shè)公式

30、設(shè)公式A=A=（ PQPQ）（P PQ Q）（RR S S）。）。 則則 PQ，PQ，（，（PQ）（R S）等均是）等均是A的子公式，的子公式， 但但 PP，P P和和Q Q等均不是等均不是A A的子公式，的子公式， 置換規(guī)則置換規(guī)則 設(shè)設(shè)C C是公式是公式A A的子公式，的子公式，C CD D。如果將公式。如果將公式A A中的子公式中的子公式C C置換成公式置換成公式D D之后，得到的公式是之后，得到的公式是B B，則，則A AB B。 第27頁/共80頁(3)(3) 等值演算等值演算 等值演算是指利用已知的一些等值式，根據(jù)置換規(guī)則、代入規(guī)則以及等值關(guān)系的可傳遞性推導(dǎo)出另外一些等值式的過程。

31、等值演算是指利用已知的一些等值式，根據(jù)置換規(guī)則、代入規(guī)則以及等值關(guān)系的可傳遞性推導(dǎo)出另外一些等值式的過程。 由代入規(guī)則知前述的基本等值式，不僅對任意的命題變元由代入規(guī)則知前述的基本等值式，不僅對任意的命題變元P P，Q Q，R R是成立的，而且當(dāng)是成立的，而且當(dāng)P P，Q Q，R R分別為命題公式時，這些等值式也成立分別為命題公式時，這些等值式也成立 例例2 證明命題公式的等值關(guān)系：證明命題公式的等值關(guān)系： （PQ）（RQ）（PR）Q；證明證明 （PQ）（RQ） （ PQ）( RQ) E11 （ P R）Q E3( 分配律分配律) (PR)Q E10(德德.摩根定律摩根定律) (PR) Q E

32、11 所以（所以（PQ）（RQ）（PR）Q第28頁/共80頁 例例3 證明下列命題公式的等值關(guān)系證明下列命題公式的等值關(guān)系 (P Q ) ( P ( P Q ) ) P Q 證明證明 (P Q) ( P ( P Q) (P Q) ( ( P P ) Q ) E2(結(jié)合律結(jié)合律) (P Q) ( P Q) E7(等冪律等冪律) ( P Q ) ( P Q ) E1 (交換律交換律) P (Q (P Q) E2(結(jié)合律結(jié)合律) P Q E 1，E9(交換律，吸收律交換律，吸收律) 第29頁/共80頁例例4 判別下列公式的類型。判別下列公式的類型。 （1） Q ( P（ PQ）) （2）（）（PQ）

33、 P解解（1） Q （ P（ PQ） Q （P（ PQ） E11,E6 Q （P P）（PQ） E3 Q （1（PQ） E5 Q （PQ） E4 Q P Q E10 （Q Q） P E1,E2 0 E5,E8 所以所以Q ( P ( PQ)是矛盾式。是矛盾式。 （2） （PQ） P （ PQ） P E11 P E9 于是該公式是可滿足式。于是該公式是可滿足式。 第30頁/共80頁三、命題公式的蘊(yùn)含關(guān)系三、命題公式的蘊(yùn)含關(guān)系 定義定義9-119-11 設(shè)設(shè)A A，B B是兩個公式，若公式是兩個公式，若公式A AB B是重言式，即是重言式，即A AB B1 1，則稱公式，則稱公式A A蘊(yùn)含公式蘊(yùn)含

34、公式B B，記作，記作A AB B。稱。稱“A AB B”為為蘊(yùn)含式蘊(yùn)含式。 注意：注意：符號符號“”和和 “”的區(qū)別和聯(lián)系與符號的區(qū)別和聯(lián)系與符號“”與與“”的區(qū)別和聯(lián)系類似。的區(qū)別和聯(lián)系類似。 “”不是聯(lián)結(jié)詞，不是聯(lián)結(jié)詞， “AB”不是公式，它表示公式不是公式，它表示公式A與與B之間存在蘊(yùn)含關(guān)系。之間存在蘊(yùn)含關(guān)系。 “”是聯(lián)系詞，是聯(lián)系詞，AB是一個公式。是一個公式。 AB當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)AB是永真公式是永真公式 。第31頁/共80頁 A AB B是偏序關(guān)系是偏序關(guān)系 即即 自反性自反性：AA。 反對稱反對稱：若：若AB，BA，則，則AB。 傳遞性傳遞性：若：若AB，BC，則，則 AC。

35、反對稱性的證明：反對稱性的證明： 設(shè)設(shè)AB且且BA， 由定義由定義7-11 AB1且且BA1于是于是AB(AB) (BA) E14 1 1 1因此因此 AB第32頁/共80頁傳遞性的證明：傳遞性的證明： 設(shè)設(shè)A AB B，B BC C， 則則A AB B1 1，B BC C1 1 ( ( A A B B C)C) ( ( A AB B C)C) (A (AB) B) C)C) ( ( A A (B(BC)C) (1 (1 C)C) ( ( A A 1)1) 1 1 1 1 1 1 因此因此 A AC.C.于是于是 A AC C A A C C ( ( A A C)C) (B(BB) B) 第3

36、3頁/共80頁 四、基本的蘊(yùn)含式四、基本的蘊(yùn)含式 編號蘊(yùn)蘊(yùn) 含含 式式I1PQPI2PQQI3P PQI4QPQI5P PQI6QPQI7 (PQ)PI8 (PQ) Q 設(shè)設(shè)P P、Q Q、R R是命題變元，下表中列出了是命題變元，下表中列出了1616個最基本的蘊(yùn)含式。個最基本的蘊(yùn)含式。第34頁/共80頁編號蘊(yùn)蘊(yùn) 含含 式式I9PQPQ 或表示為或表示為：P、QPQI10 P (P Q) Q P、(P Q)QI11P (PQ)Q P、PQQI12 Q (PQ)P Q、PQPI13(PQ) (QR)PR PQ、QRPRI14(P Q) (PR) (QR) R P Q、PR、QRRI15PQ(P

37、R)(Q R)I16PQ(P R)(Q R)第35頁/共80頁五、蘊(yùn)含式的判別五、蘊(yùn)含式的判別 判定判定“A B”是否成立的問題可轉(zhuǎn)化為判定是否成立的問題可轉(zhuǎn)化為判定A B是否為重言式，有下述判定方法：是否為重言式，有下述判定方法： （1）真值表；）真值表； （2）等值演算；）等值演算；（3）假定前件）假定前件A為真；為真； （4）假定后件）假定后件B為假。為假。 1. 真值表方法真值表方法 例例4 證明證明I14 ：(（PQ）（P R）（Q R）) R 證明證明 令公式令公式 F =（PQ）（PR）（QR）R， 其真值表如下：其真值表如下： 第36頁/共80頁 公式公式F對任意的一組真值指派

38、取值均為對任意的一組真值指派取值均為1，故，故F是重言式。是重言式。P Q RP Q RPQPQPRPRQ RQ R(PQ) (PR(PQ) (PR）（ Q RQ R）F0 0 00 0 00 0 10 0 10 1 00 1 00 1 10 1 11 0 01 0 01 0 11 0 11 1 01 1 01 1 11 1 10 00 01 11 11 11 11 11 11 11 11 11 10 01 10 01 11 11 10 01 11 11 10 01 10 00 00 01 10 01 10 01 11 11 11 11 11 11 11 11 1第37頁/共80頁 2. 等值

39、演算方法等值演算方法 例例5 證明證明 I I1111：PP（P PQ Q） Q Q 證明證明 （PP（P PQ Q） Q Q （PP（ PQPQ） Q Q E E1111 （ PP （ PQPQ） E E1010 （ PQPQ） （ PQPQ） E E2 2 1 1 代入規(guī)則代入規(guī)則,E,E5 5 因此因此 PP（P PQ Q） Q Q 第38頁/共80頁 3. 假定前件假定前件A真真 假定前件假定前件A A為真，檢查在此情況下，其后件為真，檢查在此情況下，其后件B B是否也為真。是否也為真。 ABAB001011100111 例例6證明證明 I12 : Q （PQ） P證明證明令前件令前件

40、 Q（PQ）為真，）為真，則則 Q為真為真, 且且PQ為真。為真。于是于是Q為假，因而為假，因而P也為假。由此也為假。由此 P為真。為真。故蘊(yùn)含式故蘊(yùn)含式 I12 成立。成立。第39頁/共80頁 4、 假定后件假定后件B假假 假定后件假定后件B B為假，檢查在此情況下，其前件為假，檢查在此情況下，其前件A A是否也為假是否也為假. . 例例7 證明蘊(yùn)含式證明蘊(yùn)含式(PQ) (RS) (P R) (Q S)證明證明 令后件令后件(P R)(Q S)為假，則為假，則P R為真，為真，Q S為假為假,于是于是P、R均為真，而均為真，而Q和和S至少一個為假。至少一個為假。 由此可知由此可知 PQ與與R

41、S中至少一個為假中至少一個為假, 因此因此(PQ) (RS)為假為假.故上述蘊(yùn)含式成立。故上述蘊(yùn)含式成立。第40頁/共80頁練習(xí)練習(xí) 7-31判斷下列等值式是否成立判斷下列等值式是否成立 （1）（）（PQ） （R Q）（PR） Q （2） （PQ）（P Q）（ PQ）解解（1）（）（PQ）（RQ）（ PQ） （ RQ） E11（ P R）Q E3 （PR）Q E10（2）（）（P Q）（ PQ） (（ PQ）（ QP）) E6，E10 (（PQ）（QP）) E11 （PQ） E14（PR）Q E11第41頁/共80頁2 2判定蘊(yùn)含式判定蘊(yùn)含式P P（Q QR R） （P PQ Q）（P PR

42、R）是否成立）是否成立 解解假定后件（假定后件（PQ）（PR）為假）為假，則則PQ為真，為真，PR為假。為假。由由P PR R為假為假, ,得得P P為真，為真，R R為假。為假。 又又PQ為真，故得為真，故得Q為為真。真。于是于是P為真，為真，QR為假。為假。從而從而 P（QR）為假。）為假。因此蘊(yùn)含式成立。因此蘊(yùn)含式成立。第42頁/共80頁9.49.4范式范式一、 析取范式和合取范式析取范式和合取范式 定義定義9-129-12 一個命題公式若它具有一個命題公式若它具有P P1 1* *PP2 2* *PPn n* *的的形式（形式（n1n1），其中），其中P Pi i* *是命題變元是命題

43、變元P Pi i或其否定或其否定P Pi i ，則稱其為則稱其為質(zhì)合取式質(zhì)合取式。 例如例如, ,PQRSPQRS是由命題變元是由命題變元P P、Q Q、R R、S S組組成的一質(zhì)合取式。成的一質(zhì)合取式。 定義定義9-139-13 一個命題公式若具有一個命題公式若具有P P1 1* *PP2 2* *PPn n* *（n1n1）的形式，其中）的形式，其中P P* *i i是命題變元是命題變元P Pi i或是其否定或是其否定P Pi i ，則稱其為，則稱其為質(zhì)析取式質(zhì)析取式。 例如例如, , QPQPR R是由命題變元是由命題變元P P、Q Q、R R組成的組成的一質(zhì)析取式。一質(zhì)析取式。 第43

44、頁/共80頁 定理定理9-49-4 （1）一質(zhì)合取式為永假式的充分必要條件是，它同時包含某個命題變元一質(zhì)合取式為永假式的充分必要條件是，它同時包含某個命題變元P及其否定及其否定P。 （2）一質(zhì)析取式為永真式的充分必要條件是，它同時包含某個命題變元一質(zhì)析取式為永真式的充分必要條件是，它同時包含某個命題變元P及其否定及其否定P。 證明證明（2）必要性必要性：假設(shè)：假設(shè)A= P1*P2*Pn*為一質(zhì)析取式，且為一質(zhì)析取式，且A為一永真式。為一永真式。 (反證法反證法) 假設(shè)假設(shè)A式中不同時包含任一命題變元及其否定式中不同時包含任一命題變元及其否定， 則在則在A中，當(dāng)中，當(dāng)Pi*為為Pi時指派時指派P

45、i取取0，當(dāng)，當(dāng)Pi*為為Pi時，指派時，指派Pi取取1。(i =1,2,n).這樣的一組真值指派使這樣的一組真值指派使A的真值取的真值取0，這與，這與A為永真式矛盾。為永真式矛盾。 例如例如A=P1P2P3.則則(P1,P2,P3)=(0,1,0)的指派，使的指派，使A的真值為的真值為0. 充分性充分性：設(shè)：設(shè)A含命題變元含命題變元Pi和和Pi，而，而PiPi是永真式，是永真式， 由結(jié)合律和零一律，由結(jié)合律和零一律，A的真值必為的真值必為1，故，故A也是永真式。也是永真式。 第44頁/共80頁定義定義9-149-14質(zhì)合取式的析取稱為析取范式。即質(zhì)合取式的析取稱為析取范式。即具有具有A A1

46、 1AA2 2AAn n(n1)(n1)的形式的公式，其中的形式的公式，其中A Ai i是是質(zhì)合取式。質(zhì)合取式。 例如例如，F(xiàn) F1 1=P(PQ)R(=P(PQ)R( PP QR)QR)是一析是一析取范式。取范式。 定義定義9-15質(zhì)析取式的合取稱為合取范式。質(zhì)析取式的合取稱為合取范式。即具有即具有A A1 1AA2 2AAn n (n1)(n1)的形式的公式，其的形式的公式，其中中AiAi是質(zhì)析取式。是質(zhì)析取式。 例如例如，F(xiàn) F2 2= = P(PQ)R(PP(PQ)R(P QR)QR)是一合取是一合取范式。范式。 F F3 3=(=( PRQ)(PQ)R(PPRQ)(PQ)R(P R)

47、R)也是一合也是一合取范式。取范式。 第45頁/共80頁二、求公式的析取范式和合取范式二、求公式的析取范式和合取范式任何一個命題公式都可以變換為與它等值的析任何一個命題公式都可以變換為與它等值的析取范式或合取范式。取范式或合取范式。按下列步驟進(jìn)行：按下列步驟進(jìn)行：（1 1）利用）利用E E1111，E E1212和和E E1414消去公式中的運(yùn)算符消去公式中的運(yùn)算符“”和和“”； (2) (2) 利用德利用德摩根定律將否定符號摩根定律將否定符號“ ”向內(nèi)向內(nèi)深入，使之只作用于命題變元；深入，使之只作用于命題變元； （3 3）利用雙重否定律）利用雙重否定律E E6 6將將 ( ( P)P)置換成

48、置換成P P； （4 4）利用分配律、結(jié)合律將公式歸約為合取范）利用分配律、結(jié)合律將公式歸約為合取范式或析取范式。式或析取范式。第46頁/共80頁 例例1 求求F1=(P(QR)S的合取范式和析取范式的合取范式和析取范式 解解 F1 (P( QR)S E11 P ( QR)S E10 P(Q R)S (析取范式析取范式) E10 ,E6 又又 F1 P(Q R)S ( PS)(Q R) E1 ,E2 ( PSQ)( PS R) （合取范式）（合取范式） E3 另外由另外由 F1 ( PSQ)( PS R)( P( PS R)(S( PS R)(Q( PS R) E3PS(Q P)(QS)(Q

49、R) （析取范式）（析取范式） E9 ,E13第47頁/共80頁例例2 2 求求 F F2 2= = (PQ) (PQ) (PQ) (PQ)的析取范式、合取的析取范式、合取范式。范式。解解F2 ( (PQ) (PQ)(PQ) (PQ) E14 (PQ)(PQ)( (PQ) (PQ) E11,E6 (P(Q(PQ)( P Q( P Q) E2,E10,E10 (PQ)( P Q) （合取范式）（合取范式） E2,E9 (P( P Q)(Q( P Q) E3 (P P) (P Q)( PQ)(Q Q)（析取范式）（析取范式） E3第48頁/共80頁 定理定理9-59-5（1）公式）公式A為永真式的

50、充分必要條件是，為永真式的充分必要條件是，A的合取范式中每一質(zhì)析取式至少包含一對互為否定的析取項。的合取范式中每一質(zhì)析取式至少包含一對互為否定的析取項。 三、利用范式判定公式類型三、利用范式判定公式類型 證明證明（2）必要性必要性（用反證法）：（用反證法）：假設(shè)假設(shè)AA1A2An中某個中某個Ai不包含一對互為否定的合取項，不包含一對互為否定的合取項， （2）公式）公式A為永假式的充分必要條件是，為永假式的充分必要條件是，A的析取范式中每一質(zhì)合取式至少包含一對互為否定的合取項。的析取范式中每一質(zhì)合取式至少包含一對互為否定的合取項。 則由定理則由定理9-4知，知，Ai不是矛盾式。不是矛盾式。 于是

51、存在一組真值指派使于是存在一組真值指派使Ai取值為真。取值為真。 對同一組真值指派，對同一組真值指派，A的取值也必為真，這與的取值也必為真，這與A是矛盾式不符，假設(shè)不成立。是矛盾式不符，假設(shè)不成立。 充分性充分性：假設(shè)任一：假設(shè)任一Ai(1in)中含有形如中含有形如PP合取式，其中合取式，其中P為命題變元。于是由定理為命題變元。于是由定理9-4知，每一知，每一Ai(1in)都為矛盾式，因此都為矛盾式，因此A1A2An必為矛盾式，即必為矛盾式，即A為矛盾式。為矛盾式。 因此因此A的析取范式中每一質(zhì)合取式至少包含一對互為否定的合取項。的析取范式中每一質(zhì)合取式至少包含一對互為否定的合取項。 第49頁

52、/共80頁 例例3 3 判別公式判別公式A=PA=P (P(Q (P(QP)P)是否為重言式或矛盾式是否為重言式或矛盾式。 解解 A A P(P(P(P( QP) EQP) E1111 P(PP(P Q)(PP) (Q)(PP) (析取范式析取范式) E) E3 3根據(jù)定理根據(jù)定理9-59-5，A A不是矛盾式。不是矛盾式。 又又A AP(P(P(P( QP) QP) （ PPPP）（ PP QP)QP)（合取范式）（合取范式） E E3 3由定理由定理9-59-5知，知，A A是重言式。是重言式。第50頁/共80頁例例4 4 利用范式判斷公式利用范式判斷公式P(P Q)的類型。的類型。 解解

53、 P(P Q) (P (P Q) ( P(P Q)E12 (P Q) ( P ( PQ) E 10 (P Q)P (析取范式析取范式) E 9 由定理由定理9-5，該公式不是永假公式。，該公式不是永假公式。 (PP ) ( P Q) （合取范式）（合取范式）E1，E 3 由定理由定理9-5，該公式也不是永真公式。，該公式也不是永真公式。由上可知，該公式是一可滿足公式。由上可知，該公式是一可滿足公式。 又又 P(P Q)(P Q)P第51頁/共80頁四、主析取范式和主合取范式四、主析取范式和主合取范式 定義定義9-169-16 設(shè)有命題變元設(shè)有命題變元P P1 1，P P2 2，,P,Pn n

54、，形如形如 的的命題公式稱為是由命題變元命題公式稱為是由命題變元P P 1 1，P P2 2，P Pn n所產(chǎn)生的所產(chǎn)生的最小項。而形如最小項。而形如 的命題公式稱為是由命題變元的命題公式稱為是由命題變元P P1 1，P P2 2，P Pn n所產(chǎn)生的最大項所產(chǎn)生的最大項 。其中。其中P Pi i* *為為P Pi i或為或為 P Pi i(i=1,2,(i=1,2,n).n). 例如例如, ,P P1 1PP2 2PP3 3， P P1 1PP2 2 P P3 3均是由均是由P P1 1，P P2 2，P P3 3所產(chǎn)所產(chǎn)生的最小項。生的最小項。 P P1 1 P P2 2PP3 3是由是由

55、P P1 1，P P2 2，P P3 3產(chǎn)生的一個最大項。產(chǎn)生的一個最大項。 *1iniP*1iniP第52頁/共80頁 定義定義9-179-17由不同最小項所組成的析取式，由不同最小項所組成的析取式，稱為稱為主析取范式主析取范式。 定義定義9-189-18由不同最大項所組成的合取式，由不同最大項所組成的合取式，稱為稱為主合取范式主合取范式。例如例如( ( P P1 1P P2 2 P P3 3) ) ( ( P P1 1 P P2 2 P P3 3) ) (P(P1 1 P P2 2 P P3 3) )是一個主析取范式。是一個主析取范式。 (P(P1 1P P2 2 P P3 3) ) (P

56、(P1 1 P P2 2 P P3 3) ) ( ( P P1 1P P2 2P P3 3) ) ( ( P P1 1 P P2 2P P3 3) )是一個主合取范式。是一個主合取范式。第53頁/共80頁 例例4 求公式求公式 F1 = P(P (QP)和公式和公式 F2 = (PQ) (PQ)的主析取范式的主析取范式. 解解 F1P(P( QP) E11 P(P Q)(PP) E3( P(Q Q)(P Q)(P(Q Q) E7,E4,E5 ( PQ)( P Q)(P Q)(PQ)(P Q) E3 ( PQ)( P Q)(P Q)(PQ) E1,E7 五、求公式的主析取范式和主合取范式五、求公

57、式的主析取范式和主合取范式對任一給定的公式除了用求范式時的四個步驟外，還要利用同一律、等冪律、互否律、分配律等進(jìn)一步將質(zhì)合取式（質(zhì)析取式）變換為最小項（最大項）的形式。對任一給定的公式除了用求范式時的四個步驟外，還要利用同一律、等冪律、互否律、分配律等進(jìn)一步將質(zhì)合取式（質(zhì)析取式）變換為最小項（最大項）的形式。第54頁/共80頁 F2(PQ) (PQ) ( P Q) (PQ) E11 ( P PQ) (Q PQ) E3 0 0 E 1, E 5 0 定理定理9-6 每一個不為永假的命題公式每一個不為永假的命題公式F F（P P1 1, P, P2 2, , , P, Pn n）必與一個由）必與一

58、個由P P1 1，P P2 2，P Pn n所產(chǎn)生的主析所產(chǎn)生的主析取范式等值。取范式等值。 永真公式永真公式的主析取范式包含所有的主析取范式包含所有2 2n n個最小項。個最小項。 永假公式永假公式的主析取范式是一個空公式。用的主析取范式是一個空公式。用0 0表表示。示。第55頁/共80頁例例5 求公式求公式 F F1 1= (P= (PQ)Q) (P(PQ)Q)和和 公式公式F F2 2=P=P(P(P (Q(QP)P)的主合取范式的主合取范式F F1 1 ( ( P P Q )Q ) ( P( P Q ) Q ) E E1111 ( ( P P Q)Q) (P(P (Q(QQ)Q) (

59、( Q Q (P(PP)P) E E 5 5, E, E4 4 ( ( P P Q)Q) (P(P Q)Q) (P(PQ)Q) (P(PQ)Q) ( ( P PQ) EQ) E 3 3 (P (P Q)Q) (P(PQ)Q) ( ( P P Q)Q) ( ( P PQ) Q) E E 7 7第56頁/共80頁 解解 F2 P(P( QP) E11 ( PP)( P QP) E3 11 E5,E1 1 定理定理9-7 每一個不為永真的公式每一個不為永真的公式 F(PF(P1 1, P, P2 2, , , P, Pn n）必與一個由必與一個由P P1 1, P, P2 2, , , P, Pn

60、n所產(chǎn)生的主合取范式等值。所產(chǎn)生的主合取范式等值。永假公式永假公式的主合取范式包含所有的主合取范式包含所有 2 2n n個最大項。個最大項。永真公式永真公式的主合取范式是一空公式，用的主合取范式是一空公式，用1 1表示。表示。 第57頁/共80頁 六、利用主范式判定公式類型六、利用主范式判定公式類型 1. 利用主析取范式判定利用主析取范式判定 (1) (1) 若公式若公式 F(PF(P1 1, P, P2 2，P Pn n) )的主析的主析取范式包含所有取范式包含所有2 2n n個最小項，則個最小項，則 F F是永真公式。是永真公式。例如，例例如，例4 4中的中的 F F1 1。 (2) (2