2. מעט היסטוריה
מקור המילה logic — יוונית: λογική (logikē).
- אריסטו (350 לפנה"ס) — התחיל את הלוגיקה הפורמלית. דוגמה הסילוגיזם המפורסם: "כל האנשים בני-תמותה. סוקרטס הוא איש. \(\Rightarrow\) סוקרטס בן-תמותה."
- ג'ורג בּוּל (George Boole, 1854) — "An Investigation of the Laws of Thought" — הציג את הלוגיקה הסימבולית ואת עקרונות הלוגיקה הפסוקית (הבולאנית). למשל \(P \vee \neg P\) (חוק השלישי הנמנע).
- גוטלוב פרגה (Gottlob Frege, 1879) — "Begriffsschrift" — הציג את הכמתים והבסיס ללוגיקה מסדר ראשון. למשל \(\forall x \exists y\, (y > x)\).
4. יחס הנביעה: ⊨ (סמנטית) מול ⊢ (סינטקטית)
יחס בינארי בין קבוצת נוסחאות \(S\) (assumptions — הנחות) ונוסחה \(\alpha\) (claim — טענה).
שני סימונים
\(S \models \alpha\) — נביעה סמנטית (semantic consequence).
\(S \vdash \alpha\) — נביעה סינטקטית (syntactic consequence).
דוגמאות
\(\{\alpha,\; \alpha \to \beta\} \models \beta\) ✓
\(\{\alpha,\; \alpha \to \beta\} \not\models \gamma\) (אין מספיק מידע על \(\gamma\)).
שלוש תכונות יחס נביעה
- "רפלקסיביות": לכל נוסחה \(\alpha \in S\) מתקיים \(S \models \alpha\).
- מונוטוניות: אם \(S \models \alpha\) ו-\(S \subseteq S'\) אז \(S' \models \alpha\).
- "טרנזיטיביות": אם \(S \models \alpha\) ו-\(S \cup \{\alpha\} \models \beta\) אז \(S \models \beta\).
הוכחה סינטקטית — דוגמה
בהינתן \(S = \{\gamma,\; \gamma \to \beta,\; \beta \to \alpha\}\):
γ, γ → β ⟹ β (כלל היסק modus ponens)
β, β → α ⟹ α (כלל היסק)
⟹ S ⊢ α
5. לוגיקה פסוקית — תחביר
השפה מורכבת מהסימנים הבאים:
- קבועים: \(\text{True},\;\text{False}\) — אטומים.
- משתנים (variables): \(p_0, p_1, p_2, \ldots\) — אטומים. לעיתים נקבל "כינויים" כמו \(A, B, C, D\).
- קשרים בוליאניים (Boolean connectives): \(\neg,\;\wedge,\;\vee,\;\to\) (ולפעמים \(\leftrightarrow\)).
- סוגריים: \(( \;\;\;)\).
היקף השפה
יש \(\aleph_0\) משתנים ובסך הכל \(\aleph_0\) נוסחאות בשפה.
כל נוסחה היא באורך סופי (b-"אורך" = מספר תווים, כאשר קבוע \(T/F\) ומשתנה \(p_i\) נספרים כתו יחיד).
6. נוסחה בנויה כהלכה — Well-Formed Formula (wff)
בתחשיב הפסוקים, נוסחה (formula) נקראת גם פסוק (proposition).
הגדרה אינדוקטיבית
קבוצת הנוסחאות הבנויות כהלכה (wff) מוגדרת באופן הבא:
- פסוקים אטומיים (Atomic propositions) — wff:
- \(\text{True},\;\text{False}\)
- כל משתנה \(p_i\)
- אם \(\alpha,\beta\) הינן wff, אז כך גם:
\((\neg\alpha),\;(\alpha \vee \beta),\;(\alpha \wedge \beta),\;(\alpha \to \beta)\).
דוגמאות לנוסחאות בנויות כהלכה
\(P \vee \neg P\)
\(\forall x \exists y\,(y > x)\) (לוגיקה מסדר ראשון).
דוגמאות לנוסחאות שאינן בנויות כהלכה
khjgrkl⟩jhfg)wre4gt
\(P \vee \vee \to \neg P\)
7. כתיב מקוצר וסדר קדימויות
בכתיב מלא — לכל פסוק יש "המון" סוגריים. נשתמש לעיתים בכתיב מקוצר, כדי להקל את הקריאה:
- נשמיט את הסוגריים החיצוניים ביותר.
- סדר קדימויות בין הקשרים (משמאל לימין): \(\neg,\;\wedge,\;\vee,\;\to\).
- מופעים שונים של אותו הקשר יבוצעו משמאל לימין.
דוגמאות
| כתיב מקוצר | כתיב מלא |
|---|
| \(\neg A \wedge B \vee \neg C \to D\) | \(((((\neg A) \wedge B) \vee (\neg C)) \to D)\) |
| \(A \to B \to C\) | \(((A \to B) \to C)\) |
| \((F \to F) \to F\) | שונה מ-\(F \to (F \to F)\)! |
הערה פורמלית
באופן פורמלי, נוסחה הבנויה כהלכה הינה בכתיב מלא. נוסחה בכתיב מקוצר
מייצגת את הנוסחה הבנויה כהלכה בכתיב מלא.
8. עץ הגזירה / בנייה (Parsing Tree)
המבנה של נוסחה מהווה עץ. זהו עץ הבנייה / עץ הגזירה של הנוסחה.
- השורש = הקשר החיצוני ביותר (הראשי).
- העלים = פסוקים אטומיים (משתנים / \(T\) / \(F\)).
דוגמה: \(\alpha = (((\neg A) \wedge (B \vee C)) \vee (\neg C)) \to D\)
→
/ \
∨ D
/ \
∧ ¬
/ \ \
¬ ∨ C
| / \
A B C
אלגוריתם בנייה
- אם \(\alpha\) אטום, בנה צומת יחיד ובו \(\alpha\).
- אחרת:
- הסר את הסוגריים החיצוניים.
- אם הסימן הראשון הוא \(\neg\), זהו הקשר המרכזי, בן יחיד = הסיפא.
- אחרת, סרוק משמאל לימין; בכל צעד בדוק אם מספר \( ( \) שווה למספר \( ) \). אם כן (כולל 0) — הקשר במיקום זה הוא הקשר המרכזי. הילדים: הביטוי משמאלו והביטוי מימינו (רקורסיבית).
10. משפט הקריאה היחידה (Unique Readability)
משפט
אם \(\alpha\) נוסחה בנויה כהלכה (wff), אזי
בדיוק אחד מהמקרים הללו מתקיים:
- \(\alpha = \text{True}\)
- \(\alpha = \text{False}\)
- \(\alpha = p_i\) עבור משתנה \(p_i\)
- \(\alpha = (\neg\beta)\) עבור \(\beta\) שהיא wff.
- \(\alpha = (\beta_1 \wedge \beta_2)\) עבור \(\beta_1, \beta_2\) wff.
- \(\alpha = (\beta_1 \vee \beta_2)\) עבור \(\beta_1, \beta_2\) wff.
- \(\alpha = (\beta_1 \to \beta_2)\) עבור \(\beta_1, \beta_2\) wff.
בכל המקרים, \(p_i, \beta, \beta_1, \beta_2\)
נקבעים באופן יחיד.
משמעות "α = (β₁ ∧ β₂)"
הכוונה היא ש-\(\alpha\) הינה
תחבירית מהצורה (of the form) \((\beta_1 \wedge \beta_2)\), ולא רק
שקולה לכך באיזשהו מובן. זה ה-Syntactic structure של הנוסחה.
11. אינדוקציה מבנית (Structural Induction)
ניתן להוכיח שתכונה \(H\) נכונה לכל הנוסחאות באינדוקציה על מבנה הנוסחה (By induction on the structure of the formula).
שלד של הוכחה באינדוקציה מבנית
תהי \(\gamma\) נוסחה כלשהי.
מקרי הבסיס
- אם \(\gamma\) הקבוע \(\text{True}\) אזי \(H\) מתקיימת, שכן ...
- אם \(\gamma\) הקבוע \(\text{False}\) אזי \(H\) מתקיימת, שכן ...
- אם \(\gamma\) המשתנה \(p_i\) אזי \(H\) מתקיימת, שכן ...
שלבי המעבר
הנחה: \(H\) מתקיימת לכל תתי-הנוסחאות-ממש של \(\gamma\). אזי:
- אם \(\gamma = (\neg\beta)\) אזי \(H\) מתקיימת עבורה, שכן ...
- אם \(\gamma = (\alpha \wedge \beta)\) אזי \(H\) מתקיימת עבורה, שכן ...
- אם \(\gamma = (\alpha \vee \beta)\) אזי \(H\) מתקיימת עבורה, שכן ...
- אם \(\gamma = (\alpha \to \beta)\) אזי \(H\) מתקיימת עבורה, שכן ...
12. דוגמה: לכל נוסחה באורך \(n\) יש \(\le n\) תתי-נוסחאות
משפט
לכל נוסחה באורך \(n\) יש לכל היותר \(n\) תתי-נוסחאות.
הוכחה. באינדוקציה מבנית. תהי γ נוסחה כלשהי.
מקרי הבסיס:
אם γ קבוע T/F או משתנה pᵢ — אורך 1, יש לה תת-נוסחה אחת (γ עצמה).
1 ≤ 1. ✓
מקרה (¬β):
יהי m האורך של β ו-u מס' תתי-הנוסחאות של β.
לפי הנחת האינדוקציה, u ≤ m.
ל-γ יש תת-נוסחה אחת יותר מאשר ל-β (היא עצמה), ואורכה גדול ב-3 (סוגריים + ¬), כלומר m+3.
לכן: u+1 ≤ m+1 ≤ m+3. ✓
מקרה (α∧β) / (α∨β) / (α→β):
יהיו m₁, m₂ אורכי α ו-β, ו-u₁, u₂ מס' תתי-הנוסחאות שלהן.
לפי הנחת האינדוקציה, u₁ ≤ m₁ ו-u₂ ≤ m₂.
ל-γ יש עד u₁+u₂+1 תתי-נוסחאות, ואורכה m₁+m₂+3.
לכן: u₁+u₂+1 ≤ m₁+m₂+1 ≤ m₁+m₂+3. ✓
∎
13. לוגיקה פסוקית — סמנטיקה
השמה (Assignment / Valuation)
השמה היא מתן ערך-אמת (truth value) של \(\text{True/False}\) לכל המשתנים.
פורמלית: \(v: \{p_0, p_1, p_2, \ldots\} \to \{T, F\}\).
ערך-האמת של פסוק עבור השמה מסוימת נקבע
רקורסיבית ע"י
טבלאות האמת של הקשרים.
טבלאות האמת של הקשרים
| \(\alpha\) | \(\beta\) | \(\neg\alpha\) | \(\alpha\vee\beta\) | \(\alpha\wedge\beta\) | \(\alpha\to\beta\) |
|---|
| F | F | T | F | F | T |
| F | T | T | T | F | T |
| T | F | F | T | F | F |
| T | T | F | T | T | T |
שתי השמות מיוחדות: \(v_T\) נותנת \(T\) לכל אטום; \(v_F\) נותנת \(F\) לכל אטום.
דוגמה לחישוב
\(\alpha = p \to (q \wedge r)\). השמה: \(v(p)=T,\;v(q)=T,\;v(r)=F\).
\(v(q \wedge r) = T \wedge F = F\). \(v(\alpha) = T \to F = F\). לכן \(v(\alpha)=F\).
14. סיפוק, ספיק, טאוטולוגיה וסתירה
סיפוק (Satisfaction)
ההשמה \(v\)
מספקת (satisfies) את \(\alpha\) אם \(v(\alpha) = T\). סימון: \(v \models \alpha\).
\(v\) מספקת קבוצה \(S\) אם היא מספקת את
כל הנוסחאות ב-\(S\).
- ספיק (satisfiable): קיימת \(v\) כך ש-\(v(\alpha) = T\). דוגמאות: \(p,\; p \vee \neg p\).
- טאוטולוגיה (tautology): לכל \(v\), \(v(\alpha) = T\). דוגמאות: \(p \vee \neg p,\; p \to p\). כל טאוטולוגיה היא ספיקה.
- סתירה (contradiction): אין \(v\) כך ש-\(v(\alpha)=T\) (כלומר לכל \(v\), \(v(\alpha)=F\)). דוגמה: \(p \wedge \neg p\). כל סתירה אינה ספיקה.
15. נביעה סמנטית (Semantic Consequence)
הגדרה
יהי \(\alpha\) פסוק ו-\(S\) קבוצה (סופית או אינסופית) של פסוקים. \(\alpha\) נובע סמנטית מ-\(S\), בסימון \(S \models \alpha\), אם"מ
כל השמה המספקת את \(S\) מספקת גם את \(\alpha\):
\[ S \models \alpha \;\Longleftrightarrow\; \forall v.\; \bigl(\forall x \in S,\; v(x) = T\bigr) \Rightarrow v(\alpha) = T. \]
שתי משמעויות של ⊨
לסימן \(\models\) שני שימושים:
• \(S \models \alpha\) — \(\alpha\) נובע סמנטית מ-\(S\) (קבוצת פסוקים, פסוק).
• \(v \models \alpha\) — \(v\) מספקת את \(\alpha\) (השמה, פסוק; כלומר \(v(\alpha) = T\)).
דוגמה לבדיקה ידנית של נביעה
\(\beta = A \vee \neg B,\;\gamma = B \to C,\;\alpha = A \vee B \vee C\). האם \(\{\beta,\gamma\} \models \alpha\)?
בונים טבלת אמת על \(A, B, C\) (8 השמות), מסמנים את השורות שבהן
גם \(v(\beta)=T\)
וגם \(v(\gamma)=T\), ובכל אחת מהן בודקים אם \(v(\alpha)=T\). אם בכולן כן — נביעה מתקיימת. אם יש שורה אחת שבה לא — נביעה מופרכת.
איך מפריכים נביעה?
הדרך היחידה להפריך נביעה לוגית היא
דוגמה להשמה שמספקת את \(S\) אך לא את \(\alpha\).
הערה: אם אין השמה שמספקת את \(S\) — הנביעה מתקיימת באופן ריקני (
vacuously) לכל \(\alpha\).
16. תכונות יחס הנביעה הסמנטית
נביעה סמנטית מקיימת את שלוש התכונות הנדרשות מיחס נביעה:
רפלקסיביות
לכל \(\alpha \in S\) מתקיים \(S \models \alpha\).
הוכחה: תהא \(\alpha \in S\) ו-\(v\) השמה כלשהי המספקת את \(S\). לפי הגדרת סיפוק קבוצה, \(v\) מספקת את כל הנוסחאות ב-\(S\), ובפרט את \(\alpha\). ∎
מונוטוניות
אם \(S \models \alpha\) ו-\(S \subseteq S'\) אז \(S' \models \alpha\).
הוכחה: תהא \(v\) המספקת את \(S'\). כיוון ש-\(S \subseteq S'\), \(v\) מספקת גם את \(S\). מכאן (לפי \(S \models \alpha\)), \(v\) מספקת גם את \(\alpha\). ∎
"טרנזיטיביות"
אם \(S \models \alpha\) ו-\(S \cup \{\alpha\} \models \beta\) אז \(S \models \beta\).
הוכחה: תהא \(v\) המספקת את \(S\). מ-\(S \models \alpha\): \(v(\alpha)=T\), ולכן \(v\) מספקת את \(S \cup \{\alpha\}\). מ-\(S \cup \{\alpha\} \models \beta\): \(v(\beta)=T\). ∎
17. משפט הדדוקציה הסמנטי
משפט הדדוקציה הסמנטית
לכל קבוצת פסוקים \(S\) ופסוקים \(\alpha, \beta\):
\[ S \models (\alpha \to \beta) \;\;\Longleftrightarrow\;\; S \cup \{\alpha\} \models \beta. \]
בפרט, לכל \(\alpha, \beta\):
\[ \{\alpha\} \models \beta \;\;\Longleftrightarrow\;\; \models (\alpha \to \beta) \quad\text{(כלומר \(\alpha\to\beta\) טאוטולוגיה).} \]
הוכחה.
(⟹) נתון S ⊨ (α→β). נוכיח S ∪ {α} ⊨ β.
תהא v המספקת את S ∪ {α}. נראה ש-v(β)=T.
v מספקת את S ∪ {α}, ובפרט את S. מכיוון ש-S ⊨ (α→β):
v(α→β) = T.
כעת v מספקת את α וגם את (α→β), ולפי טבלת האמת של →:
v(β) = T. ✓
(⟸) נתון S ∪ {α} ⊨ β. נוכיח S ⊨ (α→β).
תהא v המספקת את S. נראה ש-v(α→β)=T.
• אם v(α) = F: לפי טבלת האמת של → → v(α→β) = T. ✓
• אם v(α) = T: אזי v מספקת את S ∪ {α}, ומהנתון v(β) = T.
לפי טבלת האמת של → → v(α→β) = T. ✓
∎
למה זה חשוב?
ההבדל בין שני האגפים: \(S \models \beta\) מוגדרת עבור קבוצה \(S\) שעשויה לכלול
אינסוף פסוקים, בעוד שגרירה \(\alpha \to \beta\) מוגדרת עבור פסוק יחיד \(\alpha\) (הפסוק \(\alpha\) יכול לשלב מס' פסוקים, אך מס'
סופי). משפט הדדוקציה מאפשר "להעביר" הנחה אחת לצד הימני של ⊨.
18. סיכום ונקודות מפתח
- לוגיקה פורמלית = Syntax (תחביר) + Semantics (סמנטיקה) + Proof system (מערכת הוכחה).
- הצרנה = תרגום מטקסט טבעי לשפה הפורמלית. בחירה של לוגיקה — איזון בין כוח הביטוי ל-כוח ההיסק.
- \(\models\) = נביעה סמנטית; \(\vdash\) = נביעה סינטקטית. אידיאלית — שוות.
- wff מוגדרת אינדוקטיבית: \(T/F\), משתנה, \((\neg\alpha)\), \((\alpha \wedge \beta)\), \((\alpha \vee \beta)\), \((\alpha \to \beta)\). יש \(\aleph_0\) wff.
- כתיב מקוצר: סדר קדימויות \(\neg, \wedge, \vee, \to\); אסוציאטיביות שמאלית; השמטת סוגריים חיצוניים.
- משפט הקריאה היחידה: כל wff מתאימה לבדיוק מקרה אחד מהמקרים בהגדרה, ופירוקה יחיד.
- אינדוקציה מבנית: בסיס לאטומים (\(T/F/p_i\)); צעד לכל תת-נוסחה ממש.
- השמה \(v: \text{vars} \to \{T,F\}\) מתרחבת רקורסיבית ע"י טבלאות אמת.
- ספיק / טאוטולוגיה / סתירה: \(\exists v\) / \(\forall v\) / \(\not\exists v\) המספקת.
- \(S \models \alpha\) — כל השמה המספקת את \(S\) מספקת גם את \(\alpha\). הפרכה = השמה אחת מספקת את \(S\) אך לא את \(\alpha\).
- תכונות נביעה: רפלקסיביות, מונוטוניות, טרנזיטיביות.
- משפט הדדוקציה (סמנטי): \(S \cup \{\alpha\} \models \beta\) \(\iff\) \(S \models (\alpha\to\beta)\). מקרה פרטי: \(\{\alpha\} \models \beta \iff \alpha\to\beta\) טאוטולוגיה.
מבט קדימה
ראינו את התחביר והסמנטיקה של לוגיקה פסוקית. השלב הבא:
מערכת הוכחה (Proof system) — אקסיומות וכללי היסק שמוגדרים סינטקטית, ומשפטי
שלמות (\(\vdash \Leftrightarrow \models\)) שמוודאים שהמערכת "מסכימה" עם הסמנטיקה.