【文章內(nèi)容簡(jiǎn)介】 6n7n8紅色代價(jià) ： 5藍(lán)色 代價(jià) ： 6n0(4)n4(1)n5(12)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(45)2/27/2023 64人工智能講義n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2/27/2023 65人工智能講義目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2/27/2023 66人工智能講義目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8初始節(jié)點(diǎn)可解n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2/27/2023 67人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 68人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 69人工智能講義概述? 歸結(jié)原理 由 1965年提出。– 與演繹法完全不同，新的邏輯演算算法。– 一階邏輯中，至今為止的最有效的半可判定的算法。即，一階邏輯中任意恒真公式，使用歸結(jié)原理，總可以在有限步內(nèi)給以判定。 – 語義網(wǎng)絡(luò)、框架表示、產(chǎn)生式規(guī)則等等都是以推理方法為前提的。即，有了規(guī)則已知條件，順藤摸瓜找到結(jié)果。 而歸結(jié)方法是自動(dòng)推理、自動(dòng)推導(dǎo)證明用的。（ “數(shù)學(xué)定理機(jī)器證明 ”）? 本課程只討論一階謂詞邏輯描述下的歸結(jié)推理方法，不涉及高階謂詞邏輯問題 。 2/27/2023 70人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 71人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 72人工智能講義命題邏輯的歸結(jié)法? 基本單元：簡(jiǎn)單命題（陳述句）例： 命題： A A A3 和 B求證： A1ΛA 2ΛA 3成立，則 B成立，即： A1ΛA 2ΛA 3 → B反證法：證明 A1ΛA 2ΛA 3Λ ～ B 是矛盾式 （永假式） 2/27/2023 73人工智能講義命題邏輯的歸結(jié)法? 建立子句集– 合取范式：命題、命題和的與， 如：PΛ （ P∨Q ） Λ （ ～ P∨Q ）子句集 S：合取范式形式下的子命題（元素）的集合例：命題公式： PΛ （ P∨Q ） Λ （ ～ P∨Q ） 子句集 S： S = {P, P∨Q, ～ P∨Q} 2/27/2023 74人工智能講義命題邏輯的歸結(jié)法? 歸結(jié)式消除互補(bǔ)對(duì)，求新子句 → 得到歸結(jié)式 。如子句： C1= C1′ ∨L, C 2 = C2′ ∨ 歸結(jié)式： R(C1, C2) = C1′ ∨ C2′ 注意： C1ΛC 2 → R(C1, C2) ， 反之 不一定不一定成立。 假言推理 : 由合適公式 W1和 W1 → W2產(chǎn)生合適公式 W2 ,如何用歸結(jié)法證明 ?2/27/2023 75人工智能講義命題邏輯的歸結(jié)法? 歸結(jié)過程 – 對(duì)結(jié)論作否定 ,并加入前提中– 將命題寫成合取范式– 求出子句集– 對(duì)子句集使用歸結(jié)推理規(guī)則– 歸結(jié)式作為新子句參加歸結(jié)– 歸結(jié)式為空子句 □ ， S是不可滿足的（矛盾），原命題成立。? （證明完畢）? 謂詞的歸結(jié)：除了有量詞和函數(shù)以外，其余和命題歸結(jié)過程一樣。 2/27/2023 76人工智能講義命題邏輯的歸結(jié)法? 例 證明先將化為合取范式 建立子句集 S=對(duì) S做歸結(jié) P NIL2/27/2023 77人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 78人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 79人工智能講義子句形 引用 Herbrand定理，以說明歸結(jié)原理的意義及一個(gè)原理形成的根基與背景? SKOLEM標(biāo)準(zhǔn)形–前束范式 ：把所有的量詞都提到前面去，然后消掉所有量詞。定義 ：說公式 A是一個(gè)前束范式，如果 A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。 即 (Q1x1)…(Q nxn)M(x1, …, x n),其中Qixi為存在量詞或全稱量詞 , M(x1, …, x n) 為合取范式 (由一些子句的合取組成 )。2/27/2023 80人工智能講義子句形 ( Skolem 標(biāo)準(zhǔn)形 )? ? ? ? ? ? ? ? ? ? ? ? ?–量詞消去原則：消去存在量詞 “ ?” ，略去全程量詞 “ ?”。 注意： 左邊有全稱量詞的存在量詞，消去時(shí)該變量改寫成為全稱量詞的函數(shù)(Skloem函數(shù) )；如沒有，改寫成為常量。 例子：見《人工智能及其應(yīng)用》 P752/27/2023 81人工智能講義子句形 ( Skolem 標(biāo)準(zhǔn)形 )? ? ? ? ? ? ? ? ? ? ? ? ?–定理 ：謂詞邏輯的任意公式都可以化為與之等價(jià)的前束范式，但其前束范式不唯一。 –SKOLEM標(biāo)準(zhǔn)形定義：消去量詞后的謂詞公式。注意 ：謂詞公式 G的 SKOLEM標(biāo)準(zhǔn)形同 G并不等值 。 2/27/2023 82人工智能講義子句形 ( Skolem 標(biāo)準(zhǔn)形 )? ? ? ? ? ? ? ? ? ? ? ? ?–例 :G=(?x)(?y)(?z)(?u)P(x,y,z,u)Skolem 標(biāo)準(zhǔn)形為： (?y)(?z)P(a,y,z,f(y,z))其中， x=a(常量 )， u=f() 2/27/2023 83人工智能講義子句形? 子句與子句集–文字：不含任何連接詞的謂詞公式。–子句：一些文字的析?。ㄖ^詞的和）。–子句集 S的求?。? G → SKOLEM 標(biāo)準(zhǔn)形 → 消去存在變量 → 以 “ ， ” 取代 “ Λ ” ，并表示為集合形式 。2/27/2023 84人工智能講義子句形? G是不可滿足的 = S是不可滿足的–G與 S不等價(jià)，但在不可滿足的意義下是一致的。 –定理：若 G是給定的公式，而 S是相應(yīng)的子句集，則 G是不可滿足的 = S是不可滿足的。 注意 ： G真不一定 S真，而 S真必有 G真。即： S = G2/27/2023 85人工智能講義子句形? G = G1Λ G 2Λ G 3Λ …Λ G n 的子句形– G的子句集可以分解成幾個(gè)單獨(dú)處理。 –有 SG = S1 U S2 U S3 U …U S n則 SG 與 S1 U S2 U S3 U …U Sn在不可滿足的意義上是一致的。即 SG 不可滿足 = S1 U S2 U S3 U …U Sn不可滿足2/27/2023 86人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 87人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 88人工智能講義Herbrand定理?問題：一階邏輯公式的永真性（永假性）的判定是否能在有限步內(nèi)完成 ？2/27/2023 89人工智能講義Herbrand定理? 1936年圖靈 (Turing)和邱吉 (Church)互相獨(dú)立地證明了： “ 沒有一般的方法使得在有限步內(nèi)判定一階邏輯的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步內(nèi)判定它是永真（或永假）。對(duì)于非永真（或永假）的公式就不一定能在有限步內(nèi)得到結(jié)論。判定的過程將可能是不停止的。 ” 2/27/2023 90人工智能講義Herbrand定理? Herbrand的思想–定義：公式 G永真：對(duì)于 G的所有解釋， G都為真。–思想：尋找一個(gè)已給的公式是真的解釋。然而，如果所給定的公式的確是永假的，就沒有這樣的解釋存在，并且算法在有限步內(nèi)停止。 2/27/2023 91人工智能講義Herbrand定理? H域? H解釋? 語義樹? 結(jié)論： Herbrand定理2/27/2023 92人工智能講義Herbrand定理? H域? H解釋? 語義樹? 結(jié)論： Herbrand定理2/27/2023 93人工智能講義Herbrand定理 （ H域）? 基本方法：– 因?yàn)?量詞是任意的，所討論的個(gè)體變量域 D是任意的，所以解釋的個(gè)數(shù)是無限、不可數(shù)的 。– 簡(jiǎn)化討論域。建立一個(gè)比較簡(jiǎn)單、特殊的域，使得只要在這個(gè)論域上，該公式是不可滿足的。– 此域稱為 H域： H0為 G中所出現(xiàn)的常量的集合，若 G中沒有常量，就任取常量 ， H0={a}。 規(guī)定 為 H域 ※ 例題請(qǐng)參考教科書 P272/27/2023 94人工智能講義H域舉例? 例 1 S={P(a), ～ P(x)∨P(f(x)) }依定義有H0={a}H1={a} U{f(a)}={a,f(a)}H2={a,f(a)}U{f(a),f(f(a))}={a,f(a),f(f(a))}…H∞ = {a,f(a),f(f(a))， …}2/27/2023 95人工智能講義Herbrand定理 （ H域）? 幾個(gè)基本概念– f（ t1, t2, …t n） ： f為子句集 S中的所有函數(shù)變量。 t1, t2, …t n為 S的 H域的元素。通過它們來討論永真性。 –原子集 A：謂詞套上 H域的元素組成的集合。如A = {所有形如 P(t1, t2, …t n)的元素 }即把 H中的東西填到 S的謂詞里去。 S中的謂詞是有限的， H是可數(shù)的，因此， A也是可數(shù)的。–一旦原子集內(nèi)真值確定好（規(guī)定好），則 S在 H上的真值可確定。成為可數(shù)問題。 2/27/2023 96人工智能講義原子集舉例? 例 1 S={P(a), ～ P(x)∨P(f(x)) } H∞ = {a,f(a),f(f(a))， …} S的原子集為 A={P(a),P(f(a)),P(f(f(a))), … }2/27/2023 97人工智能講義Herbrand定理 （ H域）? 沒有變量出現(xiàn)的原子、文字、子句和子句集，分別稱作基原子、基文字、基子句和基子句集。它們?cè)谟懻撟泳浼?S的不可滿足性時(shí)占有重要置。2/27