Algorithmic theory of natural numbers: Różnice pomiędzy wersjami
(Utworzono nową stronę "The theory of one constant 0, one one-argument functor <math>s</math> and predicate of equality =.<br /> Axioms <br /> <math>\begin{align*} &\tag{I} \forall_n s(n) \neq...") |
|||
| Linia 1: | Linia 1: | ||
The theory of one constant 0, one one-argument functor <math>s</math> and predicate of equality =.<br /> | The theory of one constant 0, one one-argument functor <math>s</math> and predicate of equality =.<br /> | ||
| − | Axioms <br /> | + | '''Axioms''' <br /> |
<math>\begin{align*} | <math>\begin{align*} | ||
&\tag{I} \forall_n s(n) \neq 0 \\ | &\tag{I} \forall_n s(n) \neq 0 \\ | ||
Wersja z 17:21, 8 sie 2017
The theory of one constant 0, one one-argument functor [math]s[/math] and predicate of equality =.
Axioms
[math]\begin{align*}
&\tag{I} \forall_n s(n) \neq 0 \\
&\tag{M} \forall_n \forall_m s(n)=s(m) \implies n=m \\
&\tag{S} \forall_n \{m:=0; \mathbf{while}\ n\neq m\ \mathbf{do}\ m:=s(m)\ \mathbf{od} \}(n=m)
\end{align*} [/math]
This set of formulas gives a complete specification of the set of natural numbers with the successor operation. It means that any implementation whether hardware or software (e.g. by means of a class) that satisfies three axioms listed above is correct.
It means also that if an algorithmic formula is valid in the standard model of these axioms then it has a proof with the use of program calculus.
One may extend this set adding four axioms that define operation of addition, subtraction predecessor and predicate <.
[math]\begin{align*}
\tag{A}\label{add} & x+y \stackrel{df}{=} \{t:=0; w:=x; \textbf{while }t\neq y\textbf{ do }t:=s(t); w:=s(w) \textbf{ od}\}w & \\
\tag{L}\label{less} & x \lt y \stackrel{df}{\equiv} \{ w:=0; \textbf{while }w\neq y\land w\neq x \textbf{ do } w:=s(w) \textbf{ od}\}(w=x \land w\neq y) & \\
\tag{P}\label{predec} & P(x)\stackrel{df}{=} \{\begin{array}{l}w:=0;\
\textbf{if }x \neq 0 \textbf{ then }
\ \textbf{while } s(w)\neq x\textbf{ do } w:=s(w) \textbf{ od} \
\textbf{fi}\end{array} \}w & \\
\tag{O}\label{odejm} & x\stackrel{.}{\_\_}y \stackrel{df}{=} \{w:=x; t:=0; \mathbf{while }\ t\neq y\ \mathbf{ do }\ t:=s(t); w:=P(w)\ \mathbf{ od} \}w &
\end{align*} [/math]
