סמנטיקה בתחשיב הפסוקים

פתיחה

• היום נדבר על סמנטיקה בתחשיב הפסוקים (Propositional Logic).
• נזכיר את הלוגיקות שנלמד בקורס: תחשיב הפסוקים ותחשיב היחסים.

תחביר ומשמעות

• נתחיל עם תחביר: מהו פסוק מוגדר היטב?
• משמעות: מתי מסיקים מסקנות בתחשיב הפסוקים.
• השיעורים יתחילו בחזרה על מה שהיה בשיעור הקודם.

פעולות על קבוצות

• חיתוך: איבר שייך לחיתוך של זוג קבוצות אם הוא נמצא בשתיהן.
• איחוד: איבר שייך לאיחוד אם הוא נמצא באחת מהן או בשתיהן.
• אפרש: איבר נמצא באפרש אם הוא נמצא בקבוצה הראשונה ולא בשנייה.
• משלים: צריך קבוצת עולם, והמשלים הוא כל העברים שאינם בקבוצה.

הוכחות

• הוכחות לשוויון קבוצות: אוכלת דו-כיוונית.
• קייס אנליסיס: אם A ו-B נכונים, אז C נכון.
• חוקים לא פורמליים: אם A נובע מ-B, אז ניתן להסיק את A.

קבוצות בנויות אינדוקטיבית

• בסיס לקבוצה: איבר אחד לפחות בקבוצה.
• כלל גזירה: איך בונים איבר אחר מקיים.
• דוגמה: קבוצת הטבעיים - 0 שייך לקבוצה, אם איבר שייך לקבוצה, אז גם האיבר +1 שייך.

מכרוזות

• מכרוזת: אוסף אותיות מסודר.
• דוגמה לקבוצת מכרוזות: מכרוזות עם אותיות M, I ו-U.
• כללי יצירה: איך ליצור מכרוזות חדשות.

חזרה על נוסחאות מוגדרות היטב

• נוסחה מוגדרת היטב היא נוסחה שיש לה מבנה פורמלי.
• נוסחאות אטומיות הן השתיים.

יחס נביאה סמנטי

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

מודלים וולואציה

• ולואציה: הסמה של ערכי אמת למשתנים.
• מודל של נוסחה: כאשר ערך הנוסחה הוא T.
• יחס נביאה CPL: מגמא נובעת פסי אם ורק אם כל ולואציה שהיא מודל של גמא היא מודל של פסי.

דוגמאות וטאוטולוגיות

• דוגמה לטאוטולוגיה: A או לא A.
• טאוטולוגיה: נוסחה שנכונה בכל המקרים.

סיום

• חזרת על מושגים ויחס נביאה סמנטי.
• שבוע הבא נמשיך לעסוק בנושא.