שפה מסדר ראשון

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

בלוגיקה מתמטית, שפה מסדר ראשון (נקראת גם לוגיקה מסדר ראשון או תחשיב פרדיקטים מסדר ראשון, בסימון מקובל FOL) היא הכללה של תחשיב הפסוקים: מקום בו תחשיב הפסוקים מטפל במשתנים בוליאניים שיש להם רק ערכי אמת ושקר, בשפה מסדר ראשון מותר למשתנים לקבל כל ערך בקבוצה נתונה של אובייקטים.

במובן הרחב ביותר, המונח "שפה" משמש בלוגיקה מתמטית לתאר כל מערכת המאפשרת ניסוח של טענות באופן חד משמעי. זהו גם היעד המרכזי של שפות מסדר ראשון: טיפול פורמלי בנוסחאות. השפה עצמה היא כלי צורני (סינטקטי), ללא תוכן סמנטי. כאשר מוסיפים לשפה אקסיומות מתקבלת תורה, שאליה אפשר לצקת משמעות על ידי חקירת המודלים האפשריים.

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

המבנה של שפה מסדר ראשון[עריכת קוד מקור | עריכה]

שפה מסדר ראשון  \mathcal L מורכבת מפסוקים, שהם רצפים חוקיים של אותיות מתוך האלף-בית של השפה. באלף-בית יש ארבעה סוגים של אותיות:

  1.  \mathcal V - אוסף כל סימני המשתנים, למשל \ v_0,v_1,v_2,v_3,\dots.
  2.  \mathcal C - אוסף כל סימני הקבועים שלנו: \ c_0,c_1,c_2,\dots.
  3.  \mathcal F - אוסף כל סימני הפונקציות, כאשר כל פונקציה מאופיינת בשלושה דברים עיקריים (מלבד שמה), והם:
א. פונקציית המקומיות  \sigma , אשר בעצם אומרת לנו כמה פרמטרים מקבלת הפונקציה וכמה היא תחזיר.
ב. תחום הפונקציה  Dom , אשר בעצם אומר לנו מאילו קבוצת ערכים נקבל את הפרמטרים שלנו.
ג. וטווח הפונקציה  Rng , אשר בעצם אומר לנו לאילו קבוצת ערכים שייכת תוצאת הפונקציה.
4.  \mathcal R - אוסף כל סימני היחסים (הפרדיקטים), כאשר כל סימן יחס מאופיין במציין המקומיות  \sigma , בדומה לפונקציות. אלא אם כן צוין אחרת, ההנחה הרווחת היא שסימן השוויון שייך ל-\mathcal{R}. לרוב מקובל להשתמש בסימון  \approx במקום בסימון  =, וזאת כדי להבדיל מהסימן המקובל להשמת ערך.
5. קשרים לוגיים ושני הכמתים, לכל \ \forall וקיים \ \exists.
6. סימני עזר כגון סוגריים, פסיק ונקודתיים.

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

דוגמה. בשפה המשמשת לתאור מערכת המספרים השלמים יש שתי פונקציות (החיבור והכפל), יחס אחד ('קטן מ-', המסומן ב-'>') ושני קבועים (0 ו- 1). להלן כמה דוגמאות לביטויים:

  • \ x_6,
  • \ 1+1+1.
  • \ (x_1+x_2)\cdot (x_3+x_4).

מביטויים כאלה אפשר להרכיב פסוקים:

  • \ x_1>x_1,
  • \ \forall x_1 \exists x_2(x_1+x_2=0),
  • \ (p > 1) \and (\forall a ((a>0) \implies ((\exists b ( p = a\cdot b)) \implies (a\cdot a = 1 \or a \cdot a = p\cdot p))));
  • \ \forall x \exists y (y>x).

את הפסוק השני אפשר לקרוא: 'לכל מספר יש הפכי ביחס לחיבור'. בפסוק השלישי, איננו אומרים מהו המשתנה p; משתנה כזה נקרא משתנה חופשי, וסביר לצפות שערך האמת של הפסוק יהיה תלוי בערך המספרי שנבחר ל- p. הפסוק הזה אומר 'p ראשוני'. הפסוק הרביעי אומר שהקבוצה אינה חסומה: לכל מספר, יש מספר גדול יותר. לעומת זאת, אי-אפשר לומר בשפה הזו

  • \ x>5,

משום ש- 5 איננו קבוע של השפה. במקום זה, צריך לומר \ x>1+1+1+1+1.

יודגש שהשפה אינה מדברת דווקא על מספרים - כשבוחרים לה מודל מסוים, כל שנדרש הוא לקבוע קבוצה ברקע, שממנה המשתנים יבחרו את הערכים שלהם, ולצרף את המספר המתאים של פונקציות וקבועים. אם נתאים את סימן-היחס '<' ליחס "בהיר יותר", אפשר יהיה לפרש את הפסוק הרביעי כאומר "לכל צבע, יש צבע בהיר ממנו".

הכמתים 'לכל' ו'קיים' מאפשרים למשתנים לעבור על-פני כל האובייקטים במודל. לפעמים רוצים להגביל את הבחירה, כמו למשל באקסיומת המקבילים: "לכל ישר ונקודה שמחוץ לו, יש ישר מקביל". שפות מסדר שני תוכננו בדיוק למטרה הזו, ובהן אפשר לכמת על-פני סוגים שונים של משתנים, או אפילו על קבוצות או נוסחאות. אבל בדרך כלל אין בזה צורך. כדי לנסח את אקסיומת המקבילים, אפשר להסתפק בשפה שיש בה רק יחס אחד - 'שייך ל-', והיא מתייחסת בו זמנית גם לנקודות וגם לישרים. כך אפשר לנסח את אקסיומת המקבילים:

  • לכל a, אם קיים x כך ש- x שייך ל- a, אז לכל b כך ש- b אינה שייכת ל- a, קיים c כך ש((קיים e כך ש- e שייך ל- c), אבל לא קיים d כך ש- (d שייכת ל- a וגם d שייכת ל- c)).

כדי לחסוך בזמן, אפשר להגדיר בשפה הזו

  • a הוא קו ישר אם קיים x כך ש- x שייך ל- a, ו-
  • x היא נקודה אם קיים a כך ש- x שייך ל- a.

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

גם בשפה החשובה ביותר במתמטיקה, זו של תורת הקבוצות האקסיומטית, יש רק יחס אחד, השייכות, המסומן ב- \ \in. את יחס השוויון מגדירים לפי הכלה. שתי קבוצות שוות אם יש להן אותם איברים:

  • \ (x=y)\iff \forall z ((z \in x) \iff (z \in y)).

פינת המשל[עריכת קוד מקור | עריכה]

ניתן לחשוב על מושג השפה והמודל כעל מקבילים למושג הממשק (Interface) והמחלקה (Class) בשפות תכנות כדוגמת ג'אווה. הממשק מכיל את השיטות (הפעולות) והמשתנים, אך אינו באמת מבצע משהו מתוכם. כאשר אנו כמתכנתים בונים מחלקה המממשת אותו, רק אז השיטות והמשתנים מקבלים ערכים, ובכך מאבדים מכלליותם. היחס בין שפה למבנה לשפה הוא זהה.

ראו גם[עריכת קוד מקור | עריכה]