הועלה לאתר:  
מספר עמודים: 25
הורדת המסמך בגרסה להדפסהלהורדת המסמך בשלמותו

לוגיקה - סיכום נקודות

סיכום מאת: ניר אדר

הסימנים של תחשיב היחסים

הסימנים מתחלקים ל-2 קבוצות:

  1. סימנים לוגיים – סימנים המשותפים לכל השפות של תחשיב היחסים.
  2. פרמטרים של השפה – מילון – סימנים המיוחדים לשפה.

הסימנים הלוגיים

  • כמתים: לכלplot:\[\forall \], קיים plot:\[\exists \].
  • קשרים של תחשיב הפסוקים: plot:\[\left\{ { \to , \wedge , \vee ,\neg } \right\}\].
  • סוגריים ופסיק.
  • סימן שוויון plot:\[ \approx \].
  • משתנים: plot:\[\left\{ {{v_i}|i \in \mathbb{N}} \right\}\].

מילון: פרמטרים של השפה

  • סימני קבועים אישיים מסומנים ב-plot:\[{C_\alpha }\] כאשר plot:\[\alpha \] אינדקס מספרי.
  • סימני יחס המסומנים ב-plot:\[{R_{n,\alpha }}\] כאשר plot:\[n,\alpha  \in \mathbb{N}\]. plot:\[n\] הוא מספר הארגומנטים ביחס ו-plot:\[\alpha \] הוא אינדקס מספרי.
  • סימני פונקציה המסומנים ב-plot:\[{F_{n,\alpha }}\]. plot:\[n\] הוא מספר הארגומנטים ביחס ו-plot:\[\alpha \] הוא אינדקס מספרי.

מילון: אוסף סימני יחס, סימני פונקציה וסימני קבועים אישיים, כאשר לכל סימן פונקציה ולכל סימן יחס ידוע מספר הארגומנטים. מילון מסומן לרוב באות plot:\[\tau \]. לדוגמא: plot:\[{\tau _0} = \left\langle {{R_{1,0}},{R_{1,1}},{F_{2,0}},{F_{2,3}},{C_2},{C_3}} \right\rangle \].

מילון סופי הוא מילון המכיל מספר סופי של סימנים. מילון יחסי הוא מילון המכיל רק סימני יחס.

הגדרת אוסף הטענות בשפה

שלב 1:

הגדרת אוסף העצמים עליהם מדברים. שמות עצם אינם טענות שניתן לשאול עליהם

נכון / לא נכון.

שלב 2:

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

הגדרת אוסף שמות העצם

ההגדרה הינה באינדוקציה:  (סימני פיסוק, משתניםplot:\[ \cup \] קבועים)X.

קבוצת האטומים: סימני הקבועים מהמילון בתוספת המשתנים plot:\[\left\{ {{v_i}|i \in \mathbb{N}} \right\}\].

קבוצת הפעולות: לכל סימן פונקציה plot:\[{F_{n,\alpha }}\] במילון נגדיר פעולה המקבלת שמות עצם plot:\[{t_1},...,{t_n}\] ומוציאה כפלט את plot:\[{F_{n,\alpha }}\left( {{t_1},...,{t_n}} \right)\].

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

הגדרת אוסף הטענות/נוסחאות.

ההגדרה הינה באינדוקציה. קבוצת האטומים הינה אוסף סדרות הסימנים מהצורה plot:\[{R_{n,\alpha }}\left( {{t_1},...,{t_n}} \right)\] כאשר plot:\[{t_1},...,{t_n}\] שמות עצם, ו-plot:\[{R_{n,\alpha }}\] הינו סימן יחס plot:\[n\]-מקומי מהמילון. כל סדרת סימנים כזו תקרא נוסחה אטומית.

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

עבור הגדרת אוסף הנוסחאות נתייחס לסימן "=" כאל סימן יחס דו מקומי. דוגמא: plot:\[F\left( {x,x} \right) = F\left( {x,y} \right)\] זוהי נוסחה אטומית.

קבוצת אוסף הפעולות מתחלקת לשני חלקים:

  1. הפעלת הקשרים של תחשיב הפסוקים. אם plot:\[\alpha ,\beta \] נוסחאות, אזי גם הביטויים הנ"ל הם נוסחאות: plot:\[\left( {\alpha  \wedge \beta } \right),\left( {\alpha  \vee \beta } \right),\left( {\alpha  \to \beta } \right),\left( {\neg \alpha } \right)\].
  2. הפעלת כמתים: לכל נוסחה plot:\[\alpha \] ומשתנה plot:\[x\], גם plot:\[\forall x\alpha \] ו-plot:\[\exists x\alpha \] הן נוסחאות.

הערה: מניחים קדימות לכמתים: 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)\]

הבדלים בין סימני יחס לפונקציות

plot:\[F\left( {F\left( {} \right)} \right)\] הינו שם עצם. plot:\[R\left( {R\left( {} \right)} \right)\] לא מוגדר כחלק מתחשיב היחסים!

plot:\[R\left( {F\left( {} \right)} \right)\] הינה נוסחה אטומית. plot:\[F\left( {R\left( {} \right)} \right)\] לא קיים – אסור להפעיל סימני פונקציה על יחס.

plot:\[R \to R\] מותר. plot:\[F \to F\] - אסור. יש לתת סימני יחס בין הקשרים והכמתים.

plot:\[\forall xR\] מותר. plot:\[\forall xF\] אסור.

תגיות המסמך:

לפרק הקודםהגדרה פורמלית של השפה
לפרק הבאסמנטיקה לתחשיב היחסים - הגדרה אינטואיטיבית
מאת: bentz

תיקון

מציעה להחליף את
(a¬)
ב
a¬
שכן (a¬) אינו פסוק
מאת: משה ב

סמנטיקה
שיתוף:
| עוד