人工智能重點(diǎn)總結(jié)(編輯修改稿)
2025-07-24 08:27 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 代替C1和C2后得到新子句集S1，則由S1的不可滿足性可推出原子句集S的不可滿足性，即：S1的不可滿足性S的不可滿足性推論2 設(shè)C1與C2是子句集S中的兩個(gè)子句，C12是它們的歸結(jié)式。若把C12加入S中得到新子句集S2，則S與S2在不可滿足的意義上是等價(jià)的，即：S2的不可滿足性S的不可滿足性推論1及推論2保證了我們可以用歸結(jié)的方法來(lái)證明子句集S的不可滿足性。為了要證明子句集S的不可滿足性，只要對(duì)其中可進(jìn)行歸結(jié)的子句進(jìn)行歸結(jié)，并把歸結(jié)式加入子句集S，或者用歸結(jié)式替換它的親本子句，然后對(duì)新子句集(S1或者S2)證明不可滿足性就可以了。如果經(jīng)過(guò)歸結(jié)能得到空子句，則立即可得原子句集S是不可滿足的結(jié)論。在命題邏輯中，對(duì)不可滿足的子句集S，歸結(jié)原理是完備的。即，若子句集不可滿足，則必然存在一個(gè)從S到空子句的歸結(jié)演繹；若存在一個(gè)從S到空子句的歸結(jié)演繹，則S一定是不可滿足的。u 命題邏輯中的歸結(jié)原理 若P是原子謂詞公式，則稱P與172。P為互補(bǔ)文字。在命題邏輯中，P為命題。 設(shè)C1與C2是子句集中的任意兩個(gè)子句。如果C1中的文字L1與C2中文字L2互補(bǔ)，那么從C1和C2中分別消去L1和L2，并將兩個(gè)子句中余下的部分析取，構(gòu)成一個(gè)新子句C12，則稱這一過(guò)程為歸結(jié)。稱C12為C1和C2的歸結(jié)式，C1和C2為C12的親本子句。 設(shè)C1=172。P∨Q, C2=172。Q∨R, C3=PC1與C2歸結(jié)得到：C12=172。P∨RC12與C3歸結(jié)得到：C123=Ru 謂詞邏輯中的歸結(jié)原理在謂詞邏輯中，由于子句中含有變?cè)?，所以不能像命題邏輯那樣直接消去互補(bǔ)文字，而需要先用最一般合一對(duì)變?cè)M(jìn)行代換，然后才能進(jìn)行歸結(jié)。例如,設(shè)有兩個(gè)子句C1=P(x)∨Q(x), C2= 172。P(a)∨R(y)由于P(x)與P(a)不同，所以C1與C2不能直接進(jìn)行歸結(jié)。但是若用最一般合一σ={a/x}對(duì)兩個(gè)子句分別進(jìn)行代換：C1σ =P(a)∨Q(a) C2σ = 172。P(a)∨R(y)就可對(duì)它們進(jìn)行歸結(jié)，得到歸結(jié)式：Q(a)∨R(y)u 歸結(jié)反演及其示例*如欲證明Q為P1,P2,…,Pn的邏輯結(jié)論，只需證(P1∧P2∧…∧Pn)∧172。Q是不可滿足的，或證明其子句集是不可滿足的。而子句集的不可滿足性可用歸結(jié)原理來(lái)證明。216。 應(yīng)用歸結(jié)原理證明定理的過(guò)程稱為歸結(jié)反演。216。 設(shè)F為已知前提的公式集，Q為目標(biāo)公式(結(jié)論)，用歸結(jié)反演證明Q為真的步驟是：a) 否定Q，得到172。Q；b) 把172。Q并入到公式集F中，得到{F, 172。Q}。c) 把公式集{F, 172。Q}化為子句集S。d) 應(yīng)用歸結(jié)原理對(duì)子句集S中的子句進(jìn)行歸結(jié)，并把每次歸結(jié)得到的歸結(jié)式都并入S中。如此反復(fù)進(jìn)行，若出現(xiàn)了空子句，則停止歸結(jié)，此時(shí)就證明了Q為真。 已知求證：G是F的邏輯結(jié)論。證明：首先把F和172。G化為子句集：然后進(jìn)行歸結(jié)：(6)172。A(x,y)∨172。B(y) 由(1)與(3)歸結(jié)，{f(x)/z}(7)172。B(b) 由(4)與(6)歸結(jié)，{a/x,b/y}(8)NIL 由(5)與(7)歸結(jié)所以G是F的邏輯結(jié)論。上述歸結(jié)過(guò)程如下圖歸結(jié)樹(shù)所示。u 應(yīng)用歸結(jié)原理求取問(wèn)題的答案及其示例216。 歸結(jié)時(shí)，并不要求把子句集中所有的子句都用到。216。 在歸結(jié)過(guò)程中，一個(gè)子句可以多次被用來(lái)進(jìn)行歸結(jié)。求解的步驟：1. 把已知前提用謂詞公式表示出來(lái)，并且化為相應(yīng)的子句集。設(shè)該子句集的名字為S。2. 把待求解的問(wèn)題也用謂詞公式表示出來(lái)，然后把它否定并與謂詞Answer構(gòu)成析取式。Answer是一個(gè)為了求解問(wèn)題而專設(shè)的謂詞。3. 把此析取式化為子句集，并且把該子句集并入到子句集S中，得到子句集S`。4. 對(duì)S`應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)。5. 若得到歸結(jié)式Answer，則答案就在Answer中。 設(shè)A,B,C三人中有人從不說(shuō)真話，也有人從不說(shuō)假話。某人向這三人分別提出同一個(gè)問(wèn)題：誰(shuí)是說(shuō)謊者？A答：“B和C都是說(shuō)謊者”；B答：“A和C都是說(shuō)謊者”；C答：“A和B中至少有一個(gè)是說(shuō)謊者”。求誰(shuí)是老實(shí)人，誰(shuí)是說(shuō)謊者？解：設(shè)用T(x)表示x說(shuō)真話。T(C)∨T(A)∨T(B)172。T(C)∨172。T(A)∨172。T(B)T(A)→172。T(B)∧172。T(C)172。T(A)→T(B)∨T(C)T(B)→172。T(A)∧172。T(C)172。T(B)→T(A)∨T(C)T(C)→172。T(A)∨172。T(B)172。T(C)→T(A)∧T(B)把上述公式化成子句集，得到S：(1)172。T(A)∨172。T(B)(2)172。T(A)∨172。T(C)(3)T(C)∨T(A)∨T(B)(4)172。T(B)∨172。T(C)(5)172。T(C)∨172。T(A)∨172。T(B)(6) T(A)∨T(C)(7)T(B)∨T(C)下面先求誰(shuí)是老實(shí)人。把172。T(x)∨Ansewer(x)并入S得到S1。即多一個(gè)子句：(8)172。T(x)∨Ansewer(x)應(yīng)用歸結(jié)原理對(duì)S1進(jìn)行歸結(jié)：(9)172。T(A)∨T(C) (1)和(7)歸結(jié)(10)T(C) (6)和(9)歸結(jié)(11)Ansewer(C) (8)和(10)歸結(jié)所以C是老實(shí)人，即C從不說(shuō)假話。下面證明A不是老實(shí)人，即證明172。T(A)。對(duì)172。T(A)進(jìn)行否定，并入S中，得到子句集S2，即S2比S多如下子句：(8)172。(172。T(A)), 即T(A)應(yīng)用歸結(jié)原理對(duì)S2進(jìn)行歸結(jié)：(9)172。T(A)∨T(C) (1)和(7)歸結(jié)(10)172。T(A) (2)和(9)歸結(jié)(11)NIL (8)和(10)歸結(jié)所以A不是老實(shí)人。同樣可以證明B也不是老實(shí)人。u 應(yīng)用歸結(jié)原理的練習(xí)1. 設(shè)已知： （1）如果x是y的父親，y是z的父親，則x是z的祖父； （2）每個(gè)人都有一個(gè)父親。 試用歸結(jié)演繹推理證明：對(duì)于某人u，一定存在一個(gè)人v，v是u的祖父。 2. 張某被盜，公安局派出五個(gè)偵察員去調(diào)查。研究案情時(shí)，偵察員 A 說(shuō)“趙與錢(qián)中至少有一人作案”；偵察員 B 說(shuō)“錢(qián)與孫中至少有一人作案”；偵察員 C 說(shuō)“孫與李中至少有一人作案”；偵察員 D 說(shuō)“趙與孫中至少有一人與此案無(wú)關(guān)”；偵察員 E 說(shuō)“錢(qián)與李中至少有一人與此案無(wú)關(guān)”。如果這五個(gè)偵察員的話都是可信的，試用歸結(jié)演繹推理求出誰(shuí)是盜竊犯。u 簡(jiǎn)單模糊推理知識(shí)中只含有簡(jiǎn)單條件，且不帶可信度因子的模糊推理稱為簡(jiǎn)單模糊推理。合成推理規(guī)則：對(duì)于知識(shí)IF x is
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1