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

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

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