人工智能第五章

第三部分邏輯表示及推理方法常用的知識表示方法：非結構化方法邏輯表示法QA3,STRIPS,DART,MOMO產生式系統(tǒng)DENDRAL，MYCIN結構化方法框架語義網絡過程式知識表示法1/14/20231第五章謂詞演算（復習）數理邏輯思想的起源：Leibnitz之夢產生的歷史：Boole的工作、Frege的工作發(fā)展的現實：計算機學科的基礎（軟件到硬件）古典數理邏輯主要包括兩部分：命題邏輯和謂詞邏輯。命題邏輯又是謂詞邏輯的一種簡單情形。邏輯研究的基本內容語法語言部分：基本符號集、公式形成規(guī)則推理部分：公理集、推理規(guī)則語義語法和語義之間的關系：可靠性、完備性基本問題邏輯表示下的判定問題1/14/20232一、命題邏輯1命題一句有真假意義的話。用大寫英文字母P，Q，…，P1，P2，…，表示。

例：上海是中國最大的城市。今天是星期日。所有素數都是奇數。1+1=2。我不會解答這道題。別的星球上有生物。長春今天下雪。如果太陽從西方升起，你就可以長生不老。

嚴禁吸煙。今天的溫度有多少度？全體起立！今天好冷??！我正在說謊。1/14/202332真值如果一個命題是真的，就說它的真值是T；

如果一個命題是假的，就說它的真值是F。

T和F統(tǒng)稱為命題的真值。

也用T代表一個抽象的真命題，用F代表一個抽象的假命題。

1/14/202343聯結詞～、∨、∧、→、?設P是一個命題，命題“P是不對的”稱為P的否定，記以～P，讀作非P。例.Q:張三是好人?！玅：張三不是好人。語義規(guī)定：～P是真的當且僅當P是假的。設P，Q是兩個命題，命題“P或者Q”稱為P，Q的析取，記以PQ，讀作P析取Q。例.

P：今天下雪，Q：今天刮風， PQ：今天下雪或者刮風。語義規(guī)定：PQ是真的當且僅當P,Q中至少有一個為真。1/14/20235設P，Q是兩個命題，命題“P并且Q”稱為P，Q的合取，記以PQ，讀作P合取Q。例.P：22=5，Q：雪是黑的，

PQ：22=5并且雪是黑的。語義規(guī)定：PQ是真的當且僅當P和Q都是真的。設P，Q是兩個命題，命題“如果P，則Q”稱為P蘊涵Q，記以PQ。例.P：f(x)是可微的，Q：f(x)是連續(xù)的，

PQ：若f(x)是可微的，則f(x)是連續(xù)的。語義規(guī)定：PQ是假的當且僅當P是真的而Q是假的。1/14/20236設P，Q是兩個命題，命題“P當且僅當Q”稱為P等價Q，記以PQ。語義規(guī)定：PQ是真的當且僅當P，Q或者都是真的，或者都是假的。例P：a2+b2=a2，

Q：b=0，

PQ：a2+b2=a2當且僅當b=0。五種邏輯聯結詞的優(yōu)先級按如下次序遞增：，，，，～例.符號串PQRQ～SR意味著： ((P(QR))(Q((～S)R)))1/14/202374復合命題用聯結詞將簡單命題連接的結果。5原子命題的抽象。用大寫的英文字母P，Q，R，…等表示。6文字原子或原子的否定。7子句有限個文字的析取式稱為一個子句。特別，沒有文字的子句稱為空子句，記為。只有一個文字的子句稱為單元子句。8短語有限個文字的合取式稱為一個短語。1/14/20238復合命題的抽象公式的形成規(guī)則--是如下定義的一個符號串： (1)原子是公式；

(2)F、T是公式；

(3)若G，H是公式，則(～

G)，(GH)， (GH)，(GH)，(GH)是公式； (4)所有公式都是有限次使用(1)，(2)，(3)

得到的符號串。9公式1/14/20239設G是命題公式,A1,…,An是出現在G中的所有原子。指定A1,…,An的一組真值,則這組真值稱為G的一個解釋。設G是公式，I是G的一個解釋，G在I下的真值記為TI(G)。例.G=PQ，設解釋I，I’如下：

I： I’：

則TI(G)=T，TI’(G)=F

注意：該例子中寫成G=T或G=F是錯誤的！10解釋PQ

TT

PQ

TF

1/14/20231011真值表

公式G在其所有可能的解釋下所取真值的表，稱為G的真值表。有n個不同原子的公式，共有2n個解釋。

12恒真公式公式G稱為恒真的(或有效的)，如果G在它的所有解釋下都是真的.1/14/20231113恒假公式

公式G稱為恒假的(或不可滿足的)，如果G在它的所有解釋下都是假的.14可滿足公式

公式G稱為可滿足的，如果它不是恒假的。G是恒真的iff～

G是恒假的。G是可滿足的iff至少有一個解釋I，使G在I下為真。若G是恒真的，則G是可滿足的；反之不對。如果公式G在解釋I下是真的，則稱I滿足G；

如果G在解釋I下是假的，則稱I弄假G。

1/14/202312例.考慮G1=～(P→Q)→P，G2=(P→Q)P，G3=P～P。PQG1PQG2PG3FFTFFFFFFTTFTFTFTFTTFFTTTTTT1/14/20231315判定問題能否給出一個可行方法，對任意的公式，判定其是否是恒真公式。命題邏輯可判定？原因？因為一個命題公式的原子數目有限(n)，從而解釋的數目是有限的(2n)，所以命題邏輯的判定問題是可解的(可判定的，可計算的).1/14/20231416公式等價稱公式G，H是等價的，記以G=H，如果G，H在其任意解釋I下，其真值相同。公式G，H等價iff公式GH恒真。

基本等價式1) (GH)=(GH)(HG)；2) (GH)=(～GH)；3) GG=G，GG=G；(等冪律)4) GH=HG，GH=HG； (交換律)5) G(HS)=(GH)S，

G(HS)=(GH)S；(結合律)1/14/2023156) G(GH)=G，G(GH)=G；(吸收律)7) G(HS)=(GH)(GS)，

G(HS)=(GH)(GS)；(分配律)8) GF=G，GT=G；(同一律)9) GF=F，GT=T；(零一律)10)～(GH)=～G～H，

～(GH)=～G～H。(DeMorgan律)11)G～G=T；G～G=F（互補律）12)～～G=G（雙重否定律）1/14/20231617公式的蘊涵設G，H是兩個公式。稱H是G的邏輯結果(或稱G蘊涵H)，當且僅當對G，H的任意解釋I，如果I滿足G，則I也滿足H，記作GH。公式G蘊涵公式Hiff公式GH是恒真的。設G1,…,Gn，H是公式。稱H是G1,…,Gn的邏輯結果(或稱G1,…,Gn共同蘊涵H)，當且僅當(G1…Gn)

H。例如，P，PQ共同蘊涵Q。

1/14/202317基本蘊涵式

PQPPQQPPQQPQ～P(PQ)Q(PQ)～(PQ)P1/14/202318基本蘊涵式

～(PQ)～QP，QPQ～P，PQQP，PQQ～Q，PQ～PPQ，QRPRPQ，PR，QRR

1/14/20231918范式有限個短語的析取式稱為析取范式；有限個子句的合取式稱為合取范式。特別，一個文字既可稱為是一個合取范式，也可稱為是一個析取范式。一個子句，一個短語既可看做是合取范式，也可看做是析取范式。例如，P，PQ，PQ，(PQ)(～P～Q)是析取范式。P，PQ，PQ，(PQ)(～PR)是合取范式。

1/14/202320化范式方法：步1.使用基本等價式，將G中的邏輯聯結詞， 刪除。步2.使用～(～H)=H和摩根律，將G中所有的否定號～都放在原子之前。

步3.

反復使用分配律，即可得到等價于G的范式。

1/14/20232119演繹設S是一個命題公式的集合(前提集合)。從S推出公式G的一個演繹是公式的一個有限序列：

G1,G2,…,Gk

其中，Gi（1≤i≤k）或者屬于S，或者是某些Gj(j<i)的邏輯結果。并且Gk就是G。稱公式G為“此演繹的”邏輯結果，或稱從S演繹出G。有時也記為SG。

1/14/202322例.設S={PQ，QR，PM，～M}則下面的公式序列:

～M，PM，～P，PQ，Q，QR，R

就是從S推出R的一個演繹。演繹方法的可靠性與完備性設S是公式集合，G是一個公式。于是，從S演繹出G的充要條件是G是S的邏輯結果。1/14/202323命題邏輯的缺陷

把問題看成一個個孤立的命題，忽略了問題之間的聯系，無法描述客觀事物的結構，不能反映某些重要的常見的邏輯思維過程。1繁瑣例.表述集合個體性質及相互關系S={1,2,…,50}表述S中元素大于3這樣一個性質，需要1>3,2>3,…,50>3等50個命題。1/14/2023242不能描述問題間的邏輯聯系例如，邏輯學中著名的三段論：

P：凡人必死

Q：張三是人

R：張三必死

在命題邏輯中：應該有(PQ)R，從而公式(PQ)R應該是恒真的。顯然該公式不是恒真的，解釋{P，Q，～R}就能弄假該公式。1/14/202325原因：命題R是和命題P,Q有關系的，只是這種關系在命題邏輯中無法表示。因此，需要對命題的成分、結構和命題間的共同特性等作進一步的分析，這正是謂詞邏輯所要研究的問題。1/14/202326為了表示出這三個命題的內在關系，需要引進謂詞的概念。例如，在前面的例子“張三是人”中的“是人”是謂語，稱為謂詞，“張三”是主語，稱為個體。1/14/202327二、謂詞邏輯

1謂詞可以獨立存在的物體稱為個體。如人、學生、桌子、自然數等都可以做個體。在謂詞演算中，個體通常指一個命題里的思維對象。設D是非空個體名稱集合，定義在Dn上取值于{T，F}上的n元函數，稱為n元命題函數或n元謂詞。其中Dn表示集合D的n次笛卡爾乘積。一般地，一元謂詞描述個體的性質，二元或多元謂詞描述兩個或多個個體間的關系。0元謂詞中無個體，理解為就是命題，這樣，謂詞邏輯包括命題邏輯。1/14/202328例.D={2,3,4}設P(x)：x大于3，則P(x)為一元謂詞。指定元素--命題：P(2)=F,P(3)=F,P(4)=T設P(x,y)：x大于y,則P(x,y)為二元謂詞。指定元素--命題：P(2,3)=F,P(4,2)=T設P(x,y,z)：若x+y-1=z，則P(x,y,z)為T，否則為F。則P(x,y,z)為三元謂詞。指定元素--命題：P(2,3,4)=T,P(4,2,2)=F1/14/202329例.用謂詞的概念可將三段論做如下的符號化：令

H(x)表示“x是人”，

M(x)表示“x必死”。則三段論的三個命題表示如下：

P：H(x)M(x)

Q：H(張三)

R：M(張三)1/14/202330若想得到“命題”P的否定“命題”，應該就是“命題”～P。但是，

～P=～(H(x)M(x))

=～(～H(x)M(x))

=H(x)～M(x)亦即，“命題”P的否定“命題”是“所有人都不死”。這和人們日常對命題“所有人都必死”的否定的理解，相差得實在太遠了.1/14/202331原因－－命題P的確切意思應該是：“對任意x，如果x是人，則x必死”。但是

H(x)M(x)

中并沒有確切的表示出“對任意x”這個意思，亦即H(x)M(x)不是一個命題。因此，在謂詞邏輯中除引進謂詞外，還需要引進“對任意x”這個語句，及其對偶的語句“存在一個x”。

1/14/2023322量詞定義語句“對任意x”稱為全稱量詞，記以x；語句“存在一個x”稱為存在量詞，記以x。這時，命題P就可確切地符號化如下： x(H(x)M(x))命題P的否定命題為：

～

P=～(x(H(x)M(x)))=x(H(x)～M(x))

亦即“有一個人是不死的”。這個命題確實是“所有人都要死”的否定。

三段論的三個命題，在謂詞邏輯中是如下這樣表示的：

P：x(H(x)M(x))

Q：H(張三)

R：M(張三)1/14/202333量詞的語義規(guī)定xG(x)取T值對任意xD，G(x)都取T值；xG(x)取T值至少有一個x0D，使G(x0)取T值語義上，當D={x0,x1,…}是可數集合時，

xG(x)等價于G(x0)G(x1)…

xG(x)等價于G(x0)G(x1)…1/14/202334例.將下列命題符號化：１)一切事物都是發(fā)展變化的xF(x)其中F(x)：x是發(fā)展變化的２)存在著會說話的機器人x(F(x)G(x))其中F(x)：x會說話G(x):x是機器人如果沒有明確給出個體域，則認為個體域為一切事物。1/14/2023353)每個計算機學院的學生都學離散數學。D：全校學生集合P(x)：x是計算機學院的學生R(x):x學離散數學x(P(x)→R(x))4）存在著偶素數D：正整數集合E(x)：x是偶數P(x)：x是素數x(E(x)P(x))1/14/2023365)每個人都會犯錯誤R(x):x是人P(x):x會犯錯誤x(R(x)→P(x))1/14/2023373約束變量、自由變量在一個由謂詞，量詞，邏輯聯結詞，括號組成的有意義的符號串(公式)中，稱變量的出現是約束的，當且僅當它出現在使用這個變量的量詞范圍之內；稱變量的出現是自由的，當且僅當這個出現不是約束的。

稱變量是約束的，如果至少有一個它的出現是約束的；稱變量是自由的，如果至少有一個它的出現是自由的。例如， x(P(x，y)Q(x，z))R(x)

從左向右算起，變量x的第一，第二次出現是約束的，第三次出現是自由的；變量y，z的出現是自由的。x既是約束變量，又是自由變量；y，z只是自由變量。1/14/2023384約束變量的改名規(guī)則改名規(guī)則的理論依據xP(x)與yP(y)都是表示個體域D中的“每個個體都具有性質P”，所以可以把x改名為y，即把xP(x)改成為yP(y)。xP(x)與yP(y)都是表示個體域D中的“某個個體具有性質P”，所以也可以把x改名為y，即把xP(x)改成為yP(y)。亦即，謂詞邏輯中命題的真值，與命題中的約束變量的記法無關。這就引出了謂詞邏輯中的改名規(guī)則。1/14/202339改名規(guī)則：在由謂詞，量詞，邏輯聯結詞，括號組成的有意義的符號串(公式)中，可將其中出現的約束變量改為另一個約束變量，這種改名必須在量詞作用區(qū)域內各處以及該量詞符號中實行，并且改成的新約束變量要有別于改名區(qū)域中的所有其它變量。顯然改名規(guī)則不改變原符號串的真值。1/14/202340例:對于x(P(x，y)Q(x，z))R(x,v)，可改名為u(P(u，y)Q(u，z))R(x,v)。但下面的改名都是不對的：a.u(P(u，y)Q(x，z))R(x,v)b.x(P(u，y)Q(u，z))R(x,v)c.u(P(x，y)Q(x，z))R(x,v)d.y(P(y，y)Q(y，z))R(x,v)e.z(P(z，y)Q(z，z))R(x,v)1/14/2023415封閉公式公式中無自由變量，或將自由變量看做常量。(公式中每個變量的出現都是約束的）1/14/2023421)常量符號：用小寫英文字母a，b，c，…表示，當個體名稱集合D給出時，它可以是D中某個元素。2)變量符號：用小寫英文字母u，v，w，x，y，z，…表示，當個體名稱集合D給出時，D中任意元素可代入變量符號。6謂詞邏輯形式化中使用的四種符號1/14/2023433)函數符號：用小寫英文字母f，g，…表示，當個體名稱集合D給出時，n元函數符號f(x1，…，xn)可以是Dn到D的任意一個映射。4)謂詞符號：用大寫英文字母P，Q，R，…表示，當個體名稱集合D給出時，n元謂詞符號P(x1，…，xn)可以是Dn上的任意一個謂詞。

1/14/2023447項謂詞邏輯中的項，被遞歸定義為：1) 常量符號是項；2) 變量符號是項；3) 若f(x1,…,xn)是n元函數符號，t1,…,tn

是項，則f(t1,…,tn)是項；4)所有項都是有限次使用1)，2)，3)生成

的符號串。

8原子若P(x1,…,xn)是n元謂詞符號，t1,…,tn是項，則P(t1,…,tn)是原子。1/14/2023459公式謂詞邏輯中的公式，被遞歸定義如下：1) 原子是公式；2) 若G，H是公式，則(～G)，(GH)，

(GH)，(GH)，(GH)是公式；3) 若G是公式，x是G中的自由變量，則xG，

xG是公式；4) 所有公式都是有限次使用1)～3)生成的符號串。

1/14/20234610公式的語義解釋謂詞邏輯中公式G的一個解釋I，是由非空區(qū)域D和對G中常量符號，函數符號，謂詞符號以下列規(guī)則進行的一組指定組成：1. 對每個常量符號，指定D中一個元素；2. 對每個n元函數符號，指定一個函數，即指

定Dn到D的一個映射；3. 對每個n元謂詞符號，指定一個謂詞，即指

定Dn到{T，F}的一個映射。

1/14/202347例:1)G=x(P(f(x))Q(x，f(a)))

2)H=x(P(x)Q(x，a))設解釋I：

D={2，3}

a

2

f(2)f(3)

32

P(2)P(3)Q(2,2)Q(2,3)Q(3,2)Q(3,3)

FTTTFT1/14/202348例:TI(G) =TI((P(f(2))Q(2，f(2))) (P(f(3))Q(3，f(2))))

=TI((P(3)Q(2，3))(P(2)Q(3，3)))

=(TT)(FT)

=TTI(H) =TI(P(2)Q(2，2)P(3)Q(3，2))

=FTTF

=F1/14/20234911謂詞公式的恒真、恒假、可滿足公式G稱為可滿足的，如果存在解釋I，使G在I下取T值，簡稱I滿足G。若I不滿足G，則簡稱I弄假G。公式G稱為是恒假的(或不可滿足的)，如果不存在解釋I滿足G。公式G稱為恒真的，如果G的所有解釋I都滿足G。1/14/20235012謂詞邏輯的判定問題謂詞邏輯中公式恒真、恒假性的判斷異常困難。原因？謂詞邏輯中的恒真(恒假)公式，要求所有解釋I都滿足(弄假)該公式。而解釋I依賴于一個非空集合D。由于集合D可以是無窮集合，而集合D的“數目”也可能是無窮多個。因此，所謂公式的“所有”解釋，實際上是無法考慮的。1936年Church和Turing分別獨立地證明了：對于謂詞邏輯，判定問題是不可解的。1/14/202351謂詞邏輯是半可判定的：如果謂詞邏輯中的公式是恒真的，則有算法在有限步之內檢驗出這個公式的恒真性。如果該公式不是恒真的(當然也不是恒假的)，則無法在有限步內判定這個事實。1/14/20235213等價公式G，H稱為等價，記以G=H，如果公式GH是恒真的。公式G，H等價的充要條件是：對G，H的任意解釋I，G，H在I下的真值相同。因為對任意公式G，H，在解釋I下，G，H就是兩個命題，所以命題邏輯中給出的基本等價式，在謂詞邏輯中仍然成立。1/14/202353設G，H是公式，稱G蘊涵H，或H是G的邏輯結果，如果公式GH是恒真的，并記以GH。對任意兩個公式G，H，G蘊涵H的充要條件是：對任意解釋I，若I滿足G，則I必滿足H。同樣，命題邏輯中的基本蘊涵式仍成立。14蘊涵1/14/202354基本蘊涵式：(P∨P)

PP(P∨Q)(P∨Q)(Q∨P)(Q→R)((P∨Q)→(P∨R))xP(x)

P(y)P(y)

xP(x)xP(x)

xP(x)xP(x)∨xQ(x)

x(P(x)∨Q(x))x(P(x)∧Q(x))

xP(x)∧xQ(x)x(P(x)→Q(x))

xP(x)→xQ(x)x(P(x)→Q(x))

xP(x)→xQ(x)1/14/202355例.設G=x(A(x)B(x))，H=xA(x)xB(x)證明：GH證明：設I是滿足G的任意一個解釋。若TI(xA(x))=F,則TI(xA(x)xB(x))=T;若TI(xA(x))=T,則在I下對任意xD，有TI(A(x))=T，又由TI(x(A(x)B(x)))=T知，對任意xD，TI(A(x)B(x))=T，故TI(B(x))=T，即，TI(x(B(x)))=T，因此，TI(xA(x)xB(x))=T。1/14/202356G，H不等價。舉反例：簡單扼要、擊中要害I:D={2，3}

A(2)A(3)B(2)B(3)

TFFFTI(G)=FTI(H)=TG=x(A(x)B(x))，

H=xA(x)xB(x)？HG1/14/20235758設在一個含有凹室(alcove)的房間內，有桌子A和書架B，一個機器人(robot)和一疊書(book)?，F在要求機器人(robot)從凹室出發(fā)，把桌子A上的書搬到B處書架上，完成任務后回到凹室。請用謂詞邏輯描

述機器人完成這一工作的全過程。謂詞邏輯知識表示的例子1/14/20235859謂詞邏輯知識表示的例子解：⑴為了能夠描述這個機器人世界的有關環(huán)境和狀態(tài)變遷，要求必須先定義謂詞。注意這里需要定義兩類謂詞：一類用來描述環(huán)境狀態(tài)，另一類謂詞用來表示機器人的操作。首先定義描述環(huán)境狀態(tài)的謂詞。TABLE(x)：x是桌子，x的個體域：{a}；BOOKCASE(z)：z是書架，z的個體域：；EMPTY(y)：y手中是空的，y的個體域：{robot}；HOLDS(y，u)：y手中拿著u，u的個體域：{books}；AT(y，w)：y在w處，w的個體域：{a，b，alcove}；ON(u，x)：u被放在x之上；CLEAR(v)：v上(中)是空的，v的個體域：{a，b}.1/14/20235960謂詞邏輯知識表示的例子解：⑵使用謂詞以及聯結詞、量詞等來表示環(huán)境狀態(tài)。這樣，問題的初始狀態(tài)可表示為：S0：AT(robot,alcove)∧EMPTY(robot)∧ON(books,a)∧CLEAR(b)TABLE(a)∧BOOKCASE(b)要求達到的目標狀態(tài)為：Sg：AT(robot,alcove)∧EMPTY(robot)∧ON(books,b)∧CLEAR(a)TABLE(a)∧BOOKCASE(b)1/14/20236061謂詞邏輯知識表示的例子解：⑶從初始狀態(tài)到達目標狀態(tài)的變遷，必須由機器人一步一步地執(zhí)行相應的操作序列，得以逐步實現。因此，必須要定義操作類謂詞。仔細加以分析，必要的操作謂詞共有三類。GOTO(x,w)：機器人從x走到w處；PICK-UP(x)：機器人在x處拿起書；SET-DOWN(w)：機器人在w處放下書。一般說來，如果定義謂詞太多，將造成信息冗余，增加了問題的復雜度；如果定義謂詞太少，就不夠用。因此，定義的謂詞性質與數量要合適。1/14/20236162謂詞邏輯知識表示的例子解：⑷按照行動規(guī)劃，仔細選擇操作，一步步進行狀態(tài)替換，直到達到目標狀態(tài)。即要求把狀態(tài)變遷過程和操作序列記錄下來，來描述問題解。下面寫出該過程的最優(yōu)路徑：

AT(robot,alcove)∧EMPTY(robot)∧ON(books,a)CLEAR(b)∧TABLE(a)∧BOOKCASE(b)AT(robot,a)∧EMPTY(robot)∧ON(books,a)CLEAR(b)∧TABLE(a)∧BOOKCASE(b)AT(robot,a)∧HOLDS(robot，books)∧CLEAR(a)CLEAR(b)∧TABLE(a)∧BOOKCASE(b)GOTO(alcove,a)PICK-UP（a）1/14/20236263謂詞邏輯知識表示的例子解：

AT(robot,a)∧HOLDS(robot，books)∧CLEAR(a)CLEAR(b)∧TABLE(a)∧BOOKCASE(b)

AT(robot,b)∧HOLDS(robot，books)∧CLEAR(a)CLEAR(b)∧TABLE(a)∧BOOKCASE(b)AT(robot,b)∧EMPTY(robot)∧ON(books,b)CLEAR(a)∧TABLE(a)∧BOOKCASE(b)AT(robot,alcove)∧EMPTY(robot)∧ON(books,b)CLEAR(a)∧TABLE(a)∧BOOKCASE(b)（解畢）GOTO（b,alcove）GOTO（a,b）SET-DOWN（b）1/14/20236364謂詞邏輯知識表示的例子解：這樣,得到目標為

AT(robot,alcove)∧EMPTY(robot)∧ON(books,b)CLEAR(a)∧TABLE(a)∧BOOKCASE(b)

這里順便指出，若機器人智商不高，這個任務過程會產生許多冗余。比如，機器人拿著書，找不到b處，無所適從而又扛回來了；或者……等?？梢姡瑢嶋H的機器人智能控制要更加復雜得多，雖然有時也很有趣。

1/14/202364例將自然數公理符號化：A1：每一個數，有且僅有一個直接后繼者；A2：沒有一個數使0是直接后繼者；A3：對任意異于0的數，有且僅有一個直接先行者。解：令f(x)表示x的直接后繼者g(x)表示x的直接先行者E(x,y)表示x等于y謂詞邏輯知識表示的例子1/14/202365于是將上述三個公理符號化如下：A1：每一個數，有且僅有一個直接后繼者

xy(E(y,f(x))∧z(E(z,f(x))→E(y,z)))A2：沒有一個數使0是直接后繼者～(xE(0,f(x)))A3：對任意異于0的數，有且僅有一個直接先行者x(～E(0,x)→y(E(y,g(x))∧z(E(z,g(x))→E(y,z))))1/14/202366解：令P(x)表示x是病人D(x)表示x是醫(yī)生Q(x)表示x是騙子L(x,y)表示x喜歡yA1=x(P(x)∧y(D(y)→L(x,y)))A2=～(xy(P(x)∧Q(y)∧L(x,y)))x(P(x)y(Q(y)～L(x,y)))

xy(P(x)∧Q(y)～L(x,y))B=x(D(x)→～Q(x))例已知某些病人喜歡所有的醫(yī)生，沒有一個病人喜歡任意一個騙子。證明任意一個醫(yī)生都不是騙子。1/14/202367剩下的任務就是調用某一過程證明A1∧A2→B是一階邏輯中的恒真公式，即B是A1、A2的邏輯結果。我們把它留到下一章中討論。1/14/20236869

邏輯知識表示的主要特點是建立在某種形式邏輯的基礎上，并利用了邏輯方法研究推理的規(guī)律，即條件與結論之間的蘊涵關系。邏輯表示法的主要優(yōu)點如下：

（1）自然

一階謂詞邏輯是一種接近于自然語言的形式語言系統(tǒng)，謂詞邏輯表示法接近于人們對問題的直觀理解，易于被人們接受。

（2）明確

邏輯表示法對如何由簡單陳述句構造復雜陳述句的方法有明確規(guī)定，如聯結詞、量詞的用法與含義等。對于用邏輯表示法表示的知識，人們都可以按照一種標準的方法去解釋它，因此用這種方法表示的知識明確、易于理解。謂詞邏輯表示的特性1/14/20236970（3）精確

謂詞邏輯是一種二值邏輯，其謂詞公式的真值只有“真”與“假”，因此可用來表示精確知識，并可保證經演繹推理所得結論的精確性。（4）靈活

邏輯表示法把知識和處理知識的程序有效地分開。在使用這種方法表示知識時，無須考慮程序中處理知識的細節(jié)。（5）模塊化

在邏輯表示法中，各條知識都是相對獨立的，它們之間不直接發(fā)生聯系。因此添加、刪除、修改知識的工作比較容易進行。謂詞邏輯表示的特性1/14/20237071

邏輯表示法也存在一些不足，其主要缺點如下：

（1）知識表示能力差

邏輯表示法只能表示確定性知識，而不能表示非確定性知識，如不精確、模糊性知識。實際上，人類的大部分知識都不同程度地具有某種不確定性，這就使得它表示知識的范圍和能力受到了一定的限制。另外，邏輯表示法還難以表示過程性知識和啟發(fā)性知識。

（2）知識庫管理困難

邏輯表示法缺乏知識的組織原則，利用這種表示法所形成的知識庫管理比較困難。

（3）存在組合爆炸

由于邏輯表示法難以表示啟發(fā)性知識，因此在推理過程中只能盲目地使用推理規(guī)則。這樣，當系統(tǒng)知識量較大時，容易發(fā)生組合爆炸。

（4）系統(tǒng)效率低

邏輯表示法的推理過程是根據形式邏輯進行的。它把推理演算與知識含義截然分開，拋棄了表達內容中所含有的語義信息，往往使推理過程冗長，降低了系統(tǒng)效率。謂詞邏輯表示的特性1/14/20237115前束范式

謂詞邏輯中公式G稱為前束范式，如果G有如下形狀：

Q1x1…QnxnM

其中Qixi或者是xi，或者是xi，i=1,…,n，M是不含量詞的公式，Q1x1…Qnxn稱為首標，M稱為母式。例如， xyz(P(x，y)Q(x，z))

xyzP(x，y，z)1/14/202372對任意謂詞公式，量詞是不能隨便提前的。？xP(x)P(a)=x(P(x)P(a))？xP(x)P(a)=x(P(x)P(a))1/14/202373xP(x)→P(a)是恒真公式.任取解釋I，若P(a)在I下為真,則xP(x)→P(a)在I下為真;若P(a)在I下為假,則xP(x)在I下為假,故xP(x)→P(a)在I下為真．因此,xP(x)→P(a)是恒真公式.1/14/202374而x(P(x)P(a))不是恒真公式。設解釋I為：D={1，2}a

1P(1)P(2)FT則TI(x(P(x)P(a)))=TI((P(1)P(1))(P(2)P(1)))=TF=F因此，xP(x)P(a)≠x(P(x)P(a))1/14/202375x（P(x)P(a)）為恒真公式。任取解釋I，由P(a)P(a)為真，知，存在xD，使得P(x)P(a)為真，即

x（P(x)P(a)）為真。因此，x（P(x)P(a)）為恒真公式。1/14/202376而xP(x)P(a)不是恒真公式。對于解釋I，若xP(x)在I下為F，則xP(x)P(a)在I下為T。若xP(x)在I下為T，則如果P(a)在I下為T，則xP(x)P(a)在I下為T，否則如果P(a)在I下為F，則xP(x)P(a)在I下為F。比如，對于前面給出的解釋I，TI(xP(x)P(a))=(P(1)P(2))P(1)=(FT)F=F因此，x(P(x)P(a))和xP(x)P(a)不等價。1/14/202377引理1設G是僅含有自由變量x的公式，記以G(x)，H是不含變量x的公式，于是有(1)x(G(x)∨H)=xG(x)∨H(1)’x(G(x)∨H)=xG(x)∨H(2)x(G(x)∧H)=xG(x)∧H(2)’x(G(x)∧H)=xG(x)∧H(3)～(xG(x))=x(～G(x))(4)～(xG(x))=x(～G(x))1/14/202378引理2設H，G是兩個僅含有自由變量x的公式，分別記以H(x)，G(x)，于是有：(1)xG(x)∧xH(x)=x(G(x)∧H(x))(2)xG(x)∨xH(x)=x(G(x)∨H(x))(3)xG(x)∨xH(x)=xy(G(x)∨H(y))(4)xG(x)∧xH(x)=xy(G(x)∧H(y))1/14/202379思考?xG(x)xH(x)＝x(G(x)H(x))?xG(x)xH(x)

x(G(x)H(x)) √?x(G(x)H(x))

xG(x)xH(x) ×1/14/202380設I為：D={a,b}G(a)G(b)H(a)H(b)TFFTTI(xG(x)xH(x))=FTI(x(G(x)H(x)))=T1/14/202381?xG(x)xH(x)＝x(G(x)H(x))?x(G(x)H(x))

xG(x)xH(x)

√?xG(x)xH(x)

x(G(x)H(x))

×1/14/202382設I為：D={a,b}G(a)G(b)H(a)H(b)TFFTTI(xG(x)xH(x))=TTI(x(G(x)H(x)))=F1/14/202383化前束范式定理1任意公式G都等價于一個前束范式．證明通過如下四個步驟即可將公式G化為前束范式．步驟1：使用基本等價式F?H=(F→H)∧(H→F)F→H=～F∨H可將公式G中的?和→刪去。步驟2：使用～(～F)=F和De.Morgan律及引理1，可將公式中所有否定號～放在原子之前。步驟3：如果必要的話，則將約束變量改名．步驟4：使用引理1和引理2又將所有量詞都提到公式的最左邊。1/14/202384例將xy(z(P(x,z)∧P(y,z))uQ(x,y,u))

化為前束范式．xy(z(P(x,z)∧P(y,z))uQ(x,y,u))=xy(～z(P(x,z)∧P(y,z))∨uQ(x,y,u))=xy(z～(P(x,z)∧P(y,z))∨uQ(x,y,u))=xy(z(～P(x,z)∨～P(y,z))∨uQ(x,y,u))=xyz((～P(x,z)∨～P(y,z))∨uQ(x,y,u))=xyzu(～P(x,z)∨～P(y,z)∨Q(x,y,u))1/14/202385例.將公式xy(A(x)B(x,y))(yC(y)zD(z))

化為前束范式。

解：（1）消去聯結詞。xy（A(x)B(x,y)）(yC(y)zD(z))=～xy（～A(x)B(x,y)）（～yC(y)zD(z))（2）將公式中所有否定號～放在原子之前。

～xy（～A(x)B(x,y)）（～yC(y)zD(z))=xy(A(x)～B(x,y))(y～C(y)zD(z))（3）將約束變量改名.xy(A(x)～B(x,y))(y～C(y)zD(z))=xy(A(x)～B(x,y))(t～C(t)zD(z))（4）將量詞提到整個公式前。xy(A(x)～B(x,y))(t～C(t)zD(z))=xytz（(A(x)～B(x,y))

～C(t)D(z)）=xytz((A(x)～C(t)D(z))(～B(x,y)～C(t)D(z)))1/14/20238616Skolem范式設G是一個公式，Q1x1…QnxnM是與G等價的前束范式，其中M為合取范式形式。若Qr是存在量詞，并且它左邊沒有全稱量詞，則取異于出現在M中所有常量符號的常量符號c，并用c代替M中所有的xr，然后在首標中刪除Qrxr。1/14/202387若Qs1,…,Qsm是所有出現在Qrxr左邊的全稱量詞(m1,1s1<s2<…<sm<r),則取異于出現在M中所有函數符號的m元函數符號f(xs1,…,xsm)，用f(xs1,…,xsm)代替出現在M中的所有xr，然后在首標中刪除Qrxr.1/14/202388對首標中的所有存在量詞做上述處理后，得到一個在首標中沒有存在量詞的前束范式，這個前束范式就稱為公式G的Skolem范式。其中用來代替xr的那些常量符號和函數符號稱為公式G的Skolem函數.1/14/202389轉化為Skolem范式的例子G=xyzuvwP(x,y,z,u,v,w)用a代替x，