人工智能 第三章3

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

2、就沒(méi)有這樣的解釋存在，并且算法在有限步內(nèi)停止。 3.4 Herbrand定理精選課件 基本方法： 因?yàn)榱吭~是任意的，所討論的個(gè)體變量域D是任意的，所以解釋的個(gè)數(shù)是無(wú)限、不可數(shù)的 。 簡(jiǎn)化討論域。建立一個(gè)比較簡(jiǎn)單、特殊的域，使得只要在這個(gè)論域上，該公式是不可滿(mǎn)足的。 此域稱(chēng)為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定理精選課件 幾個(gè)基本概念f（tn）：f為子句集S中的所有函數(shù)變量。t1, t2, tn為S的H域的元素。通過(guò)它們來(lái)討論永真性。 原子集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ù)問(wèn)題。3.4 Herbrand定理精選課件 解釋I：謂詞公式G在論域D上任何一組真值的指定稱(chēng)為一個(gè)解釋。 H解釋?zhuān)鹤泳浼疭在的H域上的解釋稱(chēng)為H解釋。 問(wèn)題： 對(duì)于所有的解釋?zhuān)羌俨趴膳卸?。因?yàn)樗薪忉尨砹怂械那闆r，如可窮舉，問(wèn)題便可解決 。3.4

6、Herbrand定理精選課件 如下三個(gè)定理保證了歸結(jié)法的正確性： 定理定理1：設(shè)I是S的論域D上的解釋?zhuān)嬖趯?duì)應(yīng)于I的H解釋I*，使得若有S|I = T，必有 S|I* = T。 定理定理2 2：子句集S是不可滿(mǎn)足的，當(dāng)且僅當(dāng)所有的S的H解釋下為假。 定理定理3 3：子句集S是不可滿(mǎn)足的，當(dāng)且僅當(dāng)對(duì)每一個(gè)解釋I下，至少有S的某個(gè)子句的某個(gè)基例為假。 3.4 Herbrand定理精選課件 基例S中某子句中所有變?cè)?hào)均以S的H域中的元素代入時(shí)，所得的基子句C稱(chēng)為C的一個(gè)基例。 若一個(gè)子句為假，則此解釋為假。 一般來(lái)說(shuō)，D是無(wú)窮不可列的，因此，子句集S也是無(wú)窮不可列的。但S確定后H是無(wú)窮可列的。不

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

8、部元素。因此，語(yǔ)義樹(shù)是完全的。每一個(gè)直到葉子節(jié)點(diǎn)的分支對(duì)應(yīng)S的一個(gè)解釋。可以通過(guò)對(duì)語(yǔ)義樹(shù)每一個(gè)分支來(lái)計(jì)算S的真值。如果每個(gè)基例都為假，則可認(rèn)為是不可滿(mǎn)足的。3.4 Herbrand定理精選課件 幾個(gè)概念 失敗結(jié)點(diǎn)： 當(dāng)（由上）延伸到點(diǎn)N時(shí)，I(N)已表明了S的某子句的某基例假。但N以前尚不能判斷這事實(shí)。就稱(chēng)N為失敗結(jié)點(diǎn)。 封閉語(yǔ)義樹(shù)：如果S的完全語(yǔ)義樹(shù)的每個(gè)分枝上都有一個(gè)失敗結(jié)點(diǎn)，就稱(chēng)它是一棵封閉語(yǔ)義樹(shù)。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封閉語(yǔ)義樹(shù)Q(f(a)SP(x)Q(x)，P(f(y)，Q(f(y) 3.4 Herbrand定理精選課件Herbrand定理：n 子句集S是不可滿(mǎn)足的，當(dāng)且僅當(dāng)對(duì)應(yīng)于S的完全語(yǔ)義數(shù)是棵有限封閉樹(shù)。 1. 子句集S是不可滿(mǎn)足的，當(dāng)且僅當(dāng)存在不可滿(mǎn)足的S的有限基例集。 3.4 Herbrand定理精選課件 定理的意義 Herbrand定理已將證明問(wèn)題轉(zhuǎn)化成了命題邏輯問(wèn)題。 由此定理保證，可以放心的用機(jī)器來(lái)實(shí)現(xiàn)自動(dòng)推理了。（歸結(jié)原理） 注意 Herbrand定理給出了一階邏輯的半可判定算法，即僅當(dāng)被證明定理是成立時(shí)，使用該算法可以在有限步得證。而當(dāng)被證定理并不成立時(shí)，使用該算法得不出任何結(jié)論。但是 3.4 Herbrand定理精選課件 仍存在的問(wèn)題問(wèn)題：基例集序列元素的數(shù)目隨子句基的元素?cái)?shù)目成指數(shù)地