第一章命題邏輯(2)

1、例如例如:公式公式,Apq Bpq Cpq p qA BC 0 0 111 0 1 111 1 0 000 1 1 111n個命題變元共產(chǎn)生個命題變元共產(chǎn)生 個不同賦值個不同賦值,在每個賦值在每個賦值下下,命題公式的值只有命題公式的值只有0和和1兩個值兩個值.于是于是n個命題變元的真值表共有個命題變元的真值表共有 種不同情種不同情況況. 2n22n注注：關(guān)于：關(guān)于n個命題變元個命題變元 ,可以構(gòu)造多少個可以構(gòu)造多少個真值表呢真值表呢?12,nppp許多公式有相同的真值表許多公式有相同的真值表等值式等值式n個命題變元個命題變元-形成的無窮個命題公式中不等形成的無窮個命題公式中不等值的有值的有 個

2、個22n一、等值式的概念一、等值式的概念 定義定義1.3.1 設(shè)設(shè)A, B為兩個命題公式，若為兩個命題公式，若A, B構(gòu)成的構(gòu)成的等價式等價式 為重言式，則稱為重言式，則稱A與與B是等值的，是等值的，記作記作 ABAB如上例如上例永永真真式式例如例如:公式公式,Apq Bpq Cpq p qA BC ABBCAC 0 0 111111 0 1 111111 1 0 000111 1 1 111111A與與B等值等值, ,記為記為AB 判斷等值式有如下方法：判斷等值式有如下方法： 1.真值表真值表 2.等值演算等值演算 3.范式范式 注意注意 , ，= 的區(qū)別的區(qū)別 的性質(zhì)的性質(zhì)二、用真值表判斷

3、公式的等值二、用真值表判斷公式的等值 例例1.3.1 判斷下面兩個公式是否等值：判斷下面兩個公式是否等值： 與與 pqpq 解解 :用真值表法判斷用真值表法判斷 是否為重言式是否為重言式.pqpq p q p q(p q) (p q) p q (p q) ( p q) 0 0 110111 0 1 101001 1 0 011001 1 1 001001從表中可知它是重言式，因而從表中可知它是重言式，因而 與與 等值，即等值，即pqpq pqpq 例例1.3.2 判斷下列各組公式是否等值：判斷下列各組公式是否等值： （1） 與與 （2） 與與pqrpqrpqrpqr解解: 下表為下表為 3個公

4、式的真值表個公式的真值表p q r0 0 01100 0 11110 1 01100 1 11111 0 01111 0 11111 1 00001 1 1111pqrpqrpqr 與與 等值，等值， 與與 不等值不等值pqrpqrpqrpqr三、等值演算三、等值演算 16組重要的等值式組重要的等值式,公式中出現(xiàn)的公式中出現(xiàn)的A,B,C仍然是元語言符號，仍然是元語言符號，它們代表任意的命題公式它們代表任意的命題公式1. 雙重否定律雙重否定律 AA 2. 冪等律冪等律,AAA AAA3. 交換律交換律,ABBA ABBA 4. 結(jié)合律結(jié)合律 ABCABCABCABC5. 分配律分配律 A(BC)

5、 (AB)(AC)A(BC) (AB)(AC)6. 德摩根律德摩根律()()ABABABAB 7. 吸收律吸收律 A(AB) A ， A(AB) A 8. 零律零律A1 1 ， A0 09. 同一律同一律A0 A ， A1 A 10. 排中律排中律1AA (11)矛盾律矛盾律 0AA (12)蘊涵等值式蘊涵等值式ABAB (13)等價等值式等價等值式()()ABABBA()()ABABA (16)歸謬論歸謬論 (14)假言易位假言易位 ABBA ABAB (15)等價否定等值式等價否定等值式 置換定理置換定理: : 設(shè)設(shè) 是含公式是含公式 的命題公式，的命題公式， 是用公式是用公式 置換了置換

6、了 中所有的中所有的 后得后得到的命題公式，若到的命題公式，若 則則 AA BB BA AABA例：例： (置換規(guī)則置換規(guī)則)pqr (蘊涵等值式蘊涵等值式)pqr 例例1.3.2 判斷下列各組公式是否等值：判斷下列各組公式是否等值： （1） 與與 pqrpqr解解: 下表為下表為 3個公式的真值表個公式的真值表p q r0 0 0110 0 1110 1 0110 1 1111 0 0111 0 1111 1 0001 1 111pqrpqr 與與 等值等值 pqrpqr解：解： (置換規(guī)則置換規(guī)則)pqr (蘊涵等值式蘊涵等值式)pqr pqr (蘊涵等值式蘊涵等值式)pqr (結(jié)合律結(jié)合

7、律)pqr （德摩根律）（德摩根律）pqr (蘊涵等值式蘊涵等值式)例例1.3.1 判斷下面兩個公式是否等值：判斷下面兩個公式是否等值： 與與 pqpq 解解 :用真值表法判斷用真值表法判斷 是否為重言式是否為重言式.pqpq p q p q(p q) (p q) p q (p q) ( p q) 0 0 110111 0 1 101001 1 0 011001 1 1 001001從表中可知它是重言式，因而從表中可知它是重言式，因而 與與 等值，即等值，即pqpq pqpq 例例1.3.3 用等值演算法驗證等值式：用等值演算法驗證等值式： (pq)r (pr)(qr) 證明證明: (pr)(

8、qr) (pr) (qr) (蘊涵等值式蘊涵等值式) (p q)r (分配律分配律) (p q)r (德摩根律德摩根律) (p q) r (蘊涵等值式蘊涵等值式)例例1.3.4 用等值演算判斷下列公式的類型：用等值演算判斷下列公式的類型： （1）(pq)pq （2）(p(pq)r （3）p(pq)p)q) 解解: : (1）(pq)pq 最后結(jié)果說明（最后結(jié)果說明（1）中公式是）中公式是重言式重言式. (pq)pq (pq)p)q (pq)p)q (pq)p)q (pp)(qp)q (1(qp)q (qq)p 1p 1 （2）(p(pq)r 最后結(jié)果說明最后結(jié)果說明（2）中公式是中公式是矛盾式

9、矛盾式. . 0r (ppq)r 0 (ppq)r （3）p p(p pq q)p p)q q) ) 最后結(jié)果說明最后結(jié)果說明（3）中公式不是重言式，中公式不是重言式，00，01都是成都是成假賦值假賦值. .并且也不是矛盾式，因為并且也不是矛盾式，因為1010，1111都是成真賦值都是成真賦值. . p p(pp)(qq)q) p(qpq) p(0(qp)q) p(pq)p)q) p1 1.4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 一、一、n元真值函數(shù)元真值函數(shù) 一般地，函數(shù)一般地，函數(shù)F : 0,1n 0,1稱為稱為n元真值元真值函數(shù)函數(shù) n元真值函數(shù)共有元真值函數(shù)共有 個個. .22n 每個真值函

10、數(shù)對應(yīng)無窮多個與之等值的命每個真值函數(shù)對應(yīng)無窮多個與之等值的命題公式題公式. .每個命題公式對應(yīng)唯一的與之等值的真每個命題公式對應(yīng)唯一的與之等值的真值函數(shù)值函數(shù). . 對于含有兩個命題變元的公式，理論上講可以書寫對于含有兩個命題變元的公式，理論上講可以書寫出無窮多個公式，但互不等值的公式恰有出無窮多個公式，但互不等值的公式恰有 =16個。對應(yīng)著個。對應(yīng)著16個不同的真值表（真值表共有個不同的真值表（真值表共有 4行，行，行上的每個記入值又可在行上的每個記入值又可在0、1中任取其一，因此構(gòu)中任取其一，因此構(gòu)成成 個不同的真值表），亦即對應(yīng)著個不同的真值表），亦即對應(yīng)著16個真值函個真值函數(shù)數(shù)Fi

11、（i=0，1，15），），其中其中Fi：00，01，10，110，1，如下表所示，如下表所示222222下表下表2元真值函數(shù)元真值函數(shù) 定義定義1.4.1 設(shè)設(shè)p、q為兩個為兩個命題命題，復(fù)合命題復(fù)合命題“如果如果 p 則則 q的否定的否定”稱作稱作p , q蘊含蘊含的否的否定。定。記作記作p q, , 稱為稱為蘊含蘊含的否定聯(lián)結(jié)詞的否定聯(lián)結(jié)詞. . p q為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p 為真為真q q為假為假. . 即即 p q (p q) CCCC邏輯設(shè)計中常用這些聯(lián)結(jié)詞邏輯設(shè)計中常用這些聯(lián)結(jié)詞 定義定義1.4.2 設(shè)設(shè)p、q為兩個為兩個命題命題，復(fù)合命題復(fù)合命題“ “ p , q中恰有一個成

12、立中恰有一個成立”稱作稱作p , q的的排斥排斥或或或或異或異或, , 記作記作p q, , 稱為稱為排斥或排斥或或或異異或或聯(lián)結(jié)詞聯(lián)結(jié)詞. . p q為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p , q中恰有一個為真中恰有一個為真. . 即即 p q (pq)(pq) (p q) (p q) pq(1)(2)()()(3)()()(4)0(5)0(6)1A BBAA BCAB CAB CABA AAAAA ()AC異或有以下性質(zhì)：異或有以下性質(zhì)：定義定義1.4.3 設(shè)設(shè)p、q為兩個命題，復(fù)合命題為兩個命題，復(fù)合命題“p與與q的否定式的否定式” ” 稱作稱作p ,q的的與非式與非式，記作，記作 p q .符號符

13、號 稱作稱作與非聯(lián)結(jié)詞與非聯(lián)結(jié)詞. .p q為假當(dāng)且僅為假當(dāng)且僅當(dāng)當(dāng)p與與q同時為真同時為真. . 即即 p q (pq） 定義定義1.4.4 設(shè)設(shè)p、q為兩個命題，復(fù)合命題為兩個命題，復(fù)合命題“p或或q的否定式的否定式” ” 稱作稱作p ,q的的或非式或非式，記作，記作 p q .符號符號 稱作稱作或非聯(lián)結(jié)詞或非聯(lián)結(jié)詞. .p q為真當(dāng)且僅為真當(dāng)且僅當(dāng)當(dāng)p與與q同時為假同時為假. . p q (pq） 二、聯(lián)結(jié)詞全功能集二、聯(lián)結(jié)詞全功能集 定義定義1.4.5 設(shè)設(shè)S是一個聯(lián)結(jié)詞集合，如果任何是一個聯(lián)結(jié)詞集合，如果任何n(n1)元真值函數(shù)都可以由僅含元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)中的聯(lián)結(jié)詞構(gòu)

14、成的公式表示，則稱詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞完備集是聯(lián)結(jié)詞完備集或全功能集或全功能集. . 定理定理1.4.1 S=,是聯(lián)結(jié)詞全功能集是聯(lián)結(jié)詞全功能集. . 定義定義1.4.6 對于一個聯(lián)結(jié)詞集合來說，如果集對于一個聯(lián)結(jié)詞集合來說，如果集合中的某個聯(lián)結(jié)詞可由集合中的其他聯(lián)結(jié)詞合中的某個聯(lián)結(jié)詞可由集合中的其他聯(lián)結(jié)詞來定義，則稱此聯(lián)結(jié)詞為來定義，則稱此聯(lián)結(jié)詞為冗余的聯(lián)結(jié)詞冗余的聯(lián)結(jié)詞。定義定義1.4.7 不含冗余聯(lián)結(jié)詞的全功能集稱為不含冗余聯(lián)結(jié)詞的全功能集稱為極極小全功能集小全功能集 證證: : (1)，(2)的成立是顯然的的成立是顯然的. . (1)(2)中含有冗中含有冗余的聯(lián)結(jié)詞余的聯(lián)結(jié)

15、詞(3)(4)(5)中不中不含有冗余的聯(lián)含有冗余的聯(lián)結(jié)詞結(jié)詞, , 是極小是極小全功能集全功能集推論推論 以下聯(lián)結(jié)詞集都是完備集以下聯(lián)結(jié)詞集都是完備集-全功能集全功能集： 11,S 22,S 33,S 44,S 55,S (3) 由于由于 是聯(lián)結(jié)詞完備集，因而任何真值函是聯(lián)結(jié)詞完備集，因而任何真值函數(shù)都可以由僅含數(shù)都可以由僅含S中的聯(lián)結(jié)詞的公式表示中的聯(lián)結(jié)詞的公式表示.同時對于任同時對于任意公式意公式因而任意真值函數(shù)都可以由僅含因而任意真值函數(shù)都可以由僅含 中的聯(lián)結(jié)詞的公中的聯(lián)結(jié)詞的公式表示，所以式表示，所以 是聯(lián)結(jié)詞完備集是聯(lián)結(jié)詞完備集., ,S , ,A B ABABAB 3S3S 45A

16、BABABAB 定理定理1.4.2 都是聯(lián)結(jié)詞完備集都是聯(lián)結(jié)詞完備集. . pq ( pq) ( pq) (pq)(pq) 而而p (pp） pp 證證: : 已知已知,為聯(lián)結(jié)詞完備集，因而只需證為聯(lián)結(jié)詞完備集，因而只需證明其中的每個聯(lián)結(jié)詞都可以由明其中的每個聯(lián)結(jié)詞都可以由定義即可定義即可. . ,由上可知是聯(lián)結(jié)詞完備集，類似可證是聯(lián)結(jié)由上可知是聯(lián)結(jié)詞完備集，類似可證是聯(lián)結(jié)詞完備集詞完備集 pq ( pq) (pq) pq (p p)(q q) 例例1.4.1：將公式將公式 化成僅含化成僅含 的的公式形式公式形式pq, 解：解：pqpq pq pq pqqpqpq pq pq pqpq ppq

17、ppq1.5 對偶與范式對偶與范式在在1.3節(jié)基本公式中多數(shù)是成對出現(xiàn)的節(jié)基本公式中多數(shù)是成對出現(xiàn)的, ,如如: :結(jié)合律結(jié)合律一、對偶式一、對偶式A BCAB CA BCAB C這些公式是對偶的這些公式是對偶的.定義定義1.5.1 在僅含在僅含 、 的命題公式的命題公式A中中, ,將將換成換成, , 換成換成, ,若若A中含有中含有0或或1, ,就就將將0換成換成1, ,1換成換成0, ,所得命題公式稱為所得命題公式稱為A的的對對偶式偶式, ,記為記為A*.性質(zhì)性質(zhì): : (A*)*=A.如如:(1) pq 與與 pq (2) pqr 與與 pqr (3) (pq)1 與與 (pq)0 互為

18、對偶式互為對偶式定理定理1.5.1 設(shè)設(shè)A和和A*互為對偶式互為對偶式, ,p1, p2 , pn是是出現(xiàn)在出現(xiàn)在A和和A*中的全部命題變元中的全部命題變元. .若將若將A和和A*寫成寫成n元函數(shù)形式元函數(shù)形式, ,則則同理同理*, ,ApqrAp q r *12121,nnA p ppAppp *12122,nnApppAp pp于是于是 *, ,A p q rApqr*,Apqrpqr , ,A p q rpqr *, ,Ap q rpqr 如如: :, ,A p q rpqr 推論推論: : A為重言式為重言式 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) A*為矛盾式為矛盾式. . 每種數(shù)字標準形都能提供很多信息

19、，如代每種數(shù)字標準形都能提供很多信息，如代數(shù)式的因式分解可判斷代數(shù)式的根情況數(shù)式的因式分解可判斷代數(shù)式的根情況. .邏邏輯公式在等值演算下也有標準形輯公式在等值演算下也有標準形-范式，范式，范式有兩種：析取范式和合取范式范式有兩種：析取范式和合取范式. .定理定理1.5.2 ( (對偶原理對偶原理) )設(shè)設(shè)A, ,B為兩個命題公為兩個命題公式式. .若若A B, ,則則A* B* 二二 簡單合取式和簡單析取式簡單合取式和簡單析取式定義定義1.5.2 命題變項及其否定統(tǒng)稱作命題變項及其否定統(tǒng)稱作文字文字. .僅有有限僅有有限個文字構(gòu)成的析取式稱作個文字構(gòu)成的析取式稱作簡單析取式簡單析取式. .僅

20、有有限個僅有有限個文字構(gòu)成的合取式稱作文字構(gòu)成的合取式稱作簡單合取式簡單合取式. . p , q等為一個文字構(gòu)成簡單析取式等為一個文字構(gòu)成簡單析取式 pp ，pq等為等為2個文字構(gòu)成的簡單析取式個文字構(gòu)成的簡單析取式 pqr , pqr等為等為3個文字構(gòu)成的簡單析個文字構(gòu)成的簡單析取式取式 p, q等為一個文字構(gòu)成的簡單合取式等為一個文字構(gòu)成的簡單合取式 pp，pq等為等為2個文字構(gòu)成的簡單合取式個文字構(gòu)成的簡單合取式 pqr,ppq等為等為3個文字構(gòu)成的簡單合取個文字構(gòu)成的簡單合取式式 應(yīng)該注意，一個文字既是簡單析取式，又是簡應(yīng)該注意，一個文字既是簡單析取式，又是簡單合取式單合取式. .為方

21、便起見，有時用為方便起見，有時用 表示表示s個簡單析取式或個簡單析取式或s個簡單合取式個簡單合取式. . 12,SA AA定理定理1.5.1 （1）一個簡單析取式是）一個簡單析取式是重言式重言式當(dāng)且僅當(dāng)它當(dāng)且僅當(dāng)它同時含某個命題變項及它的否定式同時含某個命題變項及它的否定式. （2）一個簡單合取式是）一個簡單合取式是矛盾式矛盾式當(dāng)且僅當(dāng)它當(dāng)且僅當(dāng)它同時含有某個命題變項及它的否定式同時含有某個命題變項及它的否定式.三三 范式范式 析取范式和合取范析取范式和合取范式式定義定義1.5.3 （1）析取范式：析取范式：由有限個簡單合取式構(gòu)成的析由有限個簡單合取式構(gòu)成的析取式取式. .（2）合取范式合取范

22、式：由有限個簡單析取式構(gòu)成的合由有限個簡單析取式構(gòu)成的合取式取式. .（3）范式范式：析取范式與合取范式的統(tǒng)稱析取范式與合取范式的統(tǒng)稱. . 設(shè)設(shè)Ai(i=1,2,s)為簡單合取式，為簡單合取式， 則則A=A1A2As為析取范式為析取范式. 例如，例如，A1=pq，A2=qr，A3=p，則由，則由A1, A2, A3構(gòu)造的析取范式為構(gòu)造的析取范式為 A=A1A2A3=(pq)(qr)p 設(shè)設(shè)Ai(i=1,2,s)為簡單析取式，則為簡單析取式，則A=A1A2As為合取范式為合取范式. . 例如，取例如，取A1=pqr，A2=pq，A3=r，則由，則由A1, A2, A3組成的合取范式為組成的合取

23、范式為 A=A1A2A3=(pqr)(pq)r 形如形如pqr的公式既是一個簡單合取的公式既是一個簡單合取式構(gòu)成的析取范式，又是由三個簡單析取式式構(gòu)成的析取范式，又是由三個簡單析取式構(gòu)成的合取范式構(gòu)成的合取范式. 類似地，形如類似地，形如pqr的公式既是含三的公式既是含三個簡單合取式的析取范式，又是含一個簡個簡單合取式的析取范式，又是含一個簡單析取式的合取范式單析取式的合取范式. 定理定理1.5.2 （1 1）一個析取范式是）一個析取范式是矛盾式矛盾式當(dāng)且僅當(dāng)它的每當(dāng)且僅當(dāng)它的每個簡單合取式都是矛盾式個簡單合取式都是矛盾式. .（2 2）一個合取范式是）一個合取范式是重言式重言式當(dāng)且僅當(dāng)它的每

24、當(dāng)且僅當(dāng)它的每個簡單析取式都是重言式個簡單析取式都是重言式. . 定理定理1.4.3 （范式存在定理）任一命題公式都（范式存在定理）任一命題公式都存在著與之等值的析取范式與合取范式存在著與之等值的析取范式與合取范式. . 證明證明 : :首先，我們觀察到在范式中不出現(xiàn)聯(lián)結(jié)詞首先，我們觀察到在范式中不出現(xiàn)聯(lián)結(jié)詞 與與 ，由蘊涵等值式與等價等值式可知，由蘊涵等值式與等價等值式可知 其次，在范式中不出現(xiàn)如下形式的公式：其次，在范式中不出現(xiàn)如下形式的公式： 對其利用雙重否定律和德摩根律，可得對其利用雙重否定律和德摩根律，可得 ,ABABABABAB 因而在等值的條件下，可消去任何公式中的聯(lián)結(jié)詞因而在等

25、值的條件下，可消去任何公式中的聯(lián)結(jié)詞 和和 . . ,AABABAAABABABAB 再次，在析取范式中不出現(xiàn)如下形式的公式：再次，在析取范式中不出現(xiàn)如下形式的公式： A(BC) 在合取范式中不出現(xiàn)如下形式的公式：在合取范式中不出現(xiàn)如下形式的公式： A(BC) 利用分配律，可得利用分配律，可得 A(BC) (AB)(AC) A(BC) (AB)(AC) 綜合上述綜合上述3步，可將任一公式化成與之等值的析取范步，可將任一公式化成與之等值的析取范式或合取范式式或合取范式. .求范式可使用如下步驟：求范式可使用如下步驟： 1.消去聯(lián)結(jié)詞消去聯(lián)結(jié)詞 , 2.否定號的消去（利用雙重否定律）或內(nèi)移否定號的

26、消去（利用雙重否定律）或內(nèi)移（利用德摩根律）（利用德摩根律）. 3.利用分配律：利用利用分配律：利用對對的分配律求析取范的分配律求析取范式，式，對對的分配律求合取范式的分配律求合取范式. 例例1.5.1 求下面公式的析取范式與合取范式求下面公式的析取范式與合取范式: : (pq)r)(pqr) (否定號內(nèi)移）否定號內(nèi)移） (pr)(qr)(pqr) （對對分配律）分配律） 合合取取范范式式解解:(1):(1)先求合取范式先求合取范式 (p q) r (p q) r (pq)r)(rpq) (消去消去 ） (pq) r)(r (pq) （消去（消去 ） (pq) r (消去消去 ） （2）求析取

27、范式求析取范式 求析取范式與求合取范式的前兩步是相求析取范式與求合取范式的前兩步是相同的，只是在利用分配律時有所不同同的，只是在利用分配律時有所不同. .因而可以用因而可以用（1）中前四步的結(jié)果，接中前四步的結(jié)果，接著進行著進行對對分配律演算分配律演算. .析取范式析取范式命題公式的析取范式是不唯一的命題公式的析取范式是不唯一的. .同樣，同樣，合取范式也是不唯一的合取范式也是不唯一的. .(pq)r)(pqr)(pqr)(pr)(qr)(pqp)(pqq)(pqr)(rp)(rq)(rr)(p q) r四四 主范式主范式: :主析取范式和主合取范式主析取范式和主合取范式 定義定義1.5.4

28、在含有在含有n個個命題變項命題變項的簡單合取式的簡單合取式（簡單析取式）中，若每個命題變項和它的否（簡單析取式）中，若每個命題變項和它的否定式不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)定式不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第一次，且第i個命題變項或它的否定式出現(xiàn)在從個命題變項或它的否定式出現(xiàn)在從左算起的第左算起的第i位上（若命題變項無角標，就按字位上（若命題變項無角標，就按字典順序排列），稱這樣的簡單合取式（簡單析典順序排列），稱這樣的簡單合取式（簡單析取式）為取式）為極小項（極大項）極小項（極大項）. . p p, ,q q 形成的極小項與極大項形成的極小項與極大項 p p, ,q q,

29、 ,r r 形成的極小項與極大項形成的極小項與極大項一般情況下一般情況下: :n個個命題變項共可產(chǎn)命題變項共可產(chǎn)生生2n個不同的個不同的極極小小項項 ( (極大項極大項).).其其中每個極小項中每個極小項( (極極大項大項) )都有且僅有都有且僅有一個成真賦值一個成真賦值( (成成假賦值假賦值).).若成真若成真賦值賦值( (成假賦值成假賦值) )所對應(yīng)的二進制所對應(yīng)的二進制數(shù)轉(zhuǎn)換為十進制數(shù)轉(zhuǎn)換為十進制數(shù)數(shù)i，就將所對應(yīng)，就將所對應(yīng)極小項極小項( (極大項極大項) )記作記作mi (Mi ). 定理定理1.5.4 設(shè)設(shè) 與與 是命題變項是命題變項 形成的極小項和極大項，則形成的極小項和極大項，

30、則 定義定義1.5.5 設(shè)由設(shè)由n個命題變項構(gòu)成的析取范式個命題變項構(gòu)成的析取范式（合取范式）中所有的簡單合取式（簡單析取（合取范式）中所有的簡單合取式（簡單析取式）都是極小項（極大項），則稱該析取范式式）都是極小項（極大項），則稱該析取范式（合取范式）（合取范式）為主析取范式（主合取范式為主析取范式（主合取范式).). imiM12,nppp,iimM,iiMm定理定理1.5.5 任何命題公式都存在著與之等值任何命題公式都存在著與之等值的的主析取范式主析取范式和和主合取范式主合取范式，并且是，并且是唯一唯一的的. .例例1.5.2 求例求例1.51中公式的主析取范式和主合中公式的主析取范式和

31、主合取范式取范式. . 解解: : （1 1）求主析取范式）求主析取范式 在例在例1.5.1中已給出的公式的析取范式，即中已給出的公式的析取范式，即 （p q） r (pqr)(pr)(qr) m1m3m4m7 在此析取范式中，簡單合取式在此析取范式中，簡單合取式pr，qr都都不是極小項不是極小項.下面分別求出它們派生的極小項下面分別求出它們派生的極小項. （pr） p（qq）r (pqr)(pqr) m1m3 qr (pp)qr (pqr）(pqr) m3m7001,011,100,111為其成真為其成真賦值賦值注意注意, ,因為因為公式含三個公式含三個命題變項，命題變項，所以極小項所以極小

32、項均由三個文均由三個文字組成字組成. . ( (2) )再求主合取范式再求主合取范式. . 由例由例1.5.1已求出公式的合取范式，即已求出公式的合取范式，即 (p q） r (pr)(qr)(pqr) M0M2M5M6 (pr) (p(qq)r) (pqr)(pqr) M0M2(qr) (pp)qr) (pqr)(pqr) M2M6 000,010,101,110為其為其成假賦值成假賦值主析取范式的用途主析取范式的用途: : 1 1求公式的成真賦值與成假賦值求公式的成真賦值與成假賦值- -真值表真值表 若公式若公式A中含中含n個個命題變項命題變項，A的主析取范式的主析取范式含含s(0s )個

33、個極小項極小項，則，則A有有s個個成真賦值成真賦值，它們是所含極小項角標的二進制表示，其余它們是所含極小項角標的二進制表示，其余 -s個賦值都是成假賦值個賦值都是成假賦值.在例在例1.4.2中，（中，（p q） r m1m3m4m7,各極小項均含三個文字，各極小項均含三個文字，因而各極小項的角標均為長為因而各極小項的角標均為長為3的二進制數(shù)，的二進制數(shù)，它們分別是它們分別是001，011，100，111，這四個賦，這四個賦值為該公式的成真賦值值為該公式的成真賦值,其余的為成假賦值其余的為成假賦值.2n2n已知命題公式已知命題公式A的主析取范式的主析取范式, ,立刻可寫出立刻可寫出A的真值表的真

34、值表, ,反之亦然反之亦然. .例例1.5.3 已知已知A=pqr的真值表如下的真值表如下, ,求求A的的主析取范式和主合取范式主析取范式和主合取范式 p q r p pq qp pq qr r 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1A m1m3m5m6m7A M0M2M42判斷公式的類型判斷公式的類型 設(shè)公式設(shè)公式A中含中含n個命題變項，容易看出：個命題變項，容易看出： （1） A為為重言式重言式當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A的主析取范式含全的主析取范式含全部部2n個極小項個極小項.

35、. （2） A為為矛盾式矛盾式當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A的主析取范式不含的主析取范式不含任何極小項任何極小項. .此時，記此時，記A的主析取范式為的主析取范式為0. . （3） A為為可滿足式可滿足式當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A的主析取范式至的主析取范式至少含一個極小項少含一個極小項. . 例例1.5.4 用公式的用公式的主析取范式主析取范式判斷公式的類型：判斷公式的類型： （1） (p q)q （2） (pq) r 解解 : :（1） (p q)q （pq）q (pq) q 0 這說明（這說明（1）中公式是矛盾式）中公式是矛盾式 (2) (pq) r 該公式是可滿足的，但不是重言式該公式是可滿足的，但不是重言

36、式. . m0m1m3m5m7 (pqr)(pqr)(pqr)(pqr)(pqr) (pq(rr)(pp)(qq) r) (pq)r (pq)r pq 的的成真賦值為成真賦值為000,001-m0,m1r 的成真賦值為的成真賦值為001,011,101,111-m1,m3,m5,m73判斷兩個命題公式是否等值判斷兩個命題公式是否等值 例例1.5.5 判斷下面兩組公式是否等值：判斷下面兩組公式是否等值： （1）(pq)r與（與（q）r設(shè)公式設(shè)公式A, ,B共含有共含有n個命題變項，按個命題變項，按n個命題變個命題變項求出與的主析取范式項求出與的主析取范式 與與 . .若若 , ,則則 ；否則，；

37、否則，與與不等值不等值. . AABB（1）兩公式都含命題變項）兩公式都含命題變項 p , q , r，因而極，因而極小項含三個文字小項含三個文字. .經(jīng)過演算得到經(jīng)過演算得到 所以所以 (p q) r 與與(q) r 不等值不等值 (pq) r m0m1m2m3m4m5m7 (p q) r m1m3m4m5m7 4應(yīng)用主析取范式分析和解決實際問題應(yīng)用主析取范式分析和解決實際問題 例例1.5.6某科研所要從某科研所要從3名科研骨干名科研骨干A, B, C中挑中挑選選1-2名出國進修名出國進修. .由于工作原因，選派時要滿由于工作原因，選派時要滿足以下條件：足以下條件： （）若（）若A去，則去，

38、則C同去同去. . （）若（）若B去，則去，則C不能去不能去. . （）若（）若C不去，則不去，則A或或B可以去可以去. . 問應(yīng)如何選派他們?nèi)?？問?yīng)如何選派他們?nèi)ィ?解解: :設(shè)設(shè)p: :派派A去去; ;q: :派派B去去; ;r: :派派C去去 . .由已知條件由已知條件可得公式可得公式 （p r）(q r)(r (pq)經(jīng)過演算可得經(jīng)過演算可得 (p r)(q r)(r (pq) m1m2m5由于由于 m1 = pqr, m2 = pqr, m5 = pqr 可知，選派方案有可知，選派方案有3種：種： （a）C去，而去，而A,B 都不去都不去. （b）B去，而去，而A,C 都不去都不去.

39、 （c）A,C去，而去，而B 不去不去. 幾點注意幾點注意 1. 由公式的主析取范式求主合取范式由公式的主析取范式求主合取范式 設(shè)公式設(shè)公式A含含n個個命題變項命題變項. A的的主析取范式主析取范式 S (0S )個個極小項極小項，即，即2n12;021,1,2,sniiijAmmmijs沒出現(xiàn)的極小項沒出現(xiàn)的極小項為為 , 它們的它們的角標的二進制表示為角標的二進制表示為 的成真賦值，因而的成真賦值，因而 的主析的主析取范式為取范式為 122,nsjjjmmm122nsjjjAmmmAA于是于是 由公式的主析取范式，即可求出它的主合取范式由公式的主析取范式，即可求出它的主合取范式122122122nsnsnsjjjjjjjjjAAmmmmmmMMM 2重言式與矛盾式的主合取范式重言式與矛盾式的主合取范式 矛盾式矛盾式無成真賦值，因而矛盾式的無成真賦值，因而矛盾式的主合取范主合取范式式含含2n（n為公式中命題變項個數(shù)）個為公式中命題變項個數(shù)）個極大項極大項. . 重言式無成假賦值，因而主合取范式不含任重言式