人工智能 第三章3[章節(jié)優(yōu)講]

1、3.4 Herbrand定理 問題： 一階邏輯公式的永真性（永假性）的 判定是否能在有限步內(nèi)完成？ 1優(yōu)質(zhì)教學(xué) 1936年圖靈(Turing)和邱吉(Church)互相獨(dú) 立地證明了： “沒有一般的方法使得在有限步內(nèi)判定一階邏 輯的公式是否是永真（或永假）。但是如果公 式本身是永真（或永假）的，那么就能在有限 步內(nèi)判定它是永真（或永假）。對(duì)于非永真 （或永假）的公式就不一定能在有限步內(nèi)得到 結(jié)論。判定的過程將可能是不停止的?！?3.4 Herbrand定理 2優(yōu)質(zhì)教學(xué) Herbrand的思想 定義： 公式G永真：對(duì)于G的所有解釋，G都為真。 思想： 尋找一個(gè)已給的公式是真的解釋。然而，如 果所

2、給定的公式的確是永假的，就沒有這樣 的解釋存在，并且算法在有限步內(nèi)停止。 3.4 Herbrand定理 3優(yōu)質(zhì)教學(xué) 基本方法： 因?yàn)榱吭~是任意的，所討論的個(gè)體變量域D是 任意的，所以解釋的個(gè)數(shù)是無限、不可數(shù)的 。 簡(jiǎn)化討論域。建立一個(gè)比較簡(jiǎn)單、特殊的域， 使得只要在這個(gè)論域上，該公式是不可滿足的。 此域稱為H域。 ),.,( 11nii ttfHH 3.4 Herbrand定理 4優(yōu)質(zhì)教學(xué) D域 H域 H域與D域關(guān)系示意圖 5優(yōu)質(zhì)教學(xué) H域例題 設(shè)子句集S = P(x), Q(y,f(z,b),R(a)，求H域 解： H0 a, b為子句集中出現(xiàn)的常量 H1 a, b, f(a,b), f(a

3、,a), f(b,a), f(b,b) H2 a, b, f(a,b), f(a,a), f(b,a), f(b,b)， f(a,f(a,b), f(a,f(a,a), f(a, f(b,a), f(a, f(b,b), f(b,f(a,b), f(b,f(a,a), f(b, f(b,a), f(b,f(b,b), f(f(a,b),f(a,b), f(f(a,b),f(a,a), f(f(a,b), f(b,a), f(f(a,b), f(b,b), f(f(a,a),f(a,b), f(f(a,a),f(a,a), f(f(a,a), f(b,a), f(f(a,a), f(b,b),

4、f(f(b,a),f(a,b), f(f(b,a),f(a,a), f(f(b,a), f(b,a), f(f(b,a), f(b,b), f(f(b,b),f(a,b), f(f(b,b),f(a,a), f(f(b,b), f(b,a), f(f(b,b), f(b,b) H = H1H2H3 3.4 Herbrand定理 6優(yōu)質(zhì)教學(xué) 幾個(gè)基本概念 f（tn）：f為子句集S中的所有函數(shù)變量。t1, t2, tn為S的H域的元素。通過它們來討論永 真性。 原子集A：謂詞套上H域的元素組成的集合。如 A = 所有形如 P(t1, t2, tn)的元素 即把H中的東西填到S的謂詞里去。S中的謂詞

5、是 有限的，H是可數(shù)的，因此，A也是可數(shù)的。 3.4 Herbrand定理 7優(yōu)質(zhì)教學(xué) 上例題的原子集為： A = P(a), Q(a, a), R(a), P(b), Q(b, a), Q(b, b), Q(a, b), R(b), P( f(a,b), Q(f(a, b), f(a, b), R(f(a, b), P(f(a,a), P(f(b,a), P(f(b,b),) 一旦原子集內(nèi)真值確定好（規(guī)定好），則S在H上 的真值可確定。成為可數(shù)問題。 3.4 Herbrand定理 8優(yōu)質(zhì)教學(xué) 解釋I：謂詞公式G在論域D上任何 一組真值的指定稱為一個(gè)解釋。 H解釋：子句集S在的H域上的解釋 稱

6、為H解釋。 問題： 對(duì)于所有的解釋，全是假才可判定。 因?yàn)樗薪忉尨砹怂械那闆r，如 可窮舉，問題便可解決 。 3.4 Herbrand定理 9優(yōu)質(zhì)教學(xué) 如下三個(gè)定理保證了歸結(jié)法的正確性： 定理定理1： 設(shè)I是S的論域D上的解釋，存在對(duì)應(yīng)于I的H解 釋I*，使得若有S|I = T，必有 S|I* = T。 定理定理2 2： 子句集S是不可滿足的，當(dāng)且僅當(dāng)所有的S的H 解釋下為假。 定理定理3 3： 子句集S是不可滿足的，當(dāng)且僅當(dāng)對(duì)每一個(gè)解 釋I下，至少有S的某個(gè)子句的某個(gè)基例為假。 3.4 Herbrand定理 10優(yōu)質(zhì)教學(xué) 基例 S中某子句中所有變?cè)?hào)均以S的H域中的元素代入時(shí)， 所得的

7、基子句C稱為C的一個(gè)基例。 若一個(gè)子句為假，則此解釋為假。 一般來說，D是無窮不可列的，因此，子句集S也 是無窮不可列的。但S確定后H是無窮可列的。不 過在H上證明S的不可滿足性仍然是不可能的。 解決問題的方法：語義樹 3.4 Herbrand定理 11優(yōu)質(zhì)教學(xué) 構(gòu)成方法 原子集中所有元素逐層添加的一棵二 叉樹。將元素的是與非分別標(biāo)記在兩 側(cè)的分枝上（可不完全畫完） 。 特點(diǎn) 一般情況H是可數(shù)集，S的語義樹是無 限樹。 3.4 Herbrand定理 12優(yōu)質(zhì)教學(xué) N0 P(a) N12 Q(a) P(f(a) N24 N31N38 無限語義樹 N11 P(a) Q(a) Q(a)Q(a) P(

8、f(a) N21 SP(x)Q(x)，P(f(y)，Q(f(y) 3.4 Herbrand定理 13優(yōu)質(zhì)教學(xué) 意義 S H A 語義樹 可以理解語義樹為H域的圖形解釋。 目的：把每個(gè)解釋都攤開。語義樹中包 含原子集的全部元素。因此，語義樹是 完全的。每一個(gè)直到葉子節(jié)點(diǎn)的分支對(duì) 應(yīng)S的一個(gè)解釋?？梢酝ㄟ^對(duì)語義樹每一 個(gè)分支來計(jì)算S的真值。如果每個(gè)基例都 為假，則可認(rèn)為是不可滿足的。 3.4 Herbrand定理 14優(yōu)質(zhì)教學(xué) 幾個(gè)概念 失敗結(jié)點(diǎn)： 當(dāng)（由上）延伸到點(diǎn)N時(shí)，I(N)已表明了S的某 子句的某基例假。但N以前尚不能判斷這事實(shí)。 就稱N為失敗結(jié)點(diǎn)。 封閉語義樹： 如果S的完全語義樹的每個(gè)

9、分枝上都有一個(gè)失 敗結(jié)點(diǎn)，就稱它是一棵封閉語義樹。 3.4 Herbrand定理 15優(yōu)質(zhì)教學(xué) N0 P(a) N1,2 Q(a) P(f(a) N2,4 N3,1 N3,8 N1,1 N4,2N4,1 N2,1 N3,2 N2,2 N3,6 N4,9N4,10N4,13N4,14 封閉語義樹 Q(f(a) SP(x)Q(x)，P(f(y)，Q(f(y) 3.4 Herbrand定理 16優(yōu)質(zhì)教學(xué) Herbrand定理： 1. 子句集S是不可滿足的，當(dāng)且僅當(dāng)對(duì)應(yīng)于S 的完全語義數(shù)是棵有限封閉樹。 2. 子句集S是不可滿足的，當(dāng)且僅當(dāng)存在不 可滿足的S的有限基例集。 3.4 Herbrand定理 17優(yōu)質(zhì)教學(xué) 定理的意義 Herbrand定理已將證明問題轉(zhuǎn)化成了命題邏輯問題。 由此定理保證，可以放心的用機(jī)器來實(shí)現(xiàn)自動(dòng)推理了。 （歸結(jié)原理） 注意 Herbrand定理給出了一階邏輯的半可判定算法，即僅 當(dāng)被證明定理是成立時(shí)，使用該算法可以在有限步得 證。而當(dāng)被證定理并不成立時(shí)，使用該算法得不出任 何結(jié)論。 但是 3.4 Herbrand定理 18優(yōu)質(zhì)教學(xué) 仍存在的問題問題： 基例集序列元素的數(shù)目隨子句基的元素?cái)?shù)目成 指數(shù)地增加。 因此，