人工智能lesson3-(文件)
【正文】 ? Pm 。 有序性策略。 祖先過濾形策略 參加歸結(jié)的兩個子句，要么至少有一個是初始子句集中的子句，要么一個是另一個的祖先。例如 S={ P?Q ,? P?Q, P? ? Q, ? P?? Q}不可滿足，但用輸入歸結(jié)策略導不出空子句。 例、 P85例 5 線性歸結(jié)策略的特點：完備、高效、與別的策略兼容。支持集策略指每次歸結(jié)時，兩個親本子句中至少要有一個是目標公式否定的子句或其后裔。 使用刪除策略，例 1可簡化為： （ 1） P?Q （ 7） ? P [ (2), (4) ] （ 2） ? P?Q （ 8） Q [ (3), (4) ] （ 3） P? ? Q （ 9） [(5), (8)] （ 4） ? P? ? Q （ 5） Q [(1), (2)] （ 6） P [(1), (3)] 刪除策略的特點： 刪除策略的思想是及早刪除無用字句，以避免無效歸結(jié)，縮小搜索空間。 例、 P(x)類含 P(a) ? Q(y)； P(x)類含 P(a)。 步３ 若 CLAUSES表中存在可歸結(jié)的子句對，則歸結(jié)之，并將歸結(jié)式并入 CLAUSES表，轉(zhuǎn)步２； 步３ 歸結(jié)失敗，退出。 同理，對 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是老實人。 （ 5）、若得到歸結(jié)式 ANS，則答案就在 ANS中。 ANS的變元應(yīng)與問題的變元完全一致。 其它例見教材 p78,例 15， 16。如此反復進行，直到出現(xiàn)空子句，就證明了 Q為真。 定理 謂詞邏輯中的歸結(jié)式是它的親本子句的邏輯結(jié)果。 C1和 C2稱為 C12的親本子句， L1， L2稱為消解文字。 {tk /xk} ， k=k+1，然后轉(zhuǎn)步（ 2）。 例、公式集 S={P(a,x,f(g(y))),P(z,h(z,u),f(u))}的差異集為 {a,z}, {x,h(z,u)}, {g(y),u} 替換與合一 設(shè) S為一非空有限具有相同謂詞名的原子謂詞公式集，求 S的 MGU的算法： （ 1）、令 k=0, Sk=S, ?k= ?（ ? 表示空替換）。 一個公式集的合一一般不唯一。 得到的集合仍是一個替換，稱為 ?與 ?的復合，記為?186。 定義７、設(shè) ?＝ {t1 / x1, t2 / x2 ,…,t n / xn }是一個替換， E是一個表達式（項、原子公式、文字、子句），把 E中出現(xiàn)的所有個體變元 xi都用 ti 替換，得到的結(jié)果記為 E? ，稱為 E在 ?下的替換實例。 替換與合一 定義６、一個替換 (Substitution)是形如 {t1 / x1, t2 / x2 ,…,t n / xn }的有限集合，其中 t1 , t2 ,…,t n 是項， x1, x2 ,…,x n是互不相同的個體變元。 定理２、歸結(jié)式 C1２ 是其親本子句 C1與 C2的邏輯結(jié)論。一旦歸結(jié)出空子句，則證明結(jié)束。根據(jù)定理 1，只須證明 P ? ?Q的子句集不可滿足。 例、把謂詞公式 ?x{?yP(x,y) ? ??y[Q(x,y)?R(x,y)]}化為子句集。 Skolem標準形的一般形式為 ?x1 ?x2 ? ? ???xnM，其中M是子句的合取式。這樣的函數(shù)稱為 Skolem函數(shù)?？衫孟铝械葍r式： ? ? A ?A； ?(A?B) ? ? A ? ? B； ?(A ? B) ? ?A ??B； ??xA(x) ? ?x? A(x)； ??xA(x) ? ? x? A(x) （ 3）、重新命名變元名，使不同量詞約束的變元有不同的名字。不
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1