6

（中間質問の波の中に忍び込ませてください。）

2 つの自然数の和の一般的な定義は次のnat_nat_sum/3とおりです。

nat_nat_sum(0, N, N).
nat_nat_sum(s(M), N, s(O)) :-
   nat_nat_sum(M, N, O).

厳密に言えば、この定義は一般的すぎます。

?- nat_nat_sum(A, B, unnatural_number).

同様に、次の回答置換が得られます。

?- nat_nat_sum(0, A, B).
   A = B.

この答えの置換はすべての自然数を含むと解釈し、他の項は気にしません。

それを踏まえて、その終了特性を考えてみましょう。実際、次の障害スライスを考慮するだけで十分です。つまり、nat_nat_sum/3このスライスが終了しないと、終了しないだけではありません。今回も全く同じ！したがって、私たちは iff と言うことができます。

nat_nat_sum(0, N, N) :- false .
nat_nat_sum(s(M)、N、s(O)):-
   nat_nat_sum(M, N, O), false .

この失敗スライスは、1 番目と 3 番目の引数の間の対称性を明らかにします。どちらもまったく同じ方法で非終了に影響を与えます! したがって、それらはまったく異なるものを記述していますが (一方は被加数、もう一方は和)、それらは終了に対してまったく同じ影響を与えます。そして、貧弱な 2 番目の引数はまったく影響を与えません。

念のため言っておくと、障害スライスは共通の終了条件 ( cTI を使用) で同一であるだけでなく、

nat_nat_sum(A,B,C)terminates_if b(A);b(C).

また、この条件でカバーされていない場合でも、まったく同じように終了します。

?- nat_nat_sum(f(X),Y,Z).

今私の質問：

nat_nat_sum/3終了条件を持つ別の定義はありますか?

nat_nat_sum2(A,B,C) terminates_if b(A);b(B);b(C).

（はいの場合はそれを示してください。いいえの場合はその理由を説明してください）

言い換えれば、新しい定義は、その引数の1 つnat_nat_sum2/3がすでに有限で根拠がある場合に終了する必要があります。

細字。純粋で単調な Prolog プログラムのみを考慮してください。(=)/2つまり、および以外に組み込みはありません。dif/2

(これには 200 の報奨金を与えます)

4

4 に答える 4

3

わかりました、終わったようです。私が考えていた解決策は次のとおりです。

nat_nat_sum2(0, N,N).
nat_nat_sum2(s(N), 0, s(N)).
nat_nat_sum2(s(N), s(M), s(s(O))) :-
   nat_nat_sum2(N, M, O).

しかし、私が気づいたように、それは @WillNess とほぼ同じ @mat のものとまったく同じです。

これは本当に良いnat_nat_sum/3ですか？オリジナルのランタイムは独立していますB(1 つを無視する場合は、しばらくチェックしてください)。

自然に拡張される@matのソリューションと比較して、私のソリューションには別の欠点がありますnat_nat_nat_sum/3

nat_nat_nat_sum(0, B, C, D) :-
   nat_nat_sum(B, C, D).
nat_nat_nat_sum(s(A), B, C, s(D)) :-
   nat_nat_nat_sum2(B, C, A, D).

どちらが与える

nat_nat_nat_sum(A,B,C,D)terminates_if b(A),b(B);b(A),b(C);b(B),b(C);b(D).

(展開版 で cTIで証明可能)

于 2014-11-29T22:57:04.073 に答える
3 
nat_nat_sum(0, B, B).
nat_nat_sum(s(A), B, s(C)) :-
        nat_nat_sum(B, A, C).

?

于 2014-11-29T22:30:49.997 に答える
1

次の 2 つの定義を使用します。

定義 1:

add(n,X,X).
add(s(X),Y,s(Z)) :- add(X,Y,Z).

定義 2:

add(n,X,X).
add(s(X),Y,Z) :- add(X,s(Y),Z).

定義 1 はパターン add(-,-,+) で終了しますが、定義 2 はパターン add(-,-,+) で終了しません。見てください：

定義 1:

?- add(X,Y,s(s(s(n)))).
X = n,
Y = s(s(s(n))) ;
X = s(n),
Y = s(s(n)) ;
X = s(s(n)),
Y = s(n) ;
X = s(s(s(n))),
Y = n
?-

定義 2:

?- add(X,Y,s(s(s(n)))).
X = n,
Y = s(s(s(n))) ;
X = s(n),
Y = s(s(n)) ;
X = s(s(n)),
Y = s(n) ;
X = s(s(s(n))),
Y = n ;
Error: Execution aborted since memory threshold exceeded.
    add/3
    add/3
?-

したがって、定義 1 は定義 2 よりも優れていると思います。

さよなら

于 2014-12-05T23:17:15.130 に答える
1

明らかなトリックは、引数を反転することです。

sum(0,N,N).
sum(N,0,N).
sum(s(A),B,s(C)):- sum(B,A,C) ; sum(A,B,C).
于 2014-11-29T18:58:55.747 に答える