命題邏輯的計算機實現(xiàn)

德州學(xué)院信息管理學(xué)院 李亞男 鄭文艷

1.離散數(shù)學(xué)基礎(chǔ)

數(shù)理邏輯研究的中心問題是推導(dǎo)，而推理的前提和結(jié)論都是可以判斷真假的陳述句，即命題。因此命題是邏輯推導(dǎo)的基本單位。在命題邏輯中，對命題的成分不再細(xì)分，因而命題也是命題邏輯中的最小的研究單位。根據(jù)命題的結(jié)構(gòu)形式，可以把命題分為原子命題和復(fù)合命題。簡單的說，原子命題是能夠判斷真假的陳述句，而復(fù)合命題是由原子命題組成的。

命題公式由以下四條約定進行遞歸定義：

（1）單個命題變元是命題公式。

（2）如果A是命題公式，那么「A也是命題公式。

（3）如果A，B是命題公式，那么（A∧B），（A∨B），（A→B）和（A←→B）都是命題公式。

（4）經(jīng)過有限次的使用（1）、（2）、（3）所組成的有意義的符號串都是命題公式。

2.主要功能模塊設(shè)計與實現(xiàn)

整個功能模塊包括文本字符分析模塊，字符的集合表示模塊，集合運算模塊以及顯示模塊，此處僅以文本字符分析模塊為例進行詳細(xì)說明。

本模塊的主要功能是將欲處理的命題公式從對話框提取出來，然后放入相應(yīng)的變量里面，為第一遍掃描和第二遍掃描做準(zhǔn)備。

2.1 第一遍掃描

（1）主要目的

統(tǒng)計出所輸入的命題公式中命題變元的個數(shù)并將命題變元按順序存入容器，為字符的集合表示模塊做準(zhǔn)備，同時將操作符統(tǒng)一變成一個，為建立語法樹做準(zhǔn)備。

（2）實現(xiàn)方法

從變量的第一個字符開始，依次遍歷到字符串變量的最后一個字符。如過遇到的是字符則首先判斷該字符是否在字符容器里面，若在字符容器里面，則僅將該字符放入字符隊列里面，若不在字符容器里面則不僅將該字符放到字符隊列里面還要將該字符放到字符容器里面。如遇到的是操作符，則首先判斷是那種操作符，如果是否定詞或析取詞或合取詞，則將其直接放入字符隊列，如若是條件詞或雙條件詞，首先去掉一個或兩個字符然后再放入字符隊列。在這里字符容器主要用于存放命題變元并且統(tǒng)計命題變元的個數(shù)，字符隊列用來存放第一遍掃描的結(jié)果。因為在命題公式里面，有的操作符不只一個字符，如雙條件命題連接詞（<->）是有3個字符表示的，在這里將其后兩個字符去掉，僅留第一個字符“<”放入字符隊列。條件連接詞（->）像雙條件命題連接詞一樣，僅將“-”放入字符隊列，為第二遍掃描建語法樹提供方便。

2.2 第二遍掃描

（1）主要目的

建立語法樹，為集合運算作準(zhǔn)備。

（2）實現(xiàn)方法

準(zhǔn)備四個棧，分別是兩操作數(shù)棧和兩個運算符棧。兩個操作數(shù)棧分別記為操作數(shù)SA棧和操作數(shù)SB棧，其中操作數(shù)SB棧為輔助棧，操作數(shù)SA棧用來存放第二遍掃描后語法樹中的操作數(shù)。兩個運算符棧分別記為運算符YA棧和運算符YB棧，其中運算符YB棧為輔助棧，運算符YA棧用來存放第二遍掃描后語法樹中的運算符。

首先在運算符YA棧中放入字符串起始符號（如#），然后從字符隊列里面依次取字符，判斷是否為命題變元，若是則放入操作數(shù)SA棧，若不是字符而是運算符則首先取運算符YA棧的棧頂元素Top，令該運算符與剛?cè)〕龅臈ｍ斣豑op比較運算符的優(yōu)先級，若其優(yōu)先級大于棧頂運算符則將該運算符進運算符YA棧，若相等則運算符YA棧彈出一元素（括號匹配），若其優(yōu)先級小于棧頂運算符則彈出運算符YA棧頂元素，讓該元素進運算符YB棧。接著判斷剛彈出的運算符是幾目運算符，根據(jù)運算符的目數(shù)從操作數(shù)SA棧彈出相應(yīng)個數(shù)的操作數(shù)進操作數(shù)SB棧，這樣循環(huán)下去直到字符隊列中的字符都被遍歷一次。

在完成上述操作后，最后令操作數(shù)依次出操作數(shù)SB棧，進操作數(shù)SA棧；令運算符依次出運算符YB棧進運算符YA棧。

到此第二此掃描后建立的語法樹就存于操作數(shù)SA棧和運算符SB棧中，集合運算模塊將用到這兩個棧里的數(shù)據(jù)。

3.重要算法

整個過程涉及到三個重要算法，字符到小項下標(biāo)的編碼，整型數(shù)到字符的轉(zhuǎn)化，以及小項下標(biāo)到主析取范式的譯碼。此處僅以字符到小項下標(biāo)的編碼為例進行詳細(xì)說明。

對于給定的字符ch，首先遍歷存放命題變元的數(shù)組ch_table[]，確定ch在數(shù)組ch_table[]中的下標(biāo)ch_index（例如：ch_table[]中的命題變元為P，Q，R，T，則字符Q所對應(yīng)的下標(biāo)就是2）。建立自增量conbase=pow（2，variablenum-ch_index-1），用于下標(biāo)基數(shù)base的增加。開始基變量設(shè)為base=0-conbase，其后每循環(huán)一次基變量自增2*conbase，在每次循環(huán)中緊接base后的conbase個整數(shù)都是該字符所對應(yīng)的小項下標(biāo)。

4.總結(jié)

由于每個命題公式都有與其等價的主析取范式，主析取范式中每一個小項下標(biāo)都轉(zhuǎn)化成十進制數(shù)，并將這些十進制數(shù)放入一個集合中，這個集合就與主析取范式形成了一一對應(yīng)的關(guān)系，進而可以推出每一個命題公式都可以用一個集合來表示，一組等價的命題公式與唯一一個集合形成一一對應(yīng)的關(guān)系。

[1]徐鳳生，郭長友，劉建軍，等.離散數(shù)學(xué)及其應(yīng)用[M].北京:機械工業(yè)出版社，2006.

[2]蔣立源，康慕寧，馮博琴.編譯原理（第三版）[M].西安:西北工業(yè)大學(xué)出版社，2006.

[3]H.M.Deitel，P.J.Deitel著.施平安，譯.C++程序設(shè)計教程（第四版）[M].北京:清華大學(xué)出版社，2004.

[4]耿素云，屈婉玲，張立昂.離散數(shù)學(xué)[M].北京:清華大學(xué)出版社，2006.

[5]陳意云.編譯原理與技術(shù)（第2版）[M].合肥:中國科學(xué)技術(shù)大學(xué)出版社，2004.

[6]齊治昌，譚慶平，寧洪.軟件工程[M].北京:高等教育出版社，2004.

[7]Michael J Pont.Software Engineering with C++ and CASE Tools.Addison Wesley，2006.

[8]張宏林.Visual C++ 6.0程序設(shè)計[M].北京:人民郵電出版社，2008.