1.4.2 主析取范式和主合取范式

定義1.4.3 含有n個命題變元的合取式中，若每個命題變元與其否定不同時出現，而二者之一必出現且僅出現一次，這樣的合取式稱為極小項。

定義1.4.4 含有n個命題變元的析取式中，若每個命題變元與其否定不同時出現，而二者之一必出現且僅出現一次，這樣的析取式稱為極大項。

一般來說，極大項和極小項中的各個變元按下標由小到大的順序排列，若無下標，則按字母順序排列。例如，對于三個命題變元p、q和r，p∧q∧r、都是極小項，p∨q∨r、都是極大項，而p∧q和都不是極小項，因為它們沒有包含所有的命題變元。同理，p∨q和也不是極大項。

含n個命題變元p₁，p₂，…，p_n的極小項可表示為，極大項可表示為，其中每一個為p_i或。由n個命題變元產生的不同的極大項和極小項的個數均為2n個。每個極小項在它的2n個賦值中只有一個成真賦值，例如，含三個變元的極小項p∧q∧r的成真賦值只有111。每個極大項在它的2n個賦值中只有一個成假賦值，例如，含三個變元的極大項的成假賦值只有011。因而每個極小項可以簡記為m_i，其中，下標i為該極小項的成真賦值；每個極大項可以簡記為M_i，其中，下標i為該極大項的成假賦值。

例如，3個命題變元可形成8個極小項，如表1.4.1所示。

一般地，n個命題變元形成的極小項可表示為

3個命題變元形成的8個極大項如表1.4.2所示。

一般地，n個命題變元形成的極大項可表示為

定義1.4.5 如果含n個命題變元的命題公式的析取范式的每個合取式全是極小項，則稱該析取范式為主析取范式。

定理1.4.2 任何命題公式的主析取范式都是存在的，并且是唯一的。

證明 給定命題公式A。

1）求A的析取范式A′，A′的形式為A₁∨A₂∨…∨A_n（n≥1）。

2）若A′中的某個簡單合取式A_i不是極小項，則補入在A_i中沒有出現的變元。例如，若p_i和都不在A_i中，則將A_i展開成如下形式：。

3）重復步驟2，直到所有的簡單合取式都含有所有的命題變元或它的否定式。

4）消去重復出現的命題變項、矛盾式及重復出現的極小項。

按上述步驟求得的就是A的主析取范式。所以，任何命題公式的主析取范式都是存在的，而且是唯一的（唯一性證明略）。

?

例1.4.2 求命題公式（p∨（q∧r））→（p∧q∧r）的主析取范式。

解

在（p∨（q∧r））→（p∧q∧r）的析取范式中含有兩個合取式和，均不是極小項，因而要補入沒有出現的變元，用代換，并用分配律展開，使得每個合取式都是極小項。對同樣補入沒有出現的變元q。消去重復出現的極小項，就得到原公式的主析取范式。極小項可以用簡記m_i表示，按m_i的下標由小到大的順序排列后可用∑表示主析取范式，如

（p∨（q∧r））→（p∧q∧r）

?m₀∨m₁∨m₂∨m₇?∑（0，1，2，7）

一個命題公式的主析取范式中的每一個極小項的成真賦值就是該公式的一個成真賦值。因而根據命題公式的真值表可以立即寫出公式的主析取范式。

例1.4.3 試由p∧q∨r的真值表（表1.4.3）求它的主析取范式。

解 由表1.4.3知，公式p∧q∨r的成真賦值為001、011、101、110、111，對應的十進制數下標的極小項為m₁、m₃、m₅、m₆、m₇。因此，p∧q∨r的主析取范式為

p∧q∨r?∑（1，3，5，6，7）

利用表1.4.1，p∧q∨r的主析取范式還可寫為

設G是含n個命題變項的命題公式，當且僅當G的主析取范式含全部2n個極小項時，G為重言式；若G為矛盾式，G的主析取范式不含任何極小項，記G的主析取范式為0；當G的主析取范式中至少含有一個極小項時，G為可滿足式。

類似地可以給出主合取范式的定義。

定義1.4.6 如果含n個命題變元的命題公式的合取范式的每個析取式全是極大項，則稱該合取范式為主合取范式。

定理1.4.3 任何命題公式的主合取范式都是存在的，并且是唯一的。

證明 給定命題公式A。

1）求A的合取范式B′，B′的形式為B₁∧B₂∧…∧B_n（n≥1）。

2）若B′中的某個析取式B_i不是極大項，則補入在B_i中沒有出現的變元。例如，若p_i和都不在B_i中，則將B_i展成如下形式：。

3）重復步驟2，直到所有的簡單析取式都含有所有的命題變元或它的否定式。

4）消去重復出現的命題變項、重言式及重復出現的極大項。

按上述步驟求得的就是A的主合取范式。所以，任何命題公式的主合取范式都是存在的，而且是唯一的（唯一性證明略）。

?

例1.4.4 求命題公式（p∨（q∧r））→（p∧q∧r）的主合取范式。

解

將極大項按下標由小到大的順序排列后可用∏表示，如

（p∨（q∧r））→（p∧q∧r）?M₃∧M₄∧M₅∧M₆?∏（3，4，5，6）

一個命題公式的主合取范式中的每一個極大項的成假賦值就是該公式的一個成假賦值。因而根據命題公式的真值表可以立即寫出公式的主合取范式。又因為，公式的主析取范式中沒有出現的極小項的賦值就是公式的成假賦值，因而主合取范式中的極大項的下標碼和主析取范式中沒有出現的極小項的下標碼相同。因此，只要求出了命題公式的主析取范式，就可以立即寫出它的主合取范式，反之亦然。

例如，已知公式G的主析取范式

G?m₀∨m₁∨m₂∨m₇?∑（0，1，2，7）

其中沒有出現的極小項的下標碼3、4、5、6就是主合取范式極大項的下標碼，因此可以直接寫出主合取范式

G?M₃∧M₄∧M₅∧M₆?∏（3，4，5，6）

重言式的主合取范式不含任何極大項，用1表示重言式；矛盾式的主合取范式包含全部2n個極大項。

利用主析取范式或主合取范式可以判斷公式是否等價及求命題公式的成真賦值和成假賦值。

例1.4.5 判斷和是否等價。

解

所以，和等價。

?

例1.4.6 判斷公式是否為重言式。

解

公式是重言式，因為主析取范式包含了所有的極小項。

?

例1.4.7 設計一個集成學習系統(tǒng)，該系統(tǒng)綜合三個基學習器的分類預測（正類或負類），以投票的方式決定輸入樣本的預測類別，即在超過半數基學習器給出正類的情況下判定該樣本為正類，否則為負類。設計滿足上述條件的集成學習分類器，并嘗試以邏輯電路圖的方式畫出該分類器。

解 三個基學習器的預測類別分別為p、q、r，集成學習器的最終預測類別為A。正類為1，負類為0。

根據題意，可將真值表列出，見表1.4.4。

由上述真值表可寫出A的表達式

化簡A的表達式得

分類器的邏輯電路圖如圖1.4.1所示。

?

例1.4.8 某單位選派A、B、C三位業(yè)務骨干去進修，由于工作需要，選派要滿足如下條件。

1）若A去，則C同去。

2）若B去，則C不能去。

3）若C不去，則A或B可以去。

問可以有哪些選派方案？

解 設p表示“派A去”，q表示“派B去”，r表示“派C去”。

由已知條件可得

該公式的成真賦值就是可行的選派方案。寫出該公式的主析取范式

有3個成真賦值，所以有3種選派方案：

1）A和B不去，C去；

2）A和C不去，B去；

3）A和C去，B不去。

?