已經交稿----命題邏輯中范式的求解及應用(共13頁)

1、精選優(yōu)質文檔-傾情為你奉上命題邏輯中范式的求解及應用陶琦春黔南民族師范學院數學系 貴州 都勻 郵編 【摘 要】 本文主要介紹范式及主范式的求解方法，以及范式的應用 ?！娟P鍵詞】范式；極大（?。╉?； 真值表；推演法；有效性 Propositional formula's Normal Form and Its ApplicationQiChun TaoMath Department of Qiannan Normal College for Nationalities, Duyun, Guizhou, 【Abstract】 This paper mainly introduces the

2、 method on solving propositional formula's normal form and its application.【Key words】normal form; biggest or smallest item; true value form; deduction method; validity命題邏輯中的范式在離散數學的教學過程中是一個重點內容，同時也是一個難點內容，學好范式的求解方法，了解一些范式的應用人們學習數理邏輯，特別是初學者有很大的幫助。本文主要歸納范式求解的常見方法和范式的一些應用。一 范式的相關概念1.命題邏輯的基本概念定義1.1

3、1 設為命題，復合命題“非”(或的否定)稱為的否定式，記作稱作否定聯結詞。規(guī)定為真當且僅當為假。定義1.2 設、為兩個命題，復合命題“或”稱為與的析取式，記為 . 稱作析取聯結詞。設、為兩個命題，復合命題“并且”稱為與的合取式，記為.稱作合取聯結詞。 定義1.3 設是出現在公式中的全部命題變項，給各指定一個真值，稱為對的一個賦值或解釋。若指定的一組使為1，則稱這組值為的成真賦值；若指定的一組使為0，則稱這組值為的成假賦值。定義1.4 僅由有限個文字構成的析取式稱作簡單析取式。僅由有限個文字構成的合取式稱作簡單合取式。定義1.5 僅由有限個簡單合取式的析取構成的命題公式稱為析取范式。僅由有限個簡

4、單析取式的合取構成的命題公式稱為合取范式。定理1（范式存在定理）：任一命題公式都存在與之等值的析取范式與合取范式。一般地，命題公式的析（合）取范式是不惟一的。為了使命題公式的范式惟一，進一步將簡單合取式和簡單析取式規(guī)范化，定義如下。定義1.6 在含有個命題變項的簡單合取式（簡單析取式）中，若每個命題變項和它的否定式恰好出現一個且僅出現一次，而且命題變項或它的否定式按下標從小到大或按字典順序排列，稱這樣的簡單合取式（簡單析取式）為極小項（極大項）。定義1.7 所有簡單合取式（簡單析取式）都是極小項（極大項）的析取范式（合取范式）稱為主析取范式（主合取范式）。 二. 范式的求法解析 1.范式的求解

5、方法求給定公式范式的步驟為1：1.消去聯結2.用雙重否定律消去雙重否定符，用德摩根律內移否定符。3.使用分配律：求析取范式時使用對的分配律，求合取范式時使用對的分配律。例1：求下面公式的析取范式與合取范式： 解：為了清晰與無誤，利用交換律使每個簡單析取式和簡單合取式中命題變項都按字典順序出現。 （1）先求合取范式 含有3個簡單析取式的合取范式。（2）求析取范式 求析取范式和合取范式的前兩步是相同的，只有利用分配律時有所不同，因而前4步與（1）相同，接著使用對的分配律。最后兩步的結果都是析取范式。 2. 主范式的求法解析求一個公式的主合?。ㄎ鋈。┓妒娇煞譃橹苯忧蠓ê烷g接求法，下面就以主合取范式為

6、例各給出它們中的各兩種求法, 并進行理論解析。 直接求法類1.1真值表法定理22：對于任意公式，可按下述方法求出其主合取范式：（1）列出公式的真值表。（2）將真值表最后一列的真值0 的左側的二進制數對應的極大項寫出。（3）將這些極大項合取起來。證明：按上述定理的出的極大項的合取式為，往下證.設含有個命題變項且由上面方法共得出個極大項.依 的順序取公式的任一解釋I，并將其對應的二進制數轉化為十進制數后記為則 .若，則其對應的極大項必為中之一。此時由極大項的性質，的.若，則其對應的極大項不在中，由極大項性質得. 于是且必為的唯一的主合取范式。特點：利用定理2求出公式的主合取范式簡單、容易理解和掌握

7、，且可以一次既可求出其主合取范式，又可求出其主析取范式。但若已知公式層次較多時，會給列真值表帶來麻煩，增大計算量。 1.2推演法定理3：對于任意公，其主合取范式可由下面的推演法求出。設為公式的個命題變項。（1） 將公式化為任一個合取范式。（2） 檢查中每個簡單析取式是否為極大項。如果是，則留下；如果某個簡單析取式 Go 不是關于的極大項，則中肯定缺少某些命題變項 . 則 在上述推演中，反復使用分配律、交換律、結合律、冪等律、互補律、零律、同一律等算律，如 ，最終將簡單析取式 化成了若干個極大項之合取。對于（1）中其它極大項的簡單析取式，重復（2）的方法，將其化成為若干個極大項的合取式。最后將公

8、式運用某些運算律，整理為標準的主合取范式。特點：當將公式初步為合取范式后，各簡單析取式所缺命題變項較少，已比較接近主合取范式時，用此方法很簡單。若公式中命題變項較多，各命題變項復雜且包含不易化為合取范式；或者化為合取范式后，所缺命題變項較多，使用推演法很麻煩，并容易產生運算錯誤。間接求法類1.3用真值表法求的主合取范式定理42：已知公式含有個命題變項.公式是按定理2 的方法，將G 化為個極大項之析取得到的的主合取范式；則將公式中未出現的關于的極大項全合取來為公式，那么即為的主合取范式。證明：即證 ，已知 .不妨設為公式的個極大項 ，而是關于命題變項的另外個極大項。又設I 為公式G 的任一解釋（

9、因中同樣包含這n個原子）。則解釋I 必使某極大項真值為0；同時有.由極大項的性質（2）知：此解釋I 必弄真其它有極大項，故 .所以 .若T1 (G )=1 則解釋I 不滿足 中任一者；于是有由極大項的性質I必滿足中某個極大項， 故 ，所以 . 因此特點：若公式 比公式的形式更為簡捷，則先求出 ，然后列出 的真值表，將最后列公式真值中1 對應的極大項析取出來，即可得到的主合取范式。（同時也可得到 的主合取范式）如若已知 的主合取范式，則可由這個定理直接寫出的主合取范式。1.4用推演法求的主合取范式G*定理：對于任意公式，可由下述方法求得其主合取范式：（1）用推演法求出公式的主析取范式G*。（2）

10、由G*，用德摩根律求出的主合取范式（3）求的主合取范（使用德摩根律） .特點：（1）如若公式的主析取范式，運用推演法，易于求得，則使用定理5，可非常方便的求出公式的主合取范式，而且二者可兼得。（2）由該定理易見，對于任何一公式的主合取范式和主析取范式可互相轉換。我們可根據實際問題靈活選擇方法。例 ：已知公式 ，求其主合取范式解：公式 層次較少，可使用真值表法，由定理2直接求。P q r p q 成假賦值 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 0 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1

11、1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 將公式 的真值中對應的極大項合取出來，則 使用真值表法解決問題的步驟：（1） 先判斷是否可用真值表法（即所求公式層次較少時可以用；（2） 列出公式的真值表；（3） 將真值表最后一列的真值0 的左側的二進制數對應的極大項寫出；（4） 將這些極大項合取起來。使用真值表法解決問題時應該注意：一般應用在所求公式層次較少的計算，必須體現出成假賦值。例：求其主析取范式和主合取范式：解: 求主合取范式在求范式的例子中已經給出公式的析取范式，即已是一個合取范式的形式，其中短句與中僅缺一個原子，所以，可直接用推演法，與定理3求知。其中已經是極大項。

12、利用矛盾律和同一律將另兩個簡單析取式化成極大項。 于是 同樣可以求主析取范式：在求范式的例子中已經給出公式的析取范式，即在此析取范式中，第一項是最小項，另外兩個簡單范式，都不是極小項。下面先分別求出它們的派生極小項。注意，因為公式含有3個命題變項，所以極小項均由3的文字組成。 于是 使用推演法解決問題的步驟：（1） 將所求公式化為任一個合取范式；（2） 檢查中每個簡單析取式是否為極大項。如果是，則留下；如果某個簡單析取式 Go 不是關于的極大項，則中肯定缺少某些命題變項 .則 使用推演法解決問題時應該注意：將所求公式化為任一個合取范式時，這個短句所缺失的原子是否較少（所缺失的原子較少時可以用此

13、方法）。例： 已知公式求主合取范式和主析取范式。解：公式包含有6 個邏輯運算層次，3 個原子以及2 個“”符，因此，若直接使用真值表法，運算將十分煩瑣。所以，可先對公式進行初步簡化。 這已經是的主合取范式，且形式簡單明了。為要求的主析取范式，下一步求的主合取范式，再由定理5 用間接方法得之。 使用推演法求的主合取范式方法解決問題的步驟：（1）用推演法求出公式的主析取范式.（2）由，用德摩根律求出 的主析取范式. （3）求的主合取范（使用德摩根律）.使用推演法求的主合取范式方法解決問題時應該注意：針對邏輯運算層次較多的，在不易直接應用真值表法與推演法的情況下。三、范式的應用 1在電路的邏輯設計方

14、面有廣泛的應用例： 加法器的設計，有兩個位二進制數相加和為，分別寫成： 其中 是第 位、 及 (是第 位向第位的進位)的和，顯然 是、 及的函數，寫成 (、)，它與、的關系如下表： (、)0 0 0 00 0 1 10 1 0 10 1 1 01 0 0 11 0 1 01 1 0 01 1 1 1在電路邏輯設計中,我們如下對應邏輯部件:“否定”對應著“非門”,“合取”可以對應“與門”,“析取”可以對應“或門”。2. 在生活中的應用 例 ：安排課表，教語言課的教師希望將課程安排在第一或第三節(jié)；教數學課的教師希望將課程安排在第二或第三節(jié)；教原理課的教師希望將課程安排在第一或第二節(jié)。如何安排課表，

15、使得三位教師都滿意。令、 分別表示語言課排在第一、第二、第三節(jié)。、 分別表示數學課排在第一、第二、第三節(jié)。、 分別表示原理課排在第一、第二、第三節(jié)。三位教師都滿意的條件是:為真。將上式寫成析取范式( 用分配律) 得:可以取(、為T ,得到兩種排法。3.在排隊論中的應用 例： 甲、乙、丙、丁四個人出去參加比賽回來后，向外部透漏比賽結果。甲說：丙第一，乙第二；乙說：丙第二，丁第三；丙說：甲第二，丁第四。已知這三個人說的都是一句真，一句假，并且無并列情況。則四個人的實際名次如何？ 解： 用表示丙第一；用表示乙第二；用表示丙第二；用表示丁第三；用表示甲第二；用表示丁第四；則因為每個人的話中至少有一個真

16、命題，所以它們的析取為真命題，進而，這三個真命題的合取也是真命題。即是一個真命題，同時這又是一個合取范式，現將其轉化為析取范式。 因為無并列情況, 所以、均為假命題，又因為分身乏術， 所以 、 、也是假命題，而該公式又是一個真命題，所以就一定是一個真命題、即丙第一、丁第三、甲第二。這樣乙就只能是第四了。于是得出實際上的比賽名次如下： 丙第一、 甲第二、丁第三、乙第四。4. 主范式在推理有效性判斷中的應用 1 7要掌握主范式在推理有效性判斷中的應用需要預備以下知識點：定義 ：設和是兩個命題公式，當且僅當是個永真式，即 ，才說是的有效結論，或可由邏輯推出.定理6 設表示第個極小項,則 設表示第個極

17、大項,則 定理7 設 表示第個極大項,則 .定理8 設和是兩個命題公式，是永真式的充分必要條件是假定為真則能推出為真，或假定為假則能推出為假。1.利用主析取范式判斷推理是否有效命題1： 設和是兩個含有個命題變元的命題公式，是的有效結論的充分必要條件是 的主析取范式中含全部個極小項.例8: 判斷下面推理是否有效：若是奇數，則不能被2整除.若是偶數，則能被2整除.因此如果是偶數，則不是奇數.解： 設：是奇數，：能被2整除，：是偶數。推理的形式結構為 由于是含有3個命題變元的命題公式，其主析取范式中含有全部8個極小項，為重言式.故推理有效.命題2 設和是兩個含有個命題變元的命題公式，若的主析取范式中

18、含全部2個極小項,則是的有效結論.2.利用主合取范式判斷推理是否有效命題3 設和是兩命題公式，它們共有個不同的命題變元，若與 的主合取范式中的每個極大項都含有這個命題變元，則是的有效結論的充分必要條件是的主合取范式中含有的主合取范式中的所有極大項.例9 判斷下面推理是否有效： 如果小王是理科生，則他的數學成績一定很好。如果小王不是文科生，他一定是理科生。小王的數學成績不好.所以小王是文科生。解： (1) 設：小王是理科生， ：小王數學成績好， ：小王是文科生.推理的前提為，結論為. 在( 的主合取范式中含有主合取范式中所有的極大項 . 為 的有效結論，故推理有效.上述給出了利用主析取范式、主合取范式判別推理有效性的兩種方法的應用。四、總結本文通過歸納范式的求解方法及范式的應用。我們對范式有了深刻的理解，我們將求主合取范式的方法分為直接方法和間接方法兩類，并獨立給出它們分別用真值表求解是兩個定理的證明。并且利用通俗的道理,使這些形式化的數理邏輯中的范式不再枯燥,與實際生活生動的聯系在一起 。參考文獻： 1 耿素云. 屈婉玲、張立昂. 離散