基本介紹
- 中文名：析取
- 外文名：Disjunctive
- 性質：一個二元邏輯算符“或”
- 領域：人工智慧、數學、數據挖掘
- 學科：離散數學、計算機科學
- 相關術語：合取
簡介,範式,有關術語的解釋,析取範式和合取範式,定義,在離散數學中有以下定理：,主析取範式和主合取範式,定義,極小項和極大項的性質,真值表技術（Technique ofTruth Table）,公式轉換法,定理,
簡介
在離散數學中，命題是一個陳述句，它或真或假，但不能既真又假。聯結詞是邏輯聯結詞或命題聯結詞的簡稱，它是自然語言中連詞的邏輯抽象。析取是最常用的邏輯聯結詞之一，表示“或”的意思。析取是邏輯和數學概念中的一個二元邏輯算符。其運算方法是：如果其兩個變數中有一個真值為“真”，其結果為“真”，兩個變數同時為假，其結果為“假”。析取在數據挖掘和資料庫等很多領域都有廣泛套用。
合取
基本符號：∧∧ 英文名：logicalconjunction 中文名：邏輯與，合取，交集，按位與，邏輯乘，與門，…命題邏輯中的二元連線詞合取，是一個兩元運算元，集合論中的交集運算元，二進制中的邏輯乘運算元，按位與（Bitwise AND），邏輯門中的“與”門（AND gate），程式語言中的&或and運算符等等。
範式
對於給定公式的判定問題，可用真值表方法加以解釋，但當公式中命題變元的數目較大時，真值表就顯得相當麻煩。每增加一個命題變元，真值表的行數就比原來增加一倍，從而使計算量增加一倍。另外，由於同一個命題公式可以有不同的表達形式，而不同的表達形式可以顯示很不同的特徵。某種特定類型的表達可以顯示出從某一角度考慮極為重要的性質。但上述的不同表達形式卻對我們研究命題演算帶來了一定的困難。因此，從理論上講，有必要對命題公式的標準形式問題進行一個深入的研究，使公式達到規範化。為此，引入範式這一概念，範式給各種千變萬化的公式提供了一個統一的表達形式，同時，範式的研究對命題演算的發展起了極其重要的作用。如在邏輯理論中判斷公式的一些性質，在論證命題的完整性時要用到範式。在工程技術的線路設計方面，自動機理論與人工智慧方面等也有極其重要的作用。
有關術語的解釋
子句
在邏輯中，子句是文字的析取，在命題邏輯中，子句通常寫做如下，這裡的符號 {\displaystyle l_{i}} 是文字:
l1∨⋯∨lnl1∨⋯∨ln 在某些情況下，子句被寫為文字的集合，所以上述子句將被寫為 l1,…,lnl1,…,ln 。從上下文中得到提示把這個集合解釋為它的元素的析取。子句可以為空；在這種情況下，它是文字的空集。空字句被指示為各種符號比如∅∅ 、⊥⊥ 或 □◻ 。空字句的真值求值總是 falsefalse。
文字 (數理邏輯)
在數理邏輯中，文字(literal)是一個原子公式(atom)或它的否定。文字可以分為兩種類型:
肯定文字就是一個原子。 否定文字是一個原子的否定。 純文字是其變數(在某個公式內)的所有出現都有相同符號的文字。
原子公式
在數理邏輯中， 原子公式或原子是沒有子公式的公式。把什麼公式當作原子依賴於所使用的邏輯。例如在命題邏輯中，唯一的原子公式是命題變數。
原子是在邏輯系統中”最小”的公式。在邏輯系統中的合式公式通常通過識別所有有效的原子公式，和給出從兩個原子公式建立公式的規則而遞歸的定義。從原子公式製作的公式是複合公式。
例如，在命題邏輯中你有如下的公式構造規則:
任何命題變數 p 是合式原子公式。 給定任何公式 A，否定 ¬A (“非 A”) 是合式公式。 給定任何兩個公式 A 和 B，合取 A ∧ B (“A 與 B”) 是合式公式。 給定任何兩個公式 A 和 B，析取 A ∨ B (“A 或 B”) 是合式公式。 給定任何兩個公式 A 和 B，蘊涵 A ⇒ B (“A 蘊涵 B “) 是合式公式。所以，我們可以建造任意的複雜的複合公式，比如，從簡單的原子公式p、q 和 r 和我們的構造規則構造出 ((p ∧ ¬(q ⇒ r)) ∨ ¬p)。
析取範式和合取範式
定義
（1）命題變元或命題變元的否定稱為文字（Character）。
（2）有限個文字的析取式稱為子句（Clouse）；有限個文字的合取式稱為短語（Phrase）。
（3）有限個短語的析取式稱為析取範式（Disjunctive Normal Form）；有限個子句的合取式稱為合取範式(ConjunctiveNormal Form)。
例
(1）P、┐P是文字、子句、短語、析取範式、合取範式。
（2）P∨Q∨┐R是子句、析取範式、合取範式。
（3）┐P∧Q∧R是短語、析取範式、合取範式。
（4）(P∧Q)∨(┐P∧Q)是析取範式。
（5）(P∨Q)∧(┐P∨Q)是合取範式。
注意：句子(P∨Q∨┐R)僅是子句、合取範式，句子(┐P∧Q∧R)僅是短語、析取範式；而對句子P∨(Q∨┐R)、┐(Q∨R)等即不是析取範式也不是合取範式，但通過將句子P∨(Q∨┐R)轉換為P∨Q∨┐R以及將句子┐(Q∨R)轉換為┐Q∧┐R後，即是析取範式和合取範式。
從上述定義和例子可以得出如下關係：
單個的文字是子句、短語、析取範式，合取範式。
析取範式、合取範式僅含聯結詞集{┐,∧,∨}。
對於任意命題公式，可以通過邏輯等價公式求出等價於它的析取範式和合取範式，其步驟如下：
（1）利用等價公式中的等價式和蘊涵式將公式中的→、«用聯結詞┐、∧、∨來取代。
（2）利用德·摩根定律將否定號┐移到各個命題變元的前端。
（3）利用結合律、分配律、吸收律、等冪律、交換律等將公式化成其等價的析取範式和合取範式。
例求公式：(P∧┐Q)«(P→R)的析取範式和合取範式。
解 (P∧┐Q)«(P→R)
= ((P∧┐Q)→(P→R))∧((P→R)→(P∧┐Q))
= (┐(P∧┐Q)∨(P→R))∧(┐(P→R)∨(P∧┐Q))
= ((┐P∨Q)∨(┐P∨R))∧(┐(┐P∨R)∨(P∧┐Q))
= (┐P∨Q∨┐P∨R)∧((P∧┐R)∨(P∧┐Q))
= (┐P∨Q∨R)∧P∧(┐R∨┐Q) 合取範式
= ((┐P∧P)∨(Q∧P)∨(R∧P))∧(┐R∨┐Q)
= (Q∧P∧┐R)∨(R∧P∧┐R)∨(Q∧P∧┐Q)∨(R∧P∧┐Q)
= (Q∧P∧┐R)∨（R∧P∧┐Q）
顯然，範式為命題公式提供了一種統一的表達形式，但這種表達形式並不惟一。
如公式：(P∨Q)∧(P∨R)
與之等價的公式：P∨(Q∧R),(P∧P)∨(Q∧R)，P∨(Q∧┐Q)∨(Q∧R),P∨(P∧R)∨(Q∧R)
等都是析取範式。這種不惟一的表達形式也給研究問題帶來了不便，下面引進更為標準的範式。
在離散數學中有以下定理：
定理的證明思路
1、化成限定性公式；
2、將否定聯結詞移到命題變數的前面；
3、消除多餘的否定聯結詞；
4、化成合取範式和析取範式。
定理1局限
1、標準化但僅僅是初步的
# 標準化的形式
# 不唯一性
2、能夠判定是否為永真或永假公式但不方便
主析取範式和主合取範式
定義
（1）設P1、P2、P3、…、Pn是n 個命題變元，一個短語或子句如果恰好包含所有這n個命題變元或命題變元的否定，且排列順序與P1、P2、P3、…、Pn的順序一致，則稱此短語或子句為關於P1、P2、P3、…、Pn的一個極小項（Minterm）或極大項（Maxterm）。
（2）由有限個極小項組成的析取範式稱為主析取範式（Principal Disjunctive Normal Form）。
（3）由有限個極大項組成的合取範式稱為主合取範式（Principal Disjunctive Normal Form）。
如果一個主析取範式不包含任何極小項，則稱該主析取範式為“空”；如果一個主合取範式不包含任何極大項，則稱該主合取範式為“空”。
定理:任何一個公式都有與之等價的主析取範式和主合取範式。
證明該定理的方法與過程，實際也就是求一個公式的主析取範式和主合取範式的方法，主要有兩種不同的方法，一是真值表技術，一是公式轉換法。
任何一個公式的主析取範式和主合取範式不僅要取決於該公式，而且取決於該公式所包含的命題變元。如公式：G1=(P→Q)∧Q G2(P,Q,R) = (P→Q)∧Q
儘管G1和G2(P,Q,R)右端的公式是一樣的，但它們求出的相應的主析取範式和主合取範式卻是不同的，前者是依賴於兩個命題變元的，後者應依賴於三個命題變元。
極小項和極大項的性質
對於兩個命題變元P，Q來說，由於每個P、Q可以取命題變元自身和其否定，所以其對應的不同的極小項和極大項分別有如下四項：
P∧Q、┐P∧Q、P∧┐Q、┐P∧┐Q；
P∨Q、┐P∨Q、P∨┐Q、┐P∨┐Q；
沒有兩個不同的極小項是等價的，且每個極小項只有一組真值指派，使該極小項的真值為真，因此可給極小項編碼，使極小項為“T”的那組真值指派為對應的極小項的編碼；如極小項┐P∧┐Q∧┐R只有在P、Q、R分別取真值0、0、0時才為真，所以有時又可用m000(m0)來表示，同理，如┐P∧Q∧┐R也可用m010(m2)來表示。
沒有兩個不同的極大項是等價的，且每個極大項只有一組真值指派，使該極大項的真值為假，因此可給極大項編碼，使極大項為“F”的那組真值指派為對應的極小項的編碼；如極小項┐P∨┐Q∨┐R只有在P、Q、R分別取真值1、1、1時才為假，所以有時又可用M111（M7）來表示，同理，如┐P∨Q∨┐R也可用M101(M5)來表示。
根據上述真值結果可知：任意兩個極小項的合取必為假，任意兩個極大項的析取必為真。
極大項的否定是極小項，極小項的否定是極大項，即
Mi∨Mj=T；mi∧mj=F（當i≠j時，i,j∈{0,1,2,3,…2n1}）
mi= ┐Mi；Mi= ┐mi(i=0,1,2,3,…2n1)
所有極小項的析取為永真公式；所有極大項的合取是永假公式。
真值表技術（Technique ofTruth Table）
根據上述對極小項的分析可知，任何一個極小項的真值解釋中僅有一種解釋使得其真值為真，而主析取範式是由一些極小項的析取組成，為此，在真值表技術中，可利用將公式的真值進行分解的方式，分解成一些子公式，該子公式僅有一種解釋使其真值為真，此時，每一個子公式都對應了一個極小項，將這些極小項的析取所得到的結果為原公式，此時原公式已表示成了一個主析取範式。
公式轉換法
除了利用真值表技術求主範式的方法以外，還可利用公式之間的等價關係來求主範式。對於任意命題公式，可以通過邏輯等價公式求出等價於它的析取範式和合取範式，其步驟如下：
（1）利用等價公式中的等價式和蘊涵式將公式中的→、«用聯結詞┐、∧、∨來取代。
（2）利用德·摩根定律將否定號┐移到各個命題變元的前端。
（3）利用結合律、分配律、吸收律、等冪律、交換律等將公式化成其等價的析取範式和合取範式。
（4）在析取範式的短語和合取範式的子句中，如同一命題變元出現多次，則將其化成只出現一次。
（5）去掉析取範式中所有永假式的短語和合取範式中所有永真式的子句，即去掉短語中含有形如P∧┐P的子公式和子句中含有形如P∨┐P的子公式。
（6）若析取範式的某一個短語中缺少該命題公式中所規定的命題變元，如缺少命題變元P，則可用公式：
(┐P∨P)∧Q=Q
將命題變元P補進去，並利用分配律展開，然後合併相同的短語，此時得到的短語將是標準的極小項；若合取範式的某一個子句中缺少該命題公式中所規定的命題變元，如缺少命題變元P，則可用公式：
(┐P∧P)∨Q=Q
將命題變元P補進去，並利用分配律展開，然後合併相同的子句，此時得到的子句將是標準的極大項。
（7）利用等冪律將相同的極小項和極大項合併，同時利用交換律進行順序調整，由此可轉換成標準的主析取範式和主合取範式。
定理
2. 設公式G，H是關於原子P1，…，Pn的兩個主析取範式。 如果G，H不完全相同，則G，H不等價。
3. 對於任意公式G，存在唯一一個與G等價的主析取範式。
4. 設命題公式G中所有不同原子為P1，…，Pn，如果G的某個析取範式G’中的每一個短語，都是關於P1，…，Pn的一個極小項，則稱G’為G的主析取範式。 恆假公式的主析取範式用0表示。
5. 對於命題公式G，都存在等價於它的主析取範式。
6. 設公式G，H是關於原子P1，…，Pn的兩個主析取範式。 如果G，H不完全相同，則G，H不等價。
7. 對於任意公式G，存在唯一一個與G等價的主析取範式。
8. 令A（a1、a2、……、an）包含有n個變數的公式，則有：
1、如果A存在與之等價的主析取範式，則必唯一；
2、如果A存在與之等價的主合取範式，則必唯一；
3、A是永真公式若且唯若與A等價的主析取範式恰有2n個極小項或沒有主合取範式；
4、A是永假公式若且唯若與A等價的主合取範式恰有2n個極大項或沒有主析取範式；
5、兩個命題公式等價若且唯若它們有相同的主合取範式或相同的主析取範式。
示例
例6 張先生手中有代號為A、B、C、D、E的五種股票，根據當前股市情況及張先生本人的經濟需求，需要
要求
（1）若A拋出，則B也拋出；
（2）B和C要留一種股票且只能留一種；
（3）C和D要么全拋，要么都不拋；
（4）D和E兩種股票中必然有一種或兩種要拋出；
（5）若E拋出，則A、B也拋出。上述五種條件全部滿足，問有幾種合理的方案供張先生選擇。
