德州學(xué)院信息管理學(xué)院 李亞男 鄭文艷
數(shù)理邏輯研究的中心問題是推導(dǎo),而推理的前提和結(jié)論都是可以判斷真假的陳述句,即命題。因此命題是邏輯推導(dǎo)的基本單位。在命題邏輯中,對(duì)命題的成分不再細(xì)分,因而命題也是命題邏輯中的最小的研究單位。根據(jù)命題的結(jié)構(gòu)形式,可以把命題分為原子命題和復(fù)合命題。簡單的說,原子命題是能夠判斷真假的陳述句,而復(fù)合命題是由原子命題組成的。
命題公式由以下四條約定進(jìn)行遞歸定義:
(1)單個(gè)命題變?cè)敲}公式。
(2)如果A是命題公式,那么「A也是命題公式。
(3)如果A,B是命題公式,那么(A∧B),(A∨B),(A→B)和(A←→B)都是命題公式。
(4)經(jīng)過有限次的使用(1)、(2)、(3)所組成的有意義的符號(hào)串都是命題公式。
整個(gè)功能模塊包括文本字符分析模塊,字符的集合表示模塊,集合運(yùn)算模塊以及顯示模塊,此處僅以文本字符分析模塊為例進(jìn)行詳細(xì)說明。
本模塊的主要功能是將欲處理的命題公式從對(duì)話框提取出來,然后放入相應(yīng)的變量里面,為第一遍掃描和第二遍掃描做準(zhǔn)備。
(1)主要目的
統(tǒng)計(jì)出所輸入的命題公式中命題變?cè)膫€(gè)數(shù)并將命題變?cè)错樞虼嫒肴萜?,為字符的集合表示模塊做準(zhǔn)備,同時(shí)將操作符統(tǒng)一變成一個(gè),為建立語法樹做準(zhǔn)備。
(2)實(shí)現(xiàn)方法
從變量的第一個(gè)字符開始,依次遍歷到字符串變量的最后一個(gè)字符。如過遇到的是字符則首先判斷該字符是否在字符容器里面,若在字符容器里面,則僅將該字符放入字符隊(duì)列里面,若不在字符容器里面則不僅將該字符放到字符隊(duì)列里面還要將該字符放到字符容器里面。如遇到的是操作符,則首先判斷是那種操作符,如果是否定詞或析取詞或合取詞,則將其直接放入字符隊(duì)列,如若是條件詞或雙條件詞,首先去掉一個(gè)或兩個(gè)字符然后再放入字符隊(duì)列。在這里字符容器主要用于存放命題變?cè)⑶医y(tǒng)計(jì)命題變?cè)膫€(gè)數(shù),字符隊(duì)列用來存放第一遍掃描的結(jié)果。因?yàn)樵诿}公式里面,有的操作符不只一個(gè)字符,如雙條件命題連接詞(<->)是有3個(gè)字符表示的,在這里將其后兩個(gè)字符去掉,僅留第一個(gè)字符“<”放入字符隊(duì)列。條件連接詞(->)像雙條件命題連接詞一樣,僅將“-”放入字符隊(duì)列,為第二遍掃描建語法樹提供方便。
(1)主要目的
建立語法樹,為集合運(yùn)算作準(zhǔn)備。
(2)實(shí)現(xiàn)方法
準(zhǔn)備四個(gè)棧,分別是兩操作數(shù)棧和兩個(gè)運(yùn)算符棧。兩個(gè)操作數(shù)棧分別記為操作數(shù)SA棧和操作數(shù)SB棧,其中操作數(shù)SB棧為輔助棧,操作數(shù)SA棧用來存放第二遍掃描后語法樹中的操作數(shù)。兩個(gè)運(yùn)算符棧分別記為運(yùn)算符YA棧和運(yùn)算符YB棧,其中運(yùn)算符YB棧為輔助棧,運(yùn)算符YA棧用來存放第二遍掃描后語法樹中的運(yùn)算符。
首先在運(yùn)算符YA棧中放入字符串起始符號(hào)(如#),然后從字符隊(duì)列里面依次取字符,判斷是否為命題變?cè)羰莿t放入操作數(shù)SA棧,若不是字符而是運(yùn)算符則首先取運(yùn)算符YA棧的棧頂元素Top,令該運(yùn)算符與剛?cè)〕龅臈m斣豑op比較運(yùn)算符的優(yōu)先級(jí),若其優(yōu)先級(jí)大于棧頂運(yùn)算符則將該運(yùn)算符進(jìn)運(yùn)算符YA棧,若相等則運(yùn)算符YA棧彈出一元素(括號(hào)匹配),若其優(yōu)先級(jí)小于棧頂運(yùn)算符則彈出運(yùn)算符YA棧頂元素,讓該元素進(jìn)運(yùn)算符YB棧。接著判斷剛彈出的運(yùn)算符是幾目運(yùn)算符,根據(jù)運(yùn)算符的目數(shù)從操作數(shù)SA棧彈出相應(yīng)個(gè)數(shù)的操作數(shù)進(jìn)操作數(shù)SB棧,這樣循環(huán)下去直到字符隊(duì)列中的字符都被遍歷一次。
在完成上述操作后,最后令操作數(shù)依次出操作數(shù)SB棧,進(jìn)操作數(shù)SA棧;令運(yùn)算符依次出運(yùn)算符YB棧進(jìn)運(yùn)算符YA棧。
到此第二此掃描后建立的語法樹就存于操作數(shù)SA棧和運(yùn)算符SB棧中,集合運(yùn)算模塊將用到這兩個(gè)棧里的數(shù)據(jù)。
整個(gè)過程涉及到三個(gè)重要算法,字符到小項(xiàng)下標(biāo)的編碼,整型數(shù)到字符的轉(zhuǎn)化,以及小項(xiàng)下標(biāo)到主析取范式的譯碼。此處僅以字符到小項(xiàng)下標(biāo)的編碼為例進(jìn)行詳細(xì)說明。
對(duì)于給定的字符ch,首先遍歷存放命題變?cè)臄?shù)組ch_table[],確定ch在數(shù)組ch_table[]中的下標(biāo)ch_index(例如:ch_table[]中的命題變?cè)獮镻,Q,R,T,則字符Q所對(duì)應(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個(gè)整數(shù)都是該字符所對(duì)應(yīng)的小項(xiàng)下標(biāo)。
由于每個(gè)命題公式都有與其等價(jià)的主析取范式,主析取范式中每一個(gè)小項(xiàng)下標(biāo)都轉(zhuǎn)化成十進(jìn)制數(shù),并將這些十進(jìn)制數(shù)放入一個(gè)集合中,這個(gè)集合就與主析取范式形成了一一對(duì)應(yīng)的關(guān)系,進(jìn)而可以推出每一個(gè)命題公式都可以用一個(gè)集合來表示,一組等價(jià)的命題公式與唯一一個(gè)集合形成一一對(duì)應(yīng)的關(guān)系。
[1]徐鳳生,郭長友,劉建軍,等.離散數(shù)學(xué)及其應(yīng)用[M].北京:機(jī)械工業(yè)出版社,2006.
[2]蔣立源,康慕寧,馮博琴.編譯原理(第三版)[M].西安:西北工業(yè)大學(xué)出版社,2006.
[3]H.M.Deitel,P.J.Deitel著.施平安,譯.C++程序設(shè)計(jì)教程(第四版)[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è)計(jì)[M].北京:人民郵電出版社,2008.