浙大版人工智能

人工智能(AI)第一章人工智能中的一級謂詞邏輯

1.1命題及邏輯聯(lián)結詞

1.2命題公式的永真性及等值

1.3對偶定理

1.4析取范式與合取范式

1.5邏輯推理

1.6命題演算的王浩算法

1.7一級謂詞邏輯的基本概念參考書：《人工智能原理與技術》俞瑞釗、史濟建浙江大學出版社第一頁，共二十八頁。第一章人工智能中的命題及邏輯聯(lián)結詞

傳統(tǒng)的形式邏輯始于古希臘的亞里士多德,已有兩千多年的歷史,它是人類思維的形式和規(guī)律。17世紀70年代數學中的形式化表示方法引入邏輯研究領域，經過幾代科學家出色工作已發(fā)展成為數理邏輯的重要方向之一。

1.1命題及邏輯連接詞定義：命題是能夠判斷真假的陳述句。例如：1.雪是白的。(是)2.他是工人。(不是)3.19是3和6的倍數。(是)4.請乘坐汽車去。(不是)一般情況下用P、Q、R等大寫符號表示命題。第二頁，共二十八頁。第一章人工智能中的謂詞邏輯邏輯連接詞定義：邏輯“非”，～，命題P的非記成～P,～P為真當且僅當P假“合取”，∧，P∧Q表示不僅P而且Q，P∧Q真<=>P和Q為真“析取”，∨，命題P∨Q為真當且僅當其中有一個為真“蘊涵”，→，P→Q意思是如果P則Q,結果為假當且僅當P為真且Q為假“等價”，，PQ為真當且僅當P,Q同時為真或同時為假PQ

～PP∧QP∨QP→QPQfffttfttttffffftftttttfttfft第三頁，共二十八頁。第一章人工智能中的謂詞邏輯例子1：命題P表示“昨天下雨”，Q表示“昨天開會”，則“昨天下雨且開會”表示成P∧Q。例子2:P表示“6大于4”，Q表示“3大于4”，R表示“18大于16”，則“如果6大于4，3不大于4，則18不大于16”寫成(P∧～Q)→～R。注意：符號表達語句時首先要確切，與原語句涵義一致。其次對于復合命題都要寫成原子命題聯(lián)結。如用P表示“18是6和9的公倍數”是錯誤的。例子3：“小張不會德文也不會法文”用P表示“小張會德文”，Q表示“小張會法文”，則原語句寫成～P∧～Q第四頁，共二十八頁。1.2命題公式的永真性與等值定義(公式):(1)原子命題是命題公式。

(2)若α是命題公式，則～α也是命題公式。

(3)如果α,β是命題公式，那么α∧β,α∨β,α→β,α

β也都是命題公式。

(4)所有命題公式都是有限次應用上述規(guī)則得到的。判斷一個字符串是否公式的方法是將任意由五個聯(lián)結符連接的原子命題用一個原子命題表示。例:α=～(～(P∧Q)→R)(P∨Q)α1=～((～P→R)P)

α2=～(P→R)P)α3=～(PP)

α4=～Pα5=P所以α是命題公式。第五頁，共二十八頁。指派：命題公式α含有n個不同的原子命題P1…Pn,它的任意一組確定值(P01,…,P0n),P0i∈{t,f}稱為α的一個指派。指派分為成真指派，成假指派。永真公式:若α的任一指派都使α為真(假)，則稱α為永真(假)公式，α存在成真指派則也稱α為可滿足公式。下面是三個永真公式：P→(P∨Q),(P∧Q)→P(((P→Q)∧(R→S))∧(P∨R))→(Q∨S)

若的所有指派都是成假指派則稱為永假公式或不可滿足公式。一般情況下可以列出公式的真值表確定其永真性。等值公式：設兩公式α,β對于任意指派都同時取相同的真假值，則稱α,β為等值公式，記成α=β

。第六頁，共二十八頁。?？吹降暮N涵聯(lián)結詞的一些永真公式1.P→(P∨Q)2.(P∧Q)→P3.(P∧(P→Q))→Q4.(～Q∧(P→Q))→～P5.((P∨Q)∧～P)→Q6.((P→Q)∧(Q→R))→(P→R)7.(((P→Q)∧(R→S))∧(P∨R))→(Q∨S)

上述永真公式都可以用列真值表的方式證明。例如：(P∧(P→Q))→QPQ(P∧(P→Q))→Qfffttftttttt第七頁，共二十八頁。常用的等值公式表1.PQ=(P→Q)∧(Q→P)(PQ)R=P(QR)2.P→Q=～P∨Q3.P∨Q=Q∨PP∧Q=Q∧P4.(P∨Q)∨R=P∨(Q∨R)(P∧Q)∧R=P∧(Q∧R)5.P∨(Q∧R)=(P∨Q)∧(P∨R)P∧(Q∨R)=(P∧Q)∨(P∧R)6.～(P∨Q)=～P∧～Q～(P∧Q)=～P∨～Q7.P∨F=PP∧T=P8.P∨T=TP∧F=F9.P∨～P=TP∧～P=F10.～～P=P第八頁，共二十八頁。替換定理：設公式β是公式α的部分公式，則將α中β的某些出現(xiàn)替換成與β等值的公式γ得到的新公式α’=α。代入規(guī)則:等值α公式中用任一公式代入等值公式中任一原子命題(處處代入)，則仍為等值公式。例子1：設α=P→(Q→R)，由于(Q→P)=～(Q∨P)，所以用右側的公式代入α的部分公式(Q→P)中得到的新公式與原公式等值，即：P→(Q→R)=P→(～Q∨P)

利用上述定理還可以證明一些新的復雜等值公式。但是我們時常需要判斷一些公式的永真性和可滿足性，最簡單的方法是使用真值表，但當變元很多時，指派總數很大，非常麻煩。因此常用二杈樹方法確定α性質。第九頁，共二十八頁。例子2：證明～(～P∧(～Q∨～R)=(P∨Q)∧(P∨R)

～(～P∧(～Q∨～R)=～(～P∧～(Q∧R))=P∨(Q∧R)=(P∨Q)∧(P∨R)

一些公式的永真性和可滿足性，最簡單的方法是使用真值表，但當變元很多時，指派總數很大，非常麻煩。因此常用逐次指派法和用二杈樹方法確定α性質。使用逐次指派法要經常用到下面公式。t∨P=P→t=tt∧P=t→P=Pf∨P=Pf∧P=ff→P=t(P→f)=～P(tP)=P(fP)=～PP∧P=P∨P=P(P→P)=t(PP)=t～～P=P第十頁，共二十八頁。例子3：設(((P∧Q)→R)∧(P→Q))→(P→R)

用逐次指派法說明它的永真或可滿足性。首先將P用t作為左分支，用f代入作為右分支，得到：

(((P∧Q)→R)∧(P→Q))→(P→R)P=tP=f(((t∧Q)→R)∧(t→Q))(((f∧Q)→R)→(t→R)∧(f→Q))→(f→R)

在使用前頁的表格，得到：

(((P∧Q)→R)∧(P→Q))→(P→R)P=tP=f((Q→R)∧Q)→Rt然后逐次再用f和t分別代入Q、R，得到最終的結果。第十一頁，共二十八頁。第一章人工智能中的謂詞邏輯二杈樹方法(例):α=(((P∧Q)→R)∧(P→Q))→(P→R)將P用t代入作為左分支，f代入作為右分支，依次代Q，R得(((P∧Q)→R)∧(P→Q))→(P→R)((Q→R)∧Q)→RR→RttR=tR=fQ=tQ=fP=tP=ftt1、置值時可以從公式中選出現(xiàn)次數最多的符號首先指定值；2、根據二杈樹方法還可以確定該公式所有的指派。第十二頁，共二十八頁。

對(P∨～R)～((PQ)(Q∧～(P→R)))，為書寫方便，常將整個過程寫成下面形式。先令P=t得：

(t∨～R)～((tQ)(Q∧～(t→R))）

=t～(Q(Q∧～R))=～(Q(Q∧～R))再令Q=t得：～(t(t∧～R))=～～R=R所以成真指派為ttt，成假指派為ttf。又令Q=f，得：～(f(f∧～R))=～(ff)=f因此成假指派還有tfx。若令P=f，則

(f∨～R)～((fQ)(Q∧～(f→R))）

=～R～(～Qf)=～R～Q

此時成真指派為ftt、fff，成假指派為ftf、fft。公式的所有成真指派ttt,ftt,fff，成假指派tfx,ttf,ftf,fft。第十三頁，共二十八頁。第一章人工智能中的謂詞邏輯1.3對偶定理(最小)完全聯(lián)結詞:任何一個公式α都能夠用聯(lián)結詞集S表達成一個與α等值的公式，則S稱為完全聯(lián)結詞集。若S中每個聯(lián)結詞都是獨立的則稱其為最小聯(lián)結詞集。容易驗證最小聯(lián)結詞集有{∧,～},{∨,～}例如(PQ)=(P→Q)∧(Q→P)=(～P∨Q)∧(～Q∨P)=～(～(～P∨Q)∨～(～Q∨P))在上述最小聯(lián)結詞意義下命題公式等價定義如下：(1)原子命題是命題公式；(2)若α是命題公式，～α也是命題公式；(3)若α，β都是命題公式，(α∨β)和(α∧β)也是命題公式；(4)命題公式只能應用上述三規(guī)則得到。第十四頁，共二十八頁。對偶公式：設α是由{∧,∨,～}表達的命題公式，將其中的∧換成∨,∨換成∧得到的新公式α*稱為α的對偶公式。例如：α=(P∨Q)∧R，對偶公式α*=(P∧Q)∨R引理：設α*是α的對偶公式,且α中含有原子命題P1,…,Pn,則～α(P1…Pn)=α*(～P1…～Pn)對偶定理：若α和β滿足α=β，則對偶公式α*和β*也滿足α*=β*。例：(P∧Q)∨(～P∨(～P∨Q))=(P∧Q)∨(～P∨Q)=(P∧Q)∨～P∨Q=((P∨～P)∧(Q∨～P))∨Q

=(Q∨～P)∨Q=Q∨～P=～P∨Q由對偶原理得：(P∨Q)∧(～P∧(～P∧Q))=～P∧Q第十五頁，共二十八頁。第一章人工智能中的謂詞邏輯1.4析取范式和合取范式定義:若公式α是由一些原子命題或它的非利用合取聯(lián)結詞‘∧’(∨)組成的，則稱α為簡單合取式(簡單析取式)。即α由{～,∨}或{～,∧}與原子命題組成，如P1∧P2∧～P3顯然它們都有特殊的性質，如唯一的成真或成假指派。定理1：設α1…αn為P1…Pm的公式，則合取式α1∧…∧αn的成真指派等于α1…αn成真指派的交集，而成假指派是α1…αn成假指派的并集。定理2：任公式α都可以表示為簡單合取式的析取(析取范式)，也可以表示為簡單析取式的合取(合取范式)。第十六頁，共二十八頁。第一章人工智能中的謂詞邏輯上述定理表明知道一個公式的成真指派可以寫出該公式。例題:設α有四個原子命題P1,P2,P3,P4,其成真指派為txft,ftxf,txxf,則對應的簡單合取為P1∧～P3∧P4,～P1∧P2∧～P4,P1∧～P4,則其析取范式為

α=(P1∧～P3∧P4)∨(～P1∧P2∧～P4)∨(P1∧～P4)

任何都可以用等值公式將其化為析取(合取)范式：1.使用公式PQ=(P→Q)∧(Q→P)P→Q=～P∨Q

消去聯(lián)結詞“

”及“→”2.使用～～P=P,～(P∨Q)=～P∧～Q,～(P∧Q)=～P∨～Q3.反復使用P∨(Q∧R)=(P∨Q)∧(P∨R)P∧(Q∨R)=(P∧Q)∨(P∧R)將公式化為范式第十七頁，共二十八頁。第一章人工智能中的謂詞邏輯例題1:將(P∧(Q→R))→S化為合取范式

(P∧(Q→R))→S=(P∧(～Q∨R))→S=～(P∧(～Q∨R))∨S=(～P∨～(～Q∨R))∨S=(～P∨(Q∧～R))∨S=((～P∨Q)∧(～P∨～R))∨S=(～P∨Q∨S)∧(～P∨～R∨S)例題2:將～P

(Q∧～R)化為析取范式

～P(Q∧～R)=(～P→(Q∧～R))∧((Q∧～R)→～P)=(P∨(Q∧～R))∧((～Q∨R)∨～P)=((P∨(Q∧～R))∧(～Q∨R))∨((P∨(Q∧～R))∧～P)=((P∧(～Q∨R))∨((Q∧～R)∧(～Q∨R))∨((Q∧～R)∧～P)=(P∧～Q)∨(P∧R)∨(Q∧～R∧～Q)∨(Q∧～R∧R)∨(Q∧～R∧～P)=(P∧～Q)(P∧R)(～P∧Q∧～R)第十八頁，共二十八頁。第一章人工智能中的謂詞邏輯1.5邏輯推理例題1:如果天氣干旱則糧食歉收,又設當糧食歉收時大多數人是不幸的，再設天氣干旱，那么可以指出大多數人是不幸的。設相應的陳述表示為：P表天氣干旱，S表糧食豐收，U表大多數人是幸運的。例子中有四個陳述句：1.如果天氣干旱，則糧食歉收；

2.如果糧食歉收，則大多數人是不幸的；

3.天氣是干旱的；

4.大多數人是不幸的。將其符號化：P→～S,～S→～U,P,～U。其實我們求證的任務是當上述表示均為真時，～U為真。第十九頁，共二十八頁。第一章人工智能中的謂詞邏輯將上述式子的合取化為范式：

(P→～S)∧(～S→～U)∧P=P∧(～P∨～S)∧(S∨～U)=…=P∧～S∧～U

如果(P→～S)∧(～S→～U)∧P為真，那么P∧～S∧～U為真，進而必須P、～S、～U均為真，所以得U為假，此時邏輯上稱～U是(P→～S)、(～S→～U)和P的邏輯結果。上述推理過程的大致思想如下：

1.將所有定理、條件命題和結果命題符號化，并將條件命題組成合取公式α；

2.將結果命題與上述條件公式α合取成公式β；

3.化β為簡單合取式，令其為真，推出其中的結果命題為真。第二十頁，共二十八頁。第一章人工智能中的謂詞邏輯定義:設命題公式序列α1…αn及命題公式β，如果對任何使α1…αn成真的指派也使β成真，則β稱為α1…αn的邏輯推論(邏輯結果)，記成：α1…αn|=β。定理1：設α1…αn及β均為命題公式，則α1…αn|=β當且僅當(α1∧…∧αn)→β

是永真的。定理2：設α1…αn及β均為命題公式，則α1…αn|=β當且僅當α1∧…∧αn∧～β

是永假的。證明：由上知β是邏輯結果當且僅當(α1∧…∧αn)→β是永真的，因此～((α1∧…∧αn)→β)是永假的，而～((α1∧…∧αn)→β)=～(～(α1∧…∧αn)∨β)=α1∧…∧αn∧～β

因此定理得證。第二十一頁，共二十八頁?？偨Y為什么建立命題、謂詞邏輯

基本思路：一個實際問題，有使用的定理和條件條件，有要證明的結論。首先將所有條件和結論轉換成命題公式集合α1…αn及命題公式β。顯然問題是，如果所有條件成立(α1…αn為真)，證明結論成立(β為真)，即按照定義β稱為α1…αn的邏輯推論(邏輯結果)，記成：α1…αn|=β。

按照定理1，就是證明(α1∧…∧αn)→β

是永真的。

按照定理2，就是證明α1∧…∧αn∧～β

是永假的。但是要證明上述公式的永假性也是非常困難的，所以必須建立一套更為復雜的理論解決求證的問題。因此，下面建立了王浩演算體系和謂詞邏輯的歸結原理，他們都是用來證明α1∧…∧αn∧～β的永假性的。第二十二頁，共二十八頁。實際問題命題轉換α1…αn|=β就是證明(α1∧…∧αn)→β

是永真的(定理1)就是證明α1∧…∧αn∧～β

是永假的(定理2)建立證明的理論體系王浩演算體系謂詞邏輯歸結原理第二十三頁，共二十八頁。第一章人工智能中的謂詞邏輯1.6一級謂詞邏輯的基本概念1.6.1謂詞:謂詞是指個體所具有的性質或若干個體之間的關系，如“數理邏輯是科學”分為兩部分，主語“數理邏輯”與謂表語“是科學”?！?整除6”，表現(xiàn)3和6間的整除關系。其中“數理邏輯”、“3”、“6”也可以是抽象的x,y等稱為個體變元?！笆强茖W”、“整除”是謂詞。一般用A、B、C等表示謂詞，如x,y間的關系寫成B(x,y),謂詞中有n個體變元則稱為n元謂詞，0元謂詞就是命題，記為P、Q、R等。為方便常用一些符號直接表示謂詞，如“等于”直接用“=”表示，這樣E(x,y)寫成“x=y”。單獨的謂詞沒有意義，必須賦予個體，通常把謂詞填以個體后的式子稱為謂詞填式。如“張山高于李四，則張山高于王五”，用A表示“高于”，a,b,c分別表示“張山”、“李四”、“王五”，則上述謂詞填式表示為A(a,b)→A(a,c)第二十四頁，共二十八頁。第一章人工智能中的謂詞邏輯1.6.2量詞:量詞有全稱量詞和存在量詞，分別記為“

x”和“ヨx”,意思為“對于所有的x”和“存在一個x”。當寫xP(x)和ヨxQ(x,y)時稱其為量詞的作用域，x稱為約束變元，y稱為自由變元。變元的取值范圍稱為個體域。例：“任何整數是正的或負的”，用M(x)表x是整數，P(x)表x是正數，N(x)表x是負數，則整個語句表示為

x(M(x)→(P(x)∨N(x)))而如果事先約定個體域是全體整數，則可以表示為

x(P(x)∨N(x))注意在受量詞約束的變元中，變元用什么記號