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

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

מושגי יסוד

ספיקות: פסוק $plot:\[\alpha \]$ ייקרא ספיק אם קיימת השמה $plot:\[z\]$ כך ש- $plot:\[z \vDash \alpha \]$ .
טאוטולוגיה: פסוק $plot:\[\alpha \]$ ייקרא טאוטולוגיה אם לכל השמה $plot:\[z\]$ מתקיים $plot:\[z \vDash \alpha \]$ .
סתירה: פסוק $plot:\[\alpha \]$ ייקרא סתירה אם לכל השמה $plot:\[z\]$ מתקיים $plot:\[z\not \vDash \alpha \]$ .

טענה: $plot:\[\alpha \]$ סתירה אמ"מ $plot:\[\neg \alpha \]$ טאוטולוגיה.

נכון / לא נכון:

אם $plot:\[\alpha \vee \beta \]$ טאוטולוגיה אזי $plot:\[\alpha \]$ טאוטולוגיה או $plot:\[\beta \]$ טאוטולוגיה – לא נכון.
אם $plot:\[\alpha \vee \beta \]$ סתירה אז $plot:\[\alpha \]$ סתירה וגם $plot:\[\beta \]$ סתירה – נכון.

הוכחת טאוטולוגיה

דרכים להוכיח שפסוק $plot:\[\alpha \]$ הוא טאוטולוגיה:

טבלת אמת: עוברים על כל ההשמות האפשריות עבור האטומים בפסוק ורואים שעבור כל אחת מהן הוא מקבל 1.
מחפשים מה ההשמה צריכה לקיים על מנת שלא תספק את $plot:\[\alpha \]$ ומוכיחים שלא קיימת השמה כזו.

הגדרה: נאמר ש- $plot:\[\alpha \]$ גורר לוגית את $plot:\[\beta \]$ ונסמן $plot:\[\alpha \vDash \beta \]$ אם כל השמה שמספקת את $plot:\[\alpha \]$ מספקת את $plot:\[\beta \]$ .

דוגמא: $plot:\[\left( {{p_0} \wedge {p_1}} \right) \vDash {p_0}\]$ .

טענה: $plot:\[\alpha \vDash \beta \]$ אמ"מ $plot:\[\alpha \to \beta \]$ היא טאוטולוגיה.

אבחנות:

אם $plot:\[\alpha \]$ טאוטולוגיה - $plot:\[\alpha \vDash \beta \]$ אזי $plot:\[\beta \]$ טאוטולוגיה.
אם $plot:\[\beta \]$ סתירה ו- $plot:\[\alpha \vDash \beta \]$ אזי $plot:\[\alpha \]$ סתירה.
אם $plot:\[\alpha \]$ סתירה, אזי לכל $plot:\[\beta \]$ מתקיים $plot:\[\alpha \vDash \beta \]$ .