תחשיב למבדא

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

תחשיב למְבְּדא הוא צורה לוגית-פורמלית ריגורוזית לטיפול בפונקציות.

תוכן עניינים

1 רקע
2 תחשיב הלמבדא
3 הכללות
4 כללים לתחשיב למבדא
5 ראו גם

[עריכה] רקע

פונקציה היא שלשה $\ ( f , A , B )$ כאשר A הוא תחום ההגדרה, B הוא הטווח (A ו-B הן קבוצות) ואילו f הוא הגרף של הפונקציה - כלומר: יחס מעל $\ A \times B$ שמכיל את הזוגות הסדורים מהצורה $\ \left( a , f(a) \right)$ . הגרף f נקרא לעתים (באופן לא פורמלי) "כלל התאמה".

כאשר עובדים עם פונקציה נהוג לסמן או לרשום:

תהי $\ f : A \to B$ הפונקציה $\ f(x)$ (או באנליזה מתמטית של פונקציות ממשיות: $\ f(x) = x^2$ )...

אבל זו צורת רישום בזבזנית ולא מדויקת, שכן מבחינה לוגית, $\ f(x)$ הוא לא פונקציה אלא מספר כלשהו! למרות שהסימונים המקובלים כיום הם לא חד-משמעיים, הם נפוצים בגלל ההרגל והנוחות שבהם.

ברם, לצרכי לוגיקה וניתוח הוכחות באמצעות מחשב יש למצוא ביטוי לוגי-פורמלי חד-משמעי שיתאר פונקציה. ביטוי זה הוא תחשיב הלמבדא.

[עריכה] תחשיב הלמבדא

תחשיב הלמבדא הוא ביטוי מהצורה:

$\ f = \lambda x \in A : f(x) \in B$

שמשמעותו היא:

הפונקציה f היא הפונקציה המתאימה לכל $\ x \in A$ איבר $\ f(x) \in B$ (כאשר f הוא כלל התאמה כלשהו).

כאשר:

הכמת "למבדא" מציין שמדובר בכלל התאמה.
האיבר הראשון אחרי הלמבדא הוא תחום ההגדרה של הפונקציה.
האיבר שאחרי הנקודתיים הוא כלל התאמה, שבדרך כלל מוצג כביטוי של x. בשביל להיות פורמליים יש לציין מאיזה טווח לקוח ביטוי זה, אבל מאחר שזה לרוב ברור מההקשר נוהגים להשמיטו. ביישומים רבים, נוח להניח שהטווח של f הוא פשוט התמונה שלה $\ Im(f)$ .

הערה: הסימון המקובל בספרים הוא דווקא

$\ f = \lambda x \in A . f(x) \in B$

אך הוא בעייתי מאחר וקשה לראות את הנקודה (ולכן מעדיפים לרשום נקודתיים).

דוגמה: את הפונקציה של שורש ריבועי נרשום כך:

$\ \sqrt{} = \lambda x \in [0 , \infty ) : \sqrt{x} \in \mathbb{R}^+$

[עריכה] הכללות

אפשר להכליל את תחשיב הלמבדא כדי לדון בפונקציות רבות משתנים ובפונקציה של פונקציה.

ראוי בנושא זה לציין את פונקציית קורי שבאמצעותה מראים שההגדרה של פונקציה בשני משתנים שקולה להגדרה של פונקציה של פונקציה במשתנה אחד.

[עריכה] כללים לתחשיב למבדא

קיימים כללים לוגיים פורמליים המאפשרים מניפולציות וטיפול בפונקציות באמצעות תחשיב למבדא.

[עריכה] כלל אלפא

כלל זה אומר ש

$\ \lambda x: f(x) = \lambda y : f(y)$

ומשמעותו הוא ש"למבדא" הוא כמת לוגי קושר. כלומר, מותר לשנות את השם של המשתנה הקשור, כל עוד לא מחליפים את שמו לשם של משתנה המופיע חופשית.

[עריכה] כלל בתא

כלל זה אומר ש

$\ \left( \lambda x: f(x) \right)(a) = f(a)$

ומשמעותו היא שהפעלה של הפונקציה על איבר כלשהו מחזירה את התמונה של אותו איבר לפי כלל ההתאמה של הפונקציה. במילים אחרות, זה כלל הצבה לחישוב הערך שמחזירה הפונקציה.