【正文】 2022/8/17 1 第 5章 基于謂詞邏輯的機(jī)器推理 2022/8/17 2 目錄 機(jī)器推理概述 一階謂詞邏輯 歸結(jié)演繹推理 應(yīng)用歸結(jié)原理求取問題答案 歸結(jié)策略 歸結(jié)反演程序舉例 * Horn子句歸結(jié)與邏輯程序 非歸結(jié)演繹推理 2022/8/17 3 機(jī)器推理概述（ 1） ?機(jī)器推理： 就是計(jì)算機(jī)推理，也稱自動(dòng)推理。它是人工智能的核心課題之一。推理是人腦的一個(gè)基本功能和重要功能。幾乎所有的人工智能領(lǐng)域都與推理有關(guān)。因此，要實(shí)現(xiàn)人工智能，就必須將推理的功能賦予機(jī)器，實(shí)現(xiàn)機(jī)器推理。 ?自動(dòng)定理證明： 是機(jī)器推理的一種重要應(yīng)用，它是利用計(jì)算機(jī)證明非數(shù)值性的結(jié)果，很多非數(shù)值領(lǐng)域的任務(wù)如醫(yī)療診斷、信息檢索、規(guī)劃制定和難題求解等方法都可以轉(zhuǎn)化一個(gè)定理證明問題 。 2022/8/17 4 ?自動(dòng)定理證明的基本方法： 機(jī)器推理概述（ 2） 定理證明器 ：它是研究一切可判定問題的證明方法。魯濱遜的歸結(jié)原理。 人機(jī)交互進(jìn)行定理證明 ：計(jì)算機(jī)作為數(shù)學(xué)家的輔助工具，用計(jì)算機(jī)幫助人完成手工證明中的難以完成的煩雜的大量計(jì)算推理和窮舉。四色定理。 判定法 ：該方法是對(duì)一類問題找出統(tǒng)一的計(jì)算機(jī)上可實(shí)現(xiàn)的算法。數(shù)學(xué)家吳文俊教授 —— 吳氏方法。 自然演繹法 ：該方法依據(jù)推理規(guī)則從前提和公理中可以推出許多定理，如果待證明的定理在其中則定理得證。LT程序、證明平面幾何的程序。 2022/8/17 5 ? 基于歸結(jié)原理的自動(dòng)定理證明過程： 機(jī)器推理概述（ 3） 定理的自然語言描述 定理的謂詞公式描述 子句集 生成子句集 定理得證 應(yīng)用歸結(jié)規(guī)則＋歸結(jié)策略 自然語言處理生成謂詞公式 已知前提：（ 1）自然數(shù)都是大于零的整數(shù)。 （ 2）所有整數(shù)不是偶數(shù)就是奇數(shù)。 （ 3）偶數(shù)除以 2是整數(shù)。 結(jié)論：所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)。 2022/8/17 6 機(jī)器推理概述（ 4） ? 本章主要解決以下幾個(gè)問題： 一階謂詞邏輯及基于一階謂詞邏輯的知識(shí)表示 謂詞公式到子句集的轉(zhuǎn)換 命題邏輯和謂詞邏輯中的歸結(jié)原理 歸結(jié)策略 2022/8/17 7 謂詞、函數(shù)、量詞 謂詞公式 謂詞邏輯中的形式演繹推理 2022/8/17 8 、函數(shù)、量詞（ 1） 命題（ proposition）： 是具有真假意義的語句。命題代表人 們進(jìn)行思維時(shí)的一種判斷，或者是否定，或者是肯定。 ?命題可以用命題符號(hào)表示。 ?用命題符號(hào)可以表示簡(jiǎn)單的邏輯關(guān)系和推理。 P:今天天氣好 Q:去旅游 S1：我有名字 S2：你有名字 P?Q表示：如果今天天氣好，就去旅游。 此時(shí)，如果 P（ 今天天氣好） 成立，則可以得到結(jié)論 Q（ 去旅游 ） 2022/8/17 9 、函數(shù)、量詞（ 2） ? 對(duì)于復(fù)雜的知識(shí)，命題符號(hào)能力不夠。 ? 無法把所描述的客觀事物的結(jié)構(gòu)及邏輯特征反映出來。 ? 無法把不同事物間的共同特征表達(dá)出來。 F：老李是小李的父親。 S1：我有名字 S2：你有名字 所有的人都有名字： SI?S2 ?S3 ?… 2022/8/17 10 、函數(shù)、量詞（ 3） 謂詞 (predicate)： 一般形式為 P（ x1, x2 ,… , xn ） P為 謂詞名， 用于刻畫個(gè)體的性質(zhì)、狀態(tài) 或個(gè)體間的關(guān)系。 x1， x2 ， … ， xn是 個(gè)體， 表示某個(gè)獨(dú)立存 在的事物或者某個(gè)抽象的概念。 S(x): x是學(xué)生； P(x,y): x是 y的雙親。 個(gè)體變?cè)淖兓秶Q為 個(gè)體域 。 包攬一切事物的集合稱為 全總個(gè)體域 。 2022/8/17 11 、函數(shù)、量詞（ 4） ? 函數(shù)： 為了表達(dá)個(gè)體之間的對(duì)應(yīng)關(guān)系，引入數(shù)學(xué)中函數(shù)概念和記法。用形如 f(x1， x2， ? ，xn)來表示個(gè)體變?cè)獙?duì)應(yīng)的個(gè)體 y，并稱之為 n元個(gè)體函數(shù) ，簡(jiǎn)稱函數(shù)。 函數(shù) father(x): 值為 x的父親。 謂詞 D(father(x) ): 表示 x的父親是醫(yī)生，值為真或假。 符號(hào)約定： 謂詞－大寫字母； P(x,y) 函數(shù)－小寫字母； f(x) 變量－ x、 y、 z、 u、 v…… ； 常量－ a、 b、 c……. 。 P(a,Y) 2022/8/17 12 、函數(shù)、量詞（ 5） 表示“對(duì)個(gè)體域中所有的（或任一個(gè)）個(gè)體” 。 記為 ?x 全稱量詞 表示“在個(gè)體域中存在個(gè)體”。 記為 ?x 存在量詞 如：“凡是人都有名字” 用 M（ x）表示“ x是人”， N（ x）表示“ x有名字” ?x（ M（ x） ? N（ x）） 如：“存在不是偶數(shù)的整數(shù)” 用 G（ x）表示 “ x是整數(shù) ” ， E（ x）表示 “ x是偶數(shù) ” ? x（ G（ x） ? 172。 E（ x）） 2022/8/17 13 、函數(shù)、量詞（ 6） 用謂詞表示命題時(shí)，一般取全總個(gè)體域，再采用使用 限定謂詞的方法來指出每個(gè)個(gè)體變?cè)膫€(gè)體域。 (2)對(duì)存在量詞，把限定詞作為一個(gè)合取項(xiàng)加入。即 ? x(P(x) ?…) 例：對(duì)于所有的自然數(shù)，均有 x+yx ?x ?y（ N （ x） ? N（ y） ? S(x,y,x)） 例 ：某些人對(duì)某些食物過敏 ? x ? y(M(x) ? N(y) ?G（ x， y）） (1)對(duì)全稱量詞，把限定詞作為蘊(yùn)含式之前件加入。 即 ?x （ P（ x） ? … ） 例 ：對(duì)于所有的自然數(shù)，均有 x+yx 也可以用函數(shù) h（ x， y） 來表示 x與 y的和 （ （ ） （ ） G(h(x,y),x)） 2022/8/17 14 、函數(shù)、量詞（ 7） 例 ：不存在最大的整數(shù)，我們可以把它表示為： 172。 ? x(G(x) ? ? y（ G（ y） ? D（ x， y）） ? x(G(x) ? ? y（ G（ y） ? D（ y， x）） 用謂詞表示命題時(shí)，形式并不是固定的。 2022/8/17 15 、函數(shù)、量詞（ 8） 練習(xí)：用謂詞公式表示下述命題。 已知前提： （ 1） 自然數(shù) 都是 大于零 的 整數(shù) 。 （ 2）所有整數(shù)不是 偶數(shù) 就是 奇數(shù) 。 （ 3）偶數(shù) 除以 2是整數(shù)。 結(jié)論：所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)。 首先定義如下謂詞： N(x):x是自然數(shù)。 I(x):x是整數(shù)。 E(x):x是偶數(shù)。 O(x):x是奇數(shù)。 GZ(x):x大于零。 s(x):x除以 2。 2022/8/17 16 、函數(shù)、量詞（ 9） 將上述各語句翻譯成謂詞公式： （ 1） 自然數(shù) 都是 大于零 的 整數(shù) 。 F1: ?x (N(x)?GZ(x) ? I(x)) （ 2）所有整數(shù)不是 偶數(shù) 就是 奇數(shù) 。 F2: ?x (I(x)?(E(x) ?O(x))) （ 3）偶數(shù) 除以 2是整數(shù)。 F3:? x (E(x) ? I(s(x))) 所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)。 G: ?x (N(x)?(I(s(x)) ?O(x))) 2022/8/17 17 （ 1） 定義 1：項(xiàng) （ 1） 個(gè)體常元和變?cè)际琼?xiàng)。 （ 2） f是 n元函數(shù)符號(hào)，若 t1， t2， … ， tn是項(xiàng)，則 f（ t1， t2， … ， tn ）是項(xiàng)。 （ 3）只有有限次使用（ 1），（ 2）得到的符號(hào)串才是項(xiàng)。 用謂詞、量詞及真值連結(jié)詞可以表達(dá)相當(dāng)復(fù)雜的命題， 我們把命題的這種符號(hào)表達(dá)式稱為 謂詞公式 。 2022/8/17 18 （ 2） 定義 2：原子公式 設(shè) P為 n元謂詞符號(hào)， t1， t2， … ， tn為項(xiàng)， P （ t1 ， t2， … ， tn ）稱為原子謂詞公式，簡(jiǎn)稱原子或原 子公式。 2022/8/17 19 （ 3） 定義 3：謂詞公式 （ 1）原子公式是謂詞公式。 （ 2）若 A、 B是謂詞公式，則 A， A ? B， A ? B， A ? B， A←→ B， ?xA， ?xA也是謂詞公式。 （ 3）只有有限步應(yīng)用（ 1）（ 2）生成的公式才是謂詞公式。 謂詞公式亦稱為謂詞邏輯中的合適（式）公式，記為 Wff。 由項(xiàng)的定義，當(dāng) t1， t2， … ， tn全為個(gè)體常元時(shí)，所得的原子謂詞公式就是原子命題公式（命題符號(hào)）。所以全體命題公式也是謂詞公式。 2022/8/17 20 （ 4） ? 轄域 ：緊接于量詞之后被量詞作用（即說明）的謂詞公式稱為該量詞的轄域。 ? 指導(dǎo)變?cè)?：量詞后的變?cè)獮橹笇?dǎo)變?cè)? ? 約束變?cè)?：在一個(gè)量詞轄域中與該量詞的指導(dǎo)變?cè)嗤淖冊(cè)Q為約束變?cè)? ? 自由變?cè)?：在一個(gè)量詞轄域中與該量詞的指導(dǎo)變?cè)煌淖冊(cè)Q為自由變?cè)? （ 1） ? x P（ x） （ 2） ? y（ G（ y） ? D（ x， y）） （ 3） ? x G(x) ? P（ x） 指導(dǎo) 變?cè)? 約束 變?cè)? 約束 變?cè)? 約束 變?cè)? 自由 變?cè)? 自由 變?cè)? 2022/8/17 21 （ 5） ? 一個(gè)變?cè)谝粋€(gè)公式中既可以約束出現(xiàn)，也可以自由出現(xiàn)，為了避免混淆，通過改名規(guī)則 改名： ? 對(duì)需要改名的變?cè)?，?yīng) 同時(shí)更改 該變?cè)诹吭~及其轄域中的 所有出現(xiàn) 。 ? 新變?cè)?hào)必須是量詞轄域內(nèi) 原先沒有 的，最好是 公式中 也 未出現(xiàn) 過的。 ? x G(x) ? P（ x） ? x G(x) ? P（ y） 2022/8/17 22 （ 6） ? 謂詞公式與命題的區(qū)別與聯(lián)系 ? 謂詞公式是 命題函數(shù) 。 ? 一個(gè)謂詞公式中所有個(gè)體變?cè)涣炕?，謂詞公式就變成了一個(gè)命題。 ? 從謂詞公式得到命題的兩種方法：給謂詞中的個(gè)體變?cè)雮€(gè)體常元；把謂詞中的個(gè)體變?cè)苛炕? 例： P（ x）表示“ x是素?cái)?shù)” ?x P（ x）， ? x P（ x）， P（ a）都是命題 2022/8/17 23 （ 7） ? 一階謂詞 ：僅個(gè)體變?cè)涣炕闹^詞。 ? 二階謂詞 ：個(gè)體變?cè)涣炕?，函?shù)符號(hào)和謂詞符號(hào)也被量化。 ? P ? x P（ x） ? 全稱命題： ? x P(x)等價(jià)于 P (a1)?P(a2)? ? ?P(an) ? 特稱命題 ? x G(x)等價(jià)于 P (a1)?P(a2)? ? ? P (an) 2022/8/17 24 （ 8） 定義 4：合取范式（ Conjunctive Normal Form） 設(shè) A為如下形式的謂詞公式： B1 ? B2 ? … ? Bn 其中 Bi（ i=1,2,… ， n）形如 L1 ? L2 ?… ? Lm， Lj（ j=1， 2,… ， m）為原子公式或其否定，則 A稱為合取范式。 例 (P(x) ? Q(y)) ?( 172。P(x) ? Q(y) ?R(x,y)) ? (172。 Q(x) ? 172。 R(x,y) ) 就是一個(gè)合取范式 2022/8/17 25 （ 9） 定義 5：析取范式 （ Disjunctive Normal Form） 設(shè) A為如下形式的謂詞公式： B1 ? B2 ?… ? Bn 其中 Bi（ i=1,2,… ， n）形如 L1 ? L2 ? … ? Lm， Lj（ j=1， 2,… ， m）為原子公式或其否定，則 A稱為析取范式 。 例 (P(x) ? 172。Q(y) ? R(x,y)) ? ( 172。P(x) ? Q(y)) ?(172。P(x) ?R(x,y) ) 就是一個(gè)析取范式 2022/8/17 26 （ 10） 謂詞公式的解釋 設(shè) D為謂詞公式 P的個(gè)體域，若對(duì) P中的個(gè)體常量、函數(shù)和謂詞按如下規(guī)定賦值： （ 1）為 每個(gè)個(gè)體常量 指派 D中的一個(gè)元素； （ 2）為 每個(gè) n元函數(shù) 指派一個(gè)從 Dn到 D的映射，其中 Dn＝ {(x1,x2,?,x n)/x1,x2,?,x n ∈ D} （ 3）為 每個(gè) n元謂詞 指派一個(gè)從 Dn到 {F,T}的映射。 則稱這些指派為公式 P在 D上的一個(gè)解釋。