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

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

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

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

בהינתן מילון plot:\[\tau \], plot:\[\tau  = \left\langle {{R_1},...,{R_m},{F_1},...,{F_k},{C_1}...,{C_l}} \right\rangle \] מבנה עבור plot:\[\tau \] מוגדר כך:

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 \]

כאשר plot:\[{D^M}\] הוא התחום, plot:\[{R_i}^M\] הוא הפירוש של סימן היחס plot:\[{R_i}\] במבנה plot:\[M\], plot:\[{F_i}^M\] הוא הפירוש של סימן הפונקציה plot:\[{F_i}\] במבנה plot:\[M\], plot:\[{C_i}^M\] הוא הפירוש של סימן הקבוע plot:\[{C_i}\] במבנה plot:\[M\].

דוגמא: plot:\[\tau  = \left\langle {{R_{2,0}},{F_{1,0}},{C_0},{C_1}} \right\rangle \]. plot:\[{M_2} = \left\langle {P\left( A \right), \subseteq ,{\text{completion}},\phi ,A} \right\rangle ,{M_1} = \left\langle {\mathbb{N}, \leqslant , + 1,2,3} \right\rangle \].

בהינתן מבנה עבור מילון plot:\[\tau \], נגדיר השמה plot:\[z\] המתאימה למשתנים ערכים מהתחום:

plot:\[z:\left\{ {{v_i}|i \in \mathbb{N}} \right\} \to {D^M}\]

נגדיר הרחבה של ההשמה plot:\[z\], שתתאים לכל שם עצם plot:\[t\] מעל המילון plot:\[\tau \] איבר בתחום שיסומן plot:\[\bar z\left( t \right)\].

נגדיר באינדוקציה על מבנה שמות העצם:

בסיס: plot:\[t\] משתנהplot:\[\bar z\left( t \right) = z\left( t \right) \Leftarrow \]. plot:\[t\] קבועplot:\[\bar z\left( {{c_i}} \right) = {c_i}^M \Leftarrow t = {c_i} \Leftarrow \].

סגור: plot:\[\bar z\left( {{F_{n,\alpha }}\left( {{t_1},...,{t_n}} \right)} \right) = F_{n,\alpha }^M\left( {\bar z\left( {{t_1}} \right),...,\bar z\left( {{t_n}} \right)} \right)\].

משתנים חופשיים וקשורים

  1. plot:\[\forall {v_1}{R_{2,0}}\left( {{v_1},{v_1}} \right)\] - כל האיברים בתחום הם ביחס עם עצמם.
  2. plot:\[{R_{2,0}}\left( {{v_1},{v_1}} \right)\] - plot:\[{v_1}\] ביחס plot:\[{R_{2,0}}\] עם עצמו.

בדוגמא הראשונה אין צורך לדעת מה הערך של plot:\[{v_1}\] בהשמה, ובנוסחה השניה כן. בנוסחה הראשונה plot:\[{v_1}\] מופיע קשור (תחת השפעת הכמת), לכן הוא אינו מופיע בתרגום הנוסחה למילים ואין צורך לדעת את הערך שההשמה נתנה לו. בנוסחה השניה plot:\[{v_1}\] חופשי.

טענה: תהי plot:\[\alpha \] נוסחה מעל מילון plot:\[\tau \] ו-plot:\[M\] מבנה עבור plot:\[\tau \]. אם plot:\[{z_1}\] ו-plot:\[{z_2}\] השמות ב-plot:\[M\] המזדהות על המשתנים החופשיים ב-plot:\[\alpha \], אז ערך האמת של plot:\[\alpha \] תחת plot:\[{z_1}\] ותחתplot:\[{z_2}\] זהה.

מסקנה: אם plot:\[\alpha \] נוסחה ללא משתנים חופשיים, אז ערך האמת של plot:\[\alpha \] אינו תלוי בהשמה.

הגדרה: נוסחה plot:\[\alpha \] בלי משתנים חופשיים נקראת פסוק.

הגדרה פורמלית: נגדיר באינדוקציה על מבנה הנוסחה plot:\[\alpha \] מתי plot:\[{v_i}\] הוא משתנה חופשי ב-plot:\[\alpha \].

בסיס: נוסחאות אטומיות: plot:\[{v_i}\] חופשי ב-plot:\[\alpha \] אם plot:\[{v_i}\] מופיע ב-plot:\[\alpha \].

סגור:     קשרים: עבור plot:\[ \circ  \in \left\{ { \wedge , \vee , \to } \right\}\], plot:\[{v_i}\] חופשי ב-plot:\[\left( {\alpha  \circ \beta } \right)\] אם plot:\[{v_i}\] חופשי ב-plot:\[\alpha \] או plot:\[{v_i}\] חופשי ב-plot:\[\beta \].

plot:\[{v_i}\] חופשי ב-plot:\[\left( {\neg \alpha } \right)\] אם plot:\[{v_i}\] חופשי ב-plot:\[\alpha \].

כמתים: plot:\[{v_i}\] חופשי ב-plot:\[\forall {v_j}\alpha \] או ב-plot:\[\exists {v_j}\alpha \] אם plot:\[{v_i}\] חופשי ב-plot:\[\alpha \] וגם plot:\[i \ne j\].

משתנה שאינו חופשי נקרא משתנה קשור.

תגיות המסמך:

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

תיקון

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

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