邏輯表示及推理方法

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

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

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

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

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

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

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

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

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

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

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

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

13、等價(jià)的，記以G=H，如果G，H在其任意解釋I下，其真值相同。 公式G，H等價(jià) iff 公式G?H恒真。 基本等價(jià)式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； (結(jié)合律),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、 （互補(bǔ)律）12) ～～G=G （雙重否定律）,3/16/2024,17,17 公式的蘊(yùn)涵,設(shè)G，H是兩個(gè)公式。 稱(chēng)H是G的邏輯結(jié)果(或稱(chēng)G蘊(yùn)涵H)，當(dāng)且僅當(dāng)對(duì)G，H的任意解釋I，如果I滿足G，則I也滿足H，記作G?H。公式G蘊(yùn)涵公式H iff 公式G?H是恒真的。設(shè)G1, …, Gn，H是公式。 稱(chēng)H是G1, …,Gn的

17、邏輯結(jié)果(或稱(chēng)G1, …, Gn共同蘊(yùn)涵H)，當(dāng)且僅當(dāng) (G1? …? Gn) ? H。 例如，P，P?Q共同蘊(yùn)涵Q。,3/16/2024,18,基本蘊(yùn)涵式,P?Q?PP?Q?QP?P?QQ?P?Q～P?(P?Q)Q?(P?Q)～(P?Q)?P,3/16/2024,19,基本蘊(yùn)涵式,～(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 范式,有限個(gè)短語(yǔ)的析取式稱(chēng)為析取范式；有限個(gè)子句的合取式稱(chēng)為合取范式。特別，一個(gè)文字既可稱(chēng)為是一個(gè)合取范式，也可稱(chēng)為是一個(gè)析取范式。一個(gè)子句，一個(gè)短語(yǔ)既可看做是合取范式，也可看做是析取范式。例如，P，P?Q，P?Q，(P?Q)?(～P? ～Q)是析取范式。 P，P?Q，P?Q，(P?Q)?(～P?R)是合取范式。,3/16/2024,21,化范式方法：,步1. 使用基本等價(jià)式，將G中的邏輯聯(lián)結(jié)

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

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

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

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

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

24、題，這樣，謂詞邏輯包括命題邏輯。,3/16/2024,29,例.,D={2,3,4}設(shè)P(x)：x大于3，則P(x)為一元謂詞。 指定元素--命題：P(2)=F, P(3)=F, P(4)=T設(shè)P(x,y)：x大于y,則P(x,y)為二元謂詞。指定元素--命題：P(2,3)=F, P(4,2)=T設(shè)P(x,y,z)：若x+y-1=z，則P(x,y,z)為T(mén)，否則為F 。則P(x,y,z)為三元謂詞。指定元素--命題：P(2,

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

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

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

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

29、)?G(x1)?…,3/16/2024,35,例.將下列命題符號(hào)化：１)一切事物都是發(fā)展變化的　 ?x F(x) 其中F(x)：x是發(fā)展變化的２)存在著會(huì)說(shuō)話的機(jī)器人 ?x(F(x)?G(x))其中F(x)：x會(huì)說(shuō)話 G(x): x是機(jī)器人如果沒(méi)有明確給出個(gè)體域，則認(rèn)為個(gè)體域?yàn)橐磺惺挛铩?3/16/2024,36,3) 每個(gè)計(jì)算機(jī)學(xué)院的學(xué)生都學(xué)離散數(shù)學(xué)。D：全校學(xué)生集合P(x

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

31、約束的，當(dāng)且僅當(dāng)它出現(xiàn)在使用這個(gè)變量的量詞范圍之內(nèi)；稱(chēng)變量的出現(xiàn)是自由的，當(dāng)且僅當(dāng)這個(gè)出現(xiàn)不是約束的。 稱(chēng)變量是約束的，如果至少有一個(gè)它的出現(xiàn)是約束的； 稱(chēng)變量是自由的，如果至少有一個(gè)它的出現(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)都是表示個(gè)體域D中的“每個(gè)個(gè)體都具有性質(zhì)P”，所以可以把x改名為y，即把?xP(x)改成為?yP(y)。?xP(x)與?yP(y)都是表示個(gè)體域D中的“某個(gè)個(gè)體具有性質(zhì)P” ，所以也可以把x改名為y，即把?xP(x)改成為?yP(y)。亦即，謂詞邏輯中命題的真值，與命題中的約束變量的記法無(wú)關(guān)。這就引出了謂詞邏輯中的改名規(guī)則。,3/16/2024,40,,改名

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

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、中無(wú)自由變量，或?qū)⒆杂勺兞靠醋龀Ａ俊?(公式中每個(gè)變量的出現(xiàn)都是約束的）,3/16/2024,43,1) 常量符號(hào)：用小寫(xiě)英文字母a，b，c，…表示，當(dāng)個(gè)體名稱(chēng)集合D給出時(shí)，它可以是D中某個(gè)元素。2) 變量符號(hào)：用小寫(xiě)英文字母u，v，w，x，y，z，…表示，當(dāng)個(gè)體名稱(chēng)集合D給出時(shí)，D中任意元素可代入變量符號(hào)。,6 謂詞邏輯形式化中使用的四種符號(hào),3/16/2024,44,,3) 函數(shù)符號(hào)：用小寫(xiě)英文字母f，g，…表示，當(dāng)個(gè)體名稱(chēng)集合

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

37、) 所有項(xiàng)都是有限次使用1)，2)，3)生成的符號(hào)串。 8 原子若P(x1,…,xn)是n元謂詞符號(hào)，t1,…,tn是項(xiàng)，則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)生成的符號(hào)串。,3/16/2024,47,10 公式的語(yǔ)義解釋,謂詞邏輯中公式G的一個(gè)解釋I，是由非空區(qū)域D和對(duì)G中常量符號(hào)，函數(shù)符號(hào)，謂詞符號(hào)以下列規(guī)則進(jìn)行的一組指定組成：1. 對(duì)每個(gè)常量符號(hào)，指定D中一個(gè)元素；2. 對(duì)每個(gè)n元函數(shù)符號(hào)，指定一個(gè)函數(shù)，即指定Dn到D的一個(gè)映射；3. 對(duì)每個(gè)n元謂詞符號(hào)，指定一個(gè)謂詞，即指定Dn到{T，F(xiàn)}的一個(gè)映射。,3/16/2024,4

39、8,例:,1) G=?x(P(f(x))?Q(x，f(a)))2) H=?x(P(x)?Q(x，a)) 設(shè)解釋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稱(chēng)為可滿足的，如果存在解釋I，使G在I下取 T值，簡(jiǎn)稱(chēng)I滿足G。 若I不滿足G，則簡(jiǎn)稱(chēng)I弄假G。公式G稱(chēng)為是恒假的(或不可滿足的)，如果不存在解釋I滿足G。公式G稱(chēng)為恒真的，如果G的所有解釋I都滿足G。,3/16/2024,51,12 謂詞邏輯的判定問(wèn)題,謂詞邏輯中公式恒真、恒假性的判斷異常困難。原因？謂詞邏輯中的恒真(恒假)公式，要求所有解釋I都滿足(弄假)該公式。而解釋I依賴(lài)于一個(gè)非空集合

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

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

44、若I滿足G，則I必滿足H。同樣，命題邏輯中的基本蘊(yùn)涵式仍成立。,14 蘊(yùn)涵,3/16/2024,55,基本蘊(yùn)涵式：,(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,例.設(shè)G= ?x(A(x)?B(x))， H= ?x A(x)? ?x B(x) 證明： G?H證明：設(shè)I是滿足G的任意一個(gè)解釋。若TI(?x A(x))=F,則TI (?xA(x)??xB(x) )=T;若TI(?x A(

46、x))=T,則在I下對(duì)任意x?D，有TI(A(x))=T，又由TI(?x(A(x)?B(x)))=T知，對(duì)任意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不等價(jià)。舉反例：簡(jiǎn)單扼要、擊中要害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,設(shè)在一個(gè)含有凹室(alcove)的房間內(nèi)，有桌子A和書(shū)架B，一個(gè)機(jī)器人(robot)和 一疊書(shū)(book)?，F(xiàn)在要求機(jī)器人(robot)從凹室出發(fā)，把桌子A上的書(shū)搬

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

49、 z是書(shū)架， z的個(gè)體域： {b }；EMPTY(y)： y手中是空的， y的個(gè)體域： {robot}；HOLDS(y，u)：y手中拿著u， u的個(gè)體域： {books}；AT(y，w)： y在w處， w的個(gè)體域： {a，b，alcove }；ON(u，x)： u被放在x之上；CLEAR(v)： v上(中)是空的，v的個(gè)體域：{a，b }.,3/16/2024,60,60,謂詞邏輯知識(shí)表示的例子,解：⑵使

50、用謂詞以及聯(lián)結(jié)詞、量詞等來(lái)表示環(huán)境狀態(tài)。這樣，問(wèn)題的初始狀態(tài)可表示為：S0：AT(robot, alcove)∧EMPTY(robot)∧ON(books, a)∧CLEAR(b)TABLE(a)∧BOOKCASE (b)要求達(dá)到的目標(biāo)狀態(tài)為：Sg：AT(robot, alcove)∧EMPTY(robot)∧ON(books, b)∧CLEAR(a)TABLE(a)∧BOOKCASE (b),3/16/2024,61,

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

52、謂詞性質(zhì)與數(shù)量要合適。,3/16/2024,62,62,謂詞邏輯知識(shí)表示的例子,解：⑷按照行動(dòng)規(guī)劃，仔細(xì)選擇操作，一步步進(jìn)行狀態(tài)替換，直到達(dá)到目標(biāo)狀態(tài)。即要求把狀態(tài)變遷過(guò)程和操作序列記錄下來(lái)，來(lái)描述問(wèn)題解。下面寫(xiě)出該過(guò)程的最優(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,謂詞邏輯知識(shí)表示的例子,解： 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,謂詞邏輯知識(shí)表示的例子,解：這樣,得到目標(biāo)為  AT(robot, alcove)∧EMPTY(robot)∧ON(books, b)CLEAR(a)∧TABLE(a)∧BOOKCASE (b) 這里順便指

56、出，若機(jī)器人智商不高，這個(gè)任務(wù)過(guò)程會(huì)產(chǎn)生許多冗余。比如，機(jī)器人拿著書(shū)，找不到b處，無(wú)所適從而又扛回來(lái)了；或者……等。可見(jiàn)，實(shí)際的機(jī)器人智能控制要更加復(fù)雜得多，雖然有時(shí)也很有趣。,3/16/2024,65,例 將自然數(shù)公理符號(hào)化：A1：每一個(gè)數(shù)，有且僅有一個(gè)直接后繼者；A2：沒(méi)有一個(gè)數(shù)使0是直接后繼者；A3：對(duì)任意異于0的數(shù)，有且僅有一個(gè)直接先行者。解：令f(x)表示x的直接后繼者g(x)表示x的直接先行者E(x,y)表示

57、x等于y,謂詞邏輯知識(shí)表示的例子,3/16/2024,66,于是將上述三個(gè)公理符號(hào)化如下：A1：每一個(gè)數(shù)，有且僅有一個(gè)直接后繼者 ?x?y(E(y,f(x))∧?z(E(z,f(x))→E(y,z)))A2：沒(méi)有一個(gè)數(shù)使0是直接后繼者 ～(?xE(0,f(x)))A3：對(duì)任意異于0的數(shù)，有且僅有一個(gè)直接先行者 ?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ī)生， 沒(méi)有一個(gè)病人喜歡任意一個(gè)騙子。 證明任意一個(gè)醫(yī)生都不是騙子。,3/16/2024,68,剩下的任務(wù)就是調(diào)用某一過(guò)程證明A1∧A2→B是一階邏輯中的恒真公式，即B是A1、A2的邏輯結(jié)果。我們把它留到下一章中討論。,3/16/2024,69,69,邏輯知識(shí)表示的主要特點(diǎn)是建立在某種形式邏輯的基礎(chǔ)上，并利用了邏輯方法研究推理的規(guī)律，即條件與

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

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

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

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

64、 其中 Qixi或者是?xi，或者是?xi，i=1,…,n， M是不含量詞的公式，Q1x1…Qnxn稱(chēng)為首標(biāo)，M稱(chēng)為母式。例如，?x?y?z(P(x，y)?Q(x，z)) ?x?y?zP(x，y，z),3/16/2024,73,對(duì)任意謂詞公式，量詞是不能隨便提前的。？ ?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))不是恒真公式。設(shè)解釋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)不是恒真公式。對(duì)于解釋I，若?xP(x)在I下為F，則?xP(x) ?P(a)在I下為T(mén)。若?xP(x)在I下為T(mén)，則如果P(a)在I下為T(mén)，則?xP(x) ?P(a)在I下為T(mén)，否則如果P(a)在I下為F，則?xP(x) ?P(a)在I下為F。比如，對(duì)于前面給出的解釋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)不等價(jià)。,3/16/2024,78,引理1 設(shè)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