人工智能lesson3--文庫吧
2025-07-09 21:56 本頁面
【正文】 / xn }， ?＝{u1 / y1, u2 / y2 ,…,um / ym }是兩個替換，則將集合{t1 ? / x1, t2 ? / x2 ,…,tn ? / xn， u1 / y1, u2 / y2 ,…,um / ym }中符合下列條件的兩種情形刪除： １）、 ti ? / xi ，當(dāng) ti ? ＝ xi 。 ２）、 ui / yi ，當(dāng) yi ? { x1, x2 ,…, xn } 。 得到的集合仍是一個替換，稱為 ?與 ?的復(fù)合，記為?186。?。 例、見教材 p67例 。 定義９、設(shè) S= { F1, F2 ,…, Fn }是一個原子謂詞公式集，若存在一個替換 ?，使得 F1 ?＝ F2 ?＝ … ＝ Fn ?，則稱 ?為 S的一個合一（ Unifier），并稱 S為可合一的。 一個公式集的合一一般不唯一。 定義１０、設(shè) ?是公式集 S的一個合一，如果對 S的任何一個合一 ?，都存在一個替換 ?，使得 ?＝ ? 186。?，則稱 ?為 S的一個最一般合一（ Most General Unifier），簡稱 MGU。 定義１１、設(shè) S是一個非空的具有相同謂詞名的原子公式集，從 S中各公式的左邊第一個項開始，同時向右比較，每一組不都相同的項的差異部分組成的集合稱為 S的差異集。 例、公式集 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= ?（ ? 表示空替換）。 （ 2）、若 Sk只含有一個謂詞公式，則算法停止， ?k就是要求的最一般合一。 （ 3）、求 Sk的差異集 Dk 。 （ 4）、若 Dk中存在元素 xk 和 tk ，其中 xk是變元， tk是項且 xk不在 tk中出現(xiàn)，則置 Sk+1 = Sk{tk /xk} ， ?k+1 = ?k186。 {tk /xk} ， k=k+1，然后轉(zhuǎn)步（ 2）。 （ 5）、算法停止， S的最一般合一不存在。 定理 3（合一定理）、如果 S是一個非空有限可合一的公式集，則合一算法總是在步（ 2）停止，且最后的 ?k即是 S的最一般合一。 謂詞邏輯中的歸結(jié)原理 定義 1 設(shè) C1， C2是兩個沒有相同變元的子句， L1，L2分別是 C1， C2中的兩個文字，如果 L1與 ?L2有最一般合一 ? ，則子句 C12=(C1?{L1?})? (C2?{L2?})，稱作C1和 C2的二元歸結(jié)式（二元消解式）。 C1和 C2稱為 C12的親本子句， L1， L2稱為消解文字。 若在參加歸結(jié)的子句內(nèi)部含有可合一文字，則在進(jìn)行歸結(jié)之前，應(yīng)對這些文字進(jìn)行合一。 定義 1如果子句 C中，兩個或兩個以上的文字有一個最一般合一 ? ，則稱 C?為 C的因子。 定義 1子句 C1， C2的歸結(jié)式，是下列二元歸結(jié)式之一： 1）、 C1和 C2的二元歸結(jié)式； 2）、 C1和 C2的因子的二元歸結(jié)式； 3）、 C1的因子和 C2的二元歸結(jié)式； 4）、 C1的因子和 C2的因子的二元歸結(jié)式。 定理 謂詞邏輯中的歸結(jié)式是它的親本子句的邏輯結(jié)果。 類似于命題邏輯中的兩個推論仍成立。 歸結(jié)反演：應(yīng)用歸結(jié)原理證明定理的過程稱為歸結(jié)反演。 若 F為已知前提的公式集， Q為結(jié)論，用歸結(jié)反演證明Q為真的步驟是： （ 1）、否定 Q，得到 ?Q； （ 2）、把 ?Q并入到公式集 F中，得到 {F, ?Q}； （ 3）、把公式集 {F, ?Q}化為子句集 S； （ 4）、應(yīng)用歸結(jié)原理對子句集 S中的子句進(jìn)行歸結(jié)，并把每次歸結(jié)得到的歸結(jié)式都并入 S中。如此反復(fù)進(jìn)行，直到出現(xiàn)空子句，就證明了 Q為真。 例、自然數(shù)都是大于零的數(shù)；所有整數(shù)不是偶數(shù)就是奇數(shù)；偶數(shù)除以 2是整數(shù)。求證：所有自然數(shù)不是奇數(shù)就是其一半為整數(shù)的數(shù)。 證明：前提： F1 ： ?x(N(x) ?GZ(x) ?I(x)) F2 ： ?x(I(x) ?E(x) ? O(x)) F3 ： ?x(E(x) ?I(h(x))) 結(jié)論： G： ?x(N(x) ?O(x) ? I(h(x))) F F F3 及 ?G 化為子句集： （ 1） ?N(x)?GZ(x) （ 2） ?N(y)?I(y) （ 3） ?I(z)?E(z) ? O(z) （ 4） ?E(u)?I(h(u)) （ 5） N( c) （ 6） ?O(c) （ 7） ?I(h( c)) 歸結(jié)： （ 8） I( c) ( (2), (5), c/y ) （ 9） ?I(c) ? E( c) ( (3), (6), c/z ) （ 10） E( c) ( (8), (9) ) （ 11） I(h( c)) ( (4), (10), c/u ) （ 12） ? ( (7),
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1