范式--離散數(shù)學(xué)

1、1,2.3 范式,2.3.1 析取范式與合取范式簡單析取式與簡單合取式析取范式與合取范式2.3.2 主析取范式與主合取范式極小項與極大項主析取范式與主合取范式主范式的用途,2,2.3.1 析取范式與合取范式,1、簡單析取式與簡單合取式（1）文字,命題變元及命題變元的否定稱為文字，并稱命題變元為正文字，命題變元的否定為反文字。,如 p 、?q 等。,3,簡單析取式（基本和）：由有限個文字構(gòu)成的析取式。,如 p, ?q, p?

2、?q, p?q?r, …,如 p, ?q, p??q, p?q?r, …,簡單合取式（基本積）：由有限個文字構(gòu)成的合取式。,（2）簡單析取式與簡單合取式,4,在上述表達式中，當 bj=1 時取 Pij 的正文字， bj=0 時取Pij 的反文字。,（3）一般形式,5,（4）簡單析取式與簡單合取式的性質(zhì),定理2.3 (1) 一個簡單析取式是重言式當且僅當它同時含某個命題變元和它的否定。(2) 一個簡單合取式是矛盾式當且僅當它同時含某個

3、命題變元和它的否定。,6,2、析取范式與合取范式（1）定義,定義2.16 （1）由有限個簡單合取式組成的析取式 A1?A2???Ar ，稱為析取范式，其中A1,A2,?,Ar 是簡單合取式。（2）由有限個簡單析取式組成的合取式 A1?A2???Ar 稱為合取范式，其中A1,A2,?,Ar是簡單析取式。（3）析取范式與合取范式的統(tǒng)稱為范式 。,7,（2）析取范式與合取范式的性質(zhì),定理2.4 (1) 一個析取范式是矛盾式當

4、且僅當它的每一個簡單合取式都是矛盾式(2) 一個合取范式是重言式當且僅當它的每一個簡單析取式都是重言式,8,（3）范式存在定理,定理2.5 任何命題公式都存在著與之等值的析取范式與合取范式。,這個定理意味著：,且B是范式。,9,（4）范式求解步驟,求公式A的范式的步驟：(1) 消去A中的蘊涵詞?和等價詞 ?。 A?B??A?B， A?B?(?A?B)?(A??B)(2) 否定聯(lián)結(jié)詞?的內(nèi)移或消去 ? ?

5、A? A，?(A?B)??A??B，?(A?B)??A??B,(3) 使用分配律進行化簡、整合。 A?(B?C)?(A?B)?(A?C) 求合取范式 A?(B?C)? (A?B)?(A?C) 求析取范式,10,舉例,例1 求?(p?q)??r 的析取范式與合取范式解 ?(p?q)??r ? ?(?p?q)??r ? (p??q)??r

6、 析取范式 ? (p??r)?(?q??r) 合取范式,11,例2 求,的合取范式。,求公式 的合取范式。,12,例 3,范式的表達式不唯一。,13,2.3.2 主析取范式與主合取范式,1、極大項與極小項（1）定義,定義2.17 在含有n個命題變項的簡單合取式(簡單析取式)中，若每個命題變項均以文字的形式出現(xiàn)且

7、僅出現(xiàn)一次，而且第i(1?i?n)個文字(按下標或字母順序排列)出現(xiàn)在左起第 i 位上，稱這樣的簡單合取式（簡單析取式）為極小項（極大項）。,14,說明:,(1) n個命題變項產(chǎn)生2n個極小項和2n個極大項。(2) 2n個極小項(極大項)均互不等值。(3) 用mi表示第i個極小項，其中i是該極小項成真賦值的十進制表示；用Mi表示第i個極大項，其中i是該極大項成假賦值的十進制表示，mi(Mi)稱為極小項(極大項)的名稱。,15

8、,2個變元的極大項與極小項,16,（2）極大項與極小項的關(guān)系,定理2.6 設(shè)mi 與Mi是由同一組命題變項形成的極小項和極大項， 則?mi ? Mi ，?Mi ? mi 。,17,2、主范式（1）定義,主析取范式:由極小項構(gòu)成的析取范式主合取范式:由極大項構(gòu)成的合取范式例如，n=3, 命題變項為p, q, r時， (?p??q?r)?(?p?q?r) ? m1?m3 是主析取范式 (p?q??r)?(?p?q

9、??r) ? M1?M5 是主合取范式,18,（2）主范式存在定理,定理2.7 任何命題公式都存在著與之等值的主析取范式和主合取范式，并且是惟一的。,19,（3）求主析取范式的步驟,設(shè)公式A含命題變項p1,p2,…,pn(1) 求A的析取范式A?=B1? B2? … ? Bs, 其中Bj是簡單合取式 ； (2) 若某個Bj既不含pi, 又不含?pi, 則將Bj展開成 Bj ? Bj?(pi??pi) ?

10、(Bj?pi)?(Bj??pi)重復(fù)這個過程, 直到所有簡單合取式都是長度為n的極小項為止；(3) 消去重復(fù)出現(xiàn)的極小項, 即用mi代替mi?mi；(4) 將極小項按下標從小到大排列。,20,解 (1) ?(p?q)??r ? (p??q)??r p??q ? (p??q)?1 同一律 ? (p??q)?(?r?r)

11、 排中律 ? (p??q??r)?(p??q?r) 分配律 ? m4?m5 ?r ? (?p?p)?(?q?q)??r 同一律, 排中律 ? (?p??q??r)?(?p?q??r)?(p??q??r)?(p?q??r) ? m

12、0? m2? m4? m6 分配律得 ?(p?q)??r ? m0? m2? m4 ?m5 ? m6可記作 ? ?(0,2,4,5,6),例4 求?(p?q)??r 的主析取范式。,21,（4）求主合取范式的步驟,設(shè)公式A含命題變項p1,p2,…,pn(1) 求A的合取范式A?=B1?B2? … ?Bs, 其

13、中Bj是簡單析取式；(2) 若某個Bj既不含pi, 又不含?pi, 則將Bj展開成 Bj ? Bj?(pi??pi) ? (Bj?pi)?(Bj??pi)重復(fù)這個過程, 直到所有簡單析取式都是長度為n的極大項為止；(3) 消去重復(fù)出現(xiàn)的極大項, 即用Mi代替Mi?Mi；(4) 將極大項按下標從小到大排列。,22,例5 求?(p?q)??r 的主合取范式。,?(p?q)??r ? (p??r)?(?q??r

14、) p??r ? p?0??r 同一律 ? p?(q??q)??r 矛盾律 ? (p?q??r)?(p??q??r) 分配律 ? M1?M3 ?q??r ? (p??p)??q??r

15、 同一律, 矛盾律 ? (p??q??r)?(?p??q??r) 分配律 ? M3?M7得 ?(p?q)??r ? M1?M3?M7可記作 ? ?(1,3,7),23,（5）范式的快速求取方法,設(shè)公式含有n個命題變項, 則（1）長度為k的簡單合取式可展開成2n-k個極小項的析取。例如 公式含p,q,r

16、 q ? (?p ? q ? ?r) ?(?p ? q ? r) ?(p ? q ? ?r) ?(p ? q ? r) ? m2? m3? m6? m7（2）長度為k的簡單析取式可展開成2n-k個極大項的合取例如 p??r ? (p?q??r)?(p??q??r) ? M1?M3,24,實例,例6 (1) 求 A ? (?p?q)?(?p??q?r)?r的主析取

17、范式,解：用快速求法(1) ?p?q ? (?p?q??r)?(?p?q?r) ? m2? m3 ?p??q?r ? m1 r ?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r) ? m1? m3? m5? m7得 A? m1? m2? m3? m5? m7 ? ?(1,2,3,5,7),25,實例(續(xù)),(2) 求 B? ?p?(p?q??r)的主合取范式

18、解 ?p ? (?p?q?r)?(?p?q??r)?(?p??q?r)?(?p??q??r) ? M4?M5?M6?M7 p?q??r ? M1得 B? M1?M4?M5?M6?M7 ? ?(1,4,5,6,7),26,3、主析取范式的用途(1) 求公式的成真賦值和成假賦值,設(shè)公式A含n個命題變項, A的主析取范式有s個極小項, 則A有s個成真賦值, 它們是極小項下標的二進制表示, 其余2

19、n-s個賦值都是成假賦值 例如 ?(p?q)??r ? m0? m2? m4 ?m5 ? m6 成真賦值: 000,010,100,101,110; 成假賦值: 001,011,111,27,(2) 判斷公式的類型,設(shè)A含n個命題變項，則：（1）A為重言式當且僅當A的主析取范式含2n個極小項；（2）A為矛盾式當且僅當 A的主析取范式不含任何極小項，記作0； （3）A為可滿足式當且僅當A的主析取范式中至少含一個

20、極小項。,28,例7 用主析取范式判斷公式的類型:(1) A? ?(p?q)?q (2) B? p?(p?q) (3) C? (p?q)?r,解：(1) A ? ?(? p?q)?q ? ( p??q)?q ? 0 矛盾式(2) B ? ? p?(p?q) ? 1 ? m0?m1?m2?m3 重言式(3) C ? ?(p?q)?r ? (?p??q)?r ? (?p

21、??q?r)?(?p??q??r)?(?p??q?r) ?(?p?q?r)?(p??q?r)?(p?q?r) ? m0?m1?m3? m5?m7 非重言式的可滿足式,29,(3) 判斷兩個公式是否等值,例8 用主析取范式判斷下面2組公式是否等值:(1) p與(?p?q)?(p?q)解 p ? p?(?q?q) ? (p??q)?(p?q) ? m2?m3

22、(?p?q)?(p?q) ? ?(?p?q)?(p?q) ? (p??q)?(p?q) ? m2?m3故 p ? (?p?q)?(p?q),30,解： (p?q)?r ? (p?q??r)?(p?q?r) ?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r) ? m1?m3?m5? m6?m7

23、 p?(q?r) ? (p?q)?(p? r) ?(p?q??r)?(p?q?r)?(p??q?r)?(p?q?r) ? m5? m6?m7故 (p?q)?r p?(q?r),(2) (p?q)?r 與 p?(q?r),31,應(yīng)用題實例,例9 某單位要從A,B,C三人中選派若干人出國考察,

24、需滿足下述條件:(1) 若A去, 則C必須去;(2) 若B去, 則C不能去;(3) A和B必須去一人且只能去一人.問有幾種可能的選派方案?解 記p:派A去, q:派B去, r:派C去(1) p?r, (2) q??r, (3) (p??q)?(?p?q)求下式的成真賦值 A=(p?r)?(q??r)?((p??q)?(?p?q)),32,求A的主析取范式,A=(p?r)?(q??r)?((p??q

25、)?(?p?q)) ? (?p?r)?(?q??r)?((p??q)?(?p?q)) ? ((?p??q)?(?p??r)?(r??q)?(r??r)) ?((p??q)?(?p?q)) ? ((?p??q)?(p??q))?((?p??r)?(p??q)) ?((r??q)?(p??q))?((?p??q)?(?p?q)) ?((?

26、p??r)?(?p?q))?((r??q)?(?p?q)) ? (p??q?r)?(?p?q??r)成真賦值:101,010結(jié)論: 方案1 派A與C去, 方案2 派B去,33,4、主合取范式的應(yīng)用,上述應(yīng)用，對于主合取范式也都適用，另外，可以根據(jù)下列對應(yīng)關(guān)系由主析取范式求主合取范式,沒有出現(xiàn)的極小項是,其中t=2n-s,,于是,設(shè),34,例9 求A=(?p??q?r)?(?p?q?r)?(p?q?r)的主合取范式