析取範式

在離散數學中，僅由有限個文字構成的合取式稱為簡單合取式，而由有限個簡單合取式構成的析取式稱為析取範式。範式存在定理說明了它的存在性：任一命題公式都存在著與之等值的析取範式與合取範式。但它並不是惟一的。主析取範式是惟一的。

基本介紹

• 中文名：析取範式
• 外文名：disjunctive normal form
• 學科：離散數學
• 簡稱：DNF
• 相關術語：合取範式
• 套用領域：人工智慧、數據挖掘

簡單析取式

析取

析取是最常用的邏輯聯結詞之一，表示“或”的意思。析取是邏輯和數學概念中的一個二元邏輯算符。其運算方法是：如果其兩個變數中有一個真值為“真”，其結果為“真”，兩個變數同時為假，其結果為“假”。析取在數據挖掘和資料庫等很多領域都有廣泛套用。

定義

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

例如， 等為一個文字構成的簡單析取式。一個文字既是簡單析取式，又是簡單合取式。

簡單析取式：

簡單合取式：

定理

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

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

析取範式

定義

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

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

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

設 為簡單的合取式，則 為析取範式。

例如，析取範式：

合取範式：

定理

（1）一個析取範式是矛盾式若且唯若它的每個簡單合取式都是矛盾式。

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

存在性

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

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

證明：

1、由蘊涵等值式和等價等值式可知，

因而，在等值的條件下，可消去任何公式中的聯結詞 和

2、用雙重否定率和德摩根律，可得

3、利用分配律，可得

求析取範式

步驟

第一步：消去聯結詞和；

第二步：消去否定號 ；

第三步：利用分配律。

示例

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

解：

（1）合取範式：

（2）析取範式

主析取範式

設由n個命題變項構成的析取範式中所有簡單合取項都是極小項，則稱該析取範式為主析取範式。主析取範式存在且惟一。