反饋

主析取範式

主析取範式是大學數學裏一門名叫離散數學（Discrete mathematics）的課程中的內容，在離散數學的數理邏輯一節中，利用真值表和等值演算法可以化簡或推證一些命題，但是當命題的變元的數目較多時，上述方法都顯得不方便，所以需要給出把命題公式規範的方法，即把命題公式化成主合取範式和主析取範式的方法。

中文名: 主析取範式
外文名: Principal disjunctive normal form

別名: 離散數學
類型: 數理公式

主析取範式內容簡介

主析取範式 ^[1]

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

主析取範式基本內容

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

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

主析取範式析取範式與合取範式

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

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

例如，文字：p, ¬q, r, q.

簡單析取式：p, q, p∨q, p∨¬p∨r, ¬p∨q∨¬r.

簡單合取式：p, ¬r, ¬p∧r, ¬p∧q∧r, p∧q∧¬r.

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

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

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

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

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

例如，析取範式：(¬p∧q)∨r, ¬p∨q∨r, p∨¬q∨r.

合取範式：(p∨q∨r)∧(¬q∨r), ¬p∧q∧r, p∧¬q∧r.

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

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

範式的特點：

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

A→B↔¬A∨B

A←B↔(¬A∨B)∧(A∨¬B)

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

¬¬A, ¬(A∧B), ¬(A∨B)

因為：¬¬A↔A

¬(A∧B)↔¬A∨¬B

¬(A∨B)↔¬A∧¬B

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

A∧(B∨C)

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

A∨(B∧C)

因為：A∧(B∨C)↔(A∧B)∨(A∧C)

A∨(B∧C)↔(A∨B)∧(A∨C)

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

求範式的步驟：

1．消去聯結詞→、←；

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

3．利用分配律。

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

例2.7 求公式(p→q)↔r的析取範式與合取範式。

解: (1)合取範式：

(2) 析取範式

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

主析取範式詳細介紹

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

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

證明：（反證法）

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

——證畢