人工智能,第三章281-資料下載頁(yè)
2025-02-19 12:42本頁(yè)面
【正文】 Herbrand定理 ? H域 ? H解釋 ? 語義樹 ? 結(jié)論： Herbrand定理 Herbrand定理 ? H域 ? H解釋 ? 語義樹 ? 結(jié)論： Herbrand定理 Herbrand定理 （語義樹） ?構(gòu)成方法 – 原子集中所有元素逐層添加的一棵二叉樹。將元素的是與非分別標(biāo)記在兩側(cè)的分枝上（可不完全畫完） 。 ?特點(diǎn) – 一般情況 H是無限可數(shù)集， S的語義樹是無限樹。 N0 P(a) N12 Q(a) P(f(a)) N24 N31 N38 無限語義樹 N11 ~P(a) ~Q(a) Q(a) ~Q(a) ~P(f(a)) N21 S＝ {～ P(x)∨Q(x) ， P(f(y))，～ Q(f(y))} Herbrand定理 （語義樹） ? 意義 – S ? H ? A ?語義樹 – 可以理解語義樹為 H域的圖形解釋 。 目的：把每個(gè)解釋都攤開 。 語義樹中包含原子集的全部元素 。 因此 ， 語義樹是完全的 。 每一個(gè)直到葉子節(jié)點(diǎn)的分支對(duì)應(yīng) S的一個(gè)解釋 。 可以通過對(duì)語義樹每一個(gè)分支來計(jì)算 S的真值 。 如果每個(gè)基例都為假 ， 則可認(rèn)為是不可滿足的 。 Herbrand定理 （語義樹） ? 幾個(gè)概念 – 失敗結(jié)點(diǎn) ： 當(dāng)（由上）延伸到點(diǎn) N時(shí)， I(N)已表明了 S的某子句的某基例為假。但 N以前尚不能判斷這個(gè)事實(shí)。就稱 N為失敗結(jié)點(diǎn)。 – 封閉語義樹 ： 如果 S的完全語義樹的每個(gè)分枝上都有一個(gè)失敗結(jié)點(diǎn) ， 就稱它是一棵封閉語義樹 。 N0 P(a) N1,2 Q(a) P(f(a)) N2,4 N3,1 N3,8 N1,1 N4,2 N4,1 N2,1 N3,2 N2,2 N3,6 N4,9 N4,10 N4,13 N4,14 封閉語義樹 Q(f(a)) S＝ {～ P(x)∨Q(x) ， P(f(y))，～ Q(f(y))} Herbrand定理 ? H域 ? H解釋 ? 語義樹 ? 結(jié)論： Herbrand定理 Herbrand定理 ? H域 ? H解釋 ? 語義樹 ? 結(jié)論： Herbrand定理 Herbrand定理 （結(jié)論） Herbrand定理： 1. 子句集 S是不可滿足的，當(dāng)且僅當(dāng)對(duì)應(yīng)于 S的完全語義數(shù)是棵有限封閉樹 。 2. 子句集 S是不可滿足的，當(dāng)且僅當(dāng)存在不可滿足的 S的有限基例集。 Herbrand定理 （結(jié)論） ? 定理的意義 – Herbrand定理已將證明問題轉(zhuǎn)化成了命題邏輯問題 。 – 由此定理保證，可以放心的用機(jī)器來實(shí)現(xiàn)自動(dòng)推理了。（歸結(jié)原理） ? 注意 – Herbrand定理給出了一階邏輯的半可判定算法，即僅當(dāng)被證明定理是成立時(shí)，使用該算法可以在有限步得證。而當(dāng)被證定理并不成立時(shí)，使用該算法得不出任何結(jié)論。 但是 ? ? ? ? ? ? ? ? ? ? ? ? ? Herbrand定理 （結(jié)論） ? 仍存在的 問題 ： 基例集序列元素的數(shù)目隨子句集的元素?cái)?shù)目成指數(shù)地增加。 ? 因此 ， Herbrand定理是 30年代提出的 ，始終沒有顯著的成績(jī) 。 ??? 直至 1965年 Robinson提出了 歸結(jié)原理 。 歸結(jié)原理與 Herbrand定理 ? 歸結(jié)過程是語義樹的倒塌過程 ? 最后歸結(jié)出空，就是剩一個(gè)根節(jié)點(diǎn)，就說明語義樹是有限封閉的，證明結(jié)束。 習(xí)題：設(shè)已知： (1)能閱讀者是識(shí)字的； (2)海豚不識(shí)字； (3)有些海豚是很聰明的 。 試證明：有些聰明者并不能閱讀 。 證 首先 ， 定義如下謂詞： R(x)： x能閱讀 。 L(x)： x識(shí)字 。 I(x)： x是聰明的 。 D(x)： x是海豚。 然后把上述各語句翻譯為謂詞公式： (1) x(R(x)→L(x)) (2) x(D(x)→ ﹁ L(x)) 已知條件 (3) x(D(x)∧I(x)) (4) x(I(x)∧ ﹁ R(x)) ??求題設(shè)與結(jié)論否定的子句集 ， 得 (1)﹁ R(x)∨L(x) (2)﹁ D(y)∨ ﹁ L(y) (3)D(a) (4)I(a) (5)﹁ I(z)∨R(z) 歸結(jié)得 (6) R(a) (5)， (4)， {a/z} (7) L(a) (6)， (1)， {a/x} (8) ﹁ D(a) (7), (2), {a/y} (9)□ (8), (3) ：所有不貧窮且聰明的人都快樂。那些看書的人是聰明的。李明能看書且不貧窮。快樂的人過著激動(dòng)人心的生活。 求證：李明過著激動(dòng)人心的生活 給定謂詞：某人 x貧窮 , Poor(x)。 某人 x聰明 , Smart(x)。 某人 x,快樂 happy(x)。 某人 x讀書 ,Read(x)。 某人 x過著激動(dòng)人心的生活 , Exciting(x)。 證明： 由前提：所有不貧窮且聰明的人都快樂 (?x)( ～ Poor(x) ∧ Smart(x) → happy(x)) 那些看書的人是聰明的 (?x)(Read(x) → Smart(x)) 李明能看書且不貧窮 Read(LM) ∧ ～ Poor(LM) 快樂的人過著激動(dòng)人心的生活 (?x) (happy(x) → Exciting(x)) 由結(jié)論的否定 ～ Exciting(LM) 子句集： S = { Poor(x) ∨ ～ Smart(x) ∨ happy(x), ～ Read(y) ∨ Smart(y)， Read(LM), ～ Poor(LM) ， ～ happy(z) ∨ Exciting(z) ， ～ Exciting(LM)} 演講完畢，謝謝觀看！
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1