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

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

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

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

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

5、P和和Q Q均取值為真時(shí)，均取值為真時(shí)，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頁(yè)/共80頁(yè)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至少有一個(gè)取值為真時(shí)，至

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

7、家看電視。Q：今天晚上我去劇場(chǎng)看戲：今天晚上我去劇場(chǎng)看戲 例例7中的命題可表示為中的命題可表示為P Q，或者表示為（，或者表示為（PQ(PQ)。 由于由于“ ”可用可用“”，“ ”和和“ ”表示，故我們不把它當(dāng)作表示，故我們不把它當(dāng)作基本基本聯(lián)結(jié)詞。聯(lián)結(jié)詞。 PQP Q000011101110第6頁(yè)/共80頁(yè) 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為假時(shí)，為假時(shí)，PQ為假，否則為假，否則

8、PQPQ為真。為真。 PQPQ001011100111 例例8 將命題將命題“如果我得到這本小說(shuō)，那么我今夜就讀完它。如果我得到這本小說(shuō)，那么我今夜就讀完它?！狈?hào)化。符號(hào)化。解解 令令P：我得到這本小說(shuō)；：我得到這本小說(shuō)；Q：我今夜就讀完它。：我今夜就讀完它。 于是上述命題可表示為于是上述命題可表示為PQPQ。 例例9 若若P：雪是黑色的；：雪是黑色的；Q：太陽(yáng)從西邊升起；：太陽(yáng)從西邊升起；R：太陽(yáng)從東邊升起。：太陽(yáng)從東邊升起。則則PQPQ和和PRPR所表示的命題都是真的所表示的命題都是真的. . 第7頁(yè)/共80頁(yè)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的真值相同時(shí)的真值相同時(shí),P,PQ Q取真取真, ,否則取假。否則取假。 PQP Q001010100111 例例10 非本倉(cāng)庫(kù)工作人員，一律不得入內(nèi)。非本倉(cāng)庫(kù)工作人員，一律不得入內(nèi)。解解 令令P：某人是倉(cāng)庫(kù)工作人員；：某人是倉(cāng)庫(kù)工作人員； Q Q：某人可以進(jìn)入倉(cāng)庫(kù)。：某人可以進(jìn)入倉(cāng)庫(kù)。 則上述命題可表示為則上述命題可表示為PQ。第8頁(yè)/共80頁(yè) 例例1111 黃山比喜馬拉雅山高，當(dāng)且僅當(dāng)黃山比喜馬拉雅山高，當(dāng)且僅當(dāng)3 3是素?cái)?shù)是素?cái)?shù) 令令P P：黃

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

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

12、是雨夾雪，那么我去學(xué)校。）如果明天早上不是雨夾雪，那么我去學(xué)校。 （4）只有當(dāng)明天早上不下雨且不下雪時(shí)，我才去學(xué)校。）只有當(dāng)明天早上不下雨且不下雪時(shí)，我才去學(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頁(yè)/共80頁(yè) 例例13 將下列命題符號(hào)化將下列命題符號(hào)化 （1） 派小王或小李出差；派小王或小李出差； （2） 我們不能既劃船又跑步；我們不能既劃船又跑步； （3） 如果你來(lái)了，那么他唱不唱歌將看你是否伴奏而定

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

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

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

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

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

18、串是否為命題公式。 （1） P(QPR）；）； （2）（）（PQ）（QR） 解解 （1） 不是命題公式。不是命題公式。 （2 2） 是命題公式。是命題公式。 第14頁(yè)/共80頁(yè)二、真值指派二、真值指派 命題公式代表一個(gè)命題，但只有當(dāng)公式中的每一個(gè)命題變?cè)加靡粋€(gè)確定的命題代入時(shí)，命題公式才有確定的真值，成為命題。命題公式代表一個(gè)命題，但只有當(dāng)公式中的每一個(gè)命題變?cè)加靡粋€(gè)確定的命題代入時(shí)，命題公式才有確定的真值，成為命題。 定義定義97 設(shè)設(shè)F F為含有命題變?cè)獮楹忻}變?cè)狿 P1 1，P P2 2，,P,Pn n的命題公式，對(duì)的命題公式，對(duì)P P1 1，P P2 2，,P,Pn n分別指定

19、一個(gè)真值分別指定一個(gè)真值, ,稱為對(duì)公式稱為對(duì)公式F F的一組的一組真值指派真值指派。 公式與其命題變?cè)g的真值關(guān)系，可以用真值表的方法表示出來(lái)。公式與其命題變?cè)g的真值關(guān)系，可以用真值表的方法表示出來(lái)。 第15頁(yè)/共80頁(yè) 例例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頁(yè)/共80頁(yè) 三、公式類型三、公式類型 定義定義9-8 如果對(duì)于命題公式如果對(duì)于命題公式F所包含的命題變?cè)娜魏我唤M真值指派，所包含的命題變?cè)娜魏我唤M真值指派，F(xiàn)的真值恒為真，則稱公式的真值恒為真，則稱公式F為為重言式重言式（或（或永真公式永真公式），常用），常用“1”表示。相反地，若對(duì)于表示。相反地，若對(duì)于F所包

21、含的命題變?cè)娜魏我唤M真值指派，所包含的命題變?cè)娜魏我唤M真值指派，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頁(yè)/共80頁(yè) 解解 令令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頁(yè)所示，它是可滿足公式。頁(yè)所示，它是可滿足公式。第18頁(yè)/共80頁(yè)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是兩個(gè)命題公式是兩個(gè)命題公式, P1, P2, , Pn 是所有出現(xiàn)于是所有出現(xiàn)于A和和B中的命題變?cè)?，如果?duì)于中的命題變?cè)?，如果?duì)于P1, P2, , Pn 的任一組真值指派，的任一組真值指派，A和和B的真值都相同的真值都相同,則稱公式則稱公式A和和B等值等值，記為，記為A B,稱稱 AB為等值式為等值式。注意注意：（1 1）符號(hào)）符號(hào)“”與與“”的區(qū)別與聯(lián)系。的區(qū)別與聯(lián)系。 “”不是聯(lián)結(jié)詞，不是聯(lián)結(jié)詞，A AB B不表示一個(gè)公式，它表示兩個(gè)公式間的一種關(guān)系，即等值關(guān)系。不表示一個(gè)公式，它表示兩個(gè)公式間的一種關(guān)系，即等值關(guān)系。 “”是聯(lián)結(jié)詞，是聯(lián)結(jié)詞，A AB B是一個(gè)公式。是一個(gè)公

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

25、等值式個(gè)最基本的等值式:編號(hào) 公公 式式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頁(yè)/共80頁(yè)編號(hào) 公公 式式E8E8E9E9E10E10E11E12E13E14E15P11 零一律 P00 零一律P（PQ）P 吸收律P（PQ）P 吸收律 （PQ）PQ 德.摩根定律 （PQ）PQ

26、德.摩根定律PQPQPQ (PQ)(PQ)P (QR) (PQ) RPQ (PQ)(QP) PQQP第22頁(yè)/共80頁(yè)三、等值式的判別三、等值式的判別 有兩種方法：真值表方法，命題演算方法有兩種方法：真值表方法，命題演算方法 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頁(yè)/共80頁(yè)例例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頁(yè)/共80頁(yè) 例例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頁(yè)/共80頁(yè) (1) 代入規(guī)則代入規(guī)則 代入規(guī)則代入規(guī)則 對(duì)于重言式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入，得到的仍是重言式。對(duì)于重言式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入，得到的仍是重言式。2等值演算方法等值演算方法 例如例如 F=（PQ）（ QP）是重言式，若）是重言式，若用公式用公式AB代換命題變?cè)鷵Q命題變?cè)狿得公式得公式 F1=（AB）Q）（ Q（AB）

29、，）， F1仍是重言式。仍是重言式。注意：因?yàn)樽⒁猓阂驗(yàn)锳 B當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A B是重言式。所以，若對(duì)于等值式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入，則得到的仍是等值式。是重言式。所以，若對(duì)于等值式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入，則得到的仍是等值式。第26頁(yè)/共80頁(yè)(2) 置置 換規(guī)則換規(guī)則 定義定義9-109-10 設(shè)設(shè)C C是命題公式是命題公式A A的一部分（即的一部分（即C C是公式是公式A A中連續(xù)的幾個(gè)符號(hào)），且中連續(xù)的幾個(gè)符號(hào)），且C C本身也是一個(gè)命題公式，則稱本身也是一個(gè)命題公式，則稱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頁(yè)/共80頁(yè)(3)(3) 等值演算等值演算 等值演算是指利用已知的一些等值式，根據(jù)置換規(guī)則、代入規(guī)則以及等值關(guān)系的可傳遞性推導(dǎo)出另外一些等值式的過(guò)程。

31、等值演算是指利用已知的一些等值式，根據(jù)置換規(guī)則、代入規(guī)則以及等值關(guān)系的可傳遞性推導(dǎo)出另外一些等值式的過(guò)程。 由代入規(guī)則知前述的基本等值式，不僅對(duì)任意的命題變?cè)纱胍?guī)則知前述的基本等值式，不僅對(duì)任意的命題變?cè)狿 P，Q Q，R R是成立的，而且當(dāng)是成立的，而且當(dāng)P P，Q Q，R R分別為命題公式時(shí)，這些等值式也成立分別為命題公式時(shí)，這些等值式也成立 例例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頁(yè)/共80頁(yè) 例例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頁(yè)/共80頁(yè)例例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頁(yè)/共80頁(yè)三、命題公式的蘊(yùn)含關(guān)系三、命題公式的蘊(yùn)含關(guān)系 定義定義9-119-11 設(shè)設(shè)A A，B B是兩個(gè)公式，若公式是兩個(gè)公式，若公式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)含式。 注意：注意：符號(hào)符號(hào)“”和和 “”的區(qū)別和聯(lián)系與符號(hào)的區(qū)別和聯(lián)系與符號(hào)“”與與“”的區(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是一個(gè)公式。是一個(gè)公式。 AB當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)AB是永真公式是永真公式 。第31頁(yè)/共80頁(yè) A AB B是偏序關(guān)系是偏序關(guān)系 即即 自反性自反性：AA。 反對(duì)稱反對(duì)稱：若：若AB，BA，則，則AB。 傳遞性傳遞性：若：若AB，BC，則，則 AC。

35、反對(duì)稱性的證明：反對(duì)稱性的證明： 設(shè)設(shè)AB且且BA， 由定義由定義7-11 AB1且且BA1于是于是AB(AB) (BA) E14 1 1 1因此因此 AB第32頁(yè)/共80頁(yè)傳遞性的證明：傳遞性的證明： 設(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頁(yè)/共80頁(yè) 四、基本的蘊(yùn)含式四、基本的蘊(yùn)含式 編號(hào)蘊(yùn)蘊(yùn) 含含 式式I1PQPI2PQQI3P PQI4QPQI5P PQI6QPQI7 (PQ)PI8 (PQ) Q 設(shè)設(shè)P P、Q Q、R R是命題變?cè)?，下表中列出了是命題變?cè)?，下表中列出?616個(gè)最基本的蘊(yùn)含式。個(gè)最基本的蘊(yùn)含式。第34頁(yè)/共80頁(yè)編號(hào)蘊(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頁(yè)/共80頁(yè)五、蘊(yùn)含式的判別五、蘊(yùn)含式的判別 判定判定“A B”是否成立的問(wèn)題可轉(zhuǎn)化為判定是否成立的問(wè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頁(yè)/共80頁(yè) 公式公式F對(duì)任意的一組真值指派

38、取值均為對(duì)任意的一組真值指派取值均為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頁(yè)/共80頁(yè) 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頁(yè)/共80頁(yè) 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頁(yè)/共80頁(yè) 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至少一個(gè)為假。至少一個(gè)為假。 由此可知由此可知 PQ與與R

41、S中至少一個(gè)為假中至少一個(gè)為假, 因此因此(PQ) (RS)為假為假.故上述蘊(yùn)含式成立。故上述蘊(yùn)含式成立。第40頁(yè)/共80頁(yè)練習(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頁(yè)/共80頁(yè)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頁(yè)/共80頁(yè)9.49.4范式范式一、 析取范式和合取范式析取范式和合取范式 定義定義9-129-12 一個(gè)命題公式若它具有一個(gè)命題公式若它具有P P1 1* *PP2 2* *PPn n* *的的形式（形式（n1n1），其中），其中P Pi i* *是命題變?cè)敲}

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

44、頁(yè)/共80頁(yè) 定理定理9-49-4 （1）一質(zhì)合取式為永假式的充分必要條件是，它同時(shí)包含某個(gè)命題變?cè)毁|(zhì)合取式為永假式的充分必要條件是，它同時(shí)包含某個(gè)命題變?cè)狿及其否定及其否定P。 （2）一質(zhì)析取式為永真式的充分必要條件是，它同時(shí)包含某個(gè)命題變?cè)毁|(zhì)析取式為永真式的充分必要條件是，它同時(shí)包含某個(gè)命題變?cè)狿及其否定及其否定P。 證明證明（2）必要性必要性：假設(shè)：假設(shè)A= P1*P2*Pn*為一質(zhì)析取式，且為一質(zhì)析取式，且A為一永真式。為一永真式。 (反證法反證法) 假設(shè)假設(shè)A式中不同時(shí)包含任一命題變?cè)捌浞穸ㄊ街胁煌瑫r(shí)包含任一命題變?cè)捌浞穸ǎ?則在則在A中，當(dāng)中，當(dāng)Pi*為為Pi時(shí)指派時(shí)指派P

45、i取取0，當(dāng)，當(dāng)Pi*為為Pi時(shí)，指派時(shí)，指派Pi取取1。(i =1,2,n).這樣的一組真值指派使這樣的一組真值指派使A的真值取的真值取0，這與，這與A為永真式矛盾。為永真式矛盾。 例如例如A=P1P2P3.則則(P1,P2,P3)=(0,1,0)的指派，使的指派，使A的真值為的真值為0. 充分性充分性：設(shè)：設(shè)A含命題變?cè)}變?cè)狿i和和Pi，而，而PiPi是永真式，是永真式， 由結(jié)合律和零一律，由結(jié)合律和零一律，A的真值必為的真值必為1，故，故A也是永真式。也是永真式。 第44頁(yè)/共80頁(yè)定義定義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頁(yè)/共80頁(yè)二、求公式的析取范式和合取范式二、求公式的析取范式和合取范式任何一個(gè)命題公式都可以變換為與它等值的析任何一個(gè)命題公式都可以變換為與它等值的析取范式或合取范式。取范式或合取范式。按下列步驟進(jìn)行：按下列步驟進(jìn)行：（1 1）利用）利用E E1111，E E1212和和E E1414消去公式中的運(yùn)算符消去公式中的運(yùn)算符“”和和“”； (2) (2) 利用德利用德摩根定律將否定符號(hào)摩根定律將否定符號(hào)“ ”向內(nèi)向內(nèi)深入，使之只作用于命題變?cè)?；深入，使之只作用于命題變?cè)?（3 3）利用雙重否定律）利用雙重否定律E E6 6將將 ( ( P)P)置換成

48、置換成P P； （4 4）利用分配律、結(jié)合律將公式歸約為合取范）利用分配律、結(jié)合律將公式歸約為合取范式或析取范式。式或析取范式。第46頁(yè)/共80頁(yè) 例例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頁(yè)/共80頁(yè)例例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頁(yè)/共80頁(yè) 定理定理9-59-5（1）公式）公式A為永真式的

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

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

52、/共80頁(yè) 例例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頁(yè)/共80頁(yè)例例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頁(yè)/共80頁(yè)四、主析取范式和主合取范式四、主析取范式和主合取范式 定義定義9-169-16 設(shè)有命題變?cè)O(shè)有命題變?cè)狿 P1 1，P P2 2，,P,Pn n

54、，形如形如 的的命題公式稱為是由命題變?cè)}公式稱為是由命題變?cè)狿 P 1 1，P P2 2，P Pn n所產(chǎn)生的所產(chǎn)生的最小項(xiàng)。而形如最小項(xiàng)。而形如 的命題公式稱為是由命題變?cè)拿}公式稱為是由命題變?cè)狿 P1 1，P P2 2，P Pn n所產(chǎn)生的最大項(xiàng)所產(chǎn)生的最大項(xiàng) 。其中。其中P Pi i* *為為P Pi i或?yàn)榛驗(yàn)?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)生的最小項(xiàng)。生的最小項(xiàng)。 P P1 1 P P2 2PP3 3是由是由

55、P P1 1，P P2 2，P P3 3產(chǎn)生的一個(gè)最大項(xiàng)。產(chǎn)生的一個(gè)最大項(xiàng)。 *1iniP*1iniP第52頁(yè)/共80頁(yè) 定義定義9-179-17由不同最小項(xiàng)所組成的析取式，由不同最小項(xiàng)所組成的析取式，稱為稱為主析取范式主析取范式。 定義定義9-189-18由不同最大項(xiàng)所組成的合取式，由不同最大項(xiàng)所組成的合取式，稱為稱為主合取范式主合取范式。例如例如( ( 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) )是一個(gè)主析取范式。是一個(gè)主析取范式。 (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) )是一個(gè)主合取范式。是一個(gè)主合取范式。第53頁(yè)/共80頁(yè) 例例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、式的主析取范式和主合取范式對(duì)任一給定的公式除了用求范式時(shí)的四個(gè)步驟外，還要利用同一律、等冪律、互否律、分配律等進(jìn)一步將質(zhì)合取式（質(zhì)析取式）變換為最小項(xiàng)（最大項(xiàng)）的形式。對(duì)任一給定的公式除了用求范式時(shí)的四個(gè)步驟外，還要利用同一律、等冪律、互否律、分配律等進(jìn)一步將質(zhì)合取式（質(zhì)析取式）變換為最小項(xiàng)（最大項(xiàng)）的形式。第54頁(yè)/共80頁(yè) F2(PQ) (PQ) ( P Q) (PQ) E11 ( P PQ) (Q PQ) E3 0 0 E 1, E 5 0 定理定理9-6 每一個(gè)不為永假的命題公式每一個(gè)不為永假的命題公式F F（P P1 1, P, P2 2, , , P, Pn n）必與一個(gè)由）必與一

58、個(gè)由P P1 1，P P2 2，P Pn n所產(chǎn)生的主析所產(chǎn)生的主析取范式等值。取范式等值。 永真公式永真公式的主析取范式包含所有的主析取范式包含所有2 2n n個(gè)最小項(xiàng)。個(gè)最小項(xiàng)。 永假公式永假公式的主析取范式是一個(gè)空公式。用的主析取范式是一個(gè)空公式。用0 0表表示。示。第55頁(yè)/共80頁(yè)例例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頁(yè)/共80頁(yè) 解解 F2 P(P( QP) E11 ( PP)( P QP) E3 11 E5,E1 1 定理定理9-7 每一個(gè)不為永真的公式每一個(gè)不為永真的公式 F(PF(P1 1, P, P2 2, , , P, Pn n）必與一個(gè)由必與一個(gè)由P P1 1, P, P2 2, , , P, Pn

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