ペアノ算術とProlog

ペアノ算術をPrologで表現してみる。

元ネタ
第3巻『数学ガール／ゲーデルの不完全性定理』
Prolog by Example: Peano Arithmetics

Swi-Prologを使います。

と…その前にペアノの公理で自然数を定義しよう。

---

ペアノの公理１
0は自然数である



Prologコード
natural_n(0).

---

ペアノの公理2
どんな自然数nに対しても後続数s(n)は自然数である



Prologコード
natural_n(s(N)) :- natural_n(N).

---

ペアノの公理3
どんな自然数nに対してもs(n)は0ではない



Prologコードは無し

---

ペアノの公理4
どんな自然数m,nに対しても、s(m)=s(n)ならばm=nである



Prologコードは無し

---

ペアノの公理5

自然数nに対する述語P(n)で、次の2つが成り立つとする。
・P(0)である。
・どんな自然数kに対しても、P(k)ならばP(s(k))である。
このときどんな自然数nに対してもP(n)が成り立つ。

Prologコードは無し

---

ここまでのPrologコードまとめ

natural_n(0).
natural_n(s(N)) :- natural_n(N).

---

実行してみる。

?- natural_n(X).
X = 0 ;
X = s(0) ;
X = s(s(0)) ;
X = s(s(s(0))) ;
X = s(s(s(s(0)))) ;
X = s(s(s(s(s(0))))) .

自然数が出来た!
「これが自然数？」と言いたい人もいるでしょうが、これで良いんです!!
s(0)を1
s(s(0))を2
s(s(s(0)))を3
というふうに読み替えて下さい。

---

さて、ここからがペアノ算術

足し算の公理1
どんな自然数nに対しても、n + 0 = nが成り立つ


Prologコード
sum(N,0,N).

---

余談ですが自然数に０を含める考え方(0,1,2 ...)と含めない考え方(1,2,3 ...)があり、上の足し算の公理は前者です。
後者の場合の公理はこうなります。

足し算の公理１(０は自然数に含めない)
どんな自然数nに対しても、n + 1 = s(n)が成り立つ

"0"という自然数は存在しないので、こうするしかないのでしょう。
この場合は、
s(1)を2
s(s(1))を3
s(s(s(1)))を4
というふうに読み替えて下さい。

Prologコード
sum(N,1,s(N)).

---

足し算の公理2



Prologコード
sum(N,s(M),s(K)) :- sum(N,M,K).

---

Prologコードまとめ

sum(N,0,N).     %In case of natural numbers contain 0.
sum(N,1,s(N)).  %In case of natural numbers contain NO 0.
sum(N,s(M),s(K)) :- sum(N,M,K).  %K=N+M

X=3+2を実行してみます。

?- sum(s(s(s(0))),s(s(0)),X).
X = s(s(s(s(s(0))))) ;
false.

X=5になりました。
おっと、ここで作った自然数は"5"とは言わないんでしたね。
s(s(s(s(s(0)))))ですね、でも長ったらしいので５と言う事にします。

因みに、０は自然数に含めない場合で
X=4+3を実行してみます。

?- sum(s(s(s(1))),s(s(1)),X).
X = s(s(s(s(s(s(1)))))) ;
false.

X=7になりました。

０を自然数に含める場合は、例えば２をs(s(0))と表現すると
sum(N,s(M),s(K)) :- sum(N,M,K).
を再帰的に評価し、最終的に
sum(N,0,N).
にマッチして、再帰の階段を戻って結果が出る訳です。

０を自然数に含めない場合は、例えば２をs(1)と表現して、最終的に
sum(N,1,s(N)).
の方にマッチするのです。

---

ではここからは掛け算です。
掛け算の公理1
０を自然数に含める場合

Prologコード
prod(M,0,0).

０を自然数に含めない場合

Prologコード
prod(M,1,M).

---

掛け算の公理2

Prologコード
prod(M,s(N),P) :-
     prod(M,N,K),
     sum(K,M,P).   % K=M+N

---

Prologコードまとめ

prod(M,0,0).    %In case of natural numbers contain 0.
prod(M,1,M).    %In case of natural numbers contain NO 0.
prod(M,s(N),P) :-
    prod(M,N,K),
    sum(K,M,P).   % K=M+N

実行

０を自然数に含める場合、X=2*3

?- prod(s(s(0)),s(s(s(0))),X).
X = s(s(s(s(s(s(0)))))) ;
false.

X=6となりました。


０を自然数に含めない場合、X=2*4

?- prod(s(1),s(s(s(1))),X).
X = s(s(s(s(s(s(s(1))))))) ;
false.

X=8となりました。