基于謂詞邏輯的機器推理

1、2022-2-151第第三三章章 基于謂詞邏輯的機器推理基于謂詞邏輯的機器推理2022-2-152目錄目錄3.0 3.0 機器推理概述機器推理概述3.1 3.1 一階謂詞邏輯一階謂詞邏輯3.2 3.2 歸結演繹推理歸結演繹推理3.3 3.3 應用歸結原理求取問題答案應用歸結原理求取問題答案3.4 3.4 歸結策略歸結策略3.5 3.5 歸結反演程序舉例歸結反演程序舉例* *3.6 3.6 HornHorn子句歸結與邏輯程序子句歸結與邏輯程序3.7 3.7 非歸結演繹推理非歸結演繹推理2022-2-1533.0 3.0 機器推理概述（機器推理概述（1 1）n機器推理：機器推理： 就是計算機推理，

2、也稱自動推理。它是人工智能的就是計算機推理，也稱自動推理。它是人工智能的核心課題之一。推理是人腦的一個基本功能和重要功能。核心課題之一。推理是人腦的一個基本功能和重要功能。幾乎所有的人工智能領域都與推理有關。因此，要實現(xiàn)人幾乎所有的人工智能領域都與推理有關。因此，要實現(xiàn)人工智能，就必須將推理的功能賦予機器，實現(xiàn)機器推理。工智能，就必須將推理的功能賦予機器，實現(xiàn)機器推理。n自動定理證明：自動定理證明： 是典型的機器推理問題之一，它是利用計算機證明非是典型的機器推理問題之一，它是利用計算機證明非數(shù)值性的結果，很多非數(shù)值領域的任務如醫(yī)療診斷、信息數(shù)值性的結果，很多非數(shù)值領域的任務如醫(yī)療診斷、信息檢索

3、、規(guī)劃制定和難題求解等方法都可以轉化一個定理證檢索、規(guī)劃制定和難題求解等方法都可以轉化一個定理證明問題明問題。n自動定理證明的基本方法：自動定理證明的基本方法：3.0 3.0 機器推理概述（機器推理概述（2 2）定理證明器定理證明器：它是研究一切可判定問題的證明方法。魯濱：它是研究一切可判定問題的證明方法。魯濱遜的消解原理。王湘浩教授在歸結策略研究方面有突出貢遜的消解原理。王湘浩教授在歸結策略研究方面有突出貢獻。（本章主要內(nèi)容）獻。（本章主要內(nèi)容）計算機輔助證明計算機輔助證明：計算機作為數(shù)學家的輔助工具，用計算：計算機作為數(shù)學家的輔助工具，用計算機幫助人完成手工證明中的、難以完成的煩雜的大量計

4、算、機幫助人完成手工證明中的、難以完成的煩雜的大量計算、推理和窮舉。阿普爾等人證明四色定理（推理和窮舉。阿普爾等人證明四色定理（124124年未解決的）。年未解決的）。判定法判定法：該方法是對一類問題找出統(tǒng)一的計算機上可實現(xiàn)：該方法是對一類問題找出統(tǒng)一的計算機上可實現(xiàn)的算法。數(shù)學家吳文俊教授（吳氏方法）證明初等幾何定的算法。數(shù)學家吳文俊教授（吳氏方法）證明初等幾何定理，將幾何問題代數(shù)化。理，將幾何問題代數(shù)化。 自然演繹法自然演繹法：該方法依據(jù)推理規(guī)則從前提和公理中可以推：該方法依據(jù)推理規(guī)則從前提和公理中可以推出許多定理，如果待證明的定理在其中則定理得證。紐厄出許多定理，如果待證明的定理在其中則

5、定理得證。紐厄爾等人的爾等人的LTLT程序、籍勒洛特證明平面幾何定理的程序。程序、籍勒洛特證明平面幾何定理的程序。2022-2-155n基于歸結原理的自動定理證明過程：基于歸結原理的自動定理證明過程：3.0 3.0 機器推理概述（機器推理概述（3 3）定理的謂詞公式描述定理的謂詞公式描述生成子句集生成子句集 子句集表示子句集表示 推出空子句推出空子句 定理得證定理得證應用歸結規(guī)則歸結策略應用歸結規(guī)則歸結策略定理的自然語言描述定理的自然語言描述自然語言處理生成謂詞公式自然語言處理生成謂詞公式2022-2-1563.0 3.0 機器推理概述（機器推理概述（4 4）n本章主要解決以下幾個問題：本章主

6、要解決以下幾個問題：1、一階謂詞邏輯及基于一階謂詞邏輯的知識表示、一階謂詞邏輯及基于一階謂詞邏輯的知識表示2、謂詞公式到子句集的轉換、謂詞公式到子句集的轉換3、命題邏輯和謂詞邏輯中的歸結原理、命題邏輯和謂詞邏輯中的歸結原理4、歸結策略、歸結策略2022-2-1573.13.1一階謂詞邏輯一階謂詞邏輯3.1.1 3.1.1 謂詞、函數(shù)、量詞謂詞、函數(shù)、量詞3.1.2 3.1.2 謂詞公式謂詞公式3.1.3 3.1.3 謂詞邏輯中的形式演繹推理謂詞邏輯中的形式演繹推理2022-2-1583.1.13.1.1謂詞、函數(shù)、量詞（謂詞、函數(shù)、量詞（1 1）命題：命題：是具有真假意義的語句。命題代表人們進

7、行思維時的是具有真假意義的語句。命題代表人們進行思維時的一種判斷，或者是否定，或者是肯定。一種判斷，或者是否定，或者是肯定。命題可以用命題符號表示。命題可以用命題符號表示。用命題符號可以表示簡單的邏輯關系和推理。用命題符號可以表示簡單的邏輯關系和推理。 P:今天天氣好今天天氣好 Q:去旅游去旅游 S1：我有名字：我有名字 S2：你有名字：你有名字PQ表示：如果今天天氣好，就去旅游。表示：如果今天天氣好，就去旅游。此時，如果此時，如果P（今天天氣好）今天天氣好）成立，則可以得到結論成立，則可以得到結論Q（去旅游去旅游）2022-2-1593.1.13.1.1謂詞、函數(shù)、量詞（謂詞、函數(shù)、量詞（2

8、 2）n對于復雜的知識，命題符號能力不夠。對于復雜的知識，命題符號能力不夠。n無法把所描述的客觀事物的結構及邏輯特征反映出無法把所描述的客觀事物的結構及邏輯特征反映出來。來。n無法把不同事物間的共同特征表達出來。無法把不同事物間的共同特征表達出來。F：老李是小李的父親。：老李是小李的父親。S1：我有名字：我有名字 S2：你有名字：你有名字所有的人都有名字：所有的人都有名字： SI S2 S3 2022-2-15103.1.13.1.1謂詞、函數(shù)、量詞（謂詞、函數(shù)、量詞（3 3）謂詞：謂詞：一般形式為一般形式為P（x1， x2 ， xn ） P為為謂詞名，謂詞名，用于刻畫個體的性質(zhì)、狀態(tài)用于刻畫

9、個體的性質(zhì)、狀態(tài) 或個體間的關系。或個體間的關系。 x1， x2 ， xn是是個體，個體，表示某個獨立存表示某個獨立存 在的事物或者某個抽象的概念。在的事物或者某個抽象的概念。 S(x): x是學生；是學生； P(x,y): x是是y的雙親。的雙親。個體域：個體域：個體變元的變化范圍稱為個體域。個體變元的變化范圍稱為個體域。 包攬一切事物的集合稱為全總個體域。包攬一切事物的集合稱為全總個體域。2022-2-15113.1.13.1.1謂詞、函數(shù)、量詞（謂詞、函數(shù)、量詞（4 4）n函數(shù)：函數(shù)：為了表達個體之間的對應關系，引入數(shù)為了表達個體之間的對應關系，引入數(shù)學中函數(shù)概念和記法。用形如學中函數(shù)概

10、念和記法。用形如f f（x1x1，x2x2，xnxn）來表示個體變元對應的個體來表示個體變元對應的個體y，并稱之為，并稱之為n元個體函數(shù)元個體函數(shù)，簡稱函數(shù)。，簡稱函數(shù)。函數(shù)函數(shù) father(x): 值為值為x的父親。的父親。謂詞謂詞D(father(x) ): 表示表示x的父親是醫(yī)生，值為真或假。的父親是醫(yī)生，值為真或假。符號約定：符號約定：謂詞大寫字母；謂詞大寫字母； P(x,y) 函數(shù)小寫字母；函數(shù)小寫字母；f(x) 變量變量 x、y、z、u、v； 常量常量a、b、c.。 P(a,Y)2022-2-15123.1.13.1.1謂詞、函數(shù)、量詞（謂詞、函數(shù)、量詞（5 5）表示表示“對個體

11、域中所有的（或任一個）個體對個體域中所有的（或任一個）個體” 。 記為記為 x 全稱量詞全稱量詞 表示表示“在個體域中存在個體在個體域中存在個體”。 記為記為 x存在量詞存在量詞 如：如：“凡是人都有名字凡是人都有名字”可表示為可表示為 ： x（M（x） N（x） 其中，其中，M（x）表示）表示“x是人是人”，N（x）表示）表示“x有名字有名字”。M（x）是限定謂詞，因為）是限定謂詞，因為x取全總個體域。取全總個體域。如果如果x取成人類集合，則該命題課表示為：取成人類集合，則該命題課表示為： x N（x）如：如：“存在不是偶數(shù)的整數(shù)存在不是偶數(shù)的整數(shù)”可表示為可表示為 x（G（x） E（x）

12、其中，其中，G（x）表示）表示“x是整數(shù)是整數(shù)”，E（x）表示）表示“x是偶數(shù)是偶數(shù)”2022-2-15133.1.13.1.1謂詞、函數(shù)、量詞（謂詞、函數(shù)、量詞（6 6）用謂詞表示命題時，一般取全總個體域，再采用使用用謂詞表示命題時，一般取全總個體域，再采用使用限定謂詞的方法來指出每個個體變元的個體域，有兩條：限定謂詞的方法來指出每個個體變元的個體域，有兩條： (2)對存在量詞，把限定詞作為一個合取項加入。對存在量詞，把限定詞作為一個合取項加入。 即即 x(P(x) )例：對于所有的自然數(shù)，均有例：對于所有的自然數(shù)，均有x+yx (1) x y (N (x) N(y) S(x,y,x) (2

13、) x y ( N (x) N(y)G( s(x,y),x) （使用函數(shù)）（使用函數(shù)）例：某些人對某些食物過敏例：某些人對某些食物過敏 x y ( M(x) N(x) G(x,y)(1)對全稱量詞，把限定詞作為蘊含式之前件加入。對全稱量詞，把限定詞作為蘊含式之前件加入。 即即 x （P（x） ）2022-2-15143.1.13.1.1謂詞、函數(shù)、量詞（謂詞、函數(shù)、量詞（7 7）例：不存在最大的整數(shù)，我們可以給出兩種它表示：例：不存在最大的整數(shù)，我們可以給出兩種它表示： 可以翻譯為：存在一個整數(shù)比任意整數(shù)都大的否定：可以翻譯為：存在一個整數(shù)比任意整數(shù)都大的否定： x(G(x) y（G（y） D

14、（x，y）也可以翻譯為：對任意整數(shù)都存在一個比它大的整數(shù)：也可以翻譯為：對任意整數(shù)都存在一個比它大的整數(shù)： x(G(x) y（G（y） D（y，x）用謂詞表示命題時，形式并不是固定的。用謂詞表示命題時，形式并不是固定的。2022-2-15153.1.13.1.1謂詞、函數(shù)、量詞（謂詞、函數(shù)、量詞（8 8）補充例：用謂詞公式表示下述命題。補充例：用謂詞公式表示下述命題。已知前提：已知前提：（1）自然數(shù)自然數(shù)都是都是大于零大于零的的整數(shù)整數(shù)。（2）所有整數(shù)不是）所有整數(shù)不是偶數(shù)偶數(shù)就是就是奇數(shù)奇數(shù)。（3）偶數(shù)）偶數(shù)除以除以2是整數(shù)。是整數(shù)。結論：所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)。結論：所有自然

15、數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)。2022-2-15163.1.13.1.1謂詞、函數(shù)、量詞（謂詞、函數(shù)、量詞（9 9）首先定義如下謂詞：首先定義如下謂詞： N(x):xN(x):x是自然數(shù)。是自然數(shù)。 I(x):xI(x):x是整數(shù)。是整數(shù)。 E(x):xE(x):x是偶數(shù)。是偶數(shù)。 O(x):xO(x):x是奇數(shù)。是奇數(shù)。 GZ(x):xGZ(x):x大于零。大于零。 s(x):xs(x):x除以除以2 2。將上述各語句翻譯成謂詞公式：將上述各語句翻譯成謂詞公式： F1:F1:自然數(shù)都是大于零的整數(shù)。自然數(shù)都是大于零的整數(shù)。 x (N(x)x (N(x)GZ(x) GZ(x) I(x) I(x

16、) F2: F2:所有整數(shù)不是偶數(shù)就是奇數(shù)。所有整數(shù)不是偶數(shù)就是奇數(shù)。 x (I(x)x (I(x)(E(x) (E(x) O(x) O(x) F3: F3:偶數(shù)除以偶數(shù)除以2是整數(shù)是整數(shù) 。 x (E(x) x (E(x) I(s(x) I(s(x) G: G:所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù) x (N(x)x (N(x)(I(s(x) (I(s(x) O(x) O(x) 2022-2-1517練習練習：將下列序數(shù)用謂詞公式表示：將下列序數(shù)用謂詞公式表示：n人死不會復生人死不會復生n人總是要死的人總是要死的n人的壽命不會超過人的壽命不會超過200歲歲參

17、考答案：參考答案：n x x t t1 1 t t2 2 ( MAN(x) ( MAN(x) DIED( DIED(t t1 1) ) GT( GT(t t2 2 , ,t t1 1) ) D DIED(x,IED(x,t t2 2)n x x t t1 1 t t2 2 ( MAN(x) ( MAN(x) BORN(x, BORN(x,t t1 1) ) GT( GT(t t2 2 , ,t t1 1) ) D DIED(x,IED(x,t t2 2)n x x t t1 1 t t2 2 ( MAN(x) ( MAN(x) BORN(x, BORN(x,t t1 1) ) D DIED(x

18、,IED(x,t t2 2) ) LTLT(d(d(t t2 2 , , t t1 1) ,200) ) ,200) 或或n x x t t1 1 t t2 2 ( MAN(x) ( MAN(x) BORN(x, BORN(x,t t1 1) ) GT(d( GT(d(t t2 2 , , t t1 1) ,200 ) ) ,200 ) D DIED(x,IED(x,t t2 2)3.1.13.1.1謂詞、函數(shù)、量詞（謂詞、函數(shù)、量詞（1010）2022-2-1518n基于歸結原理的自動定理證明過程：基于歸結原理的自動定理證明過程：回顧回顧定理的定理的謂詞公式謂詞公式描述描述生成子句集生成子句

19、集 子句集表示子句集表示 推出空子句推出空子句 定理得證定理得證應用歸結規(guī)則歸結策略應用歸結規(guī)則歸結策略定理的自然語言描述定理的自然語言描述自然語言處理生成謂詞公式自然語言處理生成謂詞公式2022-2-1519本次課內(nèi)容提要：本次課內(nèi)容提要：n謂詞公式的形式定義謂詞公式的形式定義n謂詞公式的真值確定謂詞公式的真值確定n基于謂詞公式形式的形式演繹推理基于謂詞公式形式的形式演繹推理2022-2-15203.1.23.1.2謂詞公式（謂詞公式（1 1）定義定義1：項：項（1）個體常元和變元都是項。個體常元和變元都是項。（2）f是是n元函數(shù)符號，若元函數(shù)符號，若t1，t2，tn是項，則是項，則 f（

20、t1，t2， tn ）是項。）是項。（3）只有有限次使用（）只有有限次使用（1）和（）和（2）得到的符號串才是項。）得到的符號串才是項。定義定義2：原子公式：原子公式 設設P為為n元謂詞符號，元謂詞符號， t1，t2，tn為項，為項， P （ t1 ，2，tn ）稱為原子謂詞公式，簡稱原子或原）稱為原子謂詞公式，簡稱原子或原子公式。子公式。2022-2-15213.1.23.1.2謂詞公式（謂詞公式（2 2）定義定義3：謂詞公式：謂詞公式（1）原子公式是謂詞公式。）原子公式是謂詞公式。（2）若）若A、B是謂詞公式，則是謂詞公式，則A、A B、A B、A B、 AB、 xA，、，、 xA也是謂詞

21、公式。也是謂詞公式。（3）只有有限步應用（）只有有限步應用（1）（）（2）生成的公式才是謂詞公式。）生成的公式才是謂詞公式。如上定義的謂詞公式亦稱為謂詞邏輯中的合適（式）公式，如上定義的謂詞公式亦稱為謂詞邏輯中的合適（式）公式，記為記為Wff。 謂詞公式的幾個相關概念謂詞公式的幾個相關概念 2022-2-15223.1.23.1.2謂詞公式（謂詞公式（3 3）n轄域轄域：緊接于量詞之后被量詞作用（即說明）：緊接于量詞之后被量詞作用（即說明）的謂詞公式稱為該量詞的轄域。的謂詞公式稱為該量詞的轄域。n指導變元指導變元：量詞后的變元為指導變元。：量詞后的變元為指導變元。n約束變元約束變元：在一個量詞

22、轄域中與該量詞的指導：在一個量詞轄域中與該量詞的指導變元相同的變元稱為約束變元。變元相同的變元稱為約束變元。n自由變元自由變元：在一個量詞轄域中與該量詞的指導：在一個量詞轄域中與該量詞的指導變元不同的變元稱為約束變元。變元不同的變元稱為約束變元。 （1） x P（x） （2） y（G（y） D（x，y） （3） x G(x) P（x） 指導指導變元變元約束約束變元變元約束約束變元變元約束約束變元變元自由自由變元變元自由自由變元變元2022-2-15233.1.23.1.2謂詞公式（謂詞公式（4 4）n一個變元在一個公式中既可以約束出現(xiàn)，也一個變元在一個公式中既可以約束出現(xiàn)，也可以自由出現(xiàn)，例如

23、：可以自由出現(xiàn)，例如： x G(x) P（x） n通過通過改名規(guī)則改名規(guī)則可以避免混淆：可以避免混淆：n對需要改名的變元，應同時更改該變元在對需要改名的變元，應同時更改該變元在量詞及其轄域中的所有出現(xiàn)。量詞及其轄域中的所有出現(xiàn)。n新變元符號必須是量詞轄域內(nèi)原先沒有的，新變元符號必須是量詞轄域內(nèi)原先沒有的，最好是公式中也未出現(xiàn)過的。最好是公式中也未出現(xiàn)過的。n x G(x) P（y）謂詞公式與命題的區(qū)別與聯(lián)系謂詞公式與命題的區(qū)別與聯(lián)系2022-2-15243.1.23.1.2謂詞公式（謂詞公式（5 5）n謂詞公式與命題的區(qū)別與聯(lián)系謂詞公式與命題的區(qū)別與聯(lián)系n謂詞公式是謂詞公式是命題函數(shù)命題函數(shù)。

24、n一個謂詞公式中所有個體變元被量化，就變成一個謂詞公式中所有個體變元被量化，就變成一個命題。一個命題。n從謂詞公式得到命題的從謂詞公式得到命題的兩種方法兩種方法：給謂詞中的：給謂詞中的個體變元代入個體常元；把謂詞中的個體變元個體變元代入個體常元；把謂詞中的個體變元全部量化。全部量化。例：例：P（x）表示）表示“x是素數(shù)是素數(shù)” x P（x），）， x P（x），）， P P（a a）都是命題。）都是命題。2022-2-15253.1.23.1.2謂詞公式（謂詞公式（6 6）n全稱命題：全稱命題： x P(xx P(x）等價于）等價于P P(a(a1 1) ) P P(a(a2 2) ) P P

25、(a(an n) ) n特稱命題特稱命題 x G(x) x G(x) 等價于等價于P P(a(a1 1) ) P P(a(a2 2) ) P P(a(an n) )n一階謂詞一階謂詞：僅個體變元被量化的謂詞。：僅個體變元被量化的謂詞。n二階謂詞二階謂詞：個體變元被量化，函數(shù)符號和謂詞符：個體變元被量化，函數(shù)符號和謂詞符號也被量化。號也被量化。 P x P（x）n約定，以后討論的謂詞公式中沒有自由變元。約定，以后討論的謂詞公式中沒有自由變元。2022-2-15263.1.23.1.2謂詞公式（謂詞公式（7 7）定義定義4：合取范式：合取范式 設設A為如下形式的謂詞公式：為如下形式的謂詞公式： B

26、1 B2 Bn其中其中Bi（i=1,2,，n）形如）形如L1 L2 Lm，Lj（j=1，2,，m）為原子公式或其否定，則）為原子公式或其否定，則A稱為合取范式。稱為合取范式。例例 (P(x) Q(y) ( P(x) Q(y) R(x,y) ( Q(x) R(x,y) ) 就是一個合取范式就是一個合取范式2022-2-15273.1.23.1.2謂詞公式（謂詞公式（8 8）定義定義5：析取范式：析取范式設設A為如下形式的謂詞公式：為如下形式的謂詞公式： B1 B2 Bn其中其中Bi（i=1,2,，n）形如）形如L1 L2 Lm，Lj（j=1，2,，m）為原子公式或其否定，則）為原子公式或其否定，

27、則A稱為合取范式稱為合取范式。例例 (P(x) Q(y) R(x,y) ( P(x) Q(y) (P(x) R(x,y) ) 就是一個析取范式就是一個析取范式2022-2-15283.1.23.1.2謂詞公式（謂詞公式（9 9）謂詞公式的解釋：謂詞公式的解釋： 設設D D為謂詞公式為謂詞公式P P的個體域，若對的個體域，若對P P中的個體常量、函數(shù)和中的個體常量、函數(shù)和謂詞按如下規(guī)定賦值：謂詞按如下規(guī)定賦值： （1 1）為）為每個個體常量每個個體常量指派指派D D中的一個元素；中的一個元素； （2 2）為）為每個每個n n元函數(shù)元函數(shù)指派一個從指派一個從D Dn n到到D D的映射，其中的映射

28、，其中 D Dn n(x(x1 1,x,x2 2,x,xn n)|x)|x1 1,x,x2 2,x,xn n DD （3 3）為）為每個每個n n元謂詞元謂詞指派一個從指派一個從D Dn n到到F,TF,T的映射。的映射。 則稱這些指派為公式則稱這些指派為公式P P在在D D上的一個解釋。上的一個解釋。 謂詞公式的真值是通過對該謂詞公式的解釋確定的。謂詞公式的真值是通過對該謂詞公式的解釋確定的。2022-2-15293.1.23.1.2謂詞公式（謂詞公式（1010）例：設個體域例：設個體域D D1,2,1,2,求公式求公式A A x x y Py P（x x，y y）在在D D上的解上的解釋，

29、并指出在每一種解釋下公式釋，并指出在每一種解釋下公式A A的真值。的真值。解：公式里沒有個體常量和函數(shù)，所以直接為謂詞指派真值，設解：公式里沒有個體常量和函數(shù)，所以直接為謂詞指派真值，設為為: P（1，1）T P（1，2）F P（2，1）T P（2，2）F 這就是這就是A A在在D D上的一個解釋。上的一個解釋。在此解釋下，在此解釋下， 當當x x1 1時有時有y y1 1使使P P（x x，y y）的真值為）的真值為T T； 當當x x2 2時有時有y y1 1使使P P（x x，y y）的真值為）的真值為 T T；即對于即對于D D中的所有中的所有X X都有都有y y1 1使使P P（x

30、x，y y）的真值為）的真值為T T，所以在此解釋下公式所以在此解釋下公式A A的真值為的真值為T T。該公式共有該公式共有8 8種解釋。為什么？有使種解釋。為什么？有使A A為假的解釋嗎？為假的解釋嗎？2022-2-15303.1.23.1.2謂詞公式（謂詞公式（1111）例：例：設個體域設個體域D D1,2,1,2, 求公式求公式A A x x P P（x x）Q Q（f(x),bf(x),b）在在D D上的解釋，并指上的解釋，并指出在每一種解釋下公式出在每一種解釋下公式A A的真值。的真值。解：解：n為個體常量為個體常量b b指派指派D D中的值：中的值： b=1 b=1 n為函數(shù)為函數(shù)

31、f(x)f(x)指派指派D D中的值：中的值： f(1)=2,f(2)=1f(1)=2,f(2)=1n 對謂詞指派真值為：對謂詞指派真值為： P(1)=F, P(2)=T,Q(1,1)=T, Q(2,1)=FP(1)=F, P(2)=T,Q(1,1)=T, Q(2,1)=F 2022-2-15313.1.23.1.2謂詞公式（謂詞公式（1212）在此解釋下，在此解釋下， 當當x1時有：時有： P(1)=F, Q(f(1),1)=Q(2,1)=FP(1)=F, Q(f(1),1)=Q(2,1)=F 所以所以P P（x x）Q Q（f(x),bf(x),b）為）為T T。 當當x x2 2時有時有

32、 P(2)=T, Q(f(2),1)=Q(1,1)=TP(2)=T, Q(f(2),1)=Q(1,1)=T 所以所以P P（x x）Q Q（f(x),bf(x),b）為）為T T。 即對個體域即對個體域D D中的所有中的所有x x均有均有P P（x x）Q Q（f(x),bf(x),b），所以公式），所以公式B B在此解釋下的真值為在此解釋下的真值為T T。n該公式共有多少種解釋？請大家再說出該公式共有多少種解釋？請大家再說出2 2種解釋。該公式是永種解釋。該公式是永真式嗎？真式嗎？2022-2-15323.1.23.1.2謂詞公式（謂詞公式（1313）定義定義6：謂詞公式在個體域上的永真、永

33、假、可滿足：謂詞公式在個體域上的永真、永假、可滿足設設P為謂詞公式，為謂詞公式，D為其個體域，對于為其個體域，對于D中的任一解釋中的任一解釋I：（1）若）若P恒為真，則稱恒為真，則稱P在在D上永真或是上永真或是D上的永真式。上的永真式。（2）若）若P恒為假，則稱恒為假，則稱P在在D上永假或是上永假或是D上的永假式。上的永假式。（3）若至少有一個解釋，可是）若至少有一個解釋，可是P為真，則稱為真，則稱P在在D上是上是可滿足式可滿足式。2022-2-15333.1.23.1.2謂詞公式（謂詞公式（1414）定義定義7：謂詞公式全總個體域上的永真、永假、可滿足：謂詞公式全總個體域上的永真、永假、可滿

34、足設設P為謂詞公式，對于任何個體域：為謂詞公式，對于任何個體域：（1）若）若P都永真，則稱都永真，則稱P為永真式。為永真式。（2）若）若P都永假，則稱都永假，則稱P為永假式。為永假式。（3）若）若P都可滿足，則稱都可滿足，則稱P為可滿足式。為可滿足式。2022-2-15343.1.33.1.3謂詞邏輯中的形式演繹推理（謂詞邏輯中的形式演繹推理（1 1）n自然演繹推理自然演繹推理 利用一階謂詞推理規(guī)則的符號表示形式，可以把關于自利用一階謂詞推理規(guī)則的符號表示形式，可以把關于自然語言的邏輯推理問題，轉化為符號表達式的推演變換。這然語言的邏輯推理問題，轉化為符號表達式的推演變換。這種推理十分類似于人

35、們用自然語言推理的思維過程，因而稱種推理十分類似于人們用自然語言推理的思維過程，因而稱為自然演繹推理。為自然演繹推理。 常用邏輯等價式常用邏輯等價式 常用邏輯蘊含式常用邏輯蘊含式 2022-2-1535常用邏輯等價式（常用邏輯等價式（1 1）2022-2-1536常用邏輯等價式（常用邏輯等價式（2 2）2022-2-1537常用邏輯等價式（常用邏輯等價式（3 3）2022-2-1538常用邏輯等價式（常用邏輯等價式（4 4）2022-2-1539常用邏輯蘊含式（常用邏輯蘊含式（1)1)2022-2-1540常用邏輯蘊含式常用邏輯蘊含式(2)(2)2022-2-15413.1.33.1.3謂詞邏

36、輯中的形式演繹推理（謂詞邏輯中的形式演繹推理（2 2）例例3.4 設有前提：設有前提： （1）凡是大學生都學過計算機；）凡是大學生都學過計算機； （2）小王是大學生。）小王是大學生。 試問：小王學過計算機嗎？試問：小王學過計算機嗎？)x(M)x(S(x)( 1)a(S)(2)a(M)a(S)(2)a(S)(3)a(M)(4解：令解：令S（x）：x是大學生是大學生M（x）：x學過計算機；學過計算機；a：小王小王上面命題用謂詞公式表示為：上面命題用謂詞公式表示為：)x(M)x(S(x)( 1前提前提(1),US前提前提(2),(3),I3我們進行形式推理：我們進行形式推理：M(a)，即小王學過計算

37、機。，即小王學過計算機。xA(x)=A(y)y是個體域中任一確定元素是個體域中任一確定元素(A B) A = B2022-2-15423.1.33.1.3謂詞邏輯中的形式演繹推理（謂詞邏輯中的形式演繹推理（3 3）例例3.5 證明證明 是是 和和 邏輯邏輯 結果。結果。)b, a(P )y, x(W)y, x(P(yx )b, a(W )y, a(W)y, a(P(y)( 2)b, a(W)b, a(P)(3)b, a(P)( 5證：證：)y, x(W)y, x(P(yx)( 1前提前提(1),US(2),US)b, a(W)( 4前提前提(3),(4),I4(A B) B = A 拒取式拒取

38、式2022-2-15433.1.33.1.3謂詞邏輯中的形式演繹推理（謂詞邏輯中的形式演繹推理（4 4）練習：練習： 證明證明 )x(P)x(R(x)x(Q)x(R(x)x(Q)x(P(x 證：證：)x(Q)x(P(x)( 1前提前提(1),US(2),E24(3),(5),I6)y(Q)y(P)(2)()()3(yPyQ)y(Q)y(R)( 5)y(P)y(R)( 6)x(P)x(R(x)( 7)x(Q)x(R(x)( 4前提前提(4),US(1),UGAB = B A 逆反律逆反律(AB) (BC) = A B 假言三段論假言三段論A(y) = xA(x) 全稱推廣規(guī)則全稱推廣規(guī)則2022

39、-2-1544n基于歸結原理的自動定理證明過程：基于歸結原理的自動定理證明過程：回顧回顧定理的謂詞公式描述定理的謂詞公式描述生成子句集生成子句集 子句集表示子句集表示 推出空子句推出空子句 定理得證定理得證應用歸結規(guī)則歸結策略應用歸結規(guī)則歸結策略定理的自然語言描述定理的自然語言描述自然語言處理生成謂詞公式自然語言處理生成謂詞公式2022-2-1545n需要的預備知識需要的預備知識謂詞公式的定義謂詞公式的定義邏輯等價式邏輯等價式邏輯蘊涵式邏輯蘊涵式n本次課程內(nèi)容提要：本次課程內(nèi)容提要：任意謂詞公式變換成子句集任意謂詞公式變換成子句集命題邏輯中的歸結原理命題邏輯中的歸結原理2022-2-15463

40、.23.2歸結演繹推理歸結演繹推理3.2.1 3.2.1 子句集子句集3.2.2 3.2.2 命題邏輯中的歸結原理命題邏輯中的歸結原理3.2.3 3.2.3 替換與合一替換與合一3.2.4 3.2.4 謂詞邏輯中的歸結原理謂詞邏輯中的歸結原理2022-2-15473.2.13.2.1子句集子句集(1)(1)定義定義1：原子謂詞公式及其否定稱為：原子謂詞公式及其否定稱為文字。文字。如如P(x), Q (x) 若干個文字的一個析取式稱為一個若干個文字的一個析取式稱為一個子句。子句。如如P (x) Q (x) 由由r個文字組成的子句叫個文字組成的子句叫r-文字子句。文字子句。 1-文字子句叫文字子句

41、叫單元子句。單元子句。如如P (x), Q (x) 不含任何文字的子句稱為不含任何文字的子句稱為空子句。空子句。記為記為或或NIL。 子句的集合叫子句的集合叫子句集，子句集，子句之間的關系是與關系。子句之間的關系是與關系。如：如： I(z) R(z), I(A), R(x) L(x), D(y) 歸結原理是基于子句集的，所以要考慮任意謂詞公式到子句集歸結原理是基于子句集的，所以要考慮任意謂詞公式到子句集的變換。的變換。2022-2-1548思考：謂詞公式與子句集形式上的不同思考：謂詞公式與子句集形式上的不同子句集子句集：無量詞約束；無量詞約束； 元素只是文字的析??；元素只是文字的析??； 否定符

42、只作用于單個文字；否定符只作用于單個文字； 元素間默認為合取。元素間默認為合取。n謂詞公式形式：謂詞公式形式： x y P(x，y) yQ(x,y) R(x,y)n對應的子句集形式：對應的子句集形式： P(x，f(x) Q(x,g(x) , P(y，f(y) R(y,g(y)請注意：子句集有什么特點？請注意：子句集有什么特點？2022-2-15493.2.13.2.1子句子句集集(2)(2)定義定義2：對一個謂詞公式：對一個謂詞公式G，通過以下步驟所得的子句集，通過以下步驟所得的子句集 S，稱為，稱為G的的子句集子句集。 例例3.7： x y P(x，y) yQ(x,y) R(x,y)由第一步

43、可得：由第一步可得： x y P(x，y) y Q(x,y) R(x,y)1、消蘊含詞和等值詞、消蘊含詞和等值詞理論根據(jù)：理論根據(jù)：AB A B A B (A B) ( B A)蘊含表達式蘊含表達式等價表達式等價表達式2022-2-15503.2.13.2.1子句子句集集(3)(3)由上步：由上步： x y P(x，y) y Q(x,y) R(x,y) 可得：可得： x y P(x，y) y Q(x,y) R(x,y) x y P(x，y) zQ(x,z) R(x,z) 3、適當改名，使變量標準化適當改名，使變量標準化即：對于不同的約束，對應于不同的變量即：對于不同的約束，對應于不同的變量2、

44、移動否定詞作用范圍，使其僅作用于原子公式移動否定詞作用范圍，使其僅作用于原子公式理論根據(jù)：理論根據(jù)： (A) A (A B) A B (A B) A B xP(x) xP(x) xP(x) xP (x)雙重否定律雙重否定律摩根定律摩根定律量詞轉換定律量詞轉換定律2022-2-15513.2.13.2.1子句集子句集(4)(4)4、 消去存在量詞消去存在量詞 (Skolem化）化）,同時進行變元替換同時進行變元替換 。 原則：對于一個受存在量詞約束的變量，如果它原則：對于一個受存在量詞約束的變量，如果它不受全稱量詞約不受全稱量詞約束束，則該變量用一個常量代替（這個常量叫，則該變量用一個常量代替（

45、這個常量叫Skolem常量常量）；如果它）；如果它受受全稱量詞約束全稱量詞約束，則該變量用一個函數(shù)代替（這個函數(shù)叫，則該變量用一個函數(shù)代替（這個函數(shù)叫Skolem函數(shù)函數(shù)） 。 由上步：由上步： x y P(x，y) zQ(x,z) R(x,z) 可得：可得： x P(x，f(x) Q(x,g(x) R(x,g(x) P(x，f(x) Q(x,g(x) R(x,g(x)5、消去所有全稱量詞。、消去所有全稱量詞。思考：思考：設設M(u,v)表示表示u是是v的母親。對公式的母親。對公式 y M(y, eva) 和和 x y M(y,x) 中的存在量詞進行中的存在量詞進行Skolem代換，比較兩種替

46、換結果的不同。代換，比較兩種替換結果的不同。2022-2-15523.2.13.2.1子句集子句集(5)(5)由上步：由上步： P(x，f(x) Q(x,g(x) R(x,g(x)可得：可得： P(x，f(x) Q(x,g(x) P(x，f(x) R(x,g(x) P(x，f(x) Q(x,g(x) P(y，f(y) R(y,g(y)7、適當改名，使子句間無同名變元適當改名，使子句間無同名變元 P(x，f(x) Q(x,g(x) , P(y，f(y) R(y,g(y)8、消去合取詞，以子句為元素組成一個集合消去合取詞，以子句為元素組成一個集合S6、化公式為合取范式、化公式為合取范式 理論依據(jù)：

47、理論依據(jù)： A （B C） （A B） （A C） （ A B ） C （A C） （B C）2022-2-15533.2.13.2.1子句集子句集(6)(6) 子句集子句集：無量詞約束；（無量詞約束；（3，4，5） 元素只是文字的析取；（元素只是文字的析取；（1） 否定符只作用于單個文字；（否定符只作用于單個文字；（2） 元素間默認為合取。（元素間默認為合取。（6，7，8）化子句集的步驟總結：化子句集的步驟總結：1、消去蘊含詞和等值詞。、消去蘊含詞和等值詞。2、使否定詞僅作用于原子公式。、使否定詞僅作用于原子公式。3、適當改名使量詞間不含同名指導變元。、適當改名使量詞間不含同名指導變元。4、

48、消去存在量詞。、消去存在量詞。5、消去全稱量詞。、消去全稱量詞。6、化公式為合取范式。、化公式為合取范式。7、適當改名，使子句間無同名變元。適當改名，使子句間無同名變元。8、消去合取詞，以子句為元素組成一個集合、消去合取詞，以子句為元素組成一個集合S。2022-2-15543.2.13.2.1子句集子句集(7)(7)練習：已知前提：練習：已知前提：（1）自然數(shù)都是大于零的整數(shù)。）自然數(shù)都是大于零的整數(shù)。（2）所有整數(shù)不是偶數(shù)就是奇數(shù)。）所有整數(shù)不是偶數(shù)就是奇數(shù)。（3）偶數(shù)除以）偶數(shù)除以2是整數(shù)。是整數(shù)。結論：所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)。結論：所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)。 上

49、述定理的謂詞公式表示：上述定理的謂詞公式表示： F1: F1: x (N(x)x (N(x)GZ(x) GZ(x) I(x) I(x) F2: F2: x (I(x)x (I(x)(E(x)(E(x) O(x) O(x) F3: F3: x (E(x) x (E(x) I(s(x) I(s(x) G: G: x (N(x)x (N(x)(I(s(x) (I(s(x) O(x)O(x)試將試將 F1F1、F2F2、F3F3、G G 化為子句集?；癁樽泳浼?。2022-2-15553.2.13.2.1子句集子句集(8)(8)解：解：F1F1、F2F2、 F3F3、GG的子句集為：的子句集為：（1 1

50、） N(x) N(x) GZ(x) GZ(x)（2 2） N(y) N(y) I(y) I(y)（3 3） I(z) I(z) E(z) E(z) O(z)O(z) F2F2（4 4） E(u) E(u) I(s(u) I(s(u) F3F3（5 5） N(a)N(a)（6 6） O(a) GO(a) G（7 7） I(s(a)I(s(a)F1F12022-2-15563.2.13.2.1子句集子句集(9)(9)Skolem標準型標準型 在求子句集的過程中，消去存在量詞之后，把所有全稱量詞在求子句集的過程中，消去存在量詞之后，把所有全稱量詞都依次移到式子的最左邊，再將右部的式子化為合取范式，這

51、都依次移到式子的最左邊，再將右部的式子化為合取范式，這樣得到的式子就是樣得到的式子就是Skolem標準型。標準型。 x y P(x，y) zQ(x,z) R(x,z)= x P(x，f(x) Q(x,g(x) R(x,g(x) = x P(x，f(x) Q(x,g(x) P(x，f(x) R(x,g(x) P(x，f(x) Q(x,g(x) , P(y，f(y) R(y,g(y)消去合取詞和全稱量詞，就得到了原公式的子句集消去合取詞和全稱量詞，就得到了原公式的子句集2022-2-15573.2.13.2.1子句集子句集(10)(10)例例3.8 設設)w, v,u(Q)z, y, x(P(wv

52、uzyxG 消去存在量詞消去存在量詞 用用a代替代替x 用用f（y，z）代替代替u 用用g（y，z，v）代替代替w得到得到G的的Skolem標準型標準型)v, z, y(g, x),z, y( f (Q)z, y, a(P(vzy 進而得進而得G的子句集為：的子句集為： )v, z, y(g, x),z, y( f (Q),z, y, a(P 2022-2-15583.2.13.2.1子句集子句集(11)(11) 引入引入Skolem函數(shù)，是由于存在量詞在全稱量詞的轄函數(shù)，是由于存在量詞在全稱量詞的轄域內(nèi)，其約束變元的取值完全依賴于全稱量詞的取值。域內(nèi)，其約束變元的取值完全依賴于全稱量詞的取值

53、。Skolem反映了這種依賴關系。反映了這種依賴關系。 但但Skolem標準型與原公式一般標準型與原公式一般并不等價并不等價。 有公式：有公式： G xP(x) 它的它的Skolem標準型是標準型是 G P(a) 我們給出如下的解釋我們給出如下的解釋I： D0,1, a/0, P(0)/F, P(1)/T 在此解釋下，在此解釋下，GT, G F2022-2-15593.2.13.2.1子句集子句集(12)(12)定義定義3：子句集：子句集S是不可滿足的，當且僅當其全是不可滿足的，當且僅當其全部子句的合取式是不可滿足的。部子句的合取式是不可滿足的。定理定理1：謂詞公式：謂詞公式G不可滿足當且僅當

54、其子句集不可滿足當且僅當其子句集S不可滿足。不可滿足。(歸結原理定理證明的理論基礎歸結原理定理證明的理論基礎)（證明略）（證明略）2022-2-15603.2.23.2.2命題邏輯中的歸結原理命題邏輯中的歸結原理(1)(1)n歸結原理的提出歸結原理的提出 歸結原理歸結原理(principle of resolution)(principle of resolution)又又稱消解原理稱消解原理,1965,1965年魯濱遜（年魯濱遜（J.A.RobinsonJ.A.Robinson）提出，從理論上解決了定理證明問題。歸結原提出，從理論上解決了定理證明問題。歸結原理提出的是一種證明子句集不可滿足性

55、，從而理提出的是一種證明子句集不可滿足性，從而實現(xiàn)定理證明的一種理論及方法。實現(xiàn)定理證明的一種理論及方法。2022-2-15613.2.23.2.2命題邏輯中的歸結原理命題邏輯中的歸結原理(2)(2)定義定義4 設設L為一個文字，則為一個文字，則L與與L為為互補文字互補文字。 定義定義5 設設C1， C2是命題邏輯中的兩個子句，是命題邏輯中的兩個子句， C1中有文字中有文字L1 ，C2中有文字中有文字L2 ，且，且L1與與L2互補，互補， 從從C1 、 C2中分別刪除中分別刪除L1 、L2 ， 再將剩余部分析取起來，再將剩余部分析取起來， 記構成的新子句為記構成的新子句為C1 2，則，則C1

56、2為為C1 、 C2的的歸結式歸結式， C1 、 C2稱為其歸結式的稱為其歸結式的親本子句親本子句， 稱稱L1 、L2 為為消解基消解基。例例3.9 設設 ，則，則C1 、 C2的歸結式為：的歸結式為： SQC,RQPC 21RSPC 122022-2-15623.2.23.2.2命題邏輯中的歸結原理命題邏輯中的歸結原理(3)(3)定理定理2 歸結式是其親本子句的邏輯結果。歸結式是其親本子句的邏輯結果。證明：設證明：設C C1 1=L=L C C1 1，C C2 2 = = L L C C2 2 其中其中C C1 1、C C2 2 都是文字的析取式。都是文字的析取式。 則則C C1 1 、C

57、C2 2可變換為：可變換為： C C1 1= C= C1 1 L= L= C C1 1 L L C C2 2= = L L C C2 2= = L L C C2 2 由假言三段論得：由假言三段論得： C C1 1 C C2 2 = =（ C C1 1 L L）（L L C C2 2） = C= C1 1 C C2 2= C= C1 1 C C2 2 則則C C1 1 、C C2 2的歸結式為：的歸結式為：C C1 1 C C2 2命題邏輯中的歸結原理：命題邏輯中的歸結原理：)L(C)L(CCC2211212022-2-15633.2.23.2.2命題邏輯中的歸結原理命題邏輯中的歸結原理(4)(

58、4)n利用歸結原理證明命題公式的思路利用歸結原理證明命題公式的思路歸結反演歸結反演n先求出要證明的命題公式的否定式的子句集先求出要證明的命題公式的否定式的子句集S S；n然后對子句集然后對子句集S S（一次或者多次）使用歸結原理；（一次或者多次）使用歸結原理；n若在某一步推出了空子句，即推出了矛盾，則說明子句集若在某一步推出了空子句，即推出了矛盾，則說明子句集S S是不是不可滿足的，從而原否定式也是不可滿足的，進而說明原公式是永可滿足的，從而原否定式也是不可滿足的，進而說明原公式是永真的。真的。（為什么？）（為什么？）理由：理由：證明：證明：F1 F1 F2 Fn G永真永真等價于：等價于：

59、（F1 F1 F2 Fn G）永假）永假進一步變換可得：進一步變換可得： F1 F1 F2 Fn G2022-2-15643.2.23.2.2命題邏輯中的歸結原理命題邏輯中的歸結原理(5)(5)推論推論 設設C1， C2是子句集是子句集S的兩個子句，的兩個子句，C1 2是是 它們的它們的歸結式，則：歸結式，則：（1）若用）若用C1 2來代替來代替C1， C2 ，得到新的子句集，得到新的子句集S1 ，則，則由由S1不可滿足性可以推出原子句集不可滿足性可以推出原子句集S的不可滿足性。即的不可滿足性。即： （2）若用）若用C1 2加入到加入到S中，得到新的子句集中，得到新的子句集S2 ，則，則S2與

60、與原原S同不可滿足。即：同不可滿足。即：S2的不可滿足性的不可滿足性 S不可滿足不可滿足 S1的不可滿足性的不可滿足性= S不可滿足不可滿足注意：注意：反之不成立反之不成立.例：例：S:P Q, Q, Q; S Q, Q, Q; S1 1: :P, Q, Q2022-2-15653.2.23.2.2命題邏輯中的歸結原理命題邏輯中的歸結原理(6)(6)例例3.12 設公理集：設公理集：P, (P Q) R, (S T) Q, T求證：求證：R 化子句集：化子句集： (P(P Q) Q) R R= (P= (P Q)Q) R R= P= P QQ R R (S (S T) T) Q Q= (S=