離散數(shù)學(xué)第一章第四節(jié)

1、第1-4講 范式,1.對(duì)偶式2.對(duì)偶原理3.合取范式和析取范式4.主析取范式5.主合取范式6.真值表法求主析(合)取范式7.用等價(jià)公式求主析(合)取范式8.主析、合取范式互求9.范式的應(yīng)用10. 作業(yè),,,,,1、對(duì)偶式,定義１設(shè)命題公式Ａ中僅含有聯(lián)結(jié)詞?、∨、∧，將Ａ中∨、∧、Ｔ、Ｆ分別換成∧、∨、Ｆ、Ｔ所得的命題公式A*叫Ａ的對(duì)偶式。,從基本恒等式中不難發(fā)現(xiàn)，多數(shù)公式是成對(duì)出現(xiàn)，因而互為對(duì)偶式。,例１ 求P↑Q和

2、P↓Q的對(duì)偶式解：因?yàn)镻↑Q??(P∧Q)，故P↑Q的對(duì)偶式為?(P∨Q)，即P↓Q。那麼P↑Q和P↓Q互為對(duì)偶式。,,,,,定理１ 設(shè)Ａ(P1,P2，…,Pn)與A*(P1,P2，…,Pn)是對(duì)偶式，則 (1) ?Ａ(P1,P2，…,Pn)? A* (?P1,?P2，…,?Pn) (2) Ａ(?P1,?P2，…,?Pn)? ?A*(P1,P2，…,Pn),證：由于Ａ僅含連接詞?、∧、∨,對(duì)Ａ取否定，由德．摩根律可知

3、，Ａ中的∨、∧、Ｔ、Ｆ將分別轉(zhuǎn)化為∧、∨、Ｆ、Ｔ，且每一變?cè)紝?號(hào)。所以 ?Ａ(P1, P2，…,Pn) ? A*(?P1,?P2，…,?Pn) Ａ(?P1,?P2，…,?Pn)?? A*(P1, P2，…,Pn),,,,,例１設(shè)A*（P,Q,R）是?P∧(?Q∨R)，證明 A* (?P,?Q,?R) ? ?A(P,Q,R),證：因A*（P,Q,R）? ?

4、P∧(?Q∨R)，代入可得 A*(?P,?Q,?R)?P∧(Q∨?R)。而按對(duì)偶式的定義，由A*（P,Q,R）可寫(xiě)出 Ａ(P,Q,R)??P∨(?Q∧R)故 ?Ａ(P,Q,R)??（?P∨(?Q∧R)） ?P∧?(?Q∧R) （德．摩根律） ?P∧(Q∨?R) （德．摩根律） ? A*(?P,?Q,?

5、R),,,,,2. 對(duì)偶原理,證：設(shè)Ａ(P1, P2，…, Pn)?Ｂ(P1, P2，…, Pn)，按等價(jià)定義可知Ａ(P1, P2，…, Pn)?Ｂ(P1, P2，…, Pn)是永真式。那么Ａ(?P1,?P2，…, ?Pn)?Ｂ(?P1,?P2，…, ?Pn)亦為永真式。所以 Ａ(?P1,?P2，…, ?Pn)?Ｂ(?P1,?P2，…, ?Pn)。根據(jù)定理１中(2)式： Ａ(?P1,?P2，…, ?Pn)??A

6、*(P1, P2，…, Pn)， B(?P1,?P2，…, ?Pn)? ? B* (P1, P2，…, Pn)。所以, ? A* (P1, P2，…, Pn)?? B* (P1, P2，…, Pn)。故 A*?B*。,定理2 (對(duì)偶原理)設(shè)A*、B*分別是命題公式Ａ、Ｂ的對(duì)偶式。如果Ａ?Ｂ，則A*?B*。,,,,,問(wèn)題１： 很多命題公式的外表形式雖不同，但它們是等價(jià)的。形式不同的所有等價(jià)命題公式是否可以化為唯一的

7、標(biāo)準(zhǔn)形式呢？問(wèn)題 2：如果已知一個(gè)命題公式的成真和成假賦值,能否求出該命題公式?,定義1 一個(gè)命題公式稱為合取范式，當(dāng)且僅當(dāng)它具有形式：A1∧A2∧…∧An (n≥1)，其中A1、A2、... An都是由命題變?cè)蚱浞穸?gòu)成的析取式。,3、合取范式和析取范式,例如，(P∨?Q∨R)∧(?P∨Q)∧?Q是合取范式。這里， A1是P∨?Q∨R， A2是?P∨Q， A3是?Q。,,,,,求析取范式或合取范式的步驟：⑴ 將命題公式中的

8、聯(lián)結(jié)詞全部化為?、∧、∨；⑵ 利用德．摩根律，將?直接移到各命題變?cè)?；?利用分配律、結(jié)合律將命題公式化為析取范式或合取范式。,定義2 一個(gè)命題公式稱為析取范式，當(dāng)且僅當(dāng)它具有形式：A1∨A2∨...∨An (n≥1)，其中A1、A2、... An都是由命題變?cè)蚱浞穸?gòu)成的合取式。 例如，?P∨(P∧Q)∨(P∧?Q∧R)是析取范式。,,,,,例４ 求下列命題的析取范式和合取范式：

9、 Q∧（(P∨?Q)→R）,解：求析取范式：Q∧（(P∨?Q)→R）?Q∧（?(P∨?Q)∨R） （ ①消去→）?Q∧（(?P∧Q)∨R） （② 內(nèi)移?）?（Q∧(?P∧Q)）∨(Q∧R) （③ 用∧對(duì)∨的分配律）? (?P∧Q)∨(Q∧R) （④ 析取范式）求合取范式（①,②兩個(gè)步驟相同）：Q∧（(P∨?Q)→R） ?Q∧（(?P∧Q)∨R）

10、?Q∧（(?P∨R)∧(Q∨R)）?Q∧(?P∨R)∧(Q∨R）,,任一命題公式都有一個(gè)與之等值的析取范式和合取范式。,,,,,4、主析取范式（小項(xiàng)）,定義3 在ｎ個(gè)變?cè)暮先∈街?，若每一個(gè)變?cè)c其否定不同時(shí)存在，但二者之一必須出現(xiàn)且僅出現(xiàn)一次,同時(shí)按某種順序第ｉ個(gè)命題變?cè)蚱浞穸ǔ霈F(xiàn)在左起第ｉ個(gè)位置上，則這種合取式叫小項(xiàng)。,,例如，三個(gè)命題變?cè)小ⅲ?、Ｒ可形成８?jìng)€(gè)小項(xiàng)：,,,,,4、主析取范式（小項(xiàng)的性質(zhì)）,小項(xiàng)有如下幾個(gè)性質(zhì)：

11、⑴ 每一個(gè)小項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為Ｔ，而在其余2n-1種指派下均為Ｆ。⑵ 任意兩個(gè)不同小項(xiàng)的合取式永假： ｍi∧ｍj?Ｆ (i≠j)⑶ 全體小項(xiàng)的析取式永真，記為：,,定義4 給定命題公式Ａ，如果Ａ與命題公式Ｂ等價(jià),且Ｂ僅由小項(xiàng)的析取組成，則Ｂ稱為Ａ的主析取范式。,,,,,4、主析取范式（小項(xiàng)性質(zhì)1、2舉例）,對(duì) 性質(zhì)1和 性質(zhì)2舉例如下： ｍ0 ：(?P∧?Q∧?R) 和 ｍ4

12、：(P∧?Q∧?R)：,,,,,5、主合取范式 (大項(xiàng)),定義3 在ｎ個(gè)變?cè)奈鋈∈街?，若每一個(gè)變?cè)c其否定不同時(shí)存在，但二者之一必須出現(xiàn)且僅出現(xiàn)一次,同時(shí)按某種順序第ｉ個(gè)命題變?cè)蚱浞穸ǔ霈F(xiàn)在左起第ｉ個(gè)位置上，則這種析取式叫大項(xiàng)。,,例如，三個(gè)命題變?cè)?、Ｑ、Ｒ可形成８?jìng)€(gè)大項(xiàng)：,,,,,5、主合取范式（大項(xiàng)的性質(zhì)）,大項(xiàng)有如下幾個(gè)性質(zhì)：⑴ 每一個(gè)大項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為F，而在其余2n-1種指派下均為T(mén)。⑵ 任

13、意兩個(gè)不同大項(xiàng)的析取式永真： Mi∨Mj?T (i≠j)⑶ 全體大項(xiàng)的合取式永假，記為：,定義５ 給定命題公式Ａ，如果Ａ與命題公式Ｂ等價(jià),且Ｂ僅由大項(xiàng)的合取組成，則Ｂ稱為Ａ的主合取范式。,,,,,6、真值表法求主析(合)取范式,定理３ 一個(gè)命題公式的真值表中，真值為Ｔ（Ｆ）的指派所對(duì)應(yīng)的小項(xiàng)（大項(xiàng)）的析?。ê先。┘礊榇斯降闹魑鋈》妒剑ㄖ骱先》妒剑?。,,證：設(shè)給定的命題公式為Ａ，為敘述方便，可設(shè)使A的真值為T(mén)和F的指

14、派所對(duì)應(yīng)的小項(xiàng)分別為m1， m2，...，mk和mK+1，mK+2，...，m2n-1。令Ｂ? m1∨m2∨... ∨mk，下面證明Ａ?Ｂ。 設(shè)A在某一指派下為T(mén)，該指派所對(duì)應(yīng)的小項(xiàng)mi必在Ｂ中，因?yàn)閙i為Ｔ(小項(xiàng)性質(zhì)) ，從而B(niǎo)為T(mén)。 設(shè)A在某一指派下為F，該指派所對(duì)應(yīng)的小項(xiàng)mj必不在Ｂ中，在該指派下m1， m2，...，mk 均為Ｆ，故Ｂ為Ｆ。 以上說(shuō)明，A、B在任何指派下同真同假，因此Ａ?Ｂ

15、,任一命題公式的主析（合）取范式一定存在且唯一。,,,,,6、用真值表法求主析(合)取范式（例）,例５求Q∧（(P∨?Q)→R）的主析取范式和主合取范式。,解：給定命題公式的真值表為：,所以Q∧（(P∨?Q)→R）的主析取范式為: (?P∧Q∧?R)∨(?P∧Q∧R)∨(P∧Q∧R) ? ∑2,3,7 ； 主合取范式:(P∨Q∨R)∧(P∨Q∨?R)∧(?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨?Q∨R) ? ∏0,1,4,5,

16、6,,,,,7、用等價(jià)公式求主析(合)取范式,例6 求Q∧（(P∨?Q)→R）的主析取范式。,,解：Q∧（(P∨?Q)→R）? (?P∧Q)∨(Q∧R) (先化為析取范式)? (?P∧Q∧(R∨?R))∨((P∨?P)∧Q∧R) (補(bǔ)入未出現(xiàn)的變?cè)?? (?P∧Q∧R)∨(?P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R) (展開(kāi))? (?P∧Q∧?R)∨(?P∧Q∧R)∨(P∧Q∧R) (合并相同的小項(xiàng))? m

17、2∨m3∨m7?∑2,3,7,,,,,7、用等價(jià)公式求主析(合)取范式（續(xù)）,例7 求Q∧（(P∨?Q)→R）的主合取范式。,,解：Q∧（(P∨?Q)→R）? Q∧(?P∨R)∧(Q∨R) (化為合取范式)? ((P∧?P)∨Q∨(R∧?R))∧(?P∨(Q∧?Q)∨R)∧((P∧?P)∨Q∨R) (補(bǔ)入未出現(xiàn)的變?cè)?? (P∨Q∨R)∧(P∨Q∨?R)∧(?P∨Q∨R)∧(?P∨Q∨?R) ∧(?P

18、∨Q∨R)∧(?P∨?Q∨R)∧(P∨Q∨R)∧(?P∨Q∨R) (展開(kāi))? (P∨Q∨R)∧(P∨Q∨?R)∧(?P∨Q∨R) ∧(?P∨Q∨?R)∧(?P∨?Q∨R) (合并相同的小項(xiàng))? M0∧M1∧M4∧M5∧M6?∏0,1,4,5,6,,,,,8、主析、合取范式互求,設(shè)命題公式Ａ中含有ｎ個(gè)命題變?cè)遥恋闹魑鋈》妒街泻雮€(gè)極小項(xiàng) ｍi1 ，ｍi2 ．．．ｍik ，即 A?ｍi1∨ｍi2∨

19、 ．．．∨ｍik 那么，?Ａ的主析取范式中必含2n-k個(gè)極小項(xiàng)。設(shè)它們是ｍj1 ，ｍj2 ．．．Ｍj(2n-k)，即 ?Ａ?ｍj1 ∨ｍj2∨．．．∨ｍj (2n-k) 注意到?ｍi?Mi，? Mi? mi，所以 A???A ?? (ｍj1 ∨ｍj2∨．．．∨ｍj(2n-k) ) ??ｍj1 ∧?ｍj2 ∧ ．．．∧?ｍj(2n-k)，

20、 ?Mj1 ∧ Mj2 ∧ ．．． ∧ Mj(2n-k),,,,,9、范式的應(yīng)用,㈠．判定二命題公式是否等值。 Ａ?Ｂ當(dāng)且僅當(dāng)Ａ與Ｂ有相同的主析（合）取范式。㈡．判定命題公式的類型。設(shè)Ａ是含有ｎ個(gè)變?cè)拿}公式：①Ａ為重言式，當(dāng)且僅當(dāng)Ａ的主析取范式中含有2n個(gè)小項(xiàng)。此時(shí)，主合取范式中不含任何大項(xiàng)，可令主合取范式為T(mén)。②Ａ為永假式，當(dāng)且僅當(dāng)Ａ的主合取范式中含有2n個(gè)大項(xiàng)。此時(shí)主析取范式中不含任何小項(xiàng)，可令主析取范式為F。

21、㈢．求命題公式的成真和成假賦值。,,,,,,10、范式的應(yīng)用（例）,例７ 判斷下列命題公式的類型及成真賦值和成假賦值：⑴ ?(P→Q)∧Q； ⑵ (P→Q)∧P→Q； ⑶ (P→Q)∧Q。解：⑴ ?(P→Q)∧Q ??(?P∨Q)∧Q? P∧?Q∧Q (? F) ?(P∨(?Q∧Q))∧(?Q∨(?P∧P))∧(Q∨(?P∧P)) ?(P∨?Q)∧(P∨Q)∧(?P∨?Q)∧(P∨?Q)∧(?P∨Q)∧(P∨Q) ?(

22、P∨Q)∧(P∨?Q)∧(?P∨Q)∧(?P∨?Q) ?∏0,1,2,3 （永假式） ⑵ (P→Q)∧（P→Q） ?(?P∧?Q)∨(?P∧Q)∨(P∧?Q)∨(P∧Q) ?ｍ0∨ｍ1∨ｍ2∨ｍ3? ∑0,1,2,3 （重言式）⑶ (P→Q)∧Q ? (?P∧Q)∨(P∧Q) ?ｍ1∨ｍ3? ∑1,3 （可滿足式）在本例⑶中，成真賦值是：０１或１１；成假賦值是： １０或００。,,,,,,第1-4講 作業(yè),P39