浙大版人工智能

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

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

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

1.3對偶定理

1.4析取范式與合取范式

1.5邏輯推理

1.6命題演算的王浩算法

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

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

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

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

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

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

β也都是命題公式。

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

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

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

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

。第六頁，共二十八頁。?？吹降暮N(yùn)涵聯(lián)結(jié)詞的一些永真公式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第八頁，共二十八頁。替換定理：設(shè)公式β是公式α的部分公式，則將α中β的某些出現(xiàn)替換成與β等值的公式γ得到的新公式α’=α。代入規(guī)則:等值α公式中用任一公式代入等值公式中任一原子命題(處處代入)，則仍為等值公式。例子1：設(shè)α=P→(Q→R)，由于(Q→P)=～(Q∨P)，所以用右側(cè)的公式代入α的部分公式(Q→P)中得到的新公式與原公式等值，即：P→(Q→R)=P→(～Q∨P)

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

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

一些公式的永真性和可滿足性，最簡單的方法是使用真值表，但當(dāng)變元很多時(shí)，指派總數(shù)很大，非常麻煩。因此常用逐次指派法和用二杈樹方法確定α性質(zhì)。使用逐次指派法要經(jīng)常用到下面公式。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：設(shè)(((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，得到最終的結(jié)果。第十一頁，共二十八頁。第一章人工智能中的謂詞邏輯二杈樹方法(例):α=(((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、置值時(shí)可以從公式中選出現(xiàn)次數(shù)最多的符號首先指定值；2、根據(jù)二杈樹方法還可以確定該公式所有的指派。第十二頁，共二十八頁。

對(P∨～R)～((PQ)(Q∧～(P→R)))，為書寫方便，常將整個(gè)過程寫成下面形式。先令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

此時(shí)成真指派為ftt、fff，成假指派為ftf、fft。公式的所有成真指派ttt,ftt,fff，成假指派tfx,ttf,ftf,fft。第十三頁，共二十八頁。第一章人工智能中的謂詞邏輯1.3對偶定理(最小)完全聯(lián)結(jié)詞:任何一個(gè)公式α都能夠用聯(lián)結(jié)詞集S表達(dá)成一個(gè)與α等值的公式，則S稱為完全聯(lián)結(jié)詞集。若S中每個(gè)聯(lián)結(jié)詞都是獨(dú)立的則稱其為最小聯(lián)結(jié)詞集。容易驗(yàn)證最小聯(lián)結(jié)詞集有{∧,～},{∨,～}例如(PQ)=(P→Q)∧(Q→P)=(～P∨Q)∧(～Q∨P)=～(～(～P∨Q)∨～(～Q∨P))在上述最小聯(lián)結(jié)詞意義下命題公式等價(jià)定義如下：(1)原子命題是命題公式；(2)若α是命題公式，～α也是命題公式；(3)若α，β都是命題公式，(α∨β)和(α∧β)也是命題公式；(4)命題公式只能應(yīng)用上述三規(guī)則得到。第十四頁，共二十八頁。對偶公式：設(shè)α是由{∧,∨,～}表達(dá)的命題公式，將其中的∧換成∨,∨換成∧得到的新公式α*稱為α的對偶公式。例如：α=(P∨Q)∧R，對偶公式α*=(P∧Q)∨R引理：設(shè)α*是α的對偶公式,且α中含有原子命題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)結(jié)詞‘∧’(∨)組成的，則稱α為簡單合取式(簡單析取式)。即α由{～,∨}或{～,∧}與原子命題組成，如P1∧P2∧～P3顯然它們都有特殊的性質(zhì)，如唯一的成真或成假指派。定理1：設(shè)α1…αn為P1…Pm的公式，則合取式α1∧…∧αn的成真指派等于α1…αn成真指派的交集，而成假指派是α1…αn成假指派的并集。定理2：任公式α都可以表示為簡單合取式的析取(析取范式)，也可以表示為簡單析取式的合取(合取范式)。第十六頁，共二十八頁。第一章人工智能中的謂詞邏輯上述定理表明知道一個(gè)公式的成真指派可以寫出該公式。例題:設(shè)α有四個(gè)原子命題P1,P2,P3,P4,其成真指派為txft,ftxf,txxf,則對應(yīng)的簡單合取為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)結(jié)詞“

”及“→”2.使用～～P=P,～(P∨Q)=～P∧～Q,～(P∧Q)=～P∨～Q3.反復(fù)使用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:如果天氣干旱則糧食歉收,又設(shè)當(dāng)糧食歉收時(shí)大多數(shù)人是不幸的，再設(shè)天氣干旱，那么可以指出大多數(shù)人是不幸的。設(shè)相應(yīng)的陳述表示為：P表天氣干旱，S表糧食豐收，U表大多數(shù)人是幸運(yùn)的。例子中有四個(gè)陳述句：1.如果天氣干旱，則糧食歉收；

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

3.天氣是干旱的；

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

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

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

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

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

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

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

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

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

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

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

是永真的。

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

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

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

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

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

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

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