主析取範式

析取範式(DNF)是邏輯公式的標準化（或規範化），它是合取子句的析取。作為規範形式，它在自動定理證明中有用。一個邏輯公式被認為是DNF的，當且僅當它是一個或多個文字的一個或多個合取的析取。同合取範式（CNF）一樣，在DNF中的命題運算元是與、或和非。非運算元只能用做文字的一部分，這意味著它只能領先於命題變數。

本節給出含n個命題變項的公式的兩種規範表示方法。

要求:了解簡單析取式、簡單合取式、析取範式、合取範式的概念深刻理解極小項、極大項的定義，名稱、下角標與成真(假)賦值的關係熟練掌握求主析取(主合取)範式的方法。會用主析取範式求公式的成真賦值、成假賦值、判斷公式的類型、判斷兩個公式是否等值。

析取與合取

定義2.2命題變項及其否定統稱作文字。僅由有限個文字構成的析取式稱為簡單析取式。

僅由有限個文字構成的合取式稱為簡單合取式。

例如，文字：

簡單析取式:

簡單合取式:

定理2.1（1）一個簡單析取式是重言式當且僅當它同時含某個命題變項及它的否定。

（2）一個簡單合取式是矛盾式當且僅當它同時含某個命題變項及它的否定。

定義2.3（1）由有限個簡單合取式構成的析取式稱為析取範式。

（2）由有限個簡單析取式構成的合取式稱為合取範式。

（3）析取範式與合取範式統稱為範式。

例如，析取範式：

合取範式:

定理2.2（1）一個析取範式是矛盾式當且僅當它的每個簡單合取式都是矛盾式。

（2）一個合取範式是重言式當且僅當它的每個簡單析取式都是重言式。

範式的特點：

（1）範式中不出現聯結詞→、←;，求範式時可消去：

（2）範式中不出現如下形式的公式：

因為

（3）在析取範式中不出現如下形式的公式：

在合取範式中不出現如下形式的公式：

因為：

定理2.3(範式存在定理)任一命題公式都存在著與之等值的析取範式與合取範式。

求範式的步驟：

1．消去聯結詞→、←；

2．利用德·摩根率將否定符號┐直接移到各個命題變元之前；

3．利用分配律。

命題公式的析取範式與合取範式都不是唯一的。

例2.7求公式的析取範式與合取範式。

解:(1)合取範式：

(2)析取範式

下面介紹命題公式的唯一規範化形式的範式：主析取範式與主合取範式。

主析取

定義：對於給定的命題公式，如果有一個僅由最小項的析取構成的等值式稱為原命題公式的主析取範式。

定理：任意含n個命題變元的非永假式，其主析取範式是惟一的。

證明：（反證法）

假設非永假式有兩個不同的主析取範式A1和A2則故A1<=>A2,由於A1和A2是兩個不同的主析取範式故，至少存在一最小項mi，是mi只存在於A1和A2兩者之一中，不妨設mi在A1中，而不再A2中。設mi在A1中有一組成真指派R，於是在R指派下，主析取範式A1為真，但在R指派情況下，主析取範式A2為假，這與相矛盾。

——證畢

求主析取與主合取

定義設A為恰含命題變元p,…,p的公式。公式A稱為A的主析（合）取範式（majordisjunctive（conjunctive）normal form），如果A是A的析（合）取範式，並且其每個合（析）取子句中p,…,p均恰出現一次。

據定義，公式的主析取範式是，而其主合取範式則應是

例求公式的主析取範式及主合取範式。

此即所求的主析取範式。另外

最後一式即為所求的主合取範式。