|
בפרק זה נלמד להשתמש בהגדרות רקורסיביות על מנת להגדיר בפרולוג מתארים לזיהוי מספרים טבעיים, לחיבור ולכפל.
נשתמש בייצוג מיוחד למספרים הטבעיים (…0,1,2), כפי שמציעים Blackburn, Bos, & Striegnitz בספרם (הפנייה לספר תוכלו למצוא בקישורים הממולצים).
לפי שיטה זו, מייצגים כל מספר טבעי בעזרת הספרה 0, המילה okev, וסוגריים בלבד.
נכתוב 0 על מנת לייצג את המספר הטבעי 0, okev(0) כדי לייצג את המספר הטבעי 1 (העוקב של 0), okev(okev(0)) כדי לייצג את המספר 2 וכולי.
השיטה חושפת את המבנה של המספרים הטבעיים כבנויים על בסיס 0 ופונקצית העוקב, שעבור כל מספר טבעי מחזירה את המספר הטבעי הגדול ממנו ב-1. למרות שהכתיבה בה די מסורבלת, היא נותנת לנו כלים להרכיב ולפרק ייצוגים של מספרים טבעיים.
מספרים טבעיים
נתחיל בהגדרת המתאר numeral לזיהוי מספרים טבעיים על סמך ההגדרה האינדוקטיבית שהצגנו לעיל:
- 0 הוא מספר טבעי.
- העוקב של מספר טבעי הוא מספר טבעי.
זו הגדרה רקורסיבית: סעיף א' הוא תנאי העצירה, וסעיף ב' הוא התנאי הרקורסיבי שבו המתאר מוגדר בעזרת עצמו.
נתרגם אותה לפרולוג:
numeral(0).
numeral(okev(N)) :- numeral(N).
שימו לב לדמיון הרב בין ההגדרה במילים לבין ההגדרה בפרולוג. התרגום הוא כמעט מילולי!
חיבור
גם חיבור של שני מספרים טבעיים ניתן להגדיר באופן רקורסיבי.
ההגדרה הרקורסיבית מבוססת על השוויון הבא: (X+1)+Y=(X+Y)+1.
תנאי העצירה נוגע לחיבור עם אפס: 0+X=X.
ובפרולוג:
add(0,X,X).
add(okev(X),Y,okev(Z)) :- add(X,Y,Z).
כפל
הגדרה רקורסיבית של כפל מבוססת על חיבור:
X*(Y+1)=X*Y+X.
תנאי העצירה קובע את תוצאת ההכפלה באפס: X*0=0.
mul(_, 0, 0).
mul(X, okev(Y), _) :- add(X, Z, _), mul(X,Y,Z).
|
