利用二叉樹刻畫邏輯表達的自動推導

利用二叉樹刻畫邏輯表達的自動推導

0叉樹模型中的自動推導二叉樹t是一個有限的集合，由t（1）和t（2）組成，這是由一個或兩個不相交的二叉樹組成的。二叉樹的根可以是空的左子樹，或空的右子樹，或左或右子樹。本文主要以離散數(shù)學中命題邏輯的等效計算為例，探討了二叉樹如何實現(xiàn)邏輯表達方法的自動推理。這種方法也適用于數(shù)學中通用表的自動推理。命題邏輯的等值演算是根據(jù)已知的等值式推演出另外一些等值式的過程,主要運用于求析取范式、合取范式中.而命題邏輯表達式初始狀態(tài)是一個字符串,必須將其分解為含特定意義的邏輯結(jié)構(gòu),并選取合適的存儲結(jié)構(gòu),進而在這種結(jié)構(gòu)上設(shè)計它的基本運算,而其他復雜的等值演算就可利用這些基本運算來實現(xiàn).1叉樹的定義二叉樹一般記作:T=(Tl,Tr),其中,T是二叉樹(Tl,Tr)的名稱,Tl和Tr分別是二叉樹T的左右子樹,可以是單個元素,也可以是二叉樹,也可以為空.習慣上,用大寫字母表示二叉樹的名稱,用小寫字母表示原子,顯然,二叉樹的定義是一個遞歸的定義.下面列舉一些二叉樹的例子.(1)邏輯表達式A=?a→b的二叉樹表示方法為圖1(a);(2)邏輯表達式B=a∧b∧c的二叉樹表示方法為圖1(b);(3)邏輯表達式C=?A?B=?(?a→b)?(a∧b∧c)的二叉樹表示方法為圖1(c);(4)邏輯表達式D=(?a→b)∨b∨(a∧c)的二叉樹表示方法為圖1(d).從上面的定義和例子可以看出能夠很方便地將邏輯表達式轉(zhuǎn)換成二叉樹,只要遞歸地按照運算符優(yōu)先級將邏輯表達式分為左右兩部分,再分別對每一部分分別繼續(xù)劃分,直到劃分為單個原子即可.2運算符和原子控制因為二叉樹是一種遞歸結(jié)構(gòu),它的數(shù)據(jù)元素可以還是二叉樹,因此難以用順序存儲結(jié)構(gòu)表示,通常采用鏈式存儲結(jié)構(gòu),每一個元素可以用一個節(jié)點表示.由于二叉樹的數(shù)據(jù)元素可以是原子、運算符和二叉樹,所以需要兩種結(jié)構(gòu)的結(jié)點:一種是分支結(jié)點,用來表示運算符,一種是葉子結(jié)點,用來表示原子,它們的結(jié)構(gòu)如圖2.因為可以用是否是葉子結(jié)點來區(qū)分運算符結(jié)點和原子結(jié)點,這里就沒有設(shè)置專門的標志變量.上面抽象定義的二叉樹A,B,C,D的存儲結(jié)構(gòu)如圖3.可以看出,這種存儲結(jié)構(gòu)是可以實現(xiàn)結(jié)構(gòu)的共享,即可以節(jié)省內(nèi)存空間,也可以在某些時候操作更加方便,在圖3中二叉樹C共享了二叉樹A和B.要使用結(jié)構(gòu)共享,必需保證共享的部分在各個二叉樹中保持一致性,如果一個二叉樹對共享部分需要修改,而另一個二叉樹要保持共享部分不變,就會導致錯誤.因此,如果應用中能夠確定某個子二叉樹是靜態(tài)的,不需要改變,就可以對它進行結(jié)構(gòu)共享.在下面的命題邏輯表達式的推導過程中,二叉樹是不斷變化的,因此不能夠使用結(jié)構(gòu)共享,而是采用將公共的結(jié)構(gòu)復制的方法,如二叉樹D沒有共享二叉樹A,而是將A的結(jié)構(gòu)復制一份,這樣可以對A和D任意修改而不會互相影響.說明:命題邏輯的聯(lián)結(jié)詞運算符只有一個否定運算符(?)是一元運算符,其他的都是二元運算符,為了簡化存儲結(jié)構(gòu),整個存儲結(jié)構(gòu)按二元運算符結(jié)構(gòu)設(shè)計的,對于惟一的一元運算符?,采用將運算符節(jié)點的左子樹置為空,右子樹為操作數(shù)的方式表示.3使用二叉樹實現(xiàn)搜索邏輯公式的基本計算有了上面定義的存儲結(jié)構(gòu),我們就可以實現(xiàn)命題邏輯中其他基本運算,下面介紹一些常用命題邏輯基本運算在這種存儲結(jié)構(gòu)上的實現(xiàn)方法.3.1叉樹t的運算函數(shù)原型:Value(T);初始條件:二叉樹T存在.運算結(jié)果:將二叉樹中的原子元素賦值后,計算二叉樹T存儲的邏輯表達式的值,可按深度優(yōu)先順序遞歸地實現(xiàn).3.2w&t函數(shù)原型:AbsorptionLaw(&T);初始條件:二叉樹T存在.運算結(jié)果:實現(xiàn)邏輯運算的吸收律,對應公式A∨A?A,A∧A?A.3.3tionolt函數(shù)原型:ConvertBiconditional(&T);初始條件:二叉樹T存在.運算結(jié)果:消去雙條件聯(lián)接詞?,對應公式A?B?(A→B)∧(B→A).3.4tionolt函數(shù)原型:ConvertConditional(&T);初始條件:二叉樹T存在.運算結(jié)果:消去條件聯(lián)接詞→,對應公式A→B??(A∨B).3.5叉樹t存在.運算函數(shù)原型:NegationEmbed(&T);初始條件:二叉樹T存在.運算結(jié)果:否定深入運算,對應公式?(A∨B)?(?A∧?B),?(A∧B)?(?A∨?B),要求表達式中無→,?連接詞的條件下執(zhí)行.3.6初始條件及運算結(jié)果函數(shù)原型:DistributiveLaw(&T);初始條件:二叉樹T存在.運算結(jié)果:分配律運算,對應公式A∨(B∧C)?(A∨B)∧(A∨C),A∧(B∨C)?(A∧B)∨(A∧C).4消去雙條件粘連詞的運算下面以消去雙條件聯(lián)接詞運算為例子,詳細介紹它的算法實現(xiàn),此運算用到復制二叉樹運算.算法的思想就是從二叉樹的根開始,遞歸遍歷整個二叉樹,每發(fā)現(xiàn)一個雙條件聯(lián)接詞,就將它消去,整個算法分兩個函數(shù),函數(shù)ConvertCurrentBiconditional負責消去當前的一個雙條件聯(lián)接詞操作,而函數(shù)ConvertBiconditional負責遞歸遍歷整個二叉樹,每發(fā)現(xiàn)一個雙條件聯(lián)接詞就調(diào)用函數(shù)ConvertCurrentBiconditional來消去這個雙條件聯(lián)接詞.為了更加清楚的描述這個算法,將消去雙條件聯(lián)接詞運算的圖示結(jié)點編號如下:5生成的邏輯程式有了上面的基本運算,就很容易實現(xiàn)其他復雜的邏輯運算,例如求表達式的合取范式,它實際就是逐步對表達式進行消去雙