2.1. תזכורת – תחשיב היחסים
הסימנים של תחשיב היחסים
הסימנים מתחלקים ל-2 קבוצות:
- סימנים לוגיים – סימנים המשותפים לכל השפות של תחשיב היחסים.
- פרמטרים של השפה – מילון – סימנים המיוחדים לשפה.
הסימנים הלוגיים
- כמתים: לכל
, קיים
.
- קשרים של תחשיב הפסוקים:
.
- סוגריים ופסיק.
- סימן שוויון
.
- משתנים:
.
מילון: פרמטרים של השפה
- סימני קבועים אישיים מסומנים ב-
כאשר
אינדקס מספרי.
- סימני יחס המסומנים ב-
כאשר
.
הוא מספר הארגומנטים ביחס ו-
הוא אינדקס מספרי.
- סימני פונקציה המסומנים ב-
.
הוא מספר הארגומנטים ביחס ו-
הוא אינדקס מספרי.
מילון:
אוסף סימני יחס, סימני פונקציה וסימני קבועים אישיים, כאשר לכל סימן פונקציה ולכל
סימן יחס ידוע מספר הארגומנטים. מילון מסומן לרוב באות
.
לדוגמא:
.
מילון סופי
הוא מילון המכיל מספר סופי של סימנים. מילון יחסי הוא מילון המכיל רק סימני
יחס.
הגדרת אוסף הטענות בשפה
שלב 1: |
הגדרת אוסף העצמים עליהם מדברים. שמות
עצם אינם טענות שניתן לשאול עליהם
נכון / לא נכון. |
שלב 2: |
נגדיר את אוסף הטענות בשפה שתיקראנה נוסחאות
על סמך שמות העצם. |
הגדרת אוסף שמות העצם
ההגדרה הינה באינדוקציה: (סימני פיסוק, משתנים
קבועים)X.
קבוצת האטומים: סימני הקבועים מהמילון בתוספת המשתנים
.
קבוצת הפעולות: לכל סימן פונקציה
במילון נגדיר פעולה המקבלת
שמות עצם
ומוציאה כפלט את
.
הערה: מספר
הפעולות הינו כמספר הפונקציות במילון של השפה. ישנן שפות ללא פונקציות, ולכן ללא
פעולות ליצירת שמות עצם. מספר שמות העצם בשפות אלו זה למספר האטומים.
הגדרת אוסף הטענות/נוסחאות.
ההגדרה הינה באינדוקציה. קבוצת האטומים
הינה אוסף סדרות הסימנים מהצורה
כאשר
שמות עצם, ו-
הינו סימן יחס
-מקומי מהמילון. כל סדרת סימנים כזו תקרא נוסחה
אטומית.
אבחנה: בשם עצם יכולות להיות כלולות כמה
פונקציות. בנוסחה אטומית יש רק סימן יחס אחד (ואחד או יותר שמות עצם).
עבור הגדרת אוסף הנוסחאות נתייחס לסימן
"=" כאל סימן יחס דו מקומי. דוגמא:
זוהי נוסחה אטומית.
קבוצת אוסף הפעולות מתחלקת לשני חלקים:
- הפעלת הקשרים של תחשיב הפסוקים. אם
נוסחאות, אזי גם
הביטויים הנ"ל הם נוסחאות:
.
- הפעלת כמתים: לכל נוסחה
ומשתנה
,
גם
ו-
הן נוסחאות.
הערה: מניחים קדימות לכמתים: ![plot:\[\forall {v_i}P\left( {{v_i}} \right) \to R\left( {{v_r}} \right) \equiv
\left( {\forall {v_i}P\left( {{v_i}} \right)} \right) \to R\left( {{v_r}}
\right)\]](/documentResources/326/plot_33.png)
הבדלים בין סימני יחס לפונקציות
הינו שם עצם.
לא מוגדר כחלק מתחשיב היחסים!
הינה נוסחה אטומית.
לא קיים – אסור להפעיל סימני פונקציה על יחס.
מותר.
- אסור. יש לתת סימני יחס בין הקשרים והכמתים.
מותר.
אסור.
סמנטיקה לתחשיב היחסים - הגדרה
אינטואיטיבית
בהינתן מילון
,
מבנה עבור
מוגדר כך:
![plot:\[M
= \left\langle {{D^M},{R_1}^M,...,{R_m}^M,{F^M}_1,...,{F_k}^M,{C_1}^M...,{C_l}^M}
\right\rangle \]](/documentResources/326/plot_45.png)
כאשר
הוא התחום,
הוא הפירוש של סימן היחס
במבנה
,
הוא הפירוש של סימן הפונקציה
במבנה
,
הוא הפירוש של סימן הקבוע
במבנה
.
דוגמא:
.
.
בהינתן מבנה עבור מילון
,
נגדיר השמה
המתאימה למשתנים ערכים מהתחום:
![plot:\[z:\left\{
{{v_i}|i \in \mathbb{N}} \right\} \to {D^M}\]](/documentResources/326/plot_60.png)
נגדיר הרחבה של ההשמה
,
שתתאים לכל שם עצם
מעל המילון
איבר בתחום שיסומן
.
נגדיר באינדוקציה על מבנה שמות העצם:
בסיס:
משתנה
.
קבוע
.
סגור:
.
משתנים חופשיים וקשורים
- כל האיברים בתחום הם ביחס עם עצמם.
-
ביחס
עם עצמו.
בדוגמא הראשונה אין צורך לדעת מה הערך
של
בהשמה, ובנוסחה השניה כן. בנוסחה הראשונה
מופיע קשור (תחת השפעת הכמת), לכן הוא אינו מופיע בתרגום הנוסחה למילים ואין צורך
לדעת את הערך שההשמה נתנה לו. בנוסחה השניה
חופשי.
טענה: תהי
נוסחה מעל מילון
ו-
מבנה עבור
. אם
ו-
השמות ב-
המזדהות על המשתנים החופשיים ב-
,
אז ערך האמת של
תחת
ותחת
זהה.
מסקנה: אם
נוסחה ללא משתנים חופשיים, אז ערך האמת של
אינו תלוי בהשמה.
הגדרה:
נוסחה
בלי משתנים חופשיים נקראת פסוק.
הגדרה פורמלית: נגדיר באינדוקציה על מבנה הנוסחה
מתי
הוא משתנה חופשי ב-
.
בסיס: נוסחאות אטומיות:
חופשי ב-
אם
מופיע ב-
.
סגור: קשרים:
עבור
,
חופשי ב-
אם
חופשי ב-
או
חופשי ב-
.
חופשי ב-
אם
חופשי ב-
.
כמתים:
חופשי ב-
או ב-
אם
חופשי ב-
וגם
.
משתנה שאינו חופשי נקרא משתנה קשור.
סמנטיקה לתחשיב היחסים - הגדרה
פורמלית
הגדרת מבנה:
בהינתן מילון
:
מבנה עבור
הוא:
![plot:\[M
= \left\langle
{{D^M},{R_1}^M,...,{R_m}^M,{F^M}_1,...,{F_k}^M,{C_1}^M...,{C_l}^M}
\right\rangle \]](/documentResources/326/plot_118.png)
כאשר
הוא התחום.
- לכל
אם
הוא סימן יחס
-מקומי
אזי
, כלומר
הוא יחס
-מקומי
מעל
.
- לכל
אם
סימן פונקציה
-מקומי
אז
, כלומר
מתארת מה הערך של
עבור כל
-יה סדורה של איברים מ-
.
- לכל
, מתקיים:
.
ראינו כיצד בהינתן מבנה M
מגדירים השמה
ב-
:
וראינו כיצד להרחיב את
כך שתתאים ערך מהתחום לכל שם עצם.
בהינתן נוסחה
מעל מילון
, מבנה
והשמה
עבור
נסמן
את הטענה ש-
מסתפקת ב-
תחת
.
הגדרת ערך האמת: נגדיר באינדוקציה על מבנה
מתי
.
בסיס:
נוסחה אטומית:
עבור
שמות עצם,
.
כמו כן כאשר
, עבור
שמות עצם,
.
סגור:
- קשרים: מחשבים את ערך האמת בעזר טבלאות האמת. לכל נוסחה
, מבנה
והשמה
, מתקיים כי
או
אבל לא שניהם.
- כמתים: נניח שלכל מבנה
והשמה
אנו יודעים האם
. נרצה לדעת האם
,
למבנה והשמה מסויימים. בהינתן השמה
,
משתנה
ואיבר
, נגדיר השמה מתוקנת
:
![plot:\[z\left[ {{v_i} \leftarrow d}
\right]\left( {{v_j}} \right) = \left\{ {\begin{array}{*{20}{c}}
{z\left( {{v_j}} \right)} \hfill & {i \ne j} \hfill \\
d \hfill & {i = j} \hfill \\
\end{array} } \right.\]](/documentResources/326/plot_173.png)
נגדיר: לכל
מתקיים
.
קיים
עבורו
.