離散數(shù)學(xué)第1.5陳瑜

1、陳瑜,Email：chenyu.inbox@gmail.com2024年3月18日星期一,離散　　數(shù)學(xué),計(jì)算機(jī)學(xué)院,2024/3/18,計(jì)算機(jī)學(xué)院,2/90,主要內(nèi)容:,析取范式、合取范式、主析?。ㄖ骱先。┓妒?、極小項(xiàng)、極大項(xiàng)等的定義求主析取范式和主合取范式的方法 1）真值表法 2）等價(jià)變換法實(shí)例分析,2024/3/18,計(jì)算機(jī)學(xué)院,3/90,1.5 命題公式的范式表示：,一個(gè)命題公式可有無窮多個(gè)和它等價(jià)的命

2、題公式，用真值表或等價(jià)變換證明它們是否等價(jià)，往往比較困難，甚至連計(jì)算機(jī)也不能解決。 要解決判定問題，可用范式(公式的標(biāo)準(zhǔn)型)。范式——全名叫規(guī)范型式normal form,又叫標(biāo)準(zhǔn)型式,正規(guī)型式。把公式進(jìn)行標(biāo)準(zhǔn)化，正規(guī)化，就叫對(duì)公式求范式。,2024/3/18,計(jì)算機(jī)學(xué)院,4/90,1.5 命題公式的范式表示：,一個(gè)命題公式可有無窮多個(gè)和它等價(jià)的命題公式，用真值表或等價(jià)變換證明它們是否等價(jià)，往往比較困難，甚至連計(jì)算機(jī)也不能解決。

3、 要解決判定問題，可用范式(公式的標(biāo)準(zhǔn)型)。范式——全名叫規(guī)范型式normal form,又叫標(biāo)準(zhǔn)型式,正規(guī)型式。把公式進(jìn)行標(biāo)準(zhǔn)化，正規(guī)化，就叫對(duì)公式求范式。,2024/3/18,計(jì)算機(jī)學(xué)院,5/90,,定義1.16： 原子公式及其否定稱為句節(jié)（分別稱為正句節(jié)或負(fù)句節(jié)）。有限個(gè)句節(jié)組成的析取式稱為子句；有限個(gè)句節(jié)組成的合取式稱為短語(yǔ)。有限個(gè)短語(yǔ)組成的析取式稱為析取范式；有限個(gè)子句組成的合取式稱為合取范式。,2024

4、/3/18,計(jì)算機(jī)學(xué)院,6/90,例5.1,1）Ｐ、～Ｐ是句節(jié)、子句、短語(yǔ)、析取范式、合取范式。 2） Ｐ∨Ｑ∨～Ｒ是子句、析取范式； 3） ～Ｐ∧Ｑ∧Ｒ是短語(yǔ)、合取范式； 4）（Ｐ∧Ｑ）∨（～Ｐ∧Ｑ）是析取范式。 5）（Ｐ∨Ｑ）∧（～Ｐ∨Ｑ）是合取范式。,句子Ｐ∨（Ｑ∨～Ｒ）、 ～（Ｑ∨Ｒ）既不是析取范式也不 是合取范式。但轉(zhuǎn)換后： Ｐ∨（Ｑ∨～Ｒ）=Ｐ∨Ｑ∨～Ｒ ～（Ｑ∨Ｒ）=～Ｑ∧～Ｒ 上述兩式的

5、右端即是析取范式和合取范式。,2024/3/18,計(jì)算機(jī)學(xué)院,7/90,例5.1,1） Ｐ、～Ｐ是句節(jié)、子句、短語(yǔ)、析取范式、合取范式。 2） Ｐ∨Ｑ∨～Ｒ是子句、析取范式； 3） ～Ｐ∧Ｑ∧Ｒ是短語(yǔ) 、合取范式； 4）（Ｐ∧Ｑ）∨（～Ｐ∧Ｑ）是析取范式。 5）（Ｐ∨Ｑ）∧（～Ｐ∨Ｑ）是合取范式。,句子Ｐ∨（Ｑ∨～Ｒ）、 ～（Ｑ∨Ｒ）既不是析取范式也不 是合取范式。但轉(zhuǎn)換后： Ｐ∨（Ｑ∨～Ｒ）=Ｐ∨Ｑ∨～Ｒ

6、 ～（Ｑ∨Ｒ）=～Ｑ∧～Ｒ 上述兩式的右端即是析取范式和合取范式。,2024/3/18,計(jì)算機(jī)學(xué)院,8/90,例5.1,1） Ｐ、～Ｐ是句節(jié)、子句、短語(yǔ)、析取范式、合取范式。 2） Ｐ∨Ｑ∨～Ｒ是子句、析取范式； 3） ～Ｐ∧Ｑ∧Ｒ是短語(yǔ)、合取范式； 4）（Ｐ∧Ｑ）∨（～Ｐ∧Ｑ）是析取范式。 5）（Ｐ∨Ｑ）∧（～Ｐ∨Ｑ）是合取范式。,句子Ｐ∨（Ｑ∨～Ｒ）、 ～（Ｑ∨Ｒ）既不是析取范式也不 是合取范式。但轉(zhuǎn)換后：

7、 Ｐ∨（Ｑ∨～Ｒ）=Ｐ∨Ｑ∨～Ｒ ～（Ｑ∨Ｒ）=～Ｑ∧～Ｒ 上述兩式的右端即是析取范式和合取范式。,2024/3/18,計(jì)算機(jī)學(xué)院,9/90,例5.1,1） Ｐ、～Ｐ是句節(jié)、子句、短語(yǔ)、析取范式、合取范式。 2） Ｐ∨Ｑ∨～Ｒ是子句、析取范式； 3） ～Ｐ∧Ｑ∧Ｒ是短語(yǔ)、合取范式； 4）（Ｐ∧Ｑ）∨（～Ｐ∧Ｑ）是析取范式。 5）（Ｐ∨Ｑ）∧（～Ｐ∨Ｑ）是合取范式。,句子Ｐ∨（Ｑ∨～Ｒ）、 ～（Ｑ∨Ｒ）既不是析取范

8、式也不 是合取范式。但轉(zhuǎn)換后： Ｐ∨（Ｑ∨～Ｒ）=Ｐ∨Ｑ∨～Ｒ ～（Ｑ∨Ｒ）=～Ｑ∧～Ｒ 上述兩式的右端即是析取范式和合取范式。,2024/3/18,計(jì)算機(jī)學(xué)院,10/90,例5.1,1） Ｐ、～Ｐ是句節(jié)、子句、短語(yǔ)、析取范式、合取范式。 2） Ｐ∨Ｑ∨～Ｒ是子句、析取范式； 3） ～Ｐ∧Ｑ∧Ｒ是短語(yǔ)、合取范式； 4）（Ｐ∧Ｑ）∨（～Ｐ∧Ｑ）是析取范式。 5）（Ｐ∨Ｑ）∧（～Ｐ∨Ｑ）是合取范式。,句子Ｐ

9、∨（Ｑ∨～Ｒ）、 ～（Ｑ∨Ｒ）既不是析取范式也不 是合取范式。但轉(zhuǎn)換后： Ｐ∨（Ｑ∨～Ｒ）=Ｐ∨Ｑ∨～Ｒ ～（Ｑ∨Ｒ）=～Ｑ∧～Ｒ 上述兩式的右端即是析取范式和合取范式。,2024/3/18,計(jì)算機(jī)學(xué)院,11/90,例5.1,1） Ｐ、～Ｐ是句節(jié)、子句、短語(yǔ)、析取范式、合取范式。 2） Ｐ∨Ｑ∨～Ｒ是子句、析取范式； 3） ～Ｐ∧Ｑ∧Ｒ是短語(yǔ)、合取范式； 4）（Ｐ∧Ｑ）∨（～Ｐ∧Ｑ）是析

10、取范式。 5）（Ｐ∨Ｑ）∧（～Ｐ∨Ｑ）是合取范式。,句子Ｐ∨（Ｑ∨～Ｒ）、 ～（Ｑ∨Ｒ）既不是析取范式也不是合取范式。但轉(zhuǎn)換后： Ｐ∨（Ｑ∨～Ｒ）=Ｐ∨Ｑ∨～Ｒ ～（Ｑ∨Ｒ）=～Ｑ∧～Ｒ 上述兩式的右端即是析取范式和合取范式。,2024/3/18,計(jì)算機(jī)學(xué)院,12/90,例5.1,1） Ｐ、～Ｐ是句節(jié)、子句、短語(yǔ)、析取范式、合取范式。 2） Ｐ∨Ｑ∨～Ｒ是子句、析取范式； 3） ～Ｐ∧Ｑ∧Ｒ是短語(yǔ)、

11、合取范式； 4）（Ｐ∧Ｑ）∨（～Ｐ∧Ｑ）是析取范式。 5）（Ｐ∨Ｑ）∧（～Ｐ∨Ｑ）是合取范式。,句子Ｐ∨（Ｑ∨～Ｒ）、 ～（Ｑ∨Ｒ）既不是析取范式也不 是合取范式。但轉(zhuǎn)換后： Ｐ∨（Ｑ∨～Ｒ）=Ｐ∨Ｑ∨～Ｒ ～（Ｑ∨Ｒ）=～Ｑ∧～Ｒ 上述兩式的右端即是析取范式和合取范式。,2024/3/18,計(jì)算機(jī)學(xué)院,13/90,結(jié)論：,從上述定義和例子可以得出如下關(guān)系：,單個(gè)的句節(jié)是一個(gè)子句、短語(yǔ)、析取范式

12、、合取范式。單個(gè)的子句是析取范式。單個(gè)的短語(yǔ)是合取范式。析取范式、合取范式僅含聯(lián)結(jié)詞～ 、∧、∨，且～僅出現(xiàn)在命題變?cè)啊?2024/3/18,計(jì)算機(jī)學(xué)院,14/90,結(jié)論：,從上述定義和例子可以得出如下關(guān)系：,單個(gè)的句節(jié)是一個(gè)子句、短語(yǔ)、析取范式、合取范式。單個(gè)的子句是析取范式。單個(gè)的短語(yǔ)是合取范式。析取范式、合取范式僅含聯(lián)結(jié)詞～ 、∧、∨，且～僅出現(xiàn)在命題變?cè)啊?2024/3/18,計(jì)算機(jī)學(xué)院,15/90,結(jié)論

13、：,從上述定義和例子可以得出如下關(guān)系：,單個(gè)的句節(jié)是一個(gè)子句、短語(yǔ)、析取范式、合取范式。單個(gè)的子句是析取范式、單個(gè)的短語(yǔ)是合取范式。析取范式、合取范式僅含聯(lián)結(jié)詞～ 、∧、∨，且～僅出現(xiàn)在命題變?cè)啊?2024/3/18,計(jì)算機(jī)學(xué)院,16/90,結(jié)論：,從上述定義和例子可以得出如下關(guān)系：,單個(gè)的句節(jié)是一個(gè)子句、短語(yǔ)、析取范式、合取范式。單個(gè)的子句是合取范式、單個(gè)的短語(yǔ)是析取范式。析取范式、合取范式僅含聯(lián)結(jié)詞～ 、∧、

14、∨，且～僅出現(xiàn)在命題變?cè)啊?2024/3/18,計(jì)算機(jī)學(xué)院,17/90,定理1.6 （范式存在定理）任何命題公式都存在與之等價(jià)的合取范式與析取范式。證明： （略p14),2024/3/18,計(jì)算機(jī)學(xué)院,18/90,求一個(gè)命題公式的與之等價(jià)的析取范式和合取范式，其步驟如下：,（1）利用等價(jià)公式中的等價(jià)式和蘊(yùn)涵式將公式中的→、?等用聯(lián)結(jié)詞～ 、∧、∨來取代；（2）利用德?摩根定律將否定號(hào)┐移到各個(gè)命題變?cè)那岸?；?）利用結(jié)合律、

15、分配律、吸收律、冪等律、交換律等將公式化成其等價(jià)的析取范式和合取范式。,2024/3/18,計(jì)算機(jī)學(xué)院,19/90,求一個(gè)命題公式的與之等價(jià)的析取范式和合取范式，其步驟如下：,（1）利用等價(jià)公式中的等價(jià)式和蘊(yùn)涵式將公式中的→、?等用聯(lián)結(jié)詞～ 、∧、∨來取代；（2）利用德?摩根定律將否定號(hào)～移到各個(gè)命題變?cè)那岸?；?）利用結(jié)合律、分配律、吸收律、冪等律、交換律等將公式化成其等價(jià)的析取范式和合取范式。,2024/3/18,計(jì)算機(jī)學(xué)院,

16、20/90,求一個(gè)命題公式的與之等價(jià)的析取范式和合取范式，其步驟如下：,（1）利用等價(jià)公式中的等價(jià)式和蘊(yùn)涵式將公式中的→、?等用聯(lián)結(jié)詞～ 、∧、∨來取代；（2）利用德?摩根定律將否定號(hào)～移到各個(gè)命題變?cè)那岸?；?）利用結(jié)合律、分配律、吸收律、冪等律、交換律等將公式化成其等價(jià)的析取范式和合取范式。,2024/3/18,計(jì)算機(jī)學(xué)院,21/90,范式的求?。ɑ瘹w）過程：,（1）消除式中聯(lián)結(jié)詞→, ? P→Q ? ～P∨Q

17、 E2 P ? Q ? （P→Q）∧（Q→P） E1（2）利用德?摩根定律將聯(lián)結(jié)詞～直接移到各命題變?cè)安⒑?jiǎn)化 E19 : ～～ P ? P E23: ～（P∨Q） ? ～ P∧～Q E24: ～（P∧Q） ? ～P∨～Q,2024/3/18,計(jì)算機(jī)學(xué)院,22/90,范式的求取（化歸）過程：,（1）消除式中聯(lián)結(jié)詞→, ? P→Q

18、? ～P∨Q E2 P ? Q ? （P→Q）∧（Q→P） E1（2）利用德?摩根定律將聯(lián)結(jié)詞～直接移到各命題變?cè)安⒑?jiǎn)化 E19 : ～～ P ? P E23: ～（P∨Q） ? ～ P∧～Q E24: ～（P∧Q） ? ～P∨～Q,2024/3/18,計(jì)算機(jī)學(xué)院,23/90,,(3）利用分配律、結(jié)合律、交換律等，將公式化成合?。ㄎ鋈。┓妒?。

19、例4.2求（P∧（Q→R））→S的合取范式解：（P∧（Q→R））→S? （P∧（～Q∨R））→S? ～（P∧（～Q∨R））∨S? ～P∨～（～ Q∨R）∨S?（～P∨S）∨（Q∧～R）? （ ～P∨Q∨S）∧（ ～P∨S∨～R）,2024/3/18,計(jì)算機(jī)學(xué)院,24/90,,(3）利用分配律、結(jié)合律、交換律等，將公式化成合?。ㄎ鋈。┓妒?。例5.2求（P∧（Q→R））→S的合取范式解：（P∧（Q→R））→S? （P∧

20、（～Q∨R））→S? ～（P∧（～Q∨R））∨S? ～P∨～（～ Q∨R）∨S?（～P∨S）∨（Q∧～R）? （ ～P∨Q∨S）∧（ ～P∨S∨～R）,2024/3/18,計(jì)算機(jī)學(xué)院,25/90,,(3）利用分配律、結(jié)合律、交換律等，將公式化成合?。ㄎ鋈。┓妒?。例5.2求（P∧（Q→R））→S的合取范式解：（P∧（Q→R））→S? （P∧（～Q∨R））→S? ～（P∧（～Q∨R））∨S? ～P∨～（～ Q∨R）∨S

21、?（～P∨S）∨（Q∧～R）? （ ～P∨Q∨S）∧（ ～P∨S∨～R）,2024/3/18,計(jì)算機(jī)學(xué)院,26/90,,(3）利用分配律、結(jié)合律、交換律等，將公式化成合取（析?。┓妒?。例5.2求（P∧（Q→R））→S的合取范式解：（P∧（Q→R））→S? （P∧（～Q∨R））→S? ～（P∧（～Q∨R））∨S? ～P∨～（～ Q∨R）∨S?（～P∨S）∨（Q∧～R）? （ ～P∨Q∨S）∧（ ～P∨S∨～R）,2024

22、/3/18,計(jì)算機(jī)學(xué)院,27/90,,(3）利用分配律、結(jié)合律、交換律等，將公式化成合取（析?。┓妒健＠?.2求（P∧（Q→R））→S的合取范式解：（P∧（Q→R））→S? （P∧（～Q∨R））→S? ～（P∧（～Q∨R））∨S? ～P∨～（～ Q∨R）∨S?（～P∨S）∨（Q∧～R）? （ ～P∨Q∨S）∧（ ～P∨S∨～R）,2024/3/18,計(jì)算機(jī)學(xué)院,28/90,,(3）利用分配律、結(jié)合律、交換律等，將公式化成

23、合?。ㄎ鋈。┓妒健＠?.2求（P∧（Q→R））→S的合取范式解：（P∧（Q→R））→S? （P∧（～Q∨R））→S? ～（P∧（～Q∨R））∨S? ～P∨～（～ Q∨R）∨S?（～P∨S）∨（Q∧～R）? （ ～P∨Q∨S）∧（ ～P∨S∨～R）,2024/3/18,計(jì)算機(jī)學(xué)院,29/90,,(3）利用分配律、結(jié)合律、交換律等，將公式化成合?。ㄎ鋈。┓妒健＠?.2求（P∧（Q→R））→S的合取范式解：（P∧（Q→R

24、））→S? （P∧（～Q∨R））→S? ～（P∧（～Q∨R））∨S? ～P∨～（～ Q∨R）∨S?（～P∨S）∨（Q∧～R） （思考？）? （ ～P∨Q∨S）∧（ ～P∨S∨～R）,2024/3/18,計(jì)算機(jī)學(xué)院,30/90,,(3）利用分配律、結(jié)合律、交換律等，將公式化成合?。ㄎ鋈。┓妒?。例5.2求（P∧（Q→R））→S的合取范式解：（P∧（Q→R））→S? （P∧（～Q∨R））→S? ～（P∧（～Q∨R））∨

25、S? ～P∨～（～ Q∨R）∨S?（～P∨S）∨（Q∧～R）?（～P∨Q∨S）∧（～P∨S∨～R）（思考？）,2024/3/18,計(jì)算機(jī)學(xué)院,31/90,,一個(gè)公式的范式不是唯一的。如： P∨（Q∧R） ?（P∨Q）∧（P∨R） ?（P∨Q）∧P∨（P∨Q）∧R ?（P∧P）∨（P∧Q)∨(P ∧ R）∨（Q∧R） 由于范式不唯一，∴直接用范式判斷命題間等價(jià)還不方便。∴需要求公式的主范式

26、。,2024/3/18,計(jì)算機(jī)學(xué)院,32/90,,一個(gè)公式的范式不是唯一的。如： P∨（Q∧R） ?（P∨Q）∧（P∨R） ?（P∨Q）∧P∨（P∨Q）∧R ?（P∧P）∨（P∧Q)∨(P ∧ R）∨（Q∧R） 由于范式不唯一，∴直接用范式判斷命題間等價(jià)還不方便?！嘈枰蠊降闹鞣妒?。,2024/3/18,計(jì)算機(jī)學(xué)院,33/90,,一個(gè)公式的范式不是唯一的。如： P∨（Q∧R）

27、 ?（P∨Q）∧（P∨R） ?（P∨Q）∧P∨（P∨Q）∧R ?（P∧P）∨（P∧Q)∨(P ∧ R）∨（Q∧R） 由于范式不唯一，∴直接用范式判斷命題間等價(jià)還不方便?！嘈枰蠊降闹鞣妒?。,2024/3/18,計(jì)算機(jī)學(xué)院,34/90,,定義1.17(1) 在n個(gè)變?cè)幕痉e（短語(yǔ)）中，若每一個(gè)變?cè)c其否定并不同時(shí)存在，且二者之一必出現(xiàn)且僅出現(xiàn)一次，則稱這種基本積為極小項(xiàng)。由有限個(gè)極小項(xiàng)組成的析取式稱為

28、主析取范式。以下是由兩個(gè)原子構(gòu)成的極小項(xiàng)的真值表,2024/3/18,計(jì)算機(jī)學(xué)院,35/90,,定義1.17(1) 在n個(gè)變?cè)幕痉e（短語(yǔ)）中，若每一個(gè)變?cè)c其否定并不同時(shí)存在，且二者之一必出現(xiàn)且僅出現(xiàn)一次，則稱這種基本積為極小項(xiàng)。由有限個(gè)極小項(xiàng)組成的析取式稱為主析取范式。以下是由兩個(gè)原子構(gòu)成的極小項(xiàng)的真值表,2024/3/18,計(jì)算機(jī)學(xué)院,36/90,,定義1.17(1) 在n個(gè)變?cè)幕痉e（短語(yǔ)）中，若每一個(gè)變?cè)c其否定

29、并不同時(shí)存在，且二者之一必出現(xiàn)且僅出現(xiàn)一次，則稱這種基本積為極小項(xiàng)。由有限個(gè)極小項(xiàng)組成的析取式稱為主析取范式。以下是由兩個(gè)原子構(gòu)成的極小項(xiàng)的真值表：,2024/3/18,計(jì)算機(jī)學(xué)院,37/90,,由真值表可知：①任何兩個(gè)命題公式（極小項(xiàng)）都不是相互等價(jià)的，并且只有一組真值指派，使得該公式的值為T。②2個(gè)命題變?cè)?² = 4種不同的組合（極小項(xiàng)） 對(duì)于n個(gè)命題變?cè)?，共?n個(gè)不同的極小項(xiàng)，記為,2024/3/18,

30、計(jì)算機(jī)學(xué)院,38/90,,由真值表可知：①任何兩個(gè)命題公式（極小項(xiàng)）都不是相互等價(jià)的，并且只有一組真值指派，使得該公式的值為T。②2個(gè)命題變?cè)?² = 4種不同的組合（極小項(xiàng)） 對(duì)于n個(gè)命題變?cè)?，共?n個(gè)不同的極小項(xiàng)，記為,注：將真值表中成真賦值所對(duì)應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)i，就將所對(duì)應(yīng)的極小項(xiàng)記為mi,2024/3/18,計(jì)算機(jī)學(xué)院,39/90,主（特異、正則）合取范式：,定義1.17(2) 在n個(gè)變?cè)?/p>

31、基本和（子句）中，若每一個(gè)變?cè)c其否定并不同時(shí)存在，且二者之一必出現(xiàn)且僅出現(xiàn)一次，則這種基本和稱為極大項(xiàng)。 由有限個(gè)極大項(xiàng)組成的合取式稱為 主合取范式。 以下是由兩個(gè)原子構(gòu)成的極大項(xiàng)的真值表,2024/3/18,計(jì)算機(jī)學(xué)院,40/90,主（特異、正則）合取范式：,定義1.17(2) 在n個(gè)變?cè)幕竞停ㄗ泳洌┲?，若每一個(gè)變?cè)c其否定并不同時(shí)存在，且二者之一必出現(xiàn)且僅出現(xiàn)一次，則這種基本和稱為極大項(xiàng)。 由有限個(gè)極大項(xiàng)組成

32、的合取式稱為主合取范式。 以下是由兩個(gè)原子構(gòu)成的極大項(xiàng)的真值表,2024/3/18,計(jì)算機(jī)學(xué)院,41/90,主（特異、正則）合取范式：,定義1.17(2) 在n個(gè)變?cè)幕竞停ㄗ泳洌┲?，若每一個(gè)變?cè)c其否定并不同時(shí)存在，且二者之一必出現(xiàn)且僅出現(xiàn)一次，則這種基本和稱為極大項(xiàng)。 由有限個(gè)極大項(xiàng)組成的合取式稱為主合取范式。 以下是由兩個(gè)原子構(gòu)成的極大項(xiàng)的真值表：,2024/3/18,計(jì)算機(jī)學(xué)院,42/90,由真值表可知：

33、 ①任何兩個(gè)極大項(xiàng)都不是相互等價(jià)的且只有一組真值指派使其值為F。 ②2個(gè)命題變?cè)?² = 4種不同的組合（極大項(xiàng)）對(duì)于n個(gè)命題變?cè)?，共?n個(gè)不同的極大項(xiàng)，記為 。,2024/3/18,計(jì)算機(jī)學(xué)院,43/90,由真值表可知： ①任何兩個(gè)極大項(xiàng)都不是相互等價(jià)的且只有一組真值指派使其值為F。 ②2個(gè)命題變?cè)?² = 4種不同的組合（極大項(xiàng)）對(duì)于n個(gè)命題變?cè)?，共?n個(gè)不同

34、的極大項(xiàng)，記為： 。,注：將真值表中成假賦值所對(duì)應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)i，就將所對(duì)應(yīng)的極大項(xiàng)記為Mi,2024/3/18,計(jì)算機(jī)學(xué)院,44/90,1）沒有兩個(gè)不同的極小項(xiàng)是等價(jià)的，且每個(gè)極小項(xiàng)只有一組真值指派，使該極小項(xiàng)的真值為真；,2）沒有兩個(gè)不同的極大項(xiàng)是等價(jià)的，且每個(gè)極大項(xiàng)只有一組真值指派，使該極大項(xiàng)的真值為假；,極小項(xiàng)與極大項(xiàng)的性質(zhì)：,2024/3/18,計(jì)算機(jī)學(xué)院,45/90,1）沒有兩個(gè)

35、不同的極小項(xiàng)是等價(jià)的，且每個(gè)極小項(xiàng)只有一組真值指派，使該極小項(xiàng)的真值為真；,2）沒有兩個(gè)不同的極大項(xiàng)是等價(jià)的，且每個(gè)極大項(xiàng)只有一組真值指派，使該極大項(xiàng)的真值為假；,極小項(xiàng)與極大項(xiàng)的性質(zhì)：,2024/3/18,計(jì)算機(jī)學(xué)院,46/90,3）mi=～Mi；Mi=～mi； i=0,1,2,…,2n-1 4）Mi∨Mj=T；mi∧mj=F； i≠j； i,j∈{0,1,2,…,2n-1} 5）,極小項(xiàng)與極大項(xiàng)的性質(zhì)：,2

36、024/3/18,計(jì)算機(jī)學(xué)院,47/90,極小項(xiàng)與極大項(xiàng)的性質(zhì)：,3）mi=～Mi；Mi=～mi； i=0,1,2,…,2n-1 4）Mi∨Mj=T；mi∧mj=F； i≠j； i,j∈{0,1,2,…,2n-1} 5）,2024/3/18,計(jì)算機(jī)學(xué)院,48/90,3）mi=～Mi；Mi=～mi； i=0,1,2,…,2n-1 4）Mi∨Mj=T；mi∧mj=F； i≠j； i,j∈{0,1

37、,2,…,2n-1} 5）,極小項(xiàng)與極大項(xiàng)的性質(zhì)：,2024/3/18,計(jì)算機(jī)學(xué)院,49/90,極小項(xiàng)與極大項(xiàng)的性質(zhì)：,3）mi=～Mi；Mi=～mi； i=0,1,2,…,2n-1 4）Mi∨Mj=T；mi∧mj=F； i≠j； i,j∈{0,1,2,…,2n-1} 5）,2024/3/18,計(jì)算機(jī)學(xué)院,50/90,3）mi=～Mi；Mi=～mi； i=0,1,2,…,2n-1 4）Mi∨Mj

38、=T；mi∧mj=F； i≠j； i,j∈{0,1,2,…,2n-1} 5）,極小項(xiàng)與極大項(xiàng)的性質(zhì)：,2024/3/18,計(jì)算機(jī)學(xué)院,51/90,3）mi=～Mi；Mi=～mi； i=0,1,2,…,2n-1 4）Mi∨Mj=T；mi∧mj=F； i≠j； i,j∈{0,1,2,…,2n-1} 5）,極小項(xiàng)與極大項(xiàng)的性質(zhì)：,2024/3/18,計(jì)算機(jī)學(xué)院,52/90,極小項(xiàng)與極大項(xiàng)的性質(zhì)：,*6

39、）極大項(xiàng)取值0“當(dāng)且僅當(dāng)”：如果極大項(xiàng)中出現(xiàn)的是原子本身，則原子賦值為0；如果出現(xiàn)的是原子的否定，則原子賦值為1。 7）極小項(xiàng)取值1 “當(dāng)且僅當(dāng)”：如果極小項(xiàng)中出現(xiàn)的是原子本身，則原子賦值為1；如果出現(xiàn)的是原子的否定，則原子賦值為0。 8）當(dāng)一個(gè)極大項(xiàng)在一種解釋下取值0時(shí)，其余極大項(xiàng)在同一解釋下取值1。 9）當(dāng)一個(gè)極小項(xiàng)在一種解釋下取值1時(shí)，其余極小項(xiàng)在同一解釋下取值0。,2024/3/18,計(jì)算機(jī)學(xué)院,53/90,極

40、小項(xiàng)與極大項(xiàng)的性質(zhì)：,*6）極大項(xiàng)取值0“當(dāng)且僅當(dāng)”：如果極大項(xiàng)中出現(xiàn)的是原子本身，則原子賦值為0；如果出現(xiàn)的是原子的否定，則原子賦值為1。 *7）極小項(xiàng)取值1 “當(dāng)且僅當(dāng)”：如果極小項(xiàng)中出現(xiàn)的是原子本身，則原子賦值為1；如果出現(xiàn)的是原子的否定，則原子賦值為0。 8）當(dāng)一個(gè)極大項(xiàng)在一種解釋下取值0時(shí)，其余極大項(xiàng)在同一解釋下取值1。 9）當(dāng)一個(gè)極小項(xiàng)在一種解釋下取值1時(shí)，其余極小項(xiàng)在同一解釋下取值0。,2024/3/18,

41、計(jì)算機(jī)學(xué)院,54/90,極小項(xiàng)與極大項(xiàng)的性質(zhì)：,6）極大項(xiàng)取值0“當(dāng)且僅當(dāng)”：如果極大項(xiàng)中出現(xiàn)的是原子本身，則原子賦值為0；如果出現(xiàn)的是原子的否定，則原子賦值為1。 7）極小項(xiàng)取值1 “當(dāng)且僅當(dāng)”：如果極小項(xiàng)中出現(xiàn)的是原子本身，則原子賦值為1；如果出現(xiàn)的是原子的否定，則原子賦值為0。 8）當(dāng)一個(gè)極大項(xiàng)在一種解釋下取值0時(shí)，其余極大項(xiàng)在同一解釋下取值1。 9）當(dāng)一個(gè)極小項(xiàng)在一種解釋下取值1時(shí)，其余極小項(xiàng)在同一解釋下取值0

42、。,2024/3/18,計(jì)算機(jī)學(xué)院,55/90,極小項(xiàng)與極大項(xiàng)的性質(zhì)：,6）極大項(xiàng)取值0“當(dāng)且僅當(dāng)”：如果極大項(xiàng)中出現(xiàn)的是原子本身，則原子賦值為0；如果出現(xiàn)的是原子的否定，則原子賦值為1。 7）極小項(xiàng)取值1 “當(dāng)且僅當(dāng)”：如果極小項(xiàng)中出現(xiàn)的是原子本身，則原子賦值為1；如果出現(xiàn)的是原子的否定，則原子賦值為0。 8）當(dāng)一個(gè)極大項(xiàng)在一種解釋下取值0時(shí)，其余極大項(xiàng)在同一解釋下取值1。 9）當(dāng)一個(gè)極小項(xiàng)在一種解釋下取值1時(shí)，其余

43、極小項(xiàng)在同一解釋下取值0。,2024/3/18,計(jì)算機(jī)學(xué)院,56/90,,求主析（合）取范式的方法有： 1、 真值表技術(shù)法 2、 公式轉(zhuǎn)換法,2024/3/18,計(jì)算機(jī)學(xué)院,57/90,定理1.7 在命題公式的真值表中，使公式取值0時(shí)的解釋所對(duì)應(yīng)的全部極大項(xiàng)的合取式，是該公式的主合取范式。（P15，定理1.7）,利用真值表求主析（合）取范式：,例5.3設(shè) G=(P→Q)?R，求出它的主析取范式和主合取范式。,2024/3

44、/18,計(jì)算機(jī)學(xué)院,58/90,定理1.7 在命題公式的真值表中，使公式取值0時(shí)的解釋所對(duì)應(yīng)的全部極大項(xiàng)的合取式，是該公式的主合取范式。（P15，定理1.7）,利用真值表求主析（合）取范式：,極大項(xiàng)取值0 “當(dāng)且僅當(dāng)”：如果極大項(xiàng)中出現(xiàn)的是原子本身，則原子賦值為0；如果出現(xiàn)的是原子的否定，則原子賦值為1。,2024/3/18,計(jì)算機(jī)學(xué)院,59/90,利用真值表求主析（合）取范式：,例5.3-1設(shè) G=(P→Q)?R，求出它的主合取

45、范式。,2024/3/18,計(jì)算機(jī)學(xué)院,60/90,解：首先列出其真值表如下：,例5.3-1（續(xù)）：,2024/3/18,計(jì)算機(jī)學(xué)院,61/90,求公式的主合取范式,例5.3-1（續(xù)）,,極大項(xiàng),,極大項(xiàng),,極大項(xiàng),,極大項(xiàng),P∨Ｑ∨Ｒ,P∨ ～Ｑ∨Ｒ,～ P∨Ｑ∨ ～Ｒ,～ P∨ ～Ｑ∨Ｒ,2024/3/18,計(jì)算機(jī)學(xué)院,62/90,將極大項(xiàng)全部進(jìn)行合取后，可得到相應(yīng)的主合取范式： G=（Ｐ→Ｑ）?Ｒ =（P∨Ｑ∨Ｒ）∧（P∨～

46、Ｑ∨Ｒ）∧（～Ｐ ∨Ｑ∨～Ｒ）∧（～Ｐ∨～Ｑ∨Ｒ）,例5.3-1（續(xù)）,2024/3/18,計(jì)算機(jī)學(xué)院,63/90,定理1.8 在命題公式的真值表中，使公式取值1時(shí)的解釋所對(duì)應(yīng)的全部極小項(xiàng)的析取式，是該公式的主析取范式。 （P16，定理1.8）,利用真值表求主析（合）取范式：,2024/3/18,計(jì)算機(jī)學(xué)院,64/90,定理1.8 在命題公式的真值表中，使公式取值1時(shí)的解釋所對(duì)應(yīng)的全部極小項(xiàng)的析取式，是該公式的主析取范式。 （P16

47、，定理1.8）,利用真值表求主析（合）取范式：,極小項(xiàng)取值1 “當(dāng)且僅當(dāng)”：如果極小項(xiàng)中出現(xiàn)的是原子本身，則原子賦值為1；如果出現(xiàn)的是原子的否定，則原子賦值為0。,2024/3/18,計(jì)算機(jī)學(xué)院,65/90,利用真值表求主析（合）取范式：,例5.3-2設(shè) G=(P→Q)?R，求出它的主析取范式。,2024/3/18,計(jì)算機(jī)學(xué)院,66/90,解：首先列出其真值表如下：,例5.3-2（續(xù)）：,2024/3/18,計(jì)算機(jī)學(xué)院,67/90,

48、求公式的主析取范式,例5.3-2（續(xù)）：,,～ P∧ ～Ｑ∧Ｒ,極小項(xiàng),,極小項(xiàng),,極小項(xiàng),,極小項(xiàng),～ P∧Ｑ∧Ｒ,P∧ ～Ｑ∧ ～Ｒ,P∧Ｑ∧Ｒ,2024/3/18,計(jì)算機(jī)學(xué)院,68/90,將極小項(xiàng)全部進(jìn)行析取后，可得到相應(yīng)的主析取范式： G=（Ｐ→Ｑ）?Ｒ =（～P∧～Ｑ∧Ｒ）∨（～P∧Ｑ∧Ｒ）∨（Ｐ∧～Ｑ∧～Ｒ）∨（Ｐ∧Ｑ∧Ｒ）,例5.3-2（續(xù)）：,2024/3/18,計(jì)算機(jī)學(xué)院,69/90,公式轉(zhuǎn)換法：,1）利用等價(jià)公

49、式中的等價(jià)式和蘊(yùn)涵式將公式中的→、?用聯(lián)結(jié)詞～、∧、∨來取代； 2）利用德?摩根定律將否定號(hào)～移到各個(gè)命題變?cè)那岸耍?3）利用結(jié)合律、分配律、吸收律、冪等律、交換律等將公式化成其等價(jià)的析取范式和合取范式。 4）在析取范式的短語(yǔ)和合取范式的子句中，如同一命題變?cè)霈F(xiàn)多次，則將其化成只出現(xiàn)一次。 5）去掉析取范式中所有永假式的短語(yǔ)和合取范式中所有永真式的子句，即去掉短語(yǔ)中含有形如P∧～P的子公式和子句中含有形如P∨～P的子

50、公式。,2024/3/18,計(jì)算機(jī)學(xué)院,70/90,公式轉(zhuǎn)換法：,1）利用等價(jià)公式中的等價(jià)式和蘊(yùn)涵式將公式中的→、?用聯(lián)結(jié)詞～、∧、∨來取代； 2）利用德?摩根定律將否定號(hào)～移到各個(gè)命題變?cè)那岸耍?3）利用結(jié)合律、分配律、吸收律、冪等律、交換律等將公式化成其等價(jià)的析取范式和合取范式。 4）在析取范式的短語(yǔ)和合取范式的子句中，如同一命題變?cè)霈F(xiàn)多次，則將其化成只出現(xiàn)一次。 5）去掉析取范式中所有永假式的短語(yǔ)和合取范式中所

51、有永真式的子句，即去掉短語(yǔ)中含有形如P∧～P的子公式和子句中含有形如P∨～P的子公式。,2024/3/18,計(jì)算機(jī)學(xué)院,71/90,公式轉(zhuǎn)換法：,1）利用等價(jià)公式中的等價(jià)式和蘊(yùn)涵式將公式中的→、?用聯(lián)結(jié)詞～、∧、∨來取代； 2）利用德?摩根定律將否定號(hào)～移到各個(gè)命題變?cè)那岸耍?3）利用結(jié)合律、分配律、吸收律、冪等律、交換律等將公式化成其等價(jià)的析取范式和合取范式。 4）在析取范式的短語(yǔ)和合取范式的子句中，如同一命題變?cè)霈F(xiàn)多

52、次，則將其化成只出現(xiàn)一次。 5）去掉析取范式中所有永假式的短語(yǔ)和合取范式中所有永真式的子句，即去掉短語(yǔ)中含有形如P∧～P的子公式和子句中含有形如P∨～P的子公式。,2024/3/18,計(jì)算機(jī)學(xué)院,72/90,公式轉(zhuǎn)換法：,1）利用等價(jià)公式中的等價(jià)式和蘊(yùn)涵式將公式中的→、?用聯(lián)結(jié)詞～、∧、∨來取代； 2）利用德?摩根定律將否定號(hào)～移到各個(gè)命題變?cè)那岸耍?3）利用結(jié)合律、分配律、吸收律、冪等律、交換律等將公式化成其等價(jià)的析取范

53、式和合取范式。 4）在析取范式的短語(yǔ)和合取范式的子句中，如同一命題變?cè)霈F(xiàn)多次，則將其化成只出現(xiàn)一次。 5）去掉析取范式中所有永假式的短語(yǔ)和合取范式中所有永真式的子句，即去掉短語(yǔ)中含有形如P∧～P的子公式和子句中含有形如P∨～P的子公式。,2024/3/18,計(jì)算機(jī)學(xué)院,73/90,公式轉(zhuǎn)換法：,1）利用等價(jià)公式中的等價(jià)式和蘊(yùn)涵式將公式中的→、?用聯(lián)結(jié)詞～、∧、∨來取代； 2）利用德?摩根定律將否定號(hào)～移到各個(gè)命題變?cè)那岸?/p>

54、； 3）利用結(jié)合律、分配律、吸收律、冪等律、交換律等將公式化成其等價(jià)的析取范式和合取范式。 4）在析取范式的短語(yǔ)和合取范式的子句中，如同一命題變?cè)霈F(xiàn)多次，則將其化成只出現(xiàn)一次。 5）去掉析取范式中所有永假式的短語(yǔ)和合取范式中所有永真式的子句，即去掉短語(yǔ)中含有形如P∧～P的子公式和子句中含有形如P∨～P的子公式。,2024/3/18,計(jì)算機(jī)學(xué)院,74/90,公式轉(zhuǎn)換法：（續(xù)）,6）若析取范式的某一個(gè)短語(yǔ)中缺少該命題公式中所規(guī)

55、定的命題變?cè)狿 ，則可用公式： （～Ｐ∨Ｐ）∧Q=Q 將命題變?cè)狿補(bǔ)進(jìn)去，并利用分配律展開，然后合并相同的短語(yǔ)，此時(shí)得到的短語(yǔ)將是標(biāo)準(zhǔn)的極小項(xiàng)； 7）若合取范式的某一個(gè)子句中缺少該命題公式中所規(guī)定的命題變?cè)狿 ，則可用公式： （～Ｐ∧Ｐ）∨Q=Q 將命題變?cè)狿補(bǔ)進(jìn)去，并利用分配律展開，然后合并相同的子句，此時(shí)得到的子句將是標(biāo)準(zhǔn)的極大項(xiàng)。 8）利用冪等律將相同的極小項(xiàng)和極大項(xiàng)合并，同時(shí)利用交

56、換律進(jìn)行順序調(diào)整，由此可轉(zhuǎn)換成標(biāo)準(zhǔn)的主析取范式和主合取范式。,2024/3/18,計(jì)算機(jī)學(xué)院,75/90,公式轉(zhuǎn)換法：（續(xù)）,6）若析取范式的某一個(gè)短語(yǔ)中缺少該命題公式中所規(guī)定的命題變?cè)狿 ，則可用公式： （～Ｐ∨Ｐ）∧Q=Q 將命題變?cè)狿補(bǔ)進(jìn)去，并利用分配律展開，然后合并相同的短語(yǔ)，此時(shí)得到的短語(yǔ)將是標(biāo)準(zhǔn)的極小項(xiàng)。 7）若合取范式的某一個(gè)子句中缺少該命題公式中所規(guī)定的命題變?cè)狿 ，則可用公式：

57、（～Ｐ∧Ｐ）∨Q=Q 將命題變?cè)狿補(bǔ)進(jìn)去，并利用分配律展開，然后合并相同的子句，此時(shí)得到的子句將是標(biāo)準(zhǔn)的極大項(xiàng)。 8）利用冪等律將相同的極小項(xiàng)和極大項(xiàng)合并，同時(shí)利用交換律進(jìn)行順序調(diào)整，由此可轉(zhuǎn)換成標(biāo)準(zhǔn)的主析取范式和主合取范式。,2024/3/18,計(jì)算機(jī)學(xué)院,76/90,公式轉(zhuǎn)換法：（續(xù)）,6）若析取范式的某一個(gè)短語(yǔ)中缺少該命題公式中所規(guī)定的命題變?cè)狿 ，則可用公式： （～Ｐ∨Ｐ）∧Q=Q 將命題變?cè)狿補(bǔ)進(jìn)去

58、，并利用分配律展開，然后合并相同的短語(yǔ)，此時(shí)得到的短語(yǔ)將是標(biāo)準(zhǔn)的極小項(xiàng)。 7）若合取范式的某一個(gè)子句中缺少該命題公式中所規(guī)定的命題變?cè)狿 ，則可用公式： （～Ｐ∧Ｐ）∨Q=Q 將命題變?cè)狿補(bǔ)進(jìn)去，并利用分配律展開，然后合并相同的子句，此時(shí)得到的子句將是標(biāo)準(zhǔn)的極大項(xiàng)。 8）利用冪等律將相同的極小項(xiàng)和極大項(xiàng)合并，同時(shí)利用交換律進(jìn)行順序調(diào)整，由此可轉(zhuǎn)換成標(biāo)準(zhǔn)的主析取范式和主合取范式。,2024/3/18,計(jì)算機(jī)學(xué)院

59、,77/90,利用公式的等價(jià)求G＝(P→Q)∧R的主析取范式和主合取范式。解：G＝(P→Q)∧R＝(～P∨Q)∧R（蘊(yùn)涵）＝(～P∨Q∨(R∧～R))∧ ((～P∧P)∨(～Q∧Q)∨R)（添加R、P、Q）＝(～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)

60、（結(jié)合律）－－－－－主合取范式,例5.4：,2024/3/18,計(jì)算機(jī)學(xué)院,78/90,利用公式的等價(jià)求G＝(P→Q)∧R的主析取范式和主合取范式。解：G＝(P→Q)∧R＝(～P∨Q)∧R（蘊(yùn)涵）＝(～P∨Q∨(R∧～R))∧ ((～P∧P)∨(～Q∧Q)∨R)（添加R、P、Q）＝(～P∨Q∨R)∧(～P∨Q∨～R)∧(～P∨～Q∨R)∧(～P∨Q∨R)∧(P∨～Q∨R)∧(P∨Q∨R) （分配律）＝(P∨Q∨R)∧

61、(P∨～Q∨R)∧(～P∨Q∨R)∧(～P∨Q∨～R)∧(～P∨～Q∨R)（結(jié)合律）－－－－－主合取范式,例5.4：,2024/3/18,計(jì)算機(jī)學(xué)院,79/90,利用公式的等價(jià)求G＝(P→Q)∧R的主析取范式和主合取范式。解：G＝(P→Q)∧R＝(～P∨Q)∧R（蘊(yùn)涵）＝(～P∨Q∨(R∧～R))∧ ((～P∧P)∨(～Q∧Q)∨R)（添加R、P、Q）＝(～P∨Q∨R)∧(～P∨Q∨～R)∧(～P∨～Q∨R)∧(～P∨

62、Q∨R)∧(P∨～Q∨R)∧(P∨Q∨R) （分配律）＝(P∨Q∨R)∧(P∨～Q∨R)∧(～P∨Q∨R)∧(～P∨Q∨～R)∧(～P∨～Q∨R)（結(jié)合律）－－－－－主合取范式,例5.4：,2024/3/18,計(jì)算機(jī)學(xué)院,80/90,利用公式的等價(jià)求G＝(P→Q)∧R的主析取范式和主合取范式。解：G＝(P→Q)∧R＝(～P∨Q)∧R（蘊(yùn)涵）＝(～P∨Q∨(R∧～R))∧ ((～P∧P)∨(～Q∧Q)∨R)（添加R、P、

63、Q）＝(～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)（結(jié)合律）－－－－－主合取范式,例5.4：,2024/3/18,計(jì)算機(jī)學(xué)院,81/90,補(bǔ)充： ((～P∧P)∨(～Q∧Q)∨R)＝((～P∧P)∨[(～Q∨R) ∧(Q∨R)] ＝[(～P

64、∧P)∨(～Q∨R)] ∧[(～P∧P)∨(Q∨R)] ＝(～P∨～Q∨R)∧(～P∨Q∨R)∧(P∨～Q∨R)∧(P∨Q∨R) （分配律）,例5.4：,2024/3/18,計(jì)算機(jī)學(xué)院,82/90,利用公式的等價(jià)求G＝(P→Q)∧R的主析取范式和主合取范式。解：G＝(P→Q)∧R＝(～P∨Q)∧R（蘊(yùn)涵）＝(～P∨Q∨(R∧～R))∧ ((～P∧P)∨(～Q∧Q)∨R)（添加R、P、Q）＝(～P∨Q∨R)∧(～P∨Q∨～

65、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)（結(jié)合律）－－－－－主合取范式,例5.4：,2024/3/18,計(jì)算機(jī)學(xué)院,83/90,G＝(P→Q)∧R＝(～P∨Q)∧R （蘊(yùn)涵）＝(～P∧R)∨(Q∧R)＝(～P∧(～Q∨Q)∧R)∨((～P∨P)∧Q∧R)＝(～P∧～Q∧R)∨(～P∧

66、Q∧R)∨(～P∧Q∧R)∨(P∧Q∧R) （分配律）＝(～P∧～Q∧R)∨(～P∧Q∧R)∨(P∧Q∧R)——主析取范式,例5.4（續(xù)）,2024/3/18,計(jì)算機(jī)學(xué)院,84/90,G＝(P→Q)∧R＝(～P∨Q)∧R （蘊(yùn)涵）＝(～P∧R)∨(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∧

67、Q∧R)∨(P∧Q∧R)——主析取范式,例5.4（續(xù)）,2024/3/18,計(jì)算機(jī)學(xué)院,85/90,G＝(P→Q)∧R＝(～P∨Q)∧R （蘊(yùn)涵）＝(～P∧R)∨(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)——主析取范式,例5.4（續(xù)）,2024/3/18,計(jì)算機(jī)學(xué)院

68、,86/90,G＝(P→Q)∧R＝(～P∨Q)∧R （蘊(yùn)涵）＝(～P∧R)∨(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)——主析取范式,例5.4（續(xù)）,2024/3/18,計(jì)算機(jī)學(xué)院,87/90,G＝(P→Q)∧R＝(～P∨Q)∧R （蘊(yùn)涵）＝(～P∧R)∨(Q∧R)