【正文】 個無相同變元的子句， L1， L2分別是 C1 ， C2中的文字 σ為 L1 和 L2 的最一般合一。S(z) ? 172。 R(z) 2022/8/17 86 (10) 例 設(shè)已知： （ 1）能閱讀者是識字的； （ 2）海豚不識字； （ 3）有些海豚是很聰明的。 R(x)) 需證結(jié)論 2022/8/17 87 (11) 用歸結(jié)反演法來證明，求題設(shè)與結(jié)論否定的子句集，得： (1) 172。 R(x) ? L(x) 172。 GZ(x):x大于零。E(u) ? I(s(u)) （ 3） 172。 即證明： G： ?xT(x,Zhang) (1) 172。C(x,y) ? 172。T(u,Zhang) ? ANS（ u） 重新歸結(jié)演繹得： (5) 39。] 這說明小張的老師存在且求得小張的老師是王先生。 F(x,y)表示 x與 y是父親。 F(Da， z)? G (Lao， z) [(1),(2),{Lao/x,Da/y}] (6) G(Lao， Xiao) [(3),(5),{Xiao/x}] (7) GA(Lao,Xiao) [(4),(6),{Lao/u,Xiao/v}] 所以上述人員中，老李是小李的祖父。 P ? Q （ 3） P ? 172。 P [(2),(4)] （ 12） 172。 Q [(3),(8)] （ 28） P ? 172。 P ? 172。 ? 控制策略的目的 歸結(jié)點盡量的少。 P ? 172。 P [(2),(12)] 2022/8/17 105 （ 4） （ 25） P [(3),(5)] （ 26） P ? 172。 Q [(2),(3)] （ 10） 172。 2022/8/17 103 （ 2） ? 水平浸透法具體作法 第一輪 歸結(jié)先讓 CLAUSES表（原子句集 S）中的子句兩兩見面 進(jìn)行歸結(jié)，將產(chǎn)生的歸結(jié)集合記為 S1，再將 S1并入 CLAUSES中，得到 CLAUSES= S ∪ S1 ； 再一輪 歸結(jié)時，又讓 S ∪ S1 ∪ S2與 S2中的子句進(jìn)行歸結(jié) ?? 如此進(jìn)行，知道某一個 Sk中出現(xiàn)空子句為止。 F(y,z) ? G(x,z) (2) F(Lao,Da) (3) F(Da,Xiao) (4) 172。 （ 3）大李是小李父親。,{Wang/u,Zhang/y}] (7) 39。T(z,x) ? T(z,y) (2)T(Zhang,Li) (3)C(Li,Zhang) (4)39。C(Li,Zhang) [(4),(5),{Wang/u,Zhang/y}] (7)Nil [(3),(6)] 這說明小張的老師確實是存在的。 問：小張的老師是誰？ 解 首先定義如下謂詞： T(x,y)表示 x是 y的老師 C(x,y)表示 x與 y是同班同學(xué)。N(x) ? GZ(x) （ 2） 172。 E(x):x是偶數(shù)。 I(z) ? R(z) R(a) L(a) 172。 將上述各語句翻譯成謂詞公式： (1) (?x)(R(x)?L(x)) (2) (?x)(D(x)?172。P(y) ?R(y) (3)P(a) (4)S(a) (5) 172。P(x) ?Q(x) (2) 172。 2022/8/17 82 (6) 定義 14 子句的 C1， C2消解式，是下列二元消解式之一 : （ 1） C1和 C2的二元消解式； （ 2） C1和 C2的因子的二元消解式； （ 3） C1因子和 C2的二元消解式； （ 4） C1的因子和 C2的因子的二元消解式。 Q(x)∨ R(y),求 C1,C2的歸結(jié)式。｛ bk/ak｝或 σk+1=σk{h(a,u) /x}＝ {a/z,h(a,u) /x} S2= S1 一個公式的合一一般不唯一 2022/8/17 71 (6) 定義 10 設(shè) σ是原子公式集 S的一個合一，如果對 S的任何一個合一 θ都存在一個替換 λ，使得 θ ＝ σ ?λ 則稱 σ為 S的 最一般合一 (Most General Unifier),簡稱 MGU。 若其中 t1, t2, … , tn是不含變元的項（稱為 基項 ）時， 該替換為 基替換 ； 沒有元素的替換稱為 空替換 ，記作 ε，表示不作任何替換。T T NIL 2022/8/17 65 (11) ? 練習(xí)：證明子句集 {P ? 172。T (4, 8) (10)NIL (5, 9) 172。P?172。T?Q) = {172。即 S1的不可滿足性 = S不可滿足 S2的不可滿足性 = S不可滿足 2022/8/17 63 (9) 例 設(shè)公理集： P, (P?Q) ?R, (S?T) ?Q, T 求證： R 化子句集： (P?Q) ?R = 172。 L ＝ F（假），也就是 NIL F ?2022/8/17 60 (6) ? 利用歸結(jié)原理證明命題公式的思路 ? 先求出要證明的命題公式的否定式的子句集 S； ? 然后對子句集 S（一次或者多次）使用歸結(jié)原理； ? 若在某一步推出了空子句，即推出了矛盾，則說明子句集 S是不可滿足的，從而原否定式也是不可滿足的，進(jìn)而說明原公式是永真的。 則 C1 C2的邏輯結(jié)果為 C1= C1 ’ ?L= 172。 2022/8/17 55 (1) ? 歸結(jié)原理的提出 歸結(jié)原理 (principle of resolution)又稱消解原理 ,1965年魯濱遜（ ）提出，從理論上解決了定理證明問題。 R(x,g(x)) ] } {172。I(s(a)) 2022/8/17 51 (9) Skolem標(biāo)準(zhǔn)型 在求子句集的過程中，消去存在量詞 之后，把所有 全稱量詞 都依次移到式子的最左邊（或者 把所有的量詞都依次移到式子最右邊，再消去存在量 詞），再將右部的式子化為合取范式，這樣得到的式 子就是 Skolem標(biāo)準(zhǔn)型。G的 子句集。 適當(dāng)改名，使子句間無同名變元。 P(x， f(x)) ? [Q(x,g(x)) ? 172。 P(x， f(x)) ? 172。 P(x， y) ? ? z[Q(x， z) ? 172。B 172。 R(x,z)]} 適當(dāng)改名，使變量標(biāo)準(zhǔn)化 即：對于不同的約束，對應(yīng)于不同的變量 移動否定詞作用范圍，使其僅作用于原子公式 理論根據(jù)： 172。 Q(x,y) ?R(x,y)]} 消蘊含詞和等值詞 理論根據(jù)： A?B 172。 例如： 172。 ? 常用邏輯等價式 ? 常用邏輯蘊含式 2022/8/17 33 常用邏輯等價式（ 1） 2022/8/17 34 常用邏輯等價式（ 2） 2022/8/17 35 常用邏輯等價式（ 3） 2022/8/17 36 常用邏輯等價式（ 4） 2022/8/17 37 常用邏輯蘊含式（ 1) 2022/8/17 38 常用邏輯蘊含式 (2) 2022/8/17 39 （ 2） 例 設(shè)有前提： （ 1）凡是大學(xué)生都學(xué)過計算機(jī)； （ 2）小王是大學(xué)生。 （ 2）若 P恒為假，則稱 P在 D上永假或是 D上的永假式。 2022/8/17 27 （ 11） 例：設(shè)個體域 D＝ {1,2},求公式 A＝ ? x ? yP（ x， y）在 D上的解釋，并指出在每一種解釋下公式 A的真值。P(x) ? Q(y) ?R(x,y)) ? (172。 ? 新變元符號必須是量詞轄域內(nèi) 原先沒有 的，最好是 公式中 也 未出現(xiàn) 過的。 謂詞公式亦稱為謂詞邏輯中的合適（式）公式，記為 Wff。 G: ?x (N(x)?(I(s(x)) ?O(x))) 2022/8/17 17 （ 1） 定義 1：項 （ 1） 個體常元和變元都是項。 E(x):x是偶數(shù)。 ? x(G(x) ? ? y（ G（ y） ? D（ x， y）） ? x(G(x) ? ? y（ G（ y） ? D（ y， x）） 用謂詞表示命題時，形式并不是固定的。 符號約定： 謂詞－大寫字母； P(x,y) 函數(shù)－小寫字母； f(x) 變量－ x、 y、 z、 u、 v…… ； 常量－ a、 b、 c……. 。 x1， x2 ， … ， xn是 個體， 表示某個獨立存 在的事物或者某個抽象的概念。 ?命題可以用命題符號表示。 自然演繹法 ：該方法依據(jù)推理規(guī)則從前提和公理中可以推出許多定理，如果待證明的定理在其中則定理得證。因此，要實現(xiàn)人工智能，就必須將推理的功能賦予機(jī)器，實現(xiàn)機(jī)器推理。幾乎所有的人工智能領(lǐng)域都與推理有關(guān)。數(shù)學(xué)家吳文俊教授 —— 吳氏方法。命題代表人 們進(jìn)行思維時的一種判斷，或者是否定，或者是肯定。 S1：我有名字 S2：你有名字 所有的人都有名字： SI?S2 ?S3 ?… 2022/8/17 10 、函數(shù)、量詞（ 3） 謂詞 (predicate)： 一般形式為 P（ x1, x2 ,… , xn ） P為 謂詞名， 用于刻畫個體的性質(zhì)、狀態(tài) 或個體間的關(guān)系。 謂詞 D(father(x) ): 表示 x的父親是醫(yī)生，值為真或假。 即 ?x （ P（ x） ? … ） 例 ：對于所有的自然數(shù)，均有 x+yx 也可以用函數(shù) h（ x， y） 來表示 x與 y的和 （ （ ） （ ） G(h(x,y),x)） 2022/8/17 14 、函數(shù)、量詞（ 7） 例 ：不存在最大的整數(shù)，我們可以把它表示為： 172。 I(x):x是整數(shù)。 F3:? x (E(x) ? I(s(x))) 所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)。 （ 3）只有有限步應(yīng)用（ 1）（ 2）生成的公式才是謂詞公式。 （ 1） ? x P（ x） （ 2） ? y（ G（ y） ? D（ x， y）） （ 3） ? x G(x) ? P（ x） 指導(dǎo) 變元 約束 變元 約束 變元 約束 變元 自由 變元 自由 變元 2022/8/17 21 （ 5） ? 一個變元在一個公式中既可以約束出現(xiàn)，也可以自由出現(xiàn)，為了避免混淆，通過改名規(guī)則 改名： ? 對需要改名的變元，應(yīng) 同時更改 該變元在量詞及其轄域中的 所有出現(xiàn) 。 例 (P(x) ? Q(y)) ?( 172。 則稱這些指派為公式 P在 D上的一個解釋。 2022/8/17 30 （ 14） 定義 6：謂詞公式在個體域上的永真、永假、可滿足 設(shè) P為謂詞公式， D為其個體域，對于 D中的任一解釋 I： （ 1）若 P恒為真，則稱 P在 D上永真或是 D上的永真式。這種推理十分類似于人們用自然語言推理的思維過程，因而稱為自然演繹推理。 A 逆反律 (A?B) ? (B?C) = A ? B 假言三段論 A(y) = ?xA(x) 全稱推廣規(guī)則 2022/8/17 42 子句集 命題邏輯中的歸結(jié)原理 替換與合一 謂詞邏輯中的歸結(jié)原理 2022/8/17 43 (1) 定義 1：原子謂詞公式及其否定稱為 文字 若干