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

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

גדירות

בהינתן קבוצת פסוקים plot:[Sigma ] , מגדירה את קבוצת ההשמות המספקות אותה. עבור קבוצת פסוקים , קבוצת המודלים של מסומנת ב- plot:[Assleft( Sigma
ight)] ומוגדרת plot:[Assleft( Sigma
ight) = left{ {z|z vDash Sigma }
ight}] .

טענה: אם $plot:[{Sigma _1} subseteq {Sigma _2}]$ אז $plot:[Assleft( {{Sigma _2}} ight) subseteq Assleft( {{Sigma _1}} ight)]$ .

שאלה: בהינתן קבוצת השמות , האם קיימת קבוצת פסוקים שמגדירה את , כלומר ? אם קיימת קבוצת פסוקים כזו נאמר כי גדירה. אם קיימת קבוצת פסוקים סופית שמגדירה את נאמר ש- גדירה באופן סופי.

כמה פסוקים יש? $plot:[{aleph _0}]$ . כמה קבוצת פסוקים? $plot:[{2^{{aleph _0}}}]$ . כמה קבוצות השמות? $plot:[{2^{{2^{{aleph _0}}}}}]$ .

מאחר וכל קבוצת פסוקים מגדירה קבוצת השמות יחידה, אזי משיקולי ספירה קיימות קבוצות לא גדירות.

דוגמאות

$plot:[{K_1} = phi ]$ . האם הקבוצה גדירה? כן, למשל $plot:[Sigma = left{ {{p_1}, eg {p_1}} ight}]$ .

$plot:[{K_2}]$ הינה קבוצת כל ההשמות. כל קבוצת טאוטולוגיות מגדירה את $plot:[{K_2}]$ .

הוכחת אי גדירות

סכימת הוכחת אי גדירות של קבוצת השמות plot:[K] :

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

מראים שכל תת קבוצה סופית היא ספיקה. מראים השמה $plot:[{z_D}]$ השייכת ל- כך ש: $plot:[{z_D} vDash D]$ . (מסתמכים בבניית $plot:[{z_D}]$ על האינדקס המקסימלי המופיע גם ב- וגם ב-.
מ-3 ומ-4 אנו מקבלים סתירה: לא קיימת, ולכן לא גדירה.

הגדרה

נאמר שקבוצת השמות plot:[K] תלויה בקבוצת משתנים $plot:[D subseteq left{ {{p_i}|i in mathbb{N}} ight}]$ אם קיימות השמות $plot:[{z_1},{z_2}]$ שמזדהות על כל האטומים מחוץ ל- plot:[D] ומתקיים $plot:[{z_1} in K]$ ו- $plot:[{z_2} otin K]$ .

הגדרה

נאמר שקבוצת אטומים $plot:[S subseteq left{ {{p_i}|i in mathbb{N}} ight}]$ מהווה תומך לקבוצת השמות plot:[K] אם לכל שתי השמות $plot:[{z_1},{z_2}]$ שמזדהות על כל האטומים בתוך plot:[S] (כלומר לכל $plot:[{z_1}left( {{p_i}} ight) = {z_2}left( {{p_i}} ight),{p_i} in S]$ ) אז $plot:[{z_1} in K Leftrightarrow {z_2} in K]$ .

דוגמא: $plot:[K = left{ {z|zleft( {{p_i}} ight) = 1} ight}]$ , $plot:[{S_1} = left{ {{p_1}} ight},{S_2} = left{ {{p_1},{p_3},{p_4}} ight}]$ .

הגדרה

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

טענה

לקבוצה plot:[K] יש תומך סופי אמ"מ גדירה באופן סופי.

· מהתומך הסופי ניתן ליצור מספר פסוקים סופי, שיתאר את התומך. פסוקים אלו יגדירו את plot:[Sigma ] .

· אם plot:[K] גדירה באופן סופי אז קיימת plot:[Sigma ] סופית המגדירה אותה. מפסוקי יש מספר סופי של אטומים. אטומם אלו מהווים תומך ל-.

לפרק הקודםעקביות

לפרק הבאתחשיב היחסים

תגובות:

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

מאת: bentz

22/5/2020 16:37

תיקון

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

מאת: משה ב

16/3/2017 20:01

שיתוף:

| עוד

יש לראות בכל האמור באתר underwar.co.il מידע כללי בלבד. כל פעולה שנעשית על פי המידע והפרטים האמורים באתר underwar.co.il הינה על אחריות הגולש בלבד. בשום מקרה אתר underwar.co.il ו/או ניר אדר ו/או צוות מנהלי פורום underwar.co.il ו/או שאר חברי הפורום אינם אחראיים בשום צורה ואופן לתוצאות השימוש במידע המובא באתר זה. עשיית שימוש במידע המובא באתר underwar.co.il, הינה על אחריותו של הגולש בלבד.

פרוייקט UnderWarrior - מדריכים, מאמרים, סיכומים וחומרי לימוד בתחומי תכנות, מתמטיקה, אבטחת מידע ועוד
1997-2025 © כל הזכויות שמורות לניר אדר

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

גדירות

טענה: אם אז .

דוגמאות

הוכחת אי גדירות

הגדרה

הגדרה

הגדרה

טענה

תגיות המסמך:

תגובות:

תיקון

סמנטיקה

תוכן העניינים:

קישורים רלוונטיים:

שיתוף:

טענה: אם $plot:[{Sigma _1} subseteq {Sigma _2}]$ אז $plot:[Assleft( {{Sigma _2}} ight) subseteq Assleft( {{Sigma _1}} ight)]$ .