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