הצגת המקור של הדף "שפה מסדר ראשון"

ב[[לוגיקה מתמטית]], '''שפה מסדר ראשון''' (נקראת גם '''לוגיקה מסדר ראשון''' או '''תחשיב היחסים''' או '''[[תחשיב פרדיקטים]] מסדר ראשון''', בסימון מקובל '''FOL''') היא מנגנון חישוב לניסוח טענות [[פורמליזם (מתמטיקה)|פורמליות]] כלליות, כל עוד מסתפקים ב[[כמת|כימות]] על [[אבר (מתמטיקה)|אבר]]ים ב[[מודל (מתמטיקה)|מודל]].{{ש}}
שפה מסדר ראשון היא הכללה של [[תחשיב הפסוקים]]; כלומר, בעוד שתחשיב הפסוקים מטפל במשתנים בוליאניים שיש להם רק [[ערך אמת|ערכי אמת]], בשפה מסדר ראשון מותר למשתנים לקבל כל ערך מתוך [[קבוצה (מתמטיקה)|קבוצה]] נתונה של אובייקטים.

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

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

== המבנה של שפה מסדר ראשון ==

שפה מסדר ראשון <math> \mathcal L </math> מורכבת מ[[פסוק (לוגיקה)|פסוקים]], שהם רצפים חוקיים של אותיות מתוך ה[[אלף-בית (שפה פורמלית)|אלף-בית של השפה]]. באלף-בית יש ארבעה סוגים של אותיות:
# <math> \mathcal V </math> – אוסף כל סימני המשתנים, למשל <math>\ v_0,v_1,v_2,v_3,\dots</math>.
# <math> \mathcal C </math> – אוסף כל סימני הקבועים: <math>\ c_0,c_1,c_2,\dots</math>.
# <math> \mathcal F </math> – אוסף כל סימני הפונקציות, כאשר כל פונקציה מאופיינת בשלושה דברים עיקריים (מלבד שמה), והם:
:::::: א. [[מקומיות (תורת הקבוצות)|פונקציית המקומיות]] <math> \sigma </math>, אשר אומרת לנו כמה פרמטרים מקבלת הפונקציה (קלט) וכמה היא תחזיר (פלט).
:::::: ב. תחום הפונקציה <math> \mathrm{Dom} </math>, אשר מגדיר מאילו קבוצות ערכים יהיו הפרמטרים שלנו.
:::::: ג. וטווח הפונקציה <math> \mathrm{Rng} </math>, אשר מגדיר לאילו קבוצות ערכים שייכת תוצאת הפונקציה.
::4. <math> \mathcal R </math> – אוסף כל סימני היחסים (ה[[פרדיקט (פונקציה)|פרדיקט]]ים), כאשר כל סימן יחס מאופיין במציין המקומיות <math> \sigma </math>, בדומה לפונקציות. אלא אם כן צוין אחרת, ההנחה הרווחת היא שסימן השוויון שייך ל-<math>\mathcal{R}</math>. לרוב מקובל להשתמש בסימון <math> \approx </math> במקום בסימון <math> =</math>, וזאת כדי להבדיל מהסימן המקובל להשמת ערך.
::5. [[קשר לוגי|קשרים לוגיים]] ושני ה[[כמת]]ים, '''לכל''' <math>\ \forall</math> ו'''קיים''' <math>\ \exists</math>.
::6. סימני עזר כגון [[סוגריים]], [[פסיק]] ו[[נקודתיים]].

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

'''דוגמה:''' להלן כמה דוגמאות לביטויים בשפה המשמשת לתיאור [[חוג המספרים השלמים|מערכת המספרים השלמים]], שבה שתי פונקציות (החיבור והכפל), יחס אחד ('קטן מ-', המסומן ב-'<math><</math>') ושני קבועים (<math>0</math> ו-<math>1</math>):
* <math>\ x_6</math>
* <math>\ 1+1+1</math>
* <math>\ (x_1+x_2)\cdot (x_3+x_4)</math>
מביטויים כאלה אפשר להרכיב [[פסוק (לוגיקה מתמטית)|פסוק]]ים:
* <math>\ x_1>x_2</math>
* <math>\ \forall x_1 \exists x_2(x_1+x_2=0)</math>
* <math>\ (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))))</math>
* <math>\ \forall x \exists y (y>x)</math>

את הפסוק השני אפשר לקרוא: 'לכל מספר יש הפכי ביחס לחיבור'. בפסוק השלישי, איננו אומרים מהו המשתנה <math>p</math>; משתנה כזה נקרא '''משתנה חופשי''', וסביר לצפות שערך האמת של הפסוק יהיה תלוי בערך המספרי שנבחר ל-<math>p</math>. הפסוק הזה אומר '<math>p</math> ראשוני'. הפסוק הרביעי אומר שהקבוצה אינה חסומה: לכל מספר, יש מספר גדול יותר. לעומת זאת, אי-אפשר לומר בשפה הזו
* <math>\ x>5</math>
משום ש-5 איננו קבוע של השפה. במקום זה, צריך לומר <math>\ x>1+1+1+1+1</math>.

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

הכמתים 'לכל' ו'קיים' מאפשרים למשתנים לעבור על-פני כל האובייקטים במודל. לפעמים רוצים להגביל את הבחירה, כמו ב[[אקסיומת המקבילים]]: "לכל '''ישר''' ולכל '''נקודה''' שמחוץ לישר, יש '''ישר''' אחד ויחיד העובר דרך הנקודה ומקביל לישר הנתון". שפות מסדר שני תוכננו בדיוק למטרה הזו, ובהן אפשר לכמת על-פני סוגים שונים של משתנים, או אפילו על קבוצות או נוסחאות. אבל בדרך כלל אין בזה צורך. כדי לנסח את אקסיומת המקבילים, אפשר להסתפק בשפה שיש בה רק יחס אחד – 'שייך ל-', והיא מתייחסת בו זמנית גם לנקודות וגם לישרים. כך אפשר לנסח את אקסיומת המקבילים:
* לכל <math>a</math>, אם קיים <math>x</math> כך ש-<math>x</math> שייך ל-<math>a</math>, אז לכל <math>b</math> כך ש-<math>b</math> אינה שייכת ל-<math>a</math>, קיים <math>c</math> כך ש((קיים <math>e</math> כך ש-<math>e</math> שייך ל-<math>c</math>), אבל לא קיים <math>d</math> כך ש-(<math>d</math> שייכת ל-<math>a</math> וגם <math>d</math> שייכת ל-<math>c</math>)).
כדי לחסוך בזמן, אפשר להגדיר בשפה הזו
* <math>a</math> הוא קו ישר אם קיים <math>x</math> כך ש-<math>x</math> שייך ל-<math>a</math>, ו-
* <math>x</math> היא נקודה אם קיים <math>a</math> כך ש-<math>x</math> שייך ל-<math>a</math>.
מעכשיו המונחים 'קו' ו'נקודה' הם חלק מהשפה, מפני שאפשר להרחיב אותם בחזרה לפסוקים מפורשים.

גם בשפה החשובה ביותר במתמטיקה, זו של תורת הקבוצות האקסיומטית, יש רק יחס אחד, השייכות, המסומן ב-<math>\in</math>. את יחס השוויון מגדירים לפי הכלה. שתי קבוצות שוות אם יש להן אותם איברים:
* <math>\ (x=y)\iff \forall z ((z \in x) \iff (z \in y))</math>

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

== ראו גם ==
*[[הומומורפיזם (לוגיקה)]]
*[[תחשיב הפרדיקטים]]

==קישורים חיצוניים==
* {{אנציקלופדיה למתמטיקה|Predicate_calculus}}

[[קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה]]
[[קטגוריה:לוגיקה]]
[[קטגוריה:לוגיקה מתמטית]]