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

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

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

3、，Ａ中的∨、∧、Ｔ、Ｆ將分別轉(zhuǎn)化為∧、∨、Ｆ、Ｔ，且每一變元都將帶上?號。所以 ?Ａ(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)。而按對偶式的定義，由A*（P,Q,R）可寫出 Ａ(P,Q,R)??P∨(?Q∧R)故 ?Ａ(P,Q,R)??（?P∨(?Q∧R)） ?P∧?(?Q∧R) （德．摩根律） ?P∧(Q∨?R) （德．摩根律） ? A*(?P,?Q,?

5、R),,,,,2. 對偶原理,證：設(shè)Ａ(P1, P2，…, Pn)?Ｂ(P1, P2，…, Pn)，按等價定義可知Ａ(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 (對偶原理)設(shè)A*、B*分別是命題公式Ａ、Ｂ的對偶式。如果Ａ?Ｂ，則A*?B*。,,,,,問題１： 很多命題公式的外表形式雖不同，但它們是等價的。形式不同的所有等價命題公式是否可以化為唯一的

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

8、聯(lián)結(jié)詞全部化為?、∧、∨；⑵ 利用德．摩根律，將?直接移到各命題變元之前；⑶ 利用分配律、結(jié)合律將命題公式化為析取范式或合取范式。,定義2 一個命題公式稱為析取范式，當(dāng)且僅當(dāng)它具有形式：A1∨A2∨...∨An (n≥1)，其中A1、A2、... An都是由命題變元或其否定構(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) （③ 用∧對∨的分配律）? (?P∧Q)∨(Q∧R) （④ 析取范式）求合取范式（①,②兩個步驟相同）：Q∧（(P∨?Q)→R） ?Q∧（(?P∧Q)∨R）

10、?Q∧（(?P∨R)∧(Q∨R)）?Q∧(?P∨R)∧(Q∨R）,,任一命題公式都有一個與之等值的析取范式和合取范式。,,,,,4、主析取范式（小項）,定義3 在ｎ個變元的合取式中，若每一個變元與其否定不同時存在，但二者之一必須出現(xiàn)且僅出現(xiàn)一次,同時按某種順序第ｉ個命題變元或其否定出現(xiàn)在左起第ｉ個位置上，則這種合取式叫小項。,,例如，三個命題變元Ｐ、Ｑ、Ｒ可形成８個小項：,,,,,4、主析取范式（小項的性質(zhì)）,小項有如下幾個性質(zhì)：

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

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

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

14、派所對應(yīng)的小項分別為m1， m2，...，mk和mK+1，mK+2，...，m2n-1。令Ｂ? m1∨m2∨... ∨mk，下面證明Ａ?Ｂ。 設(shè)A在某一指派下為T，該指派所對應(yīng)的小項mi必在Ｂ中，因為mi為Ｔ(小項性質(zhì)) ，從而B為T。 設(shè)A在某一指派下為F，該指派所對應(yīng)的小項mj必不在Ｂ中，在該指派下m1， m2，...，mk 均為Ｆ，故Ｂ為Ｆ。 以上說明，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、用等價公式求主析(合)取范式,例6 求Q∧（(P∨?Q)→R）的主析取范式。,,解：Q∧（(P∨?Q)→R）? (?P∧Q)∨(Q∧R) (先化為析取范式)? (?P∧Q∧(R∨?R))∨((P∨?P)∧Q∧R) (補(bǔ)入未出現(xiàn)的變元)? (?P∧Q∧R)∨(?P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R) (展開)? (?P∧Q∧?R)∨(?P∧Q∧R)∨(P∧Q∧R) (合并相同的小項)? m

17、2∨m3∨m7?∑2,3,7,,,,,7、用等價公式求主析(合)取范式（續(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)的變元)? (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) (展開)? (P∨Q∨R)∧(P∨Q∨?R)∧(?P∨Q∨R) ∧(?P∨Q∨?R)∧(?P∨?Q∨R) (合并相同的小項)? M0∧M1∧M4∧M5∧M6?∏0,1,4,5,6,,,,,8、主析、合取范式互求,設(shè)命題公式Ａ中含有ｎ個命題變元，且Ａ的主析取范式中含ｋ個極小項 ｍi1 ，ｍi2 ．．．ｍik ，即 A?ｍi1∨ｍi2∨

19、 ．．．∨ｍik 那么，?Ａ的主析取范式中必含2n-k個極小項。設(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è)Ａ是含有ｎ個變元的命題公式：①Ａ為重言式，當(dāng)且僅當(dāng)Ａ的主析取范式中含有2n個小項。此時，主合取范式中不含任何大項，可令主合取范式為T。②Ａ為永假式，當(dāng)且僅當(dāng)Ａ的主合取范式中含有2n個大項。此時主析取范式中不含任何小項，可令主析取范式為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