【正文】 p 證明：n 王喜歡花生。歸結(jié)演繹推理歸結(jié)演繹推理（ 2）、（ 6）歸結(jié)；~（ 5） D王某被害，有四個嫌疑犯 A， B， C， D，公安局派出五個偵察員，他們帶回的信息各不一樣，甲說 A， B中至少有一人作案，乙說 B∨ ∨ n 化簡上述蘊含式為子句集n ① ??ApBBn C回答： A和 B中至少有一個是說謊者。∨ ?如果錄取 A而不錄取 B，則一定錄取 C。提示：設(shè)用 P(x)表示錄取 x） 3）歸結(jié)反演 :課堂練習p 某公司招聘工作人員， A， B， C三人應試，經(jīng)面試后，公司表示如下想法：n （ 1） M（ y） ∨ I（ f（ x））（ 2） ~M（ y） ∨ I（ f（ x））（ 2） ~3）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)2023/2/27結(jié)論：如果沒有利息，那么就沒有人去儲蓄錢。3）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)p 例、歸結(jié)反演的應用 —— 食物問題p ③ 歸結(jié)演繹 —— 應用歸結(jié)演繹方法不斷生成 歸結(jié)式 以擴展子句集 S，直到生成 空子句 □ 。2023/2/27Eat(Zhang,x)]p?星期六 105歸結(jié)演繹推理歸結(jié)演繹推理?n 王 (Wang)喜歡 (Like)所有種類的食物 (Food)?！??Killed(y)3）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)p 例、歸結(jié)反演的應用 —— 食物問題p ① 形式化 —— 把以自然語言表示的 事實 和要證明的 目標 形式化地表示為 合適公式 。3）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)p 例、歸結(jié)反演的應用 —— 食物問題p 已知下列 事實 為真 T，n 王 (Wang)喜歡 (Like)所有種類的食物 (Food)。合適公式 F永假子句集 S的不可滿足性充分必要條件有限的不可滿足的基子句集 S’ 子句集 S不可滿足性充分必要條件歸結(jié)后擴展子句集 S’子句集 S不可滿足性等價歸結(jié)的演繹推理的完備性： 若子句集 S不可滿足，就必定存在一個從 S到 空子句 □ 的歸結(jié)演繹；反之亦然。星期六 99歸結(jié)演繹推理歸結(jié)演繹推理第一對參數(shù)是可同一的，用 z/a,第二對參數(shù)也是可同一的，因為 z已經(jīng)出現(xiàn)過，所以用 a換 z,然后用 h(a,u)/x第三對參數(shù)可用 g(y)/u所以該公式是可同一的，可建立置換S1={z/a, h(a,u)/x, g(y)/u}2023/2/27∨ ∨ ∨ R(A,f(B))∨ n 建立置換 S1={A/x,g(x)),★p① 兩個 原子謂詞公式 必須具有相同的 謂詞符號 和 參數(shù)項個數(shù) ；p② 從左到右逐個 檢查 每對參數(shù)項的 可合一性 ；p③ 若每對參數(shù)項都可合一，則合一處理成功，并 建立 用于實現(xiàn)合一的 置換 。x,用 s1s2表示兩個置換 s1和 s2的合成。g(x)),g(x)),?Q,n 空子句 是不可滿足（即永假）的子句；2023/2/27C2=?L，則歸結(jié)式 C為 空 ；n 以 □ 表示為空的歸結(jié)式 C，并稱 C=□ 為 空子句；n 因為 C1和 C2是一對矛盾子句，不可同時滿足，所以 □ 是 不可滿足 的子句 ；n 通過往 S中加入 □ 而產(chǎn)生的擴展子句集 S’不可滿足；n 空子句 □ 是用 歸結(jié)原理 判定子句集 S不可滿足的 成功標志 ?！?n 歸結(jié)原理 簡單易行 ，便于計算機實現(xiàn)和執(zhí)行，從而使定理的機器自動證明成為現(xiàn)實，也成為 人工智能技術(shù)實用化的一次重要突破 。n 若能建造一個較為簡單的 特殊論域 ，使得只要證明子句集S在該域不可滿足，就可確保子句集在 任何可能的論域 上不可滿足，將是十分有意義的 ！n 海伯倫建立的特殊域 H就具有這樣的性質(zhì)。P(y)∨ ?Q(A,z)∨ P(z,g(z))因此，我們可以消去前綴。P(y)}如果要消去的存在量詞不在任何一個全稱量詞的轄域內(nèi)，那么我們就用不含變量的 Skolem函數(shù)即常量。令這種依賴關(guān)系明顯地由函數(shù) g（ y）所定義，它把每個 y值映射到存在的那個 x。如，把 (?x){p(x)=(?x)Q(x)}標準化而得到（ ?x） {p(x)=(?y)Q(y)}每個否定符號 ~最多只用到一個謂詞符號上，并反復應用狄摩根律。(?z)[?P(f(A,y))∨ ?Q(A,z)∨ P(z,g(z))]2023/2/27? ∨ Lim(i=1,2,…,n)pLij=Pij|?Pij:文字（ Literal） ，是原子謂詞公式 Pij或其取反n 合取范式 可定義為 子句 的 合取 ∧ ,Fn}星期六 56p 合取范式的標準化過程n 例、化簡合適公式(?y)(?z){P(A)∧{[P(y)∧ ?P(f(A,y))]∨ [?Q(A,z)∨ P(z,g(z))]}}⑦ 消去全稱量詞{P(A)∧{[P(y)∧ ?P(f(A,y))]∨ [?Q(A,z)∨ P(z,g(z))]}}2023/2/27星期六 50p 合取范式的標準化過程n 例、化簡合適公式?(?x){P(x)?{(?y)[P(y)?2023/2/27[?Q(x,z)(?P(x))P(x)Q)∨ ?p ② 消去蘊涵符號n 蘊涵式轉(zhuǎn)化 ： P(Q2x2)…(Q kxk)M，其中p M2. 因為母式不含量詞，所以可以變換為 合取 范式。P(x， z)∨ ~P(y， z)∨ Q(x， y， u))2023/2/27P(x))2023/2/27(P∧Q) ? 172。(172。星期六 33合適 (式 )公式p 合適公式的定義n 合適公式 適合于 一階謂詞邏輯n 遵從以下遞歸方式定義的 邏輯語句 稱為 合適公式n ① 單一謂詞公式是合適公式；n ② 若 A是合適公式，則 ?A也是合適公式；n ③ 若 A和 B都是合適公式，則 A∧ B、 A∨ B、 A?B和 A?B也都是合適公式；n ④ 若 A是合適公式， x是約束變量，則 (?x)A和 (?x)A也都是合適公式；n ⑤ 只有按上述規(guī)則 ① ④ 求得的公式，才是合適公式。星期六 31p 連詞和量詞 —— （ 2）量詞n 全稱量詞 ?p符號 (?x)P(x)：表示對于某個論域中的 所有（任意一個） 個體 x,n 命題邏輯 缺乏有效的表達 一般性概念 的能力p無法把每個知識單元抽象、細分；p如， “條條大路通羅馬 ”。（或）連接 謂詞公式 ，稱為 析取 ；產(chǎn)生的 邏輯語句 稱為 析取式 ，每個成分成為 析取項。? 主要內(nèi)容： ? 謂詞演算 ? H域和海伯倫定理 ? 歸結(jié)原理 ? 歸結(jié)反演 歸結(jié) 演 繹 推理 ★ 2023/2/272023/2/27n如伽利略在論證哥白尼的日心說時 ,曾使用了下列推理：這就是使用了肯定后件的推理，違反了經(jīng)典邏輯的邏輯規(guī)則 ,他為此曾遭到非難。即： Q為 P的邏輯結(jié)論，當且僅當 是不可滿足的。 2023/2/27 正向推理所得的中間結(jié)論恰好是逆向推理此時要求的證據(jù)求解策略 推理是只求一個解還是求所有解以及最優(yōu)解等限制策略 對推理的深度、寬度、時間、空間等進行限制2023/2/27星期六 7推理方式及其分類確定性推理、不確定性推理p按推理時所用知識的確定性來劃分，推理可分為確定性推理、不確定性推理p確定性推理（精確推理）： 推理時所用的知識都是精確的，推出的結(jié)論也是確定的，其真值或者為真，或為假，沒有第三種情況出現(xiàn)p不確定性推理（不精確推理）： 推理時所用的知識不都是精確的，推出的結(jié)論也不完全是肯定的，真值位于真與假之間，命題的外延模糊不清2023/2/27 演繹推理是從 全稱判斷 推導出 特稱判斷 或 單稱判斷 的過程167。星期六 2 引 言2023/2/27結(jié)論：由大前提推出的適合于小前提所示情況的新判斷2023/2/27又稱為數(shù)據(jù)驅(qū)動推理、前向鏈推理、模式制導推理及前件推理。星期六 13推理的控制策略④ 雙向推理167。 對逆向推理而言，如果有多條產(chǎn)生式的后件都和同一假設(shè)匹配成功，或者有多條產(chǎn)生式后件可與多個假設(shè)匹配成功。 2023/2/27 p 推理規(guī)則：n P規(guī)則： 在推理的任何步驟上都可引入前提，繼續(xù)進行推理。星期六 22自然演繹推理的基本概念n 如果行星系統(tǒng)是以太陽為中心的 ,則金星會顯示出位相變化。 ? 符號推理的重要方式是演繹推理? 它的基礎(chǔ)為謂詞演算 —— 一種 形式語言 ? 將各種陳述性（說明性）的描述以 形式化 的方式表示，以便對它們 作處理。n 復合謂詞公式 也稱為 邏輯語句 。n 復合謂詞公式也稱為 邏輯語句 。n 存在量詞 ?p符號 (?x)P(x)：來表示某個論域中 至少存在一個 個體 x，使 P(x)星期六 32p 一階謂詞邏輯n 定義： 若限定 不允許 對 謂詞 和 函數(shù)名 進行 量化 處理，且 參數(shù)項 不能是 謂詞公式 ，則這樣的謂詞邏輯是 一階 的。(P∨Q) ? 172。(?x)P(x) ? (?x)(172。星期六 38前束范式例 1：變公式（ ?x） P（ x） =（ ?x） Q（ x）為前束范式~（ ?x） P（ x） ∨ （ ?x） Q（ x）（ ?x）（ ~P（ x）） ∨ （ ?x） Q（ x）（ ?x）（ ~P（ x） ∨ Q（ x））為前束范式2023/2/27星期六 41一階邏輯公式所對應的 Skolem標準型基于如下思想來構(gòu)造：1. 一階邏輯的一個公式被變換為前束范式。星期六 42Skolem標準型p 通過變換 消去存在量詞 所得到的公式稱為 Skolem標準型 ，而拿來代替存在量詞的變量的函數(shù)稱Skolem函數(shù) 。 n 轉(zhuǎn)化步驟沒有嚴格的規(guī)定n 較合理的化簡過程，分為 8步：p① 消去多余的量詞（很少出現(xiàn)）；p② 消去蘊涵符號；p③ 減少否定的轄域（內(nèi)移否定符號）；p④ 變量標準化（變量換名）；p⑤ 消去存在量詞 (Skolem變換 ) ；p⑥ 全稱量詞前束化（化為前束形）；p⑦ 消去全稱量詞；p⑧ 把 母式 轉(zhuǎn)化為 合取范式 ?！?P(y)?！??Qn 雙重否定： ?(?P)P(x)星期六 47p 合取范式的標準化過程p ⑤ 消去存在量詞（ Skolem變換 ）n ?在 ?的轄域內(nèi)p (?z)(?w)[?Q(x,z) (Q(P星期六 53p 合取范式的標準化過程n 例、化簡合適公式(?x){P(x)∧{(?y)[P(y)∧ ?P(f(x,y))]∨ (?y)(?w)[?Q(x,y)∨ P(y,w)]}}④ 變量換名(?x){P(x)∧{(?y)[P(y)∧ ?P(f(x,y))]∨ (?z)(?w)[?Q(x,z)∨ P(z,w)]}}2023/2/27,F n都是合適公式，表示 公理 或 事實 ；n W是合適公式，表示 待證明的定理 ，稱為 目標公式 ；p 證明的方法可分兩大類：n 演繹法p直接證明 F1∧ F2∧ … ∧ Fn?W為 永真 ；n 反證法p間接證明 ?(F1∧ F2∧ … ∧ Fn?W)為 永假 ；p證明 F1∧ F2∧ … ∧ Fn星期六 60歸結(jié)演繹推理歸結(jié)演繹推理1） H域和海伯倫定理（了解）p 子句和子句集n 子句 —— 僅由 文字 的 析取 ∨ 構(gòu)成的合適公式pWi=Li1∨ Li2∨ …[P(x)∧(?y) ★2023/2/27A}代替 ~（ ?x） A啞元（虛構(gòu)變量），它可以在該轄域內(nèi)處處統(tǒng)一的被另一個沒有出現(xiàn)過的任意變量所代替，而不改變公式的真值。（ ?y） P[g（ y）， y]Skolem函數(shù)的變量是由那些全稱量詞所約束的全稱量詞量化變量，這些全稱量詞的轄域包括要被消去的存在量詞的轄域在內(nèi)。前束形公式由全稱量詞串組成的 前綴 和不含量詞的 母式 組成。這種母式叫做合取范式。?P(f(A,y2))∨ ?Q(A,z2)∨ P(z2,g(z2))?(?x){P(x)?{(?y)[P(y)星期六 68歸結(jié)演繹推理歸結(jié)演繹推理1） H域和海伯倫定理p 子句和子句集合適公式 F 合取范式 子句集 S合適公式 F永假子句集 S的不可滿足性充分必要條件重要性質(zhì)S的不可滿足性任意論域 D上的任意解釋 I,S中都 至少 有一個 子句 真值為 F2023/2/27n 海伯倫定理 ：p子句集 S不可滿足的 充要條件 是存在一個有限的不可滿足的基子句集 S’。Q(x)和 C2星期六 79歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理p 動機n 為提高判定子句集 S不可滿足的有效性 ，魯賓遜于 1965年提出了 歸結(jié) (Resolution)原理 ，也稱為 消解原理 。2023/2/27p置換元素 —— t/v（ 置換項 /變量 ）p置換 —— 若干 置換元素 的集合；n 合一處理：P(x,星期六 83　　　　P(x,2023/2/27p置換元素 —— t/v（ 置換項 /變量