離散數(shù)學(xué)第四章謂詞演算的推理理論-歸結(jié)推理系統(tǒng)

《離散數(shù)學(xué)第四章謂詞演算的推理理論-歸結(jié)推理系統(tǒng)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第四章謂詞演算的推理理論4.1謂詞演算的永真推理系統(tǒng)4.2謂詞演算的假設(shè)推理系統(tǒng)4.3謂詞演算的歸結(jié)推理系統(tǒng)4.3.1置換4.2.2歸結(jié)反演系統(tǒng)4.3.3霍恩子句邏輯程序4.3謂詞演算的歸結(jié)推理系統(tǒng)問題：從公式集S出發(fā)，證明目標公式T。在歸結(jié)系統(tǒng)中:首先否定目標公式，然后將這個公式加到公式集S中，再將該公式化成子句集，若能歸結(jié)成空子句(用□表示)，則認為證明了該公式T。引例(p45)設(shè)有語句串及它的符號表示如下：(1)無論誰能讀就有知識；?x(R(x)?L(x))(2)所有的海豚均沒有知識；?x(H(x)??L(x))(3)有些海豚有智慧。?x(H(x)?I(x))從

2、這些語句出發(fā)，證明語句：(4)一些有智慧的個體不能讀。?x(I(x)??R(x))引例(p45，提取子句)對應(yīng)語句(1)至(3)的子句集為：(1)?R(x1)?L(x1)(2)?H(x2)??L(x2)(3)H(a)(4)I(a)其中子句(3)(4)為對(3)式SKOLEM化而得，a為SKOLEM常量。要證明的定理的否定式為：??x(I(x)??R(x)),即?x(?I(x)?R(x))化為子句形式為(5)：(5)?I(x3)?R(x3)引例(p45，歸結(jié))(1)?R(x1)?L(x1)(2)?H(x2)??L(x2)(3)H(a)(4)I(a)(5)?I(x3)?R

3、(x3)(6)R(a){a/x3}(4)(5)歸結(jié)(7)L(a){a/x1}(6)(1)歸結(jié)(8)?H(a){a/x2}(7)(2)歸結(jié)(9)□(8)(3)歸結(jié)注意：歸結(jié)時使用了未討論過的置換的概念。4.3.1置換——項對變量的替換。置換準則為：(1)置換必須處處進行。(2)要求沒有變量被含有同一變量的項來代替。如表達式P(x,g(x),b)中的x不能用含有x的項f(x)來置換，即P(f(x),g(f(x)),b)是錯誤的置換。例已知表達式P(x，g(y)，b)，考察置換:P(x，g(a)，b){a/y}P(a，g(b)，b){a/x，b/y}P(f(y)，g(a)，

4、b){f(y)/x，a/y}一般地，置換可通過有序?qū)Φ募蟵t1/v1，t2/v2，…，tn/vn}來表達，其中ti/vi表示變量vi處處以項ti來代替。4.3.2歸結(jié)反演系統(tǒng)一、謂詞演算公式子句的形成二、一般歸結(jié)三、歸結(jié)反演算系統(tǒng)的應(yīng)用一、謂詞演算公式子句的形成一般步驟:(1)消去蘊含詞和等價詞(2)否定深入(3)約束變元改名(4)化為前束范式(5)消去存在量詞(按Skolem標準形)(6)消去全稱量詞(直接去掉)(7)化為合取范式(8)消去合取詞得子句集，(9)改變變量的名稱(變量符號不重復(fù)使用)例(p46-47)?xP(x)??x(A(x)??y(B(y)?W(

5、x，y)))解:(1)消去蘊含詞?xP(x)??x(?A(x)??y(B(y)?W(x，y)))(2)約束變元改名：利用改名方法對上式施行改名，以保證每一個量詞約束的變元不同名。?xP(x)??z(?A(z)??y(B(y)?W(z，y)))(3)化為前束范式?x?z?y(P(x)?(?A(z)?(B(y)?W(z，y))))(4)消去存在量詞(按Skolem標準形)原式??z(P(a)?(?A(z)?(B(f(z))?W(z，f(z)))))例(p47)(5)消去全稱量詞(直接去掉)原式?P(a)?(?A(z)?(B(f(z))?W(z，f(z))))(6)利用分配

6、律化為合取范式原式?P(a)?(?A(z)?B(f(z)))?(?A(z)?W(z，f(z)))(7)消去合取詞得子句集此時公式中只含有一些文字的析取P(a),?A(z)?B(f(z)),?A(z)?W(z，f(z))(8)改變變量的名稱：改名使得每個變量符號不出現(xiàn)在一個以上的子句中P(a),?A(z1)?B(f(z1)),?A(z2)?W(z2，f(z2))二、一般歸結(jié)只需尋找一個置換，把它們作用到母體子句上使它們含有互補的文字對(如P和?P)。例設(shè)有P(x，g(a))?Q(y)?P(z，g(a))??Q(z)可得歸結(jié)式如下：Q(y)??Q(z){z/x}Q(y)?

7、?Q(x){x/z}P(x，g(a))??P(z，g(a)){z/y}歸結(jié)反演系統(tǒng)——產(chǎn)生式系統(tǒng)子句集看作為一個綜合數(shù)據(jù)庫，而規(guī)則表就是歸結(jié)，表中的規(guī)則用到數(shù)據(jù)庫中的子句對，產(chǎn)生一個新的子句，把新子句加入數(shù)據(jù)庫中產(chǎn)生新的數(shù)據(jù)庫，形成新的歸結(jié)，重復(fù)此過程，觀察數(shù)據(jù)庫中是否含有空子句。例(p47)已知知識：(1)每個作家均寫過作品；(2)有些作家沒寫過小說；結(jié)論：有些作品不是小說。證明：令A(yù)(e)表示“e為作家”；B(e)表示“e為作品”；N(e)表示“e為小說”；W(e1，e2)表示“e1寫了e2”知識可以符號化如下：(1)?x(A(x)??y(B(y