主析取范式的求法及其應(yīng)用

1、主析取范式的求法及其應(yīng)用楊菲300203摘要： 本文綜述了求主析取范式的三種主要方法，即推演法、真值表法、構(gòu)造樹法，并從經(jīng)典例題入手分析了三種方法的應(yīng)用技巧。關(guān)鍵詞：主析取范式推演法 真值表法構(gòu)造樹法命題公式的主析取范式在數(shù)理邏輯學(xué)中具有非常重要的意義，其求解的主要目的在于使命題公式標準化，從而有利于判斷兩個命題公式是否等值，并且還可以判斷一個公式是重言式永真式還是矛盾式永假式。鑒于主析取范式求解的重要意義，本文綜述了求主析取范式的方法及各種方法的應(yīng)用技巧。1 相關(guān)概念1.1 極小項為了說明主析取范式的概念，首先介紹一下極小項的相關(guān)理論內(nèi)容。定義： n 個命題變元組成的合取式，該式中要包含所有

2、這n 個變元或它的否認，那么稱這個合取式為關(guān)于這n 個命題變元的極小項。性質(zhì)：1對于n個原子Pi,P2,Pn而言，其所有的極小項共有2n個。(2)每個小項當(dāng)其真值指派與編碼一樣時，其真值為 T,在其余2 n 1種指派情況下均 為 F。主析取范式定義：對于一個給定的命題公式，假設(shè)有一個由小項的析取組成的命題公式與其等價，那么稱該等價式為給定命題公式的主析取范式。定理 1. 對于任何一個命題公式，其主析取范式存在且唯一。證明略2 主析取范式的求法解析2.1 推演法對于給定命題公式的主析取范式可由推演法求出，其主要步驟歸納為：(1) 首先將公式化為析取范式。(2) 除去析取范式中永假的析取項，并將析

3、取式中重復(fù)出現(xiàn)的合取項和一樣變元合并。(3) 對于不是小項的合取式，補入沒有出現(xiàn)的命題變元，即通過合取添加(P P)式, 然后應(yīng)用分配律展開公式。例1.求(P Q) (Q R)的主析取范式(P Q) (Q R)(P Q) (R R) (Q R) (P P)解 (P Q R) (P Q R) (Q R P) (Q R P) miii miio mm moii moii miio miii特點：初步將命題公式化為一般析取范式后，各合式公式中缺少一到兩個命題變元即該形式已經(jīng)接近主析取范式時，可以用該法較快得解。 但是，假設(shè)命題公式中的命題變元較多且關(guān)系復(fù)雜時，化為析取范式的難度已經(jīng)很大，或者化為一般

4、析取范式后，各合式公式中缺少的命題變元較多， 使用該法會大大增加計算難度，層次較多容易出現(xiàn)錯誤，因此，此類命 題公式不宜用該法求解主析取范式。2.2 真值表法對于任意給定的命題公式，均可用真值表法求出其主析取范式：(i)根據(jù)數(shù)理邏輯運算法那么列出給定命題公式的真值表。注意：運算時要特別注意括號的嵌套，層層運算，防止出現(xiàn)邏輯錯誤2.3 將列出的真值表中最后一列即命題公式的真值為 i的對應(yīng)的極小項寫出。(3)將這些極小項用析取符號連接起來。例2.求命題公式(P Q) (R Q)的主析取范式和主合取范式。PQRP QR Q(P Q) (R Q)00000i00i0ii0i0iii0iiiiii00i

5、00i0iiiiii0iiiiiiiii因 此 所 求 的 主 析 取 范 式 是(P Q R) (P Q R)( P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R)m000m001m010m011m101m110m111主合取范式是P Q R M 100特點： 真值表法求解命題公式的主析取范式具有普遍性，無論多么復(fù)雜的命題公式都可該法易于理解，簡單方便，而且可一次求出其主析取范式和主合取范式。但是，假設(shè)命題公式的層次較多，尤其是涉及到的命題變元較多時，真值表就會非常的大，計算量也會相應(yīng)增大，容易出現(xiàn)運算錯誤。2.4 構(gòu)造樹法此法的特點就是所給出的公式容易化成合

6、取范式。假設(shè)命題公式含有較多的命題變元，且化簡后得到合取范式，其中的每一個析取式中又含有較少的命題變元，這時用推演法或者真值表法，過程就會比較復(fù)雜和混亂，容易出現(xiàn)錯誤，構(gòu)造樹法可以大大簡化這種類型的計算。 這種構(gòu)造樹方法的核心思想就是利用析取對合取的分配律。下面以一個例題來闡述一下利用構(gòu)造樹法求解主析取范式。例3某單位要從張、王、馬、牛、楊五名同志中選派一部分人外出培訓(xùn)，但是由于部門工作需要，必須滿足以下條件： 1假設(shè)張去，王也去。 2牛、楊兩同志中必有一人去。 3王、馬兩同志中去且僅去一人。 4馬、牛兩同志同去或同不去。 5假設(shè)楊去，那么張王同去。通過數(shù)理邏輯中的相關(guān)理論，分析該單位如何選派

7、他們出國。解：令P:張去，Q:王去，R:馬去，S:牛去，T:楊去那么五個條件化為命題公式分別為P Q， S T，( QR) ( Q R)，RS， T P Q ， 選 派 方 案 即 是 求PQ) ( S T) ( QR) ( Q R)(R S) (T P Q) 的 主 析取范式。( P Q) ( S T) ( QR) ( Q R) (R S) (T P Q)Q)( P Q) (S T) (Q R) ( Q R) ( R S) (R S) ( T P) ( T(P Q) ( T P) ( Q R) (Q R) ( R S) (R S) (ST) ( T Q)QQRR,SSSQTR從構(gòu)造樹上看，黑色代表非中止葉子節(jié)點，從其他中止葉子節(jié)點到根節(jié)點1的途徑分別寫出：Q T S R Q RPQ 和 TSRSR Q T P,化簡得原式的主析取范式為(PQ R S T) ( P Q R S T)。因此有兩種方案：張、王、楊去，馬、牛不去；馬、牛同去，而張、王、楊不去。特點：運用構(gòu)造樹的方法能非常方便地應(yīng)用到此類型的實際問題中，不僅能將實際問題符號化便于計算，同時又大大簡化了計算過程，抑制了容易出錯的缺點，使此類型的實際問題游刃而解。3結(jié)語本文總結(jié)了三種求主析取范式的方法，并給出了三種方法應(yīng)