Courses/CS 332L/Peano arithmetic
From CSWiki
From Wikipedia.Giuseppe Peano (August 27, 1858 – April 20, 1932) was an Italian mathematician, whose work was of exceptional philosophical value. The author of over 200 books and papers, he was a founder of mathematical logic and set theory, to which he contributed much notation. The standard axiomatization of the natural numbers is named in his honor. He spent most of his career teaching mathematics at the University of Turin.
Contents |
[edit] Peano's Axioms
Peano's axiomatization of the non-negative numbers can be represented as follows.
- Zero is a number.
- If X is a number, the successor of X is a number.
- Zero is not the successor of a number.
- Two numbers of which the successors are equal are themselves equal.
- (Induction axiom.) If a set S of numbers contains zero and also the successor of every number in S, then every number is in S.
[edit] Representing Peano numbers as data structures
We can represent the Peano numbers as follows.
- Zero is
0. - The successor of X is
s(X). That is s(0) is
s
|
0
Example:
2 is s(s(0)) 3 is s(s(s(0))
In general, to find the numeric representation of a Peano number count the number of s symbols. Here's a prolog program to do that.
peano_to_number(0, 0) :- !. peano_to_number(s(X), Y) :- !, peano_to_number(X, Z), Y is Z+1.
?- peano_to_number(s(s(s(0))), X). X = 3
Note the use of the cut (!). Always put a cut in a clause as soon as you know that the clause applies.
- The first clause applies if both arguments are 0. So the body is nothing but the cut. (Note that you still need a period (.) after the cut symbol.
- The second clause applies as soon as we see that the first argument is of the form s(X). (Those are the only two possibilities for the first argument.) So the first thing in the body is a cut.
Homework. Write a prolog program to translate from numbers to Peano numbers. Again, there are only two possibilities for the first argument. It can be either 0 or a positive number. So the two clauses will look something like this.
number_to_peano(0, 0) :- !. number_to_peano(X, s(Y)) :- number(X), X > 0, !, …
I've given you a hint. If X is > 0 then the Peano representation of it is s(Y), where Y is the Peano number for X-1.
?- number_to_peano(3, X). X = s(s(s(0)))
What happens if the first argument is a negative number? Since there are no negative Peano numbers, it should fail.
?- number_to_peano(-3, X). No
[edit] Arithmetic
[edit] Addition
We can define addition as follows.
X + 0 = X X + s(Y) = s(X + Y)
In general, each step moves an s( … ) from the second argument to the outside.
So 3 + 2 is
s(s(s(0))) + s(s(0)) = s( s(s(s(0))) + s(0) ) = s(s( s(s(s(0))) + 0 )) = s(s( s(s(s(0))) ))
which is 5.
Homework. Define a prolog predicate sum/3 that adds two Peano numbers.
?- number_to_peano(3, Three), number_to_peano(2, Two), sum(Three, Two, Sum), peano_to_number(Sum, Value). Three = s(s(s(0))), Two = s(s(0)), Sum = s(s(s(s(s(0))))), Value = 5
Don't define sum/3 by having it convert Peano numbers to regular numbers, do the arithmetic there and convert back. That is, the following will work, but it is not acceptable.
lazy_sum(X, Y, Z) :- peano_to_number(X, X0), peano_to_number(Y, Y0), Z0 is X0 + Y0, number_to_peano(Z0, Z).
?- number_to_peano(3, Three), number_to_peano(2, Two), lazy_sum(Three, Two, Sum ), peano_to_number(Sum , Value). Three = s(s(s(0))), Two = s(s(0)), Sum = s(s(s(s(s(0))))), Value = 5
[edit] Subtraction
What happens if you use sum/3 with one of the first two arguments uninstantiated but the third argument instantiated?
?- sum(A, s(s(0)), s(s(s(s(s(0)))))). A = s(s(s(0))) ?- sum(s(s(s(0))), B, s(s(s(s(s(0)))))). B = s(s(0))
Homework. Define difference/3. Explain how it works.
?- difference(s(s(s(s(s(0))))), s(s(s(0))), Z). Z = s(s(0))
What happens if the result would be a negative number?
?- difference(s(s(s(0))), s(s(s(s(s(0))))), Z). No
What happens if the first two arguments to sum/3 are uninstantiated and the third argument is instantiated?
?- sum(A, B, s(s(s(s(s(0)))))). A = s(s(s(s(s(0))))) B = 0
The first rule for sum/3 (X + 0 = X) matches, so that's the answer that's returned. If we took out the cuts, we would get all possible combinations of answers. But that involves backtracking, which we are minimizing. You may want to try it for your own information, though.
[edit] Relations
- X is equal to Y if X and Y unify, i.e., if
?- X = Y. Yes.
- X and Y unify if and only if they have the same data structures and their leaf elements are the same.
- X is less than Y if X + Z = Y for some Z ≠ 0. That is, if there is a Z such that X + Z = Y, then Z must be of the form s(_).
- X is greater than Y if Y + Z = X for some Z ≠ 0. That is, if there is a Z such that Y + Z = X, then Z must be of the form s(_).
Homework. Write predicates for eq/2, lt/2, gt/2.
[edit] Multiplication
Multiplication can be defined as repeated addition.
X * 0 = 0 X * s(Y) = X + (X * Y)
Homework. Define a prolog predicate product/3.
?- product(s(s(0)), s(s(s(0))), Z). Z = s(s(s(s(s(s(0))))))
[edit] Division
Division can be defined as repeated subtraction. If the result is not integral, division fails.
0 / s(Y) = 0 s(X) / s(Y) = 1 + (s(X) - s(Y))/s(Y).
Note that division by 0 is undefined.
?- divides(s(s(s(s(0)))), s(s(0)), Z). Z = s(s(0)) ?- divides(s(s(s(s(s(0))))), s(s(0)), Z). No ?- divides(s(s(s(s(s(s(0)))))), s(s(0)), Z). Z = s(s(s(0)))
Homework. Define divides/3.
