Αριστoτέλειο Πανεπιστήμιο Θεσσαλονίκης
Τμήμα Πληροφορικής
Εργαστήριο Γλωσσών Προγραμματισμού και Τεχνολογίας Λογισμικού

Φυσικοί Αριθμοί

Οι φυσικοί αριθμοί μπορούν να προκύψουν χρησιμοποιώντας το σύμβολο 0 και μια συνάρτηση με ένα όρισμα s(X) (successor του Χ) οποία δίνει το επομένο ενός φυσικού αριθμού. Με τον συμβολισμό αυτό το 1 αναπαριστάται σαν s(0)
το 2 σαν s(s(0)) κοκ.

Χρησιμοποιώντας αυτή την αναπαράσταση, μπορούν να ορισθούν και οι βασικές πράξεις της πρόσθεσης και του πολλαπλασιασμού καθώς και άλλες συναρτήσεις.

Η παραπάνω συμβολική αναπαράσταση των φυσικών αριθμών υλοποιείται εύκολα στην Prolog, όπως θα δούμε στα επόμενα παραδείγματα. Οι αριθμοί αναπαριστώνται με ένα σύνθετο όρο με ένα όρισμα. Έτσι ακολουθούμε με ακρίβεια τον παραπάνω ορισμό.

Το πρώτο κατηγόρημα το οποίο μπορούμε να ορίσουμε, ελέγχει αν ένας αριθμός είναι φυσικός. Η υλοποίηση βασίζεται στον αναδρομικό μαθηματικό ορισμό, ο οποίος λέει ότι:

ένας αριθμός είναι φυσικός εάν είναι το μηδέν (τερματική συνθήκη) ή είναι ο επόμενος ενός φυσικού αριθμού

Το παραπάνω γράφεται πολύ απλά σε Prolog:

%%% natural_num/0
%%% natural_num(Number)
natural_num(0).
natural_num(s(X)):-
natural_num(X).

Το σημείο το οποίο απαιτεί λίγο παραπάνω προσοχή είναι το πώς πέρνουμε τον "προηγούμενο" του αριθμού για να ελένξουμε αν και αυτός είναι φυσικός. Αυτό γίνεται μεσω της διαδικασίας ενοποίησης, στο όρισμα του κανόνα του κατηγορήματος. Ετσι αν κάνουμε την ερώτηση:

?- natural_num(s(s(0))).

η ενοποίηση στον πρώτο κανόνα θα ταυτοποιήσει το Χ με s(0),δηλαδή τον προηγούμενο του αρχικού φυσικού αριθμού.

Σύγκριση Αριθμών
Η σύγκριση δύο φυσικών αριθμών (σχέση μεγαλύτερο ή ίσο) γίνεται βάση της απλής αναδρομικής σχέσης:

ένας οποιοσδήποτε αριθμός είναι μεγαλύτερος ή ίσος με το μηδέν ένας αριθμός Χ είναι μεγαλύτερος από ένα άλλό Υ, αν είναι επόμενος ενος αριθμού Χ1 ( Χ=s(Χ1) ) ο οποιος είναι μεγαλύτερος ή ίσος από ένα Υ1 του οποίου επόμενος είναι το Υ ( Y=s(Y1) ).
το οποίο σε Prolog κωδικοποιείται με το ακόλουθο κατηγόρημα:
%%% more_eq/2
%%% more_eq(X,Y)
more_eq(_X,0).
more_eq(s(X),s(Y)):-
more_eq(X,Y).

Πρόσθεση
Ο ορισμός της πρόσθεσης σε αυτή την αναπαράσταση των φυσικών αριθμών ορίζεται με την ακόλουθη αναδρομική σχέση:

0 + Χ = Χ s(Χ) + Υ = s(Χ+Υ).

Για παράδειγμα s(0)+s(s(0)) = s( 0+s(s(0)) ) = s( 0 + s(s(0) ) = s(s(s(0))).
Η υλοποίηση σε Prolog αποτελεί απ'ευθείας κωδικοποίηση του παραπάνω ορισμού:

%%% sum/3
%%% sum(X,Y,Z)
sum(0,X,X).
sum(s(X),Y,s(Z)):-
sum(X,Y,Z).

Πολλαπλασιασμός
Αντίστοιχα ο πολλαπλασιασμός ορίζεται χρησιμοποιώντας την πρόσθεση που ορίσαμε παραπάνω, με την ακόλουθη αναδρομική σχέση:

0*Χ = 0 s(X)*Υ = Χ+Χ*Υ

η οποία κωδικοποιείται στην Prolog με τον ακόλουθο τρόπο:

%%% mult/3
%%% mult(X,Y,Z)
mult(0,_X,0).
mult(s(X),Y,Z):-
mult(X,Y,Z1),
sum(Z1,Y,Z).

Παραγοντικό
Η σχέση παραγοντικό ορίζεται χρησιμοποιώντας τον πολλαπλασιασμό από τον ακλολουθο αναδρομικό τύπο:

!0=s(0) !(s(X)) =!X * s(X).

Η οποία κωδικοποιείται σε Prolog από την επόμενη σχέση:

%%% factorial/2
%%% factorial(X,F)
factorial(0,s(0)).
factorial(s(X),Res):-
factorial(X,Res1),
mult(s(X),Res1,Res).

Δύναμη φυσικού σε φυσικό εκθέτη
Με παρόμοιο τρόπο, η δύναμη δίνεται από τον τύπο:

X^0=s(0) X^s(Y) = (X^Y) * X και η κωδικοποίηση σε Prolog:

%%% pow/3
%%% pow(X,Y,Z)
pow(X,0,s(0)).
pow(X,s(Y),Z):-
pow(X,Y,Z1),
mult(X,Z1,Z).

Άρτιοι και Περιττοί Αριθμοί
Η αναδρομική σχέση η οποία ορίζει τους περιττούς αριθμούς είναι:

το s(0) είναι περιττός ένας αριθμός είναι περιττός εάν είναι επόμενος του επομένου ενός περιττού !

το οποίο κωδικοποιείται απλά σε Prolog με το παρακάτω κατηγόρημα:

%%% odd/1
%%% odd(X)
odd(s(0)).
odd(s(s(X))):-odd(X).

Ομοίως ορίζεται και η σχέση άρτιος:

το 0 είναι άρτιος ένας αριθμός είναι άρτιος εάν είναι επόμενος του επομένου ενός άρτιου !

το οποίο σε Prolog γράφεται επίσης απλά:

%%% even/1
%%% even(X)
even(0).
even(s(s(X))):-even(X).

Εναλλακτικά η σχέση άρτιος περιττός μπορεί να υλοποιηθεί με το ακόλουθο κώδικα:

%%% odd_alt/1
%%% odd_alt(X)
odd_alt(s(X)):-even_alt(X).

%%% even_alt/1
%%% even_alt(X)
even_alt(0).
even_alt(s(X)):-odd_alt(X).

ο οποίος είναι η σχέση

το 0 είναι άρτιος ένας αριθμός είναι άρτιος εάν είναι επόμενος ενός περιττού ένας αριθμός είναι περιττός εάν είναι επόμενος ενός άρτιου

η οποία είναι πιο κοντά στην "κοινή αντίληψη" για τους άρτιους και περιττούς αριθμούς.

Όπως είδαμε παραπάνω η υλοποίηση μαθηματικών ορισμών βασισμένων στην αναδρομή και σε μαθηματικούς συμβολισμούς είναι σχετικά απλή στην γλώσσα Prolog. Οι δυνατότητες αυτές που προσφέρει η γλωσσα την κάνουν κατάλληλη για διάφορες εφαρμογές των συμβολικών μαθηματικών και ειδικότερα για μια αρκετά ενδιαφέρουσα κατηγορία η οποία ονομάζεται αυτόματη απόδειξη θεωρημάτων (automated theorem proving) .

Ο κώδικας του παραπάνω προγράμματος βρίσκεται εδώ.