邏輯表示及推理方法

1、3/16/2024,1,第三部分 邏輯表示及推理方法,常用的知識表示方法：非結構化方法邏輯表示法 QA3,STRIPS,DART,MOMO產(chǎn)生式系統(tǒng) DENDRAL，MYCIN結構化方法框架語義網(wǎng)絡過程式知識表示法,3/16/2024,2,第五章 謂詞演算（復習）,數(shù)理邏輯思想的起源：Leibnitz之夢 產(chǎn)生的歷史：Boole的工作、Frege的工作 發(fā)展的現(xiàn)實：計算機學科的基礎（軟件到硬件）

2、 古典數(shù)理邏輯主要包括兩部分：命題邏輯和謂詞邏輯。 命題邏輯又是謂詞邏輯的一種簡單情形。邏輯研究的基本內(nèi)容 語法 語言部分：基本符號集、公式形成規(guī)則 推理部分：公理集、推理規(guī)則 語義 語法和語義之間的關系：可靠性、完備性基本問題 邏輯表示下的判定問題,3/16/2024,3,一、命題邏輯,1 命題 一句有真假意義的話。用大寫英文字母P，Q，…，P1

3、，P2，…，表示。 例： 上海是中國最大的城市。 今天是星期日。所有素數(shù)都是奇數(shù)。 1+1=2。我不會解答這道題。 別的星球上有生物。長春今天下雪。如果太陽從西方升起，你就可以長生不老。 嚴禁吸煙。 今天的溫度有多少度？ 全體起立！ 今天好冷??！ 我正在說謊。,,3/16/2

4、024,4,2 真值,如果一個命題是真的，就說它的真值是T； 如果一個命題是假的，就說它的真值是F。 T和F統(tǒng)稱為命題的真值。 也用T代表一個抽象的真命題，用F代表一個抽象的假命題。,3/16/2024,5,3 聯(lián)結詞 ～、 ∨、 ∧、 →、 ?,設P是一個命題，命題 “P是不對的”稱為P的否定，記以～P，讀作非P。例.Q:張三是好人。 ～Q ：張三不是好人。語義規(guī)定： ～P是真的當且僅當P是假的。

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

6、Q是真的當且僅當P和Q都是真的。設P，Q是兩個命題，命題 “如果P，則Q”稱為P蘊涵Q，記以P?Q。例. P：f(x)是可微的， Q：f(x)是連續(xù)的，P?Q： 若f(x)是可微的，則f(x)是連續(xù)的。語義規(guī)定： P?Q是假的當且僅當P是真的而Q是假的。,3/16/2024,7,,設P，Q是兩個命題，命題 “P當且僅當Q”稱為P等價Q，記以P?Q。語義規(guī)定： P?Q是真的當且僅當P，Q或者都是真的，或者都是假的。例

7、 P ：a2+b2=a2，Q： b=0，P?Q： a2+b2=a2當且僅當b=0 。五種邏輯聯(lián)結詞的優(yōu)先級按如下次序遞增： ?，?，?，?， ～例. 符號串 P?Q?R?Q? ～S?R 意味著： ((P?(Q?R))?(Q?((～S)?R))),3/16/2024,8,,4 復合命題 用聯(lián)結詞將簡單命題連接的結果。5 原子 命題的抽象。 用大寫的英文

8、字母P，Q，R，…等表示。6 文字 原子或原子的否定。7 子句 有限個文字的析取式稱為一個子句。 特別，沒有文字的子句稱為空子句，記為 ?。 只有一個文字的子句稱為單元子句。8 短語 有限個文字的合取式稱為一個短語。,3/16/2024,9,復合命題的抽象 公式的形成規(guī)則--是如下定義的一個符號串：(1)原子是公式；(2)F、T是公式； (3)若G，H是公式，則(～

9、G)，(G?H)，(G?H)，(G?H)，(G?H)是公式；(4)所有公式都是有限次使用(1)，(2)，(3)得到的符號串。,9 公式,3/16/2024,10,設G是命題公式,A1,…,An是出現(xiàn)在G中的所有原子。指定A1,…,An的一組真值,則這組真值稱為G的一個解釋。設G是公式，I是G的一個解釋，G在I下的真值記為TI(G)。例.G=P?Q，設解釋I，I’如下：I：

10、 I’：則TI (G)=T，TI’ (G)=F 注意：該例子中寫成G=T或G=F是錯誤的！,10 解釋,P Q,,T T,3/16/2024,11,,11 真值表 公式G在其所有可能的解釋下所取真值的表，稱為G的真值表。 有n個不同原子的公式，共有2n個解釋。 12 恒真公式 公式G稱為恒真的(或有效的)，如果G在它的所有解釋下都是真的.,3/16/2024,

11、12,,13 恒假公式 公式G稱為恒假的(或不可滿足的)，如果G在它的所有解釋下都是假的.14 可滿足公式 公式G稱為可滿足的，如果它不是恒假的。G是恒真的 iff ～ G是恒假的。G是可滿足的 iff 至少有一個解釋I，使G在I下為真。若G是恒真的，則G是可滿足的； 反之不對。如果公式G在解釋I下是真的，則稱I滿足G； 如果G在解釋I下是假的，則稱I弄假G。,3/16/2024,13,例.考慮G1= ～(P

12、→Q) →P，G2=(P →Q) ?P， G3=P ? ～P。,,,,,,,,,,,,,,,,,3/16/2024,14,15 判定問題,能否給出一個可行方法，對任意的公式，判定其是否是恒真公式。命題邏輯可判定？ 原因？ 因為一個命題公式的原子數(shù)目有限(n)，從而解釋的數(shù)目是有限的(2n)，所以命題邏輯的判定問題是可解的(可判定的，可計算的).,3/16/2024,15,16 公式等價,稱公式G，H是

13、等價的，記以G=H，如果G，H在其任意解釋I下，其真值相同。 公式G，H等價 iff 公式G?H恒真。 基本等價式1) (G?H)=(G?H)?(H?G)； 2) (G?H)=(～G?H)； 3) G?G=G，G?G=G； (等冪律)4) G?H=H?G，G?H=H?

14、G； (交換律)5) G?(H?S)=(G?H)?S， G?(H?S)=(G?H)?S； (結合律),3/16/2024,16,6) G?(G?H)=G，G?(G?H)=G； (吸收律)7) G?(H?S)=(G?H)?(G?S)， G?(H?S)=(G?H)?(G?S)； (分配律)8) G?F=G

15、，G?T=G； (同一律)9) G?F=F，G?T=T； (零一律)10) ～(G?H)= ～G?～H， ～(G?H)= ～G?～H。 (De Morgan律)11) G?～G=T；G?～G=F

16、 （互補律）12) ～～G=G （雙重否定律）,3/16/2024,17,17 公式的蘊涵,設G，H是兩個公式。 稱H是G的邏輯結果(或稱G蘊涵H)，當且僅當對G，H的任意解釋I，如果I滿足G，則I也滿足H，記作G?H。公式G蘊涵公式H iff 公式G?H是恒真的。設G1, …, Gn，H是公式。 稱H是G1, …,Gn的

17、邏輯結果(或稱G1, …, Gn共同蘊涵H)，當且僅當 (G1? …? Gn) ? H。 例如，P，P?Q共同蘊涵Q。,3/16/2024,18,基本蘊涵式,P?Q?PP?Q?QP?P?QQ?P?Q～P?(P?Q)Q?(P?Q)～(P?Q)?P,3/16/2024,19,基本蘊涵式,～(P?Q)? ～QP，Q?P?Q～P，P?Q?QP，P?Q?Q～Q，P?Q? ～PP?Q，Q?R?P?RP?Q，P?R，Q?R

18、?R,3/16/2024,20,18 范式,有限個短語的析取式稱為析取范式；有限個子句的合取式稱為合取范式。特別，一個文字既可稱為是一個合取范式，也可稱為是一個析取范式。一個子句，一個短語既可看做是合取范式，也可看做是析取范式。例如，P，P?Q，P?Q，(P?Q)?(～P? ～Q)是析取范式。 P，P?Q，P?Q，(P?Q)?(～P?R)是合取范式。,3/16/2024,21,化范式方法：,步1. 使用基本等價式，將G中的邏輯聯(lián)結

19、詞?，?刪除。步2. 使用～(～H)=H和摩根律， 將G中所有的否定號～都放在原子之前。 步3. 反復使用分配律，即可得到等價于G的范 式。,3/16/2024,22,19 演繹,設S是一個命題公式的集合(前提集合)。從S推出公式G的一個演繹是公式的一個有限序列：G1, G2, …, Gk 其中，Gi （1≤i ≤ k）或者屬于S，或者是某些 Gj (j<i)的邏輯結果。 并且 Gk就

20、是G。稱公式G為“此演繹的” 邏輯結果，或稱從S演繹出G。 有時也記為S?G。,3/16/2024,23,,例. 設S={P?Q，Q?R，P?M， ～M} 則下面的公式序列: ～M，P?M， ～P，P?Q，Q，Q?R，R就是從S推出R的一個演繹。演繹方法的可靠性與完備性 設S是公式集合，G是一個公式。于是，從S演繹出G的充要條件是G是S的邏輯結果。,3/16/2024,24,命題邏輯的缺陷,把問題看成一個個孤立的命題，忽略

21、了問題之間的聯(lián)系，無法描述客觀事物的結構，不能反映某些重要的常見的邏輯思維過程。1 繁瑣例.表述集合個體性質及相互關系 S={1,2,…,50}表述S中元素大于3這樣一個性質，需要1>3,2>3,…,50>3等50個命題。,3/16/2024,25,2 不能描述問題間的邏輯聯(lián)系例如，邏輯學中著名的三段論：P：凡人必死Q：張三是人R：張三必死 在命題邏輯中：應該有(P?Q) ?R，

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

23、張三”是主語，稱為個體。,3/16/2024,28,二、謂詞邏輯,1 謂詞可以獨立存在的物體稱為個體。 如人、學生、桌子、自然數(shù)等都可以做個體。在謂詞演算中，個體通常指一個命題里的思維對象。設D是非空個體名稱集合，定義在Dn上取值于{T，F(xiàn)}上的n元函數(shù)，稱為n元命題函數(shù)或n元謂詞。其中Dn表示集合D的n次笛卡爾乘積。一般地，一元謂詞描述個體的性質，二元或多元謂詞描述兩個或多個個體間的關系。0元謂詞中無個體，理解為就是命

24、題，這樣，謂詞邏輯包括命題邏輯。,3/16/2024,29,例.,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,

25、3,4)=T,P(4,2,2)=F,3/16/2024,30,例.,用謂詞的概念可將三段論做如下的符號化： 令H(x)表示 “x是人”，M(x)表示 “x必死”。 則三段論的三個命題表示如下：P： H(x)?M(x)Q： H(張三)R： M(張三),3/16/2024,31,,若想得到 “命題”P的否定 “命題”，應該就是“命題” ～P。但是， ～P= ～(H(x)?M(x))

26、= ～(～H(x)?M(x))=H(x)? ～M(x)　亦即，“命題”P的否定 “命題”是 “所有人都不死”。這和人們?nèi)粘γ} “所有人都必死”的否定的理解，相差得實在太遠了.,3/16/2024,32,原因－－命題P的確切意思應該是： “對任意x，如果x是人，則x必死”。 但是H(x)?M(x)中并沒有確切的表示出 “對任意x”這個意思，亦即H(x)?M(x)不是一個命題。 因此，在謂詞邏輯中除引進謂詞外，還需要引進

27、“對任意x”這個語句，及其對偶的語句 “存在一個x”。,3/16/2024,33,2 量詞,定義 語句 “對任意x”稱為全稱量詞，記以?x； 語句 “存在一個x”稱為存在量詞，記以?x。這時，命題P就可確切地符號化如下：?x(H(x)?M(x)) 命題P的否定命題為： ～ P= ～(?x(H(x)?M(x)))=?x(H(x)? ～M(x))亦即 “有一個人是不死的”。這個命題確實是

28、 “所有人都要死”的否定。 三段論的三個命題，在謂詞邏輯中是如下這樣表示的：P：?x(H(x)?M(x))Q：H(張三)R：M(張三),3/16/2024,34,,量詞的語義規(guī)定 ?xG(x)取T值?對任意x?D，G(x)都取T值； ?xG(x)取T值?至少有一個x0?D，使G(x0)取T值 語義上，當D={x0,x1,…}是可數(shù)集合時，?xG(x)等價于G(x0)?G(x1)?…?xG(x)等價于G(x0

29、)?G(x1)?…,3/16/2024,35,例.將下列命題符號化：１)一切事物都是發(fā)展變化的　 ?x F(x) 其中F(x)：x是發(fā)展變化的２)存在著會說話的機器人 ?x(F(x)?G(x))其中F(x)：x會說話 G(x): x是機器人如果沒有明確給出個體域，則認為個體域為一切事物。,3/16/2024,36,3) 每個計算機學院的學生都學離散數(shù)學。D：全校學生集合P(x

30、)：x是計算機學院的學生R(x): x學離散數(shù)學?x(P(x) →R(x))4）存在著偶素數(shù)D：正整數(shù)集合E(x)：x是偶數(shù)P(x)：x是素數(shù)?x(E(x)?P(x)),3/16/2024,37,5) 每個人都會犯錯誤R(x):x是人P(x):x會犯錯誤?x(R(x) →P(x)),3/16/2024,38,3 約束變量、自由變量,在一個由謂詞，量詞，邏輯聯(lián)結詞，括號組成的有意義的符號串(公式)中，稱變量的出現(xiàn)是

31、約束的，當且僅當它出現(xiàn)在使用這個變量的量詞范圍之內(nèi)；稱變量的出現(xiàn)是自由的，當且僅當這個出現(xiàn)不是約束的。 稱變量是約束的，如果至少有一個它的出現(xiàn)是約束的； 稱變量是自由的，如果至少有一個它的出現(xiàn)是自由的。例如，?x(P(x，y)?Q(x，z))?R(x)從左向右算起，變量x的第一，第二次出現(xiàn)是約束的，第三次出現(xiàn)是自由的；變量y，z的出現(xiàn)是自由的。x既是約束變量，又是自由變量；y，z只是自由變量。,3/16/2024,

32、39,4 約束變量的改名規(guī)則,改名規(guī)則的理論依據(jù)?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ī)則。,3/16/2024,40,,改名

33、規(guī)則：在由謂詞，量詞，邏輯聯(lián)結詞，括號組成的有意義的符號串(公式)中，可將其中出現(xiàn)的約束變量改為另一個約束變量，這種改名必須在量詞作用區(qū)域內(nèi)各處以及該量詞符號中實行，并且改成的新約束變量要有別于改名區(qū)域中的所有其它變量。顯然改名規(guī)則不改變原符號串的真值。,3/16/2024,41,例:,對于?x(P(x，y)?Q(x，z)) ? R(x, v)，可改名為?u(P(u，y)?Q(u，z)) ? R(x, v) 。但下面的改名都是不對

34、的： 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),3/16/2024,42,5 封閉公式,公式

35、中無自由變量，或將自由變量看做常量。 (公式中每個變量的出現(xiàn)都是約束的）,3/16/2024,43,1) 常量符號：用小寫英文字母a，b，c，…表示，當個體名稱集合D給出時，它可以是D中某個元素。2) 變量符號：用小寫英文字母u，v，w，x，y，z，…表示，當個體名稱集合D給出時，D中任意元素可代入變量符號。,6 謂詞邏輯形式化中使用的四種符號,3/16/2024,44,,3) 函數(shù)符號：用小寫英文字母f，g，…表示，當個體名稱集合

36、D給出時，n元函數(shù)符號f(x1，…，xn)可以是Dn到D的任意一個映射。4) 謂詞符號：用大寫英文字母P，Q，R，…表示，當個體名稱集合D給出時，n元謂詞符號P(x1，…，xn)可以是Dn上的任意一個謂詞。,3/16/2024,45,,7 項謂詞邏輯中的項，被遞歸定義為：1) 常量符號是項；2) 變量符號是項；3) 若f(x1, …, xn)是n元函數(shù)符號，t1, …, tn是項，則f(t1, …, tn)是項；4

37、) 所有項都是有限次使用1)，2)，3)生成的符號串。 8 原子若P(x1,…,xn)是n元謂詞符號，t1,…,tn是項，則P(t1,…,tn)是原子。,3/16/2024,46,9 公式,謂詞邏輯中的公式，被遞歸定義如下：1) 原子是公式；2) 若G，H是公式，則(～G)，(G?H)， (G?H)， (G?H)，(G?H)是公式；3) 若G是公式，x是G中的自由變量，則?xG，?xG是公式；

38、4) 所有公式都是有限次使用1)～3)生成的符號串。,3/16/2024,47,10 公式的語義解釋,謂詞邏輯中公式G的一個解釋I，是由非空區(qū)域D和對G中常量符號，函數(shù)符號，謂詞符號以下列規(guī)則進行的一組指定組成：1. 對每個常量符號，指定D中一個元素；2. 對每個n元函數(shù)符號，指定一個函數(shù)，即指定Dn到D的一個映射；3. 對每個n元謂詞符號，指定一個謂詞，即指定Dn到{T，F(xiàn)}的一個映射。,3/16/2024,4

39、8,例:,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) 3 2 P(2) P(3) Q(2, 2) Q(2, 3) Q(3, 2) Q(3, 3) F T T T

40、F T,3/16/2024,49,例:,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)))=(T?T)?(F?T)=TTI(H)= TI(P(2)?Q(2，2)?P(3)?Q(3，2))=F?T?T?F=F,3/16/2024,50,11 謂詞公式的

41、恒真、恒假、可滿足,公式G稱為可滿足的，如果存在解釋I，使G在I下取 T值，簡稱I滿足G。 若I不滿足G，則簡稱I弄假G。公式G稱為是恒假的(或不可滿足的)，如果不存在解釋I滿足G。公式G稱為恒真的，如果G的所有解釋I都滿足G。,3/16/2024,51,12 謂詞邏輯的判定問題,謂詞邏輯中公式恒真、恒假性的判斷異常困難。原因？謂詞邏輯中的恒真(恒假)公式，要求所有解釋I都滿足(弄假)該公式。而解釋I依賴于一個非空集合

42、D。由于集合D可以是無窮集合，而集合D的 “數(shù)目”也可能是無窮多個。因此，所謂公式的 “所有”解釋，實際上是無法考慮的。1936年Church和Turing分別獨立地證明了：對于謂詞邏輯，判定問題是不可解的。,3/16/2024,52,,謂詞邏輯是半可判定的： 如果謂詞邏輯中的公式是恒真的，則有算法在有限步之內(nèi)檢驗出這個公式的恒真性。如果該公式不是恒真的(當然也不是恒假的)，則無法在有限步內(nèi)判定這個事實。,3/16/20

43、24,53,13 等價,公式G，H稱為等價，記以G=H，如果公式G?H是恒真的。公式G，H等價的充要條件是：對G，H的任意解釋I，G，H在I下的真值相同。因為對任意公式G，H，在解釋I下，G，H就是兩個命題，所以命題邏輯中給出的基本等價式，在謂詞邏輯中仍然成立。,3/16/2024,54,設G，H是公式，稱G蘊涵H，或H是G的邏輯結果，如果公式G?H是恒真的，并記以G?H。對任意兩個公式G，H，G蘊涵H的充要條件是：對任意解釋I，

44、若I滿足G，則I必滿足H。同樣，命題邏輯中的基本蘊涵式仍成立。,14 蘊涵,3/16/2024,55,基本蘊涵式：,(P∨P) ? PP ?(P∨Q)(P∨Q) ?(Q∨P)(Q→R) ? ((P∨Q) →(P∨R))?xP(x) ? P(y)P(y) ? ?xP(x)?x P(x) ? ?xP(x)?x P(x) ∨?x Q(x) ? ?x (P(x)∨Q(x))?x(P(x) ∧Q(x)) ? ?xP(x) ∧?

45、xQ(x)?x (P(x) → Q(x)) ? ?x P(x) →?x Q(x)?x (P(x) → Q(x)) ? ?x P(x) →?x Q(x),3/16/2024,56,例.設G= ?x(A(x)?B(x))， H= ?x A(x)? ?x B(x) 證明： G?H證明：設I是滿足G的任意一個解釋。若TI(?x A(x))=F,則TI (?xA(x)??xB(x) )=T;若TI(?x A(

46、x))=T,則在I下對任意x?D，有TI(A(x))=T，又由TI(?x(A(x)?B(x)))=T知，對任意x?D， TI(A(x)?B(x)) =T，故TI(B(x))=T， 即，TI(?x(B(x)))=T，因此， TI (?xA(x)??xB(x) )=T。,3/16/2024,57,G，H不等價。舉反例：簡單扼要、擊中要害I: D={2，3} A(2) A(3) B(2) B(3

47、) T F F FTI(G)=FTI(H)=T,G= ?x(A(x)?B(x))，H= ?x A(x)? ?x B(x) ？ H ? G,3/16/2024,58,58,設在一個含有凹室(alcove)的房間內(nèi)，有桌子A和書架B，一個機器人(robot)和 一疊書(book)。現(xiàn)在要求機器人(robot)從凹室出發(fā)，把桌子A上的書搬

48、到B處書架上，完成任務后回到凹室。請用謂詞邏輯描述機器人完成這一工作的全過程。,謂詞邏輯知識表示的例子,3/16/2024,59,59,謂詞邏輯知識表示的例子,解：⑴為了能夠描述這個機器人世界的有關環(huán)境和狀態(tài)變遷，要求必須先定義謂詞。注意這里需要定義兩類謂詞：一類用來描述環(huán)境狀態(tài)，另一類謂詞用來表示機器人的操作。首先定義描述環(huán)境狀態(tài)的謂詞。TABLE(x)： x是桌子， x的個體域： {a }；BOOKCASE(z)：

49、 z是書架， z的個體域： {b }；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 }.,3/16/2024,60,60,謂詞邏輯知識表示的例子,解：⑵使

50、用謂詞以及聯(lián)結詞、量詞等來表示環(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),3/16/2024,61,

51、61,謂詞邏輯知識表示的例子,解：⑶從初始狀態(tài)到達目標狀態(tài)的變遷，必須由機器人一步一步地執(zhí)行相應的操作序列，得以逐步實現(xiàn)。因此，必須要定義操作類謂詞。仔細加以分析，必要的操作謂詞共有三類。GOTO(x, w)：機器人從x走到w處；PICK-UP(x) ：機器人在x處拿起書；SET-DOWN(w) ：機器人在w處放下書。 一般說來，如果定義謂詞太多，將造成信息冗余，增加了問題的復雜度；如果定義謂詞太少，就不夠用。因此，定義的

52、謂詞性質與數(shù)量要合適。,3/16/2024,62,62,謂詞邏輯知識表示的例子,解：⑷按照行動規(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(rob

53、ot)∧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）,3/16/2024,63,63,謂詞邏輯知識表示的例子,解： AT(robot, a)∧HOLDS(robot，books)∧CLE

54、AR(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,

55、 b)CLEAR(a)∧TABLE(a)∧BOOKCASE (b) （解畢）,GOTO（b, alcove）,,GOTO（a, b）,,SET-DOWN（b）,3/16/2024,64,64,謂詞邏輯知識表示的例子,解：這樣,得到目標為  AT(robot, alcove)∧EMPTY(robot)∧ON(books, b)CLEAR(a)∧TABLE(a)∧BOOKCASE (b) 這里順便指

56、出，若機器人智商不高，這個任務過程會產(chǎn)生許多冗余。比如，機器人拿著書，找不到b處，無所適從而又扛回來了；或者……等?？梢姡瑢嶋H的機器人智能控制要更加復雜得多，雖然有時也很有趣。,3/16/2024,65,例 將自然數(shù)公理符號化：A1：每一個數(shù)，有且僅有一個直接后繼者；A2：沒有一個數(shù)使0是直接后繼者；A3：對任意異于0的數(shù)，有且僅有一個直接先行者。解：令f(x)表示x的直接后繼者g(x)表示x的直接先行者E(x,y)表示

57、x等于y,謂詞邏輯知識表示的例子,3/16/2024,66,于是將上述三個公理符號化如下：A1：每一個數(shù)，有且僅有一個直接后繼者 ?x?y(E(y,f(x))∧?z(E(z,f(x))→E(y,z)))A2：沒有一個數(shù)使0是直接后繼者 ～(?xE(0,f(x)))A3：對任意異于0的數(shù)，有且僅有一個直接先行者 ?x(～E(0,x)→?y(E(y,g(x))∧?z(E(z,g(x))→E(y,z)))),3

58、/16/2024,67,解：令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=～(?x?y(P(x) ∧Q(y)∧L(x,y))) ?x(P(x) ??y(Q(y) ?～L(x, y))) ?x?y(P(x)∧Q(y) ?～L

59、(x, y))B=?x(D(x)→～Q(x)),例 已知某些病人喜歡所有的醫(yī)生， 沒有一個病人喜歡任意一個騙子。 證明任意一個醫(yī)生都不是騙子。,3/16/2024,68,剩下的任務就是調(diào)用某一過程證明A1∧A2→B是一階邏輯中的恒真公式，即B是A1、A2的邏輯結果。我們把它留到下一章中討論。,3/16/2024,69,69,邏輯知識表示的主要特點是建立在某種形式邏輯的基礎上，并利用了邏輯方法研究推理的規(guī)律，即條件與

60、結論之間的蘊涵關系。邏輯表示法的主要優(yōu)點如下：（1）自然 一階謂詞邏輯是一種接近于自然語言的形式語言系統(tǒng)，謂詞邏輯表示法接近于人們對問題的直觀理解，易于被人們接受。（2）明確 邏輯表示法對如何由簡單陳述句構造復雜陳述句的方法有明確規(guī)定，如聯(lián)結詞、量詞的用法與含義等。對于用邏輯表示法表示的知識，人們都可以按照一種標準的方法去解釋它，因此用這種方法表示的知識明確、易于理解。,謂詞邏輯表示的特性,3/16/2024,70,

61、70,（3）精確 謂詞邏輯是一種二值邏輯，其謂詞公式的真值只有“真”與“假”，因此可用來表示精確知識，并可保證經(jīng)演繹推理所得結論的精確性。（4）靈活 邏輯表示法把知識和處理知識的程序有效地分開。在使用這種方法表示知識時，無須考慮程序中處理知識的細節(jié)。,（5）模塊化 在邏輯表示法中，各條知識都是相對獨立的，它們之間不直接發(fā)生聯(lián)系。因此添加、刪除、修改知識的工作比較容易進行。,謂詞邏輯表示的特性,3/16/2024

62、,71,71,邏輯表示法也存在一些不足，其主要缺點如下：（1）知識表示能力差 邏輯表示法只能表示確定性知識，而不能表示非確定性知識，如不精確、模糊性知識。實際上，人類的大部分知識都不同程度地具有某種不確定性，這就使得它表示知識的范圍和能力受到了一定的限制。另外，邏輯表示法還難以表示過程性知識和啟發(fā)性知識。（2）知識庫管理困難 邏輯表示法缺乏知識的組織原則，利用這種表示法所形成的知識庫管理比較困難。（3）存在組合爆炸

63、 由于邏輯表示法難以表示啟發(fā)性知識，因此在推理過程中只能盲目地使用推理規(guī)則。這樣，當系統(tǒng)知識量較大時，容易發(fā)生組合爆炸。（4）系統(tǒng)效率低 邏輯表示法的推理過程是根據(jù)形式邏輯進行的。它把推理演算與知識含義截然分開，拋棄了表達內(nèi)容中所含有的語義信息，往往使推理過程冗長，降低了系統(tǒng)效率。,謂詞邏輯表示的特性,3/16/2024,72,15 前束范式,謂詞邏輯中公式G稱為前束范式，如果G有如下形狀：Q1x1…QnxnM

64、 其中 Qixi或者是?xi，或者是?xi，i=1,…,n， M是不含量詞的公式，Q1x1…Qnxn稱為首標，M稱為母式。例如，?x?y?z(P(x，y)?Q(x，z)) ?x?y?zP(x，y，z),3/16/2024,73,對任意謂詞公式，量詞是不能隨便提前的。？ ?xP(x) ?P(a) =?x(P(x) ?P(a))？ ?xP(x) ?P(a) =?x(P(x) ?P(a)),3/

65、16/2024,74,,?xP(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) 是恒真公式.,3/16/2024,75,,而?x(P(x) ?P(a))不是恒真公式。設解釋I為： D={1，2} a 1 P(1) P(2)

66、 F T 則 TI(?x(P(x) ?P(a))) = TI ((P(1) ?P(1)) ?(P(2) ?P(1))) = T ? F = F因此， ?xP(x) ?P(a) ≠?x(P(x) ?P(a)),3/16/2024,76,,?x（P(x) ?P(a)）為恒真公式。任取解釋I，由P(a) ?P(a)為真，知， 存在x?D，使得P(x) ?P(a)為真，即

67、 ?x（P(x) ?P(a)）為真。因此，?x（P(x) ?P(a)）為恒真公式。,3/16/2024,77,,而?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(

68、?xP(x) ?P(a))= (P(1)?P(2)) ?P(1)= (F?T) ?F= F因此，?x(P(x) ?P(a))和?xP(x) ?P(a)不等價。,3/16/2024,78,引理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