析取范式與合取范式

一個公式在等值的意義下，可以有許多種不同的形式。反過來，幾個形式上完全不同的公式可能是同一個公式（在等值的意義下）。那么，在一個公式的諸多表示形式中，有沒有一種標準的形式呢？更進一步的說，有沒有一種標準形式是一個公式的唯一表示形式呢？1第二章命題邏輯等值演算2.2范式2命題公式的標準型：(主)析取范式與(主)合取范式以下討論標準型相關的概念：文字簡單析取式、簡單合取式

析取范式、合取范式（+極小項、極大項）

主析取范式、主合取范式3定義2.1（文字）命題變項及其否定統(tǒng)稱為文字。定義2.2（簡單析取式、簡單合取式）僅由有限個文字構成的析取式（或單個文字）稱作簡單析取式。僅由有限個文字構成的合取式（或單個文字）稱作簡單合取式。注意：單個文字既是簡單析取式，又是簡單合取式例：p，q，┐p，┐q，p∨┐q，p∨┐q∨r為簡單析取式

p，q，┐p，┐q，p∧┐q，p∧┐q∧r為簡單合取式4析取范式、合取范式定義2.3（1）由有限個簡單合取式的析取構成的析取式稱為析取范式。（2）由有限個簡單析取式的合取構成的合取式稱為合取范式。（3）析取范式和合取范式統(tǒng)稱為范式。由定義可知：若A1，A2，…，An為簡單合取式，則A1∨A2∨…∨An為析取范式

例如：p∨（p∧q）∨（p∧┐q∧r）為析取范式

若A1，A2，…，An為簡單析取式，則A1∧A2∧…∧An為合取范式

例如：p∧（p∨q）∧（p∨┐q∨r）為合取范式5析取范式、合取范式定義2.3（1）由有限個簡單合取式的析取構成的析取式稱為析取范式。（2）由有限個簡單析取式的合取構成的合取式稱為合取范式。（3）析取范式和合取范式統(tǒng)稱為范式。問1：p∨┐q∨r是什么范式？問2：p∧┐q∧r是什么范式？注意：簡單合取式和簡單析取式既是析取范式，也是合取范式。6析取范式和合取范式的性質：（定理2.2）（1）一個析取范式是矛盾式當且僅當它的每個簡單合取式都是矛盾式。（2）一個合取范式是重言式當且僅當它的每個簡單析取式都是重言式。（3）對于每個命題公式，都有與之等值的析取范式和合取范式。定理2.3（范式存在定理）

任意一個命題公式均存在一個與之等值的析取范式和合取范式。設A1，A2，…，An為簡單合取式，則A=A1∨A2∨…∨An為析取范式。設A1，A2，…，An為簡單析取式，則A=A1∧A2∧…∧An為合取范式。7范式的構造步驟（p24）：第一步：消去公式中出現(xiàn)的→，。A→B<=>┐A∨BAB<=>（A→B）∧（B→A）<=>（┐A∨B）∧（A∨┐B）第二步：用雙重否定律┐┐A<=>A消去雙重否定聯(lián)結詞，用德莫根律將┐內移，一直移到命題變項之前┐（A∨B）<=>┐A∧┐B┐（A∧B）<=>┐A∨┐B第三步：用分配律、結合律化去二重以上的刮號，成為析取范式或合取范式利用∧對∨的分配律求析取范式；利用∨對∧的分配律求合取范式；8例：求（p→q）r的析取范式和合取范式。解：（1）合取范式（p→q）r<=>（┐p∨q）r（消去→）<=>（（┐p∨q）→r）∧（r→（┐p∨q）)（消去）<=>（┐（┐p∨q）∨r）∧（┐r∨（┐p∨q））（消去→）

<=>（（p∧┐q）∨r）∧（┐p∨q∨┐r）（德莫根律將┐內移）

<=>（p∨r）∧（┐q∨r）∧（┐p∨q∨┐r）（∨對∧的分配律）

9（2）析取范式（p→q）r<=>（（p∧┐q）∨r）∧（┐p∨q∨┐r）

(∧對∨的分配律)<=>（（（p∧┐q）∨r）∧┐p）∨（（（p∧┐q）∨r）∧q）∨（（（p∧┐q）∨r）∧┐r）(∧對∨的分配律)<=>（p∧┐q∧┐p）∨（r∧┐p）∨<=>（p∧┐q∧┐r）∨（┐p∧r）∨（q∧r）（析取范式）

命題公式的析取范式和合取范式不是唯一的。（p∧┐q∧q）∨（r∧q）∨（p∧┐q∧┐r）∨（r∧┐r）（析取范式）10練習求下列公式的析取范式和合取范式。（1）（p→q）→r（2）（p→q）∧（q→r）解：（1）（p→q）→r<=>（p∧┐q）∨r（析取范式）

（p→q）→r<=>（p∨r）∧（┐q∨r）（合取范式）（2）（p→q）∧（q→r）<=>(┐p∨q)∧(┐q∨r)

（合取范式）

（p→q）∧（q→r)<=>(┐p∧┐q)∨(┐p∧r)∨(q∧r)

（析取范式）11教材內容組織結構：文字簡單析取式、簡單合取式析取范式、合取范式+極小項、極大項主析取范式、主合取范式課堂教學內容組織結構：文字簡單析取式、簡單合取式析取范式、合取范式析取范式+極小項主析取范式合取范式+極大項主合取范式主析取范式主合取范式或

主合取范式主析取范式熟練主析取范式的求解掌握主合取范式的求解熟練掌握12教材內容組織結構：文字簡單析取式、簡單合取式析取范式、合取范式+極小項、極大項主析取范式、主合取范式課堂教學內容組織結構：文字簡單析取式、簡單合取式析取范式、合取范式析取范式+極小項主析取范式合取范式+極大項主合取范式主析取范式主合取范式或

主合取范式主析取范式13

定義（極小項）：在共含有n個命題變項p1，p2，…，pn的簡單合取式中，每個命題變項pi或其否定式┐pi，均出現(xiàn)且兩者僅出現(xiàn)一個，并且按命題變項的下標排列（或字母按字典序列），這樣的簡單合取式稱為極小項。例如：對于含三個命題變項p、q、r的公式

p∧┐q∧r，┐p∧q∧┐r是極小項

p∧┐q不是極小項，其中沒出現(xiàn)r

p∧┐p∧┐r不是極小項，p，┐p同時出現(xiàn)14關于極小項的兩點說明

(1)極小項和其成真賦值一一對應

每一個極小項只有一個賦值使其為真，其余2n-1個賦值使其為假。例如對于含有三個不同命題變項p，q，r的極小項┐p∧q∧┐r。賦值010使其為真，其余23-1=7個賦值使其為假。這樣極小項與成真賦值建立了一一對應關系。15關于極小項的兩點說明

(2)極小項的簡記法

每一個極小項對應著一個二進制數(shù)（成真賦值），也對應一個十進制數(shù)（成真賦值的十進制表示）。如果極小項對應的成真賦值為a1a2a3，把其看作二進制數(shù)，化為十進制數(shù)為0k2n-1，則該極小項記作mk

。

n個命題變項的共產生2n個極小項，分別記為m0，m1，m2，…，m2n-1。例如上例中的極小項┐p∧q∧┐r應記作m2

。

16例：3個命題變項p，q，r可形成的極小項。

17定義（主析取范式）：如果析取范式中所有的簡單合取式都是極小項，則稱該析取范式為主析取范式。

例如：對于含三個命題變項p、q、r的公式

（1）p∨（┐p∧q）（2）（p∧q）∨（┐p∧r）

（3）（p∧┐q∧r）∨（┐p∧q∧┐r）顯然公式（1）和（2）不是主析取范式。而公式（3）是主析取范式。定理（主析取范式唯一存在性）：任何一個命題公式均存在唯一與之等值的主析取范式。18求給定命題公式A的主析取范式的步驟

（1）將公式A化為析取范式A’

（2）若A’的某簡單合取式B不是極小項，即B中缺命題變項pi，也不含它的否定，則對B做如下等值變換：B<=>B∧（pi∨┐pi）<=>（B∧pi）∨（B∧┐pi）

（3）用冪等律將重復的極小項消去，即mi∨mi<=>mi，

然后將各極小項按順序排列，從而得到主析取范式19例：求（p→q）r的主析取范式。解：（p→q）r（求析取范式）<=>（p∧┐q∧┐r）∨（┐p∧r）∨（q∧r）<=>m4∨（┐p∧r）∨（q∧r）┐p∧r<=>（┐p∧r）∧（q∨┐q）<=>（┐p∧q∧r）∨（┐p∧┐q∧r）<=>m1∨m3

q∧r<=>（p∨┐p）∧（q∧r）<=>（p∧q∧r）∨（┐p∧q∧r）<=>m3∨m7所以（p→q）r<=>m1∨m3∨m4∨m720練習求下列公式的主析取范式。（1）（p→q）→r（2）（p→q）∧（q→r）解：（1）（p→q）→r<=>（p∧┐q）∨r（析取范式）（2）（p→q）∧（q→r)<=>(┐p∧┐q)∨(┐p∧r)∨(q∧r)

（析取范式）解：（1）（p→q）→r<=>m1∨m3∨m4∨m5∨m7（2）（p→q）∧（q→r)<=>m0∨m1∨m3∨m7

21主析取范式的用途：1、公式的成真與成假賦值若公式A中含有n個命題變項，A的主析取范式含s（0≤s≤2n）個極小項，則A有s個成真賦值，它們是所含極小項的成真賦值，其余2n-s個賦值是成假賦值。例：（p→q）r<=>m1∨m3∨m4∨m7則（p→q）r的成真賦值為001，011，100，111成假賦值為000，010，101，110事實上┐（（p→q）r）<=>m0∨m2∨m5∨m6問┐（（p→q）r）的主析取范式是什么？22

2、判斷公式的類型設公式A中含n個命題變項，則（1）A為重言式當且僅當A的主析取范式含全部2n個極小項（2）A為矛盾式當且僅當A的主析取范式不含任何極小項，此時，記A的主析取范式為0（3）A為可滿足式當且僅當A的主析取范式中至少含一個極小項233、判斷兩個公式是否等值

兩命題公式A和B等值，當且僅當A和B具有相同的主析取范式。

244、分析和解決實際問題解：設p：派A去；q：派B去；r：派C去則由題意可得：

（p→r）∧（q→┐r）∧（┐r→（p∨q））求公式主析取范式：（p→r）∧（q→┐r）∧（┐r→（p∨q））

<=>m1∨m2∨m5例從ABC三人中挑選出1-2人出國進修，選派時滿足下列要求：（1）若A去，則C同去。（2）若B去，則C不去。（3）若C不去，則A或B可以去。問如何選派他們？25由于m1<=>┐p∧┐q∧r；m2<=>┐p∧q∧┐r；m5<=>p∧┐q∧r所以選派方案有3種：（a）C去，A，B都不去。（b）B去，A，C都不去。（c）A，C同去，B不去。26教材內容組織結構：文字簡單析取式、簡單合取式析取范式、合取范式+極小項、極大項主析取范式、主合取范式課堂教學內容組織結構：文字簡單析取式、簡單合取式析取范式、合取范式

析取范式+極小項主析取范式

合取范式+極大項主合取范式主析取范式主合取范式或

主合取范式主析取范式27極大項定義：在共含有n個命題變項p1，p2，…，pn的簡單析取式中，每個命題變項pi或其否定式┐pi，均出現(xiàn)且兩者僅出現(xiàn)一個，并且按命題變項的下標排列（或字母按字典序列），這樣的簡單析取式稱為極大項。例如：對于含三個命題變項p、q、r的公式

p∨┐q∨r，┐p∨q∨┐r是極大項

p∨┐q不是極大項，其中沒出現(xiàn)r

p∨┐p∨┐r不是極大項，p，┐p同時出現(xiàn)28對極大項的說明

例如：對于含有三個不同命題變項p，q，r的極大項┐p∨q∨┐r，賦值101使其為假，其余23-1=7個賦值使其為真。這樣極大項與成假賦值建立了一一對應關系。（2）極大項的記法：每一個極大項對應著一個二進制數(shù)（成假賦值），也對應一個十進制數(shù)（成假賦值的十進制表示）。如極大項對應的成假賦值a1a2a3，把其看作二進制數(shù)，化為十進制數(shù)為0k2n-1，則該極大項記作Mk。n個命題變項的共產生2n個極大項，分別記為M0，M1，M2，…，M2n-1。（1）極大項和其成假賦值一一對應:

每一個極大項只有一個賦值使其為假，其余2n-1個賦值使其為真。如極大項┐p∨q∨┐r記作M529例：3個命題變項p，q，r可形成的極小項和極大項。不難發(fā)現(xiàn)┐mi<=>Mi，mi<=>┐Mi30主合取范式定義：如果合取范式中所有的簡單析取式都是極大項，則稱該合取范式為主合取范式。

例如：對于含三個命題變項p、q、r的公式

p∧（┐p∨q），（p∨q）∧（┐p∨r）是合取范式但不是主合取范式。（p∨┐q∨r）∧（┐p∨q∨r）是主合取范式。定理（主合取范式唯一存在性）：任何一個命題公式均存在一個與之等值的主合取范式，而且是唯一的。31求給定命題公式A的主合取范式的步驟：

（1）將公式A化為合取范式A’

（2）若A’的某簡單析取式B不是極大項，即B中缺命題變項pi，也不含它的否定，則對B做如下等值變換：B<=>B∨（pi∧┐pi）<=>（B∨pi）∧（B∨┐pi）（3）用冪等律將重復的極大項消去，即Mi∧Mi<=>Mi，然后將各極大項按順序排列。32例：求（p→q）r的主合取范式。解：（p→q）r（求合取范式）<=>（p∨r）∧（┐q∨r）∧（┐p∨q∨┐r）<=>（p∨r）∧（┐q∨r）∧M5（p∨r）<=>（p∨r）∨（q∧┐q）<=>（p∨q∨r）∧（p∨┐q∨r）<=>M0∧M2（┐q∨r）<=>（p∧┐p）∨（┐q∨r）<=>（p∨┐q∨r）∧（┐p∨┐q∨r）<=>M2∧M6

所以（p→q）r<=>M0∧M2∧M5∧M633練習求下列公式的主合取范式。（1）（p→q）→r（2）（p→q）∧（q→r）解：（1）（p→q）→r<=>（p∨r）∧（┐q∨r）（2）（p→q）∧（q→r）<=>(┐p∨q)∧(┐q∨r)

（p→q）→r<=>M0∧M2∧M6（p→q）∧（q→r）<=>M2∧M4∧M5∧M6（p→q）→r<=>m1∨m3∨m4∨m5∨m7（p→q）∧（q→r)<=>m0∨m1∨m3∨m7

34主析取范式和主合取范式的關系定理：設mi和Mi是由n個命題變項p1，p2，…，pn形成的極小項和極大項，那么┐mi<=>Mi，mi<=>┐Mi

由公式的主析取范式求主合取范式：設公式A含n個命題變項，A的主析取范式含s個極小項，設A<=>mi1∨mi2∨…∨mis

，0≤ij≤2n-1A的主析取范式中，沒出現(xiàn)的極小項是mj1，mj2，…