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

בלוגיקה מתמטית, שפה מסדר ראשון (נקראת גם לוגיקה מסדר ראשון או תחשיב פרדיקטים מסדר ראשון, בסימון מקובל 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$, אשר אומרת לנו כמה פרמטרים מקבלת הפונקציה (קלט) וכמה היא תחזיר (פלט).

ב. תחום הפונקציה $\mathrm {Dom}$, אשר מגדיר מאילו קבוצות ערכים יהיו הפרמטרים שלנו.

ג. וטווח הפונקציה $\mathrm {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_{2}$
• $\ \forall x_{1}\exists x_{2}(x_{1}+x_{2}=0)$
• $\ (p>1)\land (\forall a((a>0)\implies ((\exists b(p=a\cdot b))\implies (a\cdot a=1\lor 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) בשפות תכנות כדוגמת ג'אווה. הממשק מכיל את השיטות (הפעולות) והמשתנים, אך אינו באמת מבצע משהו מתוכם. כאשר מתכנתים בונים מחלקה המממשת אותו, רק אז השיטות והמשתנים מקבלים ערכים, ובכך מאבדים מכלליותם. היחס בין שפה למבנה לשפה הוא זהה.

ראו גם

• הומומורפיזם (לוגיקה)
• תחשיב הפרדיקטים

קישורים חיצוניים

• שפה מסדר ראשון, באתר אנציקלופדיה למתמטיקה (באנגלית)

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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