人工智能lesson3-(編輯修改稿)
2024-08-20 21:56 本頁面
【文章內(nèi)容簡介】 (11) ) 定理 5（歸結(jié)原理的完備性）、如果子句集 S是不可滿足的，則必存在一個(gè)由 S推出空子句的歸結(jié)序列。 其它例見教材 p78,例 15， 16。 課堂練習(xí)： p94，題 6。 歸結(jié)演繹樹： ?N(y)?I(y) N( c) ?I(z)?E(z) ? O(z) ?O(c) I( c) ?I(c) ? E( c) E(c ) ?E(u)?I(h(u)) I(h (c )) ?I(h( c)) 應(yīng)用歸結(jié)原理求取問題答案 應(yīng)用歸結(jié)原理求取問題答案的步驟： （ 1）、把已知前提用謂詞公式表示出來，并化為子句集 S。 （ 2）、把待求解問題也用謂詞公式表示出來，然后把它的否定與謂詞 ANS構(gòu)成析取式。 ANS的變元應(yīng)與問題的變元完全一致。 （ 3）、把此析取式化為子句集，并把該子句集并入 S中得到子句集 S39。 （ 4）、對 S39。應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)。 （ 5）、若得到歸結(jié)式 ANS，則答案就在 ANS中。 例、設(shè) A、 B、 C三人中有人從不說真話，也有人從不說假話，某人向這三人分別提出同一個(gè)問題：誰是說謊者？ A答：“ B和 C都是說謊者”；B答：“ A和 C都是說謊者”； C答：“ A和 B中至少有一個(gè)是說謊者”。求誰是老實(shí)人，誰是說謊者？ 解、設(shè) T(x)表示 x說真話。如果 A說的是真話，則有： T(A) ? ? T(B) ? ?T(C ) 如果 A說的是假話，則有： ?T(A) ?T(B)? T(C )。 同理，對 B和 C有： T(B) ? ? T(A) ??T(C ) ?T(B) ?T(A)? T(C ) T(C) ? ? T(A)? ? T(B ) ? T(C) ? T(A) ?T(B ) 化為子句集 S： （ 1）、 ? T(A)? ? T(B ) （ 2）、 ? T(A)? ? T(C ) （ 3）、 T(A)?T(B)?T(C ) （４）、 ? T(B)? ? T(C ) （５）、 ? T(A)? ? T(B ) ? ? T(C ) （６）、 T(C)?T(A) （７）、 T(C)?T(B) 先求誰是老實(shí)人， 把 ?T(x)? ANS(x)并入 S （８）、 ?T(x)? ANS(x) （９）、 T(A)? ANS( C) ( (8), (6), C/x ) （１０）、 T(B)? ANS(C) ( (7), (8), C/x ) （１１）、 ?T(B)? ANS(C) ( (9), (1) ) （１２）、 ANS(C ) ( (10), (11) ) 因此 C是老實(shí)人。無論如何歸結(jié)，推不出 ANS(A), ANS(B)。下證 A是說謊者，即 ?T(A)，其否定為 （８）’ ? ? T(A)即 T(A) （９）’ ?T(B) ( (8)’, (1) ) （１０）’ T(C ) （（９）’，（７） ） （１１）’ ?T(C ) （ （８）’， （２） ） （１２）’ NIL （ （１０）’， （１１）’ ） 歸結(jié)策略 問題的提出 歸結(jié)反演的一般過程。 步１ 將子句集 S置入 CLAUSES表； 步２ 若空子句 NIL在 CLAUSES中，則歸結(jié)成功，結(jié)束。 步３ 若 CLAUSES表中存在可歸結(jié)的子句對，則歸結(jié)之，并將歸結(jié)式并入 CLAUSES表，轉(zhuǎn)步２； 步３ 歸結(jié)失敗，退出。 窮舉算法（廣度優(yōu)先策略） 第一輪：將原子句集 S中的子句兩兩歸結(jié)，產(chǎn)生的歸結(jié)式集合記為 S1，再將 S1并入 CLAUSES表； 第二輪：將新的 CLAUSES表即 S?S1中的子句與 S1中的子句兩兩歸結(jié)，產(chǎn)生的歸結(jié)式集合記為 S2，再將S2并入 CLAUSES； 第三輪：將新的 CLAUSES表即 S?S1 ?S2中的子句與 S2中的子句兩兩歸結(jié)， … 。 如此下去，直到出現(xiàn)空子句。 例 1 設(shè)有如下的子句集，用窮舉算法歸結(jié)如下： S： （ 1） P?Q
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1