人工智能 第三章3

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

2、就沒有這樣的解釋存在，并且算法在有限步內(nèi)停止。 3.4 Herbrand定理精選課件 基本方法： 因為量詞是任意的，所討論的個體變量域D是任意的，所以解釋的個數(shù)是無限、不可數(shù)的 。 簡化討論域。建立一個比較簡單、特殊的域，使得只要在這個論域上，該公式是不可滿足的。 此域稱為H域。 ),.,(11niittfHH3.4 Herbrand定理精選課件D域H域H域與D域關(guān)系示意圖精選課件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,a), f(b,a), f(b,b)H2 a, b, f(a,

3、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),f(f(b,a),f(a,b), f(f(b,a),f(a,a), f(f(

4、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 = H1H2H33.4 Herbrand定理精選課件 幾個基本概念f（tn）：f為子句集S中的所有函數(shù)變量。t1, t2, tn為S的H域的元素。通過它們來討論永真性。 原子集A：謂詞套上H域的元素組成的集合。如A = 所有形如 P(t1, t2, tn)的元素即把H中的東西填到S的謂詞里去。S中的謂詞是有限的，H是可數(shù)的，因此，A也是可數(shù)的。3.4 Herbrand定理精選課件上例題的原子集為

5、： 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定理精選課件 解釋I：謂詞公式G在論域D上任何一組真值的指定稱為一個解釋。 H解釋：子句集S在的H域上的解釋稱為H解釋。 問題： 對于所有的解釋，全是假才可判定。因為所有解釋代表了所有的情況，如可窮舉，問題便可解決 。3.4

6、Herbrand定理精選課件 如下三個定理保證了歸結(jié)法的正確性： 定理定理1：設(shè)I是S的論域D上的解釋，存在對應(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)對每一個解釋I下，至少有S的某個子句的某個基例為假。 3.4 Herbrand定理精選課件 基例S中某子句中所有變元符號均以S的H域中的元素代入時，所得的基子句C稱為C的一個基例。 若一個子句為假，則此解釋為假。 一般來說，D是無窮不可列的，因此，子句集S也是無窮不可列的。但S確定后H是無窮可列的。不

7、過在H上證明S的不可滿足性仍然是不可能的。 解決問題的方法：語義樹3.4 Herbrand定理精選課件 構(gòu)成方法原子集中所有元素逐層添加的一棵二叉樹。將元素的是與非分別標(biāo)記在兩側(cè)的分枝上（可不完全畫完） 。 特點一般情況H是可數(shù)集，S的語義樹是無限樹。 3.4 Herbrand定理精選課件N0P(a)N12Q(a)P(f(a)N24N31N38無限語義樹N11P(a)Q(a)Q(a)Q(a)P(f(a)N21SP(x)Q(x)，P(f(y)，Q(f(y) 3.4 Herbrand定理精選課件 意義S H A 語義樹可以理解語義樹為H域的圖形解釋。 目的：把每個解釋都攤開。語義樹中包含原子集的全

8、部元素。因此，語義樹是完全的。每一個直到葉子節(jié)點的分支對應(yīng)S的一個解釋。可以通過對語義樹每一個分支來計算S的真值。如果每個基例都為假，則可認(rèn)為是不可滿足的。3.4 Herbrand定理精選課件 幾個概念 失敗結(jié)點： 當(dāng)（由上）延伸到點N時，I(N)已表明了S的某子句的某基例假。但N以前尚不能判斷這事實。就稱N為失敗結(jié)點。 封閉語義樹：如果S的完全語義樹的每個分枝上都有一個失敗結(jié)點，就稱它是一棵封閉語義樹。3.4 Herbrand定理精選課件N0P(a)N1,2Q(a)P(f(a)N2,4N3,1N3,8N1,1N4,2N4,1N2,1N3,2N2,2N3,6N4,9N4,10N4,13N4,1

9、4封閉語義樹Q(f(a)SP(x)Q(x)，P(f(y)，Q(f(y) 3.4 Herbrand定理精選課件Herbrand定理：n 子句集S是不可滿足的，當(dāng)且僅當(dāng)對應(yīng)于S的完全語義數(shù)是棵有限封閉樹。 1. 子句集S是不可滿足的，當(dāng)且僅當(dāng)存在不可滿足的S的有限基例集。 3.4 Herbrand定理精選課件 定理的意義 Herbrand定理已將證明問題轉(zhuǎn)化成了命題邏輯問題。 由此定理保證，可以放心的用機(jī)器來實現(xiàn)自動推理了。（歸結(jié)原理） 注意 Herbrand定理給出了一階邏輯的半可判定算法，即僅當(dāng)被證明定理是成立時，使用該算法可以在有限步得證。而當(dāng)被證定理并不成立時，使用該算法得不出任何結(jié)論。但是 3.4 Herbrand定理精選課件 仍存在的問題問題：基例集序列元素的數(shù)目隨子句基的元素數(shù)目成指數(shù)地