離散數(shù)學(xué)第二章)

1、離散數(shù)學(xué),許雷（數(shù)學(xué)與信息科學(xué)學(xué)院）郵箱：410407667qq.com）電話：18080221926,§1.3 命題公式的等值式,定義1: 給定兩個(gè)命題公式A和B，設(shè)P1 ,P2 ,…,Pn為出現(xiàn)于A和B中的所有原子變元,若給P1 , P2 ,…,Pn任一組真值指派, A和B的真值都相同,則稱A和B是等價(jià)的或邏輯相等.記作A ? B。,§1.3 命題公式的等值式,注: (1) “ ? ”不是邏輯聯(lián)結(jié)詞

2、.(2)命題公式之間的邏輯相等關(guān)系具有： 自反性：A ? A ； 對稱性：若A ? B，則B ? A； 傳遞性：若A ? B且B ? C，則A ? C。,§1.3 命題公式的等值式,證明公式等價(jià)的方法：1. 真值表法 2. 等值演算法1. 真值表法 例1.Ｐ∨¬Ｐ?Ｑ∨¬Ｑ,1,1,1 1,1,1,1 0,1,1,0

3、 1,1,1,0 0,Q ∨¬Q,P∨¬P,P Q,,,,,,,,,,,§1.3 命題公式的等值式,例2. 證明: P?Q ?(P→Q)?(Q→P),§1.3 命題公式的等值式,例2. 證明: P?Q ?(P→Q)?(Q→P),§1.3 命題公式的等值式,例3：判斷公式 P?(Q?R)、(P∧Q)?R是否等價(jià),§1.3

4、命題公式的等值式,例3：判斷公式 P?(Q?R)、(P∧Q)?R是否等價(jià),§1.3 命題公式的等值式,2. 等值演算法(Equivalent Calculation) 等值演算中使用的一條重要規(guī)則：置換規(guī)則定義2 (子公式)：如果X是wff A的一部分,且X本身也是wff，則稱X是A的子公式。例如, P?(P?Q)為Q? (P?(P?Q))的子公式。,§1.3 命題公式的等值式,(置換定理Axiom of

5、rePlacement) 設(shè)X是wff A的子wff，若X?Y，則若將A中的X用Y來置換，所得公式B與A等價(jià)，即A?B。證：因?yàn)閷ψ冊娜我恢概?X與Y真值相同，所以Y取代X后，公式B與公式A對變元的任一指派真值也相同,所以A?B。,§1.3 命題公式的等值式,注: 滿足置換定理的條件的置換稱為等價(jià)置 換(或等價(jià)代換).定義2(等值演算)：根據(jù)已知的等價(jià)公式,推演出另外一些等價(jià)公式的

6、過程稱為等值演算.,§1.3 命題公式的等值式,常用的等價(jià)式： 1.雙重否定律： ┐┐P? P 2.結(jié)合律：(P?Q)?R?P?(Q?R) (P?Q)?R?P?(Q?R) (P?Q)?R?P?(Q?R) 3.交換律: P?Q?Q?P P?Q? Q?P P?Q ?Q?P 4.

7、分配律: P?(Q?R )?(P?Q)?(P?R) P?(Q?R)?(P?Q)?(P?R),§1.3 命題公式的等值式,常用的等價(jià)式： 5.冪等律: P?P? P P?P? P 6.吸收律: P?(P?Q) ?P P?(P?Q) ?P 7.德.摩根律: ┐(P?Q)?┐P?┐Q ┐(P?Q)

8、?┐P?┐Q 8.同一律: P?0?P P?1?P 9.零律: P?1?1 P?0?0,§1.3 命題公式的等值式,常用的等價(jià)式： 10.否定律： P?┐P?1 P?┐P?0 11. 蘊(yùn)涵等值式: P?Q? ┐P?Q 12. 等價(jià)等值式: P?Q?(P→Q)?(Q→P) 13. 假言易位: P?Q?┐Q ? ┐P 14. 等價(jià)否定等值式

9、: P?Q?┐P?┐Q 15. 歸謬論: (P?Q )?( P?┐Q)?┐P,§1.3 命題公式的等值式,其中P, Q, R等代表任意命題公式. 這樣上面的每一個(gè)公式都是一個(gè)模式, 它可以代表無數(shù)多個(gè)同類型的命題公式. 例如, P?┐P?1 中, 用(P?Q)置換P,則得 (P?Q)?┐(P?Q)?1 ,用┐P置換P,則得 (┐P)?┐(┐P)?1 。,§1.3 命題公式的等值式,例1： 證明 Q→(P

10、?(P?Q))?Q→P證: Q→(P?(P?Q)) ?Q→P ~~~~~~~~ P(吸收律)例2： 證明 (P?┐Q)?Q?P?Q證：(P?┐Q)?Q?(P?Q)?(┐Q?Q)?(P?Q)?T ?P?Q,§1.3 命題公式的等值式,例3：證明(P→Q)→(Q?R)? P?Q?R證：(

11、P→Q)→(Q?R) ?(┐P?Q)→(Q?R) ? ┐(┐P?Q)?(Q?R) ?(P?┐Q)?(Q?R) ?(P?Q?R)?(┐Q?Q?R) ? P?Q?R,§1.3 命題公式的等值式,例4：驗(yàn)證P?(Q?R) ?(P∧Q)?R證: 右?┐(P∧Q)∨R ? ┐P∨┐Q∨R ? ┐P∨(┐Q∨R) ? ┐P∨(Q?R))

12、 ? P?(Q?R)練：1.((P?Q)∧(P?R))?P?(Q∧R) 2.(P∧┐Q)∨(┐P∧Q)?(P∨Q)∧┐(P∧Q),§1.3 命題公式的等值式,等值演算的應(yīng)用： 1.驗(yàn)證等值式 2.判定公式的類型（p23,例2.5） 3.解決工作生活中的判斷問題,例5：甲、已、丙3人根據(jù)口音對王教授是哪人進(jìn)行了判斷： 甲說：王教授不是蘇州人，是上海

13、人 已說：王教授不是上海人，是蘇州人 丙說：王教授既不是上海人，也不是杭州人結(jié)果3人中有一人全對，一人對一半，一人全錯(cuò)。問王教授是哪人？,§1.4 析取范式與合取范式,定義1: (1)文字：命題變元及其否定統(tǒng)稱為文字(如P , ┐P). (2)簡單析取式：僅有有限個(gè)文字組成的析取式。 如:P，┐P?Q，P?┐P，Q?P?┐P，P?┐Q?R?┐S.(3)簡單合取式：僅有有限個(gè)文字組成的合取式。 如:

14、P, ┐Q , Q?┐P，P?┐P，Q?P?┐P, P?┐Q?R.,注意：單個(gè)文字既是簡單析取式又是簡單合取式,從定義不難看出:定理1：（1）一個(gè)簡單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變元及其否定式。（2）一個(gè)簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變元及其否定式。,§1.4 析取范式與合取范式,定義2: (1)析取范式：一個(gè)命題公式稱為析取范式,當(dāng)且僅當(dāng)它具有形式: A1∨A2∨……∨An (n大于等

15、于1)其中Ai(i=1,2,3,…n)為簡單合取式.如：P∨┐Q ，(P∧Q)∨(P∧┐Q∧R), Q∧┐P. (2)合取范式：一個(gè)命題公式稱為合取范式,當(dāng)且僅當(dāng)它具有形式: A1∧A2∧……∧An (n大于等于1)其中Ai(i=1,2,3,…n)為簡單析取式.如：P ∧ ┐Q ，(P∨Q)∧(P∨┐Q∨R), Q∧┐P.,§1.4 析取范式與合取范式,(3)范式：析取范式與合取范式統(tǒng)稱為范式。顯然, 任何合(

16、析)取范式的對偶式是析(合)取范式.,析取范式與合取范式的性質(zhì):定理2：(1) 一個(gè)析取范式是矛盾式,當(dāng)且僅當(dāng)它的每 一個(gè)簡單合取式都是矛盾式;(2)一個(gè)合取范式是重言式,當(dāng)且僅當(dāng)它的每 一個(gè)簡單析取式都是重言式.,§1.4 析取范式與合取范式,定理3 (范式存在定理)任一個(gè)命題公式都存在著與之等價(jià)的析取范式與合取范式。,§1.4 析取范式與合取范式,,求命題公式的范式的基本步驟：,§

17、;1.4 析取范式與合取范式,（１）利用等價(jià)公式：化去“→”、“?”聯(lián)結(jié)詞，把命題公式變?yōu)榕c其等價(jià)的用{¬，∧，∨}表達(dá)的公式。 例: Ｐ→Ｑ?¬Ｐ∨Ｑ， Ｐ? Ｑ?（Ｐ∧Ｑ）∨（¬Ｐ∧¬Ｑ） ?（¬Ｐ∨Ｑ）∧（Ｐ∨¬Ｑ）（２）將“¬”深入到原子命題變元之前，并使變元之前最多只有一個(gè)“¬”詞。例：

18、¬（¬Ｐ∨¬Ｑ）?¬ ¬Ｐ∧ ¬ ¬Ｑ ?Ｐ∧Ｑ,,§1.4 析取范式與合取范式,（３）利用∧對∨的分配，將公式化為析取范式，求合取范式利用∨對 ∧的分配 。（４）除去永假項(xiàng)得最簡析取范式與合取范式。例：求（Ｐ → Ｑ）? R的合取范式 解：原式 ?（¬ Ｐ∨Ｑ

19、） ? R （消去→ ）,,§1.4 析取范式與合取范式,? （（¬ Ｐ∨Ｑ） → R） ∧ （R → （¬ Ｐ∨Ｑ）） （消去?）? （¬（¬ Ｐ∨Ｑ） ∨ R ）∧ （ ¬R ∨ （ ¬Ｐ∨ Ｑ）） （消去→ ）? （ Ｐ ∧ ¬ Ｑ） ∨ R ） ∧ （ ¬P ∨ Ｑ ∨ ¬R ）（否定內(nèi)移

20、）?（ Ｐ ∨ R ） ∧ （¬ Ｑ ∨ R ） ∧ （ ¬P ∨ Ｑ ∨ ¬R ）（ ∨對或∧的分配 ）,,§1.4 析取范式與合取范式,例：求（Ｐ → Ｑ）? R的析取范式 解：原式 ?（¬ Ｐ∨Ｑ） ? R （消去→) … ? （ Ｐ ∧ ¬ Ｑ） ∨ R ） ∧ （ ¬P ∨ Ｑ ∨ ¬R ）

21、 （否定內(nèi)移 ） ? （ Ｐ ∧ ¬ Ｑ ∧ ¬P ） ∨ （ Ｐ ∧ ¬ Ｑ ∧ Ｑ ） ∨ （ Ｐ ∧ ¬ Ｑ ∧ ¬R ） ∨ （R ∧ ¬P） ∨ （R ∧ Ｑ ） ∨ （R ∧ ¬R ） ? （ Ｐ ∧ ¬ Ｑ ∧ ¬R ） ∨ （ R ∧ ¬P） ∨ （R ∧ Ｑ

22、 ）（ ∧對∨的分配）,§1.4 析取范式與合取范式,注意：（1）單個(gè)命題變元既是簡單合取式，又是簡單析取式；公式P∧Q∧R既可以看成是三個(gè)簡單析取式構(gòu)成的合取范式，也可以看成是析簡單合取式構(gòu)成的析取范式。（2）一個(gè)命題公式的析(合)取范式不是唯一的。,§1.4 析取范式與合取范式,例1：求((P?Q)?R)?P的析取范式與合取范式 解: 原式?┐(┐(P∨Q)∨R)∨P?((P∨Q )∧┐R)∨P?(P

23、∧┐R )∨(Q∧┐R)∨P (析取范式)?P∨(P∧┐R )∨(Q∧┐R)?P∨(Q∧┐R) (析取范式)?(P∨Q ∨P )∧(┐R∨P ) (合取范式)?(P∨Q)∧(┐R∨P ) (合取范式),§1.4 析取范式與合取范式,例2：求(P ? Q) ? R的析取范式與合取范式 解: 原式?((P?Q) ?R)∧(R?(P?Q) )?(┐(P?Q)∨R)∧(┐R ∨(P?Q) )?(┐(┐P∨Q)∨R)∧(┐

24、R∨┐P∨Q )?((P∧ ┐Q)∨R)∧(┐R∨┐P∨Q )?((P∨R)∧(┐Q∨R)∧(┐R∨┐P∨Q ) (合取范式)?((P∧┐Q)∧(┐R∨┐P∨Q ) )∨(R ∧(┐R∨┐P∨Q )?(P∧┐Q∧┐R)∨(R∧┐P)∨(R∧Q) (析取范式),§1.4 析取范式與合取范式,命題公式的主析(合)取范式(由于一個(gè)命題公式的析(合)取范式不是唯一, 因而它們不能作為命題公式的規(guī)范形式(標(biāo)準(zhǔn)形式), 為

25、了使任意命題公式化為唯一的標(biāo)準(zhǔn)形式, 下面引入主范式的概念.,§1.4 析取范式與合取范式,1.命題公式的主析取范式定義3：在含有n個(gè)命題變元的簡單合取式中,若每個(gè)命題變元和它的否定不同時(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，稱這樣的簡單合取式為小項(xiàng).例如,三個(gè)命題變元P,Q,R,其小項(xiàng)共有8個(gè):,§1.4 析取范式與合取范式,小項(xiàng) 編碼 真值指派 小項(xiàng)

26、的真值 ┐P?┐Q?┐R m000/ m0 000 1 ┐P?┐Q?R m001/m1 001 1 ┐P?Q?┐R m010/m2 010 1 ┐P?Q?R m011/m3 011 1 P

27、?┐Q?┐R m100/m4 100 1 P?┐Q?R m101/m5 101 1 P?Q?┐R m110/m6 110 1 P?Q?R m111/m7 111

28、 1,§1.4 析取范式與合取范式,考慮：n個(gè)命題變元可產(chǎn)生多少個(gè)?。ù螅╉?xiàng)？ n個(gè)變元的小項(xiàng): m0 ?┐P1?┐P2?………….?┐Pn m1 ?┐P1?┐P2?………….?Pn ………………………………… m2n-1?P1?P2?………….?Pn,§1.4 析取范式與合取范式,極小項(xiàng)的性質(zhì):沒有兩個(gè)小項(xiàng)是等價(jià)的, 且每個(gè)極小項(xiàng)有且僅有一個(gè)成真賦值，若成真賦值所對應(yīng)的二進(jìn)

29、制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為i，就將所對應(yīng)的極小項(xiàng)記作mi。(2) 任意兩個(gè)不同的極小項(xiàng)的合取為矛盾式.(3) 全體極小項(xiàng)的析取為永真式.,§1.4 析取范式與合取范式,定義4：設(shè)命題公式A中含有n個(gè)命題變元, 如果A的析取范式中，所有的簡單合取式都是極小項(xiàng)，則稱該析取范式為A的主析取范式。定理4:任何命題公式都存在著與之等價(jià)的主析取范式，并且是唯一的。求主析取范式的方法：真值表；等值演算發(fā),§1.4 析取范式

30、與合取范式,真值表法：在真值表中，一個(gè)公式的真值為1的指派所對應(yīng)的極小項(xiàng)的析取，即為公式的主析取范式,例：求出Ｐ→Ｑ、Ｐ∨¬Ｑ、 ¬（Ｐ∧Ｑ）、Ｐ∧¬Ｑ的主析取范式,§1.4 析取范式與合取范式,例：求出Ｐ→Ｑ、Ｐ∨¬Ｑ、 ¬（Ｐ∧Ｑ）、Ｐ∧¬Ｑ的主析取范式,§1.4 析取范式與合取范式,則可直接寫出各命題公式的

31、主析取范式：Ｐ→Ｑ?（¬Ｐ∧ ¬Ｑ）∨（ ¬Ｐ∧Ｑ）∨（Ｐ∧Ｑ）Ｐ∨¬Ｑ?（¬Ｐ∧¬Ｑ）∨（Ｐ∧¬Ｑ）∨（Ｐ∧Ｑ）¬（Ｐ∧Ｑ）?（¬Ｐ∧¬Ｑ）∨（¬Ｐ∧Ｑ）∨（Ｐ∧¬Ｑ）Ｐ∧¬Ｑ?（Ｐ∧¬Ｑ）,§1.4 析取范式與合取范式,（1）只要命題公式不是永假式，則一定可以根據(jù)該命題公式的真

32、值表直接寫出其主析取范式，其方法是找出該公式為1的行，對應(yīng)寫出極小項(xiàng)的析取式，且一定是唯一的。（2）若命題公式是含有n個(gè)變元的永真式，則它的主析取范式一定含有2n個(gè)極小項(xiàng)。（3）若二個(gè)命題公式對應(yīng)的主析取范式相同，則此二個(gè)命題公式一定是等價(jià)的。（4）命題公式的主析取范式中極小項(xiàng)的個(gè)數(shù)一定等于對應(yīng)真值表中真值為1的個(gè)數(shù)。,§1.4 析取范式與合取范式,等值演算法：下面介紹不用真值表，直接求命題公式主析取范式的方法，分四步

33、：（１）將命題公式化歸為與其等價(jià)的析取范式； （２）除去永假項(xiàng)，合并基本積中相同項(xiàng)例：Ｐ∧Ｐ∧Ｑ?Ｐ∧Ｑ），變?yōu)樽詈單鋈》妒?。（３）利用添變元的方法，將所有基本積變?yōu)闃O小項(xiàng)。,§1.4 析取范式與合取范式,例：二個(gè)變元Ｐ、Ｑ，利用“∧”對或“∨”的分配添項(xiàng)　?。?Ｐ∧（Ｑ∨¬Ｑ） ?（Ｐ∧Ｑ）∨（Ｐ∧¬Ｑ） Ｑ?Ｑ∧（Ｐ∨¬Ｐ） ?（

34、Ｐ∧Ｑ）∨（¬Ｐ∧Ｑ）（４）合并相同的極小項(xiàng)變?yōu)橐豁?xiàng)。例：求（Ｐ∧（Ｐ→Ｑ））∨Ｑ的主析取范式解：原式?（Ｐ∧¬Ｐ）∨（Ｐ∧Ｑ）∨Ｑ ----（1）化為析取范式,§1.4 析取范式與合取范式,? （Ｐ∧Ｑ）∨Ｑ ----（2）消去永假項(xiàng)，變?yōu)樽詈單鋈》妒?（Ｐ∧Ｑ）∨（Ｑ∧（Ｐ∨¬Ｐ））?（Ｐ∧Ｑ）∨（Ｐ∧

35、Ｑ）∨（¬Ｐ∧Ｑ）

36、

37、 ----（3）添項(xiàng)?（Ｐ∧Ｑ）∨（¬Ｐ∧Ｑ） ----（4）合并相同最小項(xiàng),§1.4 析取范式與合取范式,例1

38、：求((P?Q)?R)?P的主析取范式。 解: 原式?┐(┐(P∨Q)∨R)∨P?P∨(Q∧┐R) (析取范式)?(P∧(Q∨┐Q)∧(R∨┐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)∨(P∧Q∧┐R)∨(P∧┐Q∧R)∨ (P∧┐Q∧┐R)∨(┐P∧Q∧┐R) (主析取范式)?m7∨m6∨m

39、5∨m4∨m2?m2∨m4∨m5∨m6∨m7,§1.4 析取范式與合取范式,例2：求(P?Q)?R的主析取范式。解:?(P∧┐Q∧┐R)∨(R∧┐P)∨(R∧Q) (析取范式)?(P∧┐Q∧┐R)∨((R ∧┐P)∧(Q∨┐Q))∨ ((P∨┐P) ∧(R∧Q )) ?(P∧┐Q∧┐R)∨(┐P∧Q∧R)∨(┐P∧┐Q∧R)∨ (P∧Q∧R)∨(┐P∧Q∧R ) ?(P∧┐Q∧┐R)∨(┐P∧Q∧R)∨

40、 (┐P∧┐Q∧R) ∨(P∧Q∧R) (主析取范式)? m1∨ m3∨ m4∨ m7,§1.4 析取范式與合取范式,2.命題公式的主合取范式定義5：在含有n個(gè)命題變元的簡單析取式中,若每個(gè)命題變元和它的否定不同時(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，稱這樣的簡單析取式為極大項(xiàng).例如,三個(gè)命題變元P,Q,R,其大項(xiàng)共有8個(gè):,§1.4 析取范式與合取范式,大項(xiàng)

41、 編碼 真值指派 大項(xiàng)的真值 P?Q?R M000/M0 000 0 P?Q?┐R M001/M1 001 0 P?┐Q?R M010/M2 010 0P?┐Q?┐R M011/M3 011 0┐P?Q?R M100/M4

42、 100 0┐P?Q?┐R M101/M5 101 0 ┐P?┐Q?R M110/M6 110 0 ┐P?┐Q?┐R M111/M7 111 0,§1.4 析取范式與合取范式,極大項(xiàng)的性質(zhì):沒有兩個(gè)大項(xiàng)是等價(jià)的, 且每個(gè)極大項(xiàng)有且僅有一

43、個(gè)成假賦值，若成假賦值所對應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為i，就將所對應(yīng)的極大項(xiàng)記作Mi。(2) 任意兩個(gè)不同的極大項(xiàng)的析取為永真式.(3) 全體極大項(xiàng)的合取為矛盾式.,§1.4 析取范式與合取范式,定義6：設(shè)命題公式A中含有n個(gè)命題變元, 如果A的合取范式中，所有的簡單析取式都是大項(xiàng)，則稱該合取范式為A的主合取范式。定理：任何命題公式都存在著與之等價(jià)的主合取范式，并且是唯一的。,§1.4 析取范式與合取范式

44、,定理5:在命題公式A的真值表中,真值為0的指派對應(yīng)的大項(xiàng)的合取, 即為A的主合取范式,一個(gè)命題公式A的主合取范式, 還可以通過等值演算的方法求出, 其推演步驟:(1) 將A化為合取范式 ;(2) 除去合取范式中所有永真的合取項(xiàng);,§1.4 析取范式與合取范式,(3) 將合取范式中重復(fù)出現(xiàn)的簡單析取式和相同變元都消去;(4)若合取范式中某簡單析取式B中不含命題變元Pi, 添加(Pi?┐Pi), 然后應(yīng)用分配律展開. 即

45、 B ?B?0?B?(Pi?┐Pi) ?(B?Pi)?(B?┐Pi).,注：1.命題公式的主析(合)取范式唯一。 2.兩命題公式若有相同的主析(合)取范 式，則二命題公式等價(jià).,§1.4 析取范式與合取范式,例3：求((P?Q)?R)?P的主合取范式。 解: 原式?┐(┐(P∨Q)∨R)∨P? (P∨Q)∧(┐R∨P ) (合取范式)?((P∨Q)∨(R∧┐R ))∧((┐R∨P )∨(Q∧┐Q))

46、?(P∨Q∨R)∧(P∨Q∨┐R)∧(P∨Q∨┐R)∧ (P∨┐Q∨┐R) ?(P∨Q∨R)∧(P∨Q∨┐R)∧(P∨┐Q∨┐R) (主合取范式)?M0∧M1∧M3,§1.4 析取范式與合取范式,例4：求(P?Q)?R的主合取范式。 解: 原式?(P∨R)∧(┐Q∨R)∧(┐R∨┐P∨Q) (合取范式)?((P∨R)∨(Q∧┐Q)) ∧((P∧┐P) ∨(┐Q∨R)) ∧(┐P∨Q∨┐R )

47、?(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 ) (主合取范式)?M0∧M2∧M5 ∧M6,§1.4 析取范式與合取范式,3.主析取范式和主合取范式關(guān)系設(shè)Z為命題公式A的主析取范式中所有小項(xiàng)的足標(biāo)集合，R為命題公式A的主合取范式中所有大項(xiàng)的足標(biāo)集合,則

48、 R={0,1，2…….2n-1}-Z或 Z={0,1，2…….2n-1}-R。故已知命題公式A的主析取范式，可求得其主合取范式；反之亦然。注意到小項(xiàng)與大項(xiàng)之間具有關(guān)系：┐mi?Mi，┐Mi?mi（例：m5：P?┐Q?R M5：┐P?Q?┐R）,§1.4 析取范式與合取范式,4.主析(合)取范式的應(yīng)用(1)求公式的成真/成假賦值： 若公式A中含有n個(gè)命題變

49、元，且A的主析取范式含s個(gè)極小項(xiàng)，則A有s個(gè)成真賦值，有2n-s個(gè)成假賦值。（即主析取范式中的小項(xiàng)對應(yīng)的編碼是公式A的成真賦值；反之主合取范式中的大項(xiàng)對應(yīng)的編碼是公式A的成假賦值）.,§1.4 析取范式與合取范式,(2)判斷公式的類型： 設(shè)公式A中含有n個(gè)命題變元，則：（1） A為重言式? A的主析取范式含全部2n個(gè)極小項(xiàng)（2）A為矛盾式? A的主析取范式不含任何極小項(xiàng)， 記A的主析取范式為0

50、（3） A為可滿足式? A的主析取范式至少含一個(gè)極小項(xiàng)（4） A為矛盾式? A的主合取范式含全部2n個(gè)極大項(xiàng)（5） A為重言式? A的主合取范式不含任何極大項(xiàng)， 記A的主合取范式為1 （6） A為可滿足式? A的主合取范式中極大項(xiàng)的個(gè)數(shù) 一定小于2n,§1.4 析取范式與合取范式,(3)判斷兩個(gè)命題是否等價(jià),5.解決實(shí)際問題：某科研所有三名青年高級工程師A，B，C。所里要選派他們

51、中的1到2人出國進(jìn)修，由于所里工作的需要，選派時(shí)必須滿足以下條件：①若A去，則C也去②若B去，則C不能去③若C不去，則A或B去問所里應(yīng)如何選派他們？,§1.4 析取范式與合取范式,解: 設(shè) P:派A去。Q :派B去。R :派C去。根據(jù)所要滿足的條件，得命題公式為： (P?R)∧(Q? ┐R)∧(┐R?( P∨Q) )求此公式的主析取范式:原式?(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨(P∧┐Q

52、∧R) 因此有三種選派方案：Ｃ去，而Ａ、Ｂ都不去；Ｂ去，而Ａ、Ｃ都不去；Ａ、Ｃ都去，而Ｂ不去.,§1.4 析取范式與合取范式,小結(jié):本節(jié)主要介紹了范式、 析(合)取范式、(主)析(合)取范式。重點(diǎn)掌握(主)析(合)取范式的求法。 作業(yè): 1. 習(xí)題2: 7、8、9、30 2. 預(yù)習(xí)§2.3,§1.5 聯(lián)結(jié)詞的完備集,定義: {0, 1}上的n元函數(shù)

53、 f: { 0, 1}n ?{ 0, 1} 就稱為一個(gè)n元真值函數(shù)（布爾函數(shù)）自變量有2n組不同的取值，真值函數(shù)取值只有兩種：1 　0,共有 種不同的真值函數(shù),§1.5 聯(lián)結(jié)詞的完備集,62,問題：,常用五個(gè)聯(lián)結(jié)詞┐， ∧， ∨， ? ，?是否有冗余呢？,A→B?¬A∨B,A?B?( A→B) ∧ (B → A),§1.5 聯(lián)結(jié)詞的完備集,聯(lián)結(jié)詞完備集,定義：一個(gè)聯(lián)結(jié)詞集合，若對于任何

54、一個(gè)公式均可以用該集合中的聯(lián)結(jié)詞來表示或等值表示，就稱為聯(lián)結(jié)詞完備集。 如果該集合任意去掉一個(gè)聯(lián)結(jié)詞，就不再具備這種特性，就稱為最小完備集。,定理：{┐,∧,∨}是聯(lián)結(jié)詞完備集。,推論：{┐,∧,∨,→}，{┐,∧,∨,→,?}， 等都是聯(lián)結(jié)詞完備集。,§1.5 聯(lián)結(jié)詞的完備集,64,因?yàn)閜∨q ? ┐（┐p∧┐q） p∧q ? ┐（┐p∨┐q） p∨q ? ┐p → q

55、 p∧q ? ┐（p → ┐q）,推論：{┐、∧}、{┐、∨}、{┐、→}是聯(lián)結(jié)詞完備集，并且是最小聯(lián)結(jié)詞完備集。,,§1.5 聯(lián)結(jié)詞的完備集,{┐，?}是否是完備集？可以證明任何一個(gè)僅含“?”和“┐”的二元命題合式公式真值中有1和0 的個(gè)數(shù)都是偶數(shù)的。不是,§1.5 聯(lián)結(jié)詞的完備集,{∧ ， ∨ ，→ ，?}不是完備集 （只需證明┐p無法由僅含此聯(lián)結(jié)詞集中的聯(lián)結(jié)詞的公式表示即可 ）總?cè)?值的真值函數(shù)

56、不能由只含此聯(lián)結(jié)詞集中的聯(lián)結(jié)詞的命題形式來表示。因?yàn)檫@樣的命題形式在其中的命題變元都取1時(shí)也取值1, 而不為0.{∧}，{∨}，{¬}，{→}，{?}都不是完備集,§1.5 聯(lián)結(jié)詞的完備集,設(shè)p、q為二命題，復(fù)合命題“p與q的否定”稱為p與q的與非式，記作p?q，?稱與非聯(lián)結(jié)詞 易見：1、 p?q ? ┐（p∧q） 2、 p?q為真當(dāng)且僅當(dāng)p與q不同時(shí)為真,與非聯(lián)結(jié)詞?的性質(zhì)：（

57、1）p?p ? ┐(p∧p) ? ┐p（2）(p?q)?(p?q) ? ┐(p?q) ? p∧q（3）(p?p)?(q?q) ? ┐p?┐q ? ┐(┐p∧┐q) ? p∨q,定義 與非聯(lián)結(jié)詞,§1.5 聯(lián)結(jié)詞的完備集,與非聯(lián)結(jié)詞,§1.5 聯(lián)結(jié)詞的完備集,設(shè)p、q為二命題，復(fù)合命題“p或q的否定”稱為p與q的或非式，記作p?q，?稱或非聯(lián)結(jié)詞 易見：1、 p?

58、q ? ┐（p∨q） 2、 p?q為真當(dāng)且僅當(dāng)p與q同時(shí)為假,或非聯(lián)結(jié)詞,或非聯(lián)結(jié)詞?的性質(zhì)：（1）p?p ? ┐(p∨p) ? ┐p（2）(p?q)?(p?q) ? ┐(p?q) ? p∨q（3）(p?p)?(q?q) ? ┐p?┐q ? ┐(┐p∨┐q) ? p∧q,§1.5 聯(lián)結(jié)詞的完備集,或非聯(lián)結(jié)詞,§1.5

59、 聯(lián)結(jié)詞的完備集,p?q ?(p∧┐q)∨(┐p∧q),不可兼或,§1.5 聯(lián)結(jié)詞的完備集,定理：{?}是聯(lián)結(jié)詞完備集,證：┐P?┐(P?P)?P↑P P?Q?┐┐(P?Q)?┐(P↑Q) ?(P↑Q)↑(P↑Q) P?Q?┐(┐P?┐Q) ?┐((P↑P)?(Q↑Q)) ?(P↑P)↑(Q↑Q),§