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

רקע מהיר

תחביר (Syntax)

• קבועים: \(T, F\); משתנים: \(p_0, p_1, p_2, \ldots\) (או \(A, B, C, \ldots\)).
• קשרים: \(\neg, \wedge, \vee, \to\).
• סוגריים: \(( \;\;\;)\).
• סדר קדימויות (משמאל לימין): \(\neg, \wedge, \vee, \to\).
• כל מילה (נוסחה) היא סדרה סופית של הסימנים — לכן \(\aleph_0\) נוסחאות בשפה.

סמנטיקה

הסמנטיקה היא החלק בלוגיקה שבו נקבעת המשמעות. מגדירה לכל פסוק את ערך האמת שלו ע"י ערכי האמת \(T/F\) לאטומים המרכיבים אותו וע"י טבלאות האמת של הקשרים.

תכונות יחס הנביעה

1. רפלקסיביות: \(\alpha \in S \Rightarrow S \models \alpha\).
2. מונוטוניות: \(S \models \alpha\) ו-\(S \subseteq S' \Rightarrow S' \models \alpha\).
3. טרנזיטיביות: \(S \models \alpha\) ו-\(S \cup \{\alpha\} \models \beta \Rightarrow S \models \beta\).

תרגיל 1: עצי גזירה

פתרון א

מסירים סוגריים חיצוניים: \(((\neg B) \vee C) \to A\). הקשר המרכזי = \(\to\) (כשמספר \(( = )\) מתאזן).

              →
             / \
            ∨   A
           / \
          ¬   C
          |
          B

פתרון ב

מסירים סוגריים חיצוניים: \(D \wedge (((\neg(A \vee B)) \to C) \vee (\neg B))\). הקשר המרכזי = \(\wedge\).

                ∧
              /   \
             D     ∨
                 /   \
                →     ¬
              /   \    |
             ¬     C   B
             |
             ∨
            / \
           A   B

תרגיל 2: \(\mathrm{rank}(\alpha)-1 \le\) מספר הקשרים

הוכחה. באינדוקציה מבנית. נסמן ב-a את מס' הקשרים ב-α.

בסיס: α אטום (T/F/pᵢ).
  rank(α) = 1, a = 0, ולכן rank(α) - 1 = 0 ≤ 0 = a. ✓

מקרה 1: α = ¬α₁ (הקשר הראשי ¬).
הנחת האינדוקציה: rank(α₁) - 1 ≤ a₁ (מס' הקשרים ב-α₁).
לכן:
  rank(α) - 1 = rank(¬α₁) - 1 = (rank(α₁) + 1) - 1
             = rank(α₁)
             ≤ a₁ + 1       (לפי הנחת האינדוקציה: rank(α₁) ≤ a₁ + 1)
             = a            (מס' קשרים ב-α = a₁ + 1, ה-¬ הוא קשר נוסף).
✓

מקרה 2: α = α₁ ◇ α₂  עם ◇ ∈ {∧, ∨, →}.
הנחת האינדוקציה: rank(α₁) - 1 ≤ a₁, rank(α₂) - 1 ≤ a₂.
לכן:
  rank(α) - 1 = max(rank(α₁), rank(α₂)) + 1 - 1
             = max(rank(α₁), rank(α₂))
             ≤ max(a₁ + 1, a₂ + 1)
             ≤ a₁ + a₂ + 1
             = a            (a = a₁ + a₂ + 1).
✓

∎

תרגיל 3: הצרנת טיעון ובדיקת נביעה ע"י טבלת אמת

שלב 1: מילון משתנים

• \(A\) — "היום יום נעים".
• \(B\) — "אצא לטיול".

שלב 2: הצרנה

• הנחה 1: "אם היום יום נעים אצא לטיול" → \(A \to B\).
• הנחה 2: "היום יום לא נעים" → \(\neg A\).
• מסקנה: "לא אצא לטיול" → \(\neg B\).

השאלה: האם \(\{A \to B,\; \neg A\} \models \neg B\)?

שלב 3: טבלת אמת

מסקנה

בשורה \(v_3\) ההנחות סופקו, אך המסקנה \(\neg B\) לא סופקה (כי \(B=T\)). זה משמש כ-דוגמה נגדית:

תרגיל 5: \(\alpha,\beta,\gamma\) ספיקות + \(\{\alpha\wedge\beta\}\models\gamma\) ⟹ \(\gamma\) ספיקה?

הטענה נכונה — באופן ריקני, שכן ההנחה כוללת "γ ספיקה" כבר! אבל בואו נבחן את הניסוח בלי ההנחה הזו, ונראה למה היא הכרחית.

דוגמה ש"מראה" את הפלא של נביעה ריקנית

ניקח: \(\alpha = p,\; \beta = \neg p,\; \gamma = q \wedge \neg q\).

• \(\alpha\) ספיק (\(v_T \models \alpha\)). ✓
• \(\beta\) ספיק (\(v_F \models \beta\)). ✓
• \(\alpha \wedge \beta = p \wedge \neg p\) — סתירה. אין השמה שמספקת אותה.
• לכן \(\{\alpha \wedge \beta\} \models \gamma\) — באופן ריקני (vacuously) — נכון לכל \(\gamma\).
• אבל \(\gamma = q \wedge \neg q\) — סתירה, לא ספיקה!

תרגיל 6: פיצול/חיבור הנחות בנביעה

סעיף א — הפרכה

ניקח \(\alpha = p,\; \beta = \neg p,\; \gamma = q\).

• \(\{p, \neg p\}\) סתירה → \(\{\alpha, \beta\} \models \gamma\) באופן ריקני. ✓
• \(\{p\} \not\models q\): \(v(p)=T, v(q)=F\) מספקת את \(p\) אך לא את \(q\).
• \(\{\neg p\} \not\models q\): \(v(p)=F, v(q)=F\) מספקת את \(\neg p\) אך לא את \(q\).

הטענה הופרכה.

סעיף ב — נכון, מונוטוניות

הוכחה. נניח ש-{α} ⊨ γ (המקרה השני {β} ⊨ γ סימטרי).
כיוון ש-{α} ⊆ {α, β}, לפי מונוטוניות יחס הנביעה:
   {α, β} ⊨ γ.
∎

הוכחה ישירה (בלי לצטט מונוטוניות):
תהא v המספקת את {α, β}, אז בפרט v מספקת את α.
מכיוון ש-{α} ⊨ γ ו-v מספקת את α, נובע v(γ)=T.
⟹ כל v המספקת את {α, β} מספקת את γ, כלומר {α, β} ⊨ γ.

תרגיל 7: נביעה דיסיונקטיבית ופיצול לפי \(\alpha/\neg\alpha\)

סעיף א — הפרכה

ניקח \(\alpha = q,\; \beta = p,\; \delta = \neg p\).

• \(\beta \vee \delta = p \vee \neg p\) טאוטולוגיה, לכן \(\{q\} \models p \vee \neg p\). ✓
• \(\{q\} \not\models p\): \(v(p)=F, v(q)=T\) מספקת את \(q\) ולא את \(p\).
• \(\{q\} \not\models \neg p\): \(v(p)=T, v(q)=T\) מספקת את \(q\) ולא את \(\neg p\).

הטענה הופרכה.

סעיף ב — נכון, פיצול למקרים

הוכחה. נסמן S = {γ₁, γ₂, ..., γₙ}.
נתון:  S ∪ {α} ⊨ β   ו-   S ∪ {¬α} ⊨ β.
צריך:   S ⊨ β.

תהא v השמה המספקת את S. נראה ש-v(β) = T.

נחלק למקרים:

• אם v(α) = T:
  v מספקת את S וגם את α, כלומר את S ∪ {α}.
  מכיוון ש-S ∪ {α} ⊨ β, נובע v(β) = T. ✓

• אם v(α) = F:
  אז v(¬α) = T. v מספקת את S וגם את ¬α, כלומר את S ∪ {¬α}.
  מכיוון ש-S ∪ {¬α} ⊨ β, נובע v(β) = T. ✓

בכל מקרה v(β) = T, ולכן  S ⊨ β.  ∎

סיכום ונקודות חשובות

כלי המפתח לבדיקת נביעה סמנטית

1. בנו טבלת אמת על כל המשתנים שמופיעים בהנחות ובמסקנה.
2. סמנו את השורות שבהן כל ההנחות סופקו (T).
3. בכל אחת מהשורות הללו: אם המסקנה T בכולן ⟹ נביעה מתקיימת. אם יש שורה שבה המסקנה F ⟹ הפרכה.

טכניקות הוכחה

• הוכחת נביעה: תהא \(v\) השמה כלשהי המספקת את \(S\); נראה \(v(\alpha)=T\). השתמשו בטבלאות אמת, מונוטוניות וטרנזיטיביות.
• הפרכת נביעה: מצאו השמה אחת \(v\) שמספקת את \(S\) אך לא את \(\alpha\). זה מספיק!
• Proof by cases: פיצול לפי \(v(\alpha)=T\) או \(v(\alpha)=F\) — כלי חזק (תרגיל 7ב).
• נביעה ריקנית: אם \(S\) סתירה, אז \(S \models \alpha\) לכל \(\alpha\). בדקו ספיקות של \(S\) לפני הסקה!

זכרו

• טאוטולוגיה: \(\forall v.\;v(\alpha)=T\) — דוגמה: \(p \vee \neg p\).
• סתירה: \(\forall v.\;v(\alpha)=F\) — דוגמה: \(p \wedge \neg p\).
• ספיק: \(\exists v.\;v(\alpha)=T\) — כל טאוטולוגיה ספיקה, אבל לא כל פסוק ספיק טאוטולוגיה.
• משפט הדדוקציה: \(\{\alpha\} \models \beta \iff \alpha \to \beta\) טאוטולוגיה — מאפשר להחליף בין נביעה לגרירה.