[科普中國(guó)]-析取范式

簡(jiǎn)單析取式析取

析取是最常用的邏輯聯(lián)結(jié)詞之一，表示“或”的意思。析取是邏輯和數(shù)學(xué)概念中的一個(gè)二元邏輯算符。其運(yùn)算方法是：如果其兩個(gè)變量中有一個(gè)真值為“真”，其結(jié)果為“真”，兩個(gè)變量同時(shí)為假，其結(jié)果為“假”。析取在數(shù)據(jù)挖掘和數(shù)據(jù)庫(kù)等很多領(lǐng)域都有廣泛應(yīng)用。1

定義命題變項(xiàng)及其否定統(tǒng)稱作文字，僅由有限個(gè)文字構(gòu)成的析取式稱為簡(jiǎn)單析取式；僅由有限個(gè)文字構(gòu)成的合取式稱為簡(jiǎn)單合取式。2

例如， 等為一個(gè)文字構(gòu)成的簡(jiǎn)單析取式。一個(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式。

簡(jiǎn)單析取式：

簡(jiǎn)單合取式：

定理（1）一個(gè)簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變項(xiàng)及它的否定。

（2）一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變項(xiàng)及它的否定。2

析取范式定義（1）由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式稱為析取范式。

（2）由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式稱為合取范式。

（3）析取范式與合取范式統(tǒng)稱為范式**。2**

設(shè) 為簡(jiǎn)單的合取式，則 為析取范式。

例如，析取范式：

合取范式：

定理（1）一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單合取式都是矛盾式。

（2）一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析取式都是重言式。

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

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

證明：

1、由蘊(yùn)涵等值式和等價(jià)等值式可知，

因而，在等值的條件下，可消去任何公式中的聯(lián)結(jié)詞 和

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

3、利用分配律，可得

求析取范式步驟第一步：消去聯(lián)結(jié)詞和；

第二步：消去否定號(hào) ；

第三步：利用分配律。

示例求公式 的析取范式與合取范式。2

解：

（1）合取范式：

（2）析取范式

主析取范式設(shè)由n個(gè)命題變項(xiàng)構(gòu)成的析取范式中所有簡(jiǎn)單合取項(xiàng)都是極小項(xiàng)，則稱該析取范式為主析取范式。主析取范式存在且惟一。2