ברוכים הבאים לשיעור עזר ביחידה "לוגיקה מתמטית ושיטות הוכחה" בקורס "מתמטיקה דיסקרטית ח' (2023)" בטכניון. יחידה זו מהווה את אבן היסוד להבנה ויישום של חשיבה פורמלית ורכישת הכלים ההכרחיים לבניית הוכחות מתמטיות קפדניות, שהן ליבת המתמטיקה הדיסקרטית ומדעי המחשב. נתמקד במושגי יסוד, לוגיקה פסוקית ולוגיקת פרדיקטים, ובטכניקות ההוכחה העיקריות הנדרשות בקורס ובבחינה.
לוגיקה פסוקית: היסודות
לוגיקה פסוקית עוסקת בצירוף של פסוקים באמצעות קשרים לוגיים ליצירת פסוקים מורכבים יותר, ובקביעת ערך האמת שלהם.
קשרים לוגיים מרכזיים
קוניונקציה (וגם - AND)
מסומנת ב-∧. P ∧ Q נכון רק אם גם P נכון וגם Q נכון.
דיסיונקציה (או - OR)
מסומנת ב-∨. P ∨ Q נכון אם P נכון, או Q נכון, או שניהם נכונים (כוללני).
גרירה (אם-אז - IMPLIES)
מסומנת ב-→. P → Q שגוי רק כאשר P נכון ו-Q שגוי. בכל שאר המקרים הוא נכון.
שקילות (אם ורק אם - IFF)
מסומנת ב-↔. P ↔ Q נכון כאשר ל-P ול-Q יש אותו ערך אמת (שניהם נכונים או שניהם שגויים).
לוגיקה של פרדיקטים וכמתים
לוגיקה של פרדיקטים מאפשרת לנו לבטא טענות על אובייקטים ועל יחסים ביניהם, באמצעות משתנים, פרדיקטים וכמתים.
שלילת פסוקים עם כמתים
שלילת פסוקים עם כמתים היא מיומנות קריטית, במיוחד בהוכחות בדרך השלילה. כלל דה-מורגן לכמתים קובע:
- ¬(∀x P(x)) ≡ ∃x ¬P(x)
- ¬(∃x P(x)) ≡ ∀x ¬P(x)
שיטות הוכחה פורמליות
הוכחה מתמטית היא טיעון לוגי המבסס את נכונותה של טענה מסוימת (מסקנה) על בסיס הנחות יסוד או טענות שכבר הוכחו.
הוכחה ישירה (Direct Proof)
מניחים שההנחות נכונות ומסיקים את המסקנה בצעדים לוגיים ברורים. עבור P → Q, מניחים P ומוכיחים Q.
הוכחה בדרך השלילה (Proof by Contrapositive)
עבור P → Q, מוכיחים את השקילות הלוגית ¬Q → ¬P. מניחים ש-Q שגוי ומוכיחים ש-P שגוי.
הוכחה בדרך הסתירה (Proof by Contradiction)
כדי להוכיח טענה P, מניחים בשלילה ש-P שגויה (כלומר ¬P נכון), ומראים שהנחה זו מובילה לסתירה לוגית (למשל, Q ∧ ¬Q). מכאן נובע שההנחה הראשונית (¬P) שגויה, ולכן P חייבת להיות נכונה.
דגשים וטעויות נפוצות בבחינה
בחינות בטכניון מדגישות הבנה עמוקה ויישום מדויק של העקרונות. שימו לב לנקודות הבאות:
- תרגום משפה טבעית ללוגיקה פורמלית: תרגום מדויק של משפטים מורכבים לשפת הלוגיקה (פסוקית ופרדיקטים) הוא מיומנות נבחנת תדיר. שימו לב למילים כמו "רק אם", "אלא אם כן", "מספיק", "הכרחי".
- שקילויות לוגיות: ידע ויישום של חוקי הלוגיקה (דה-מורגן, דיסטריבוטיביות, אסוציאטיביות וכו') להוכחת שקילויות או פישוט ביטויים.
- שלילת פסוקים מורכבים: במיוחד אלו המכילים כמתים וקשרים לוגיים רבים. טעות נפוצה היא לשכוח לשנות את סוג הכמת או לשלול את הפרדיקט עצמו.
- מבנה ההוכחה: הקפידו על מבנה ברור, צעדים לוגיים מנומקים, והצהרה ברורה של ההנחות והמסקנות.
- תחום הדיון של הכמתים: ודאו שאתם מבינים על איזה קבוצת אובייקטים הכמתים חלים.
שאלות לדיון
- תרגמו את המשפט הבא לשפת לוגיקת הפרדיקטים: "כל סטודנט שלומד מתמטיקה דיסקרטית ומצליח בבחינה, יקבל ציון עובר, אלא אם כן הוא לא הגיש את כל התרגילים."
- הוכיחו באמצעות טבלת אמת או באמצעות שקילויות לוגיות כי הפסוק ((P → Q) ∧ P) → Q הוא טאוטולוגיה.
- הסבירו מתי עדיף להשתמש בהוכחה בדרך השלילה ומתי בהוכחה בדרך הסתירה. תנו דוגמה לכל אחת.
- שללו את הפסוק הבא: ∀x ∃y (P(x,y) ∧ ¬Q(y)).
נקודות לתשובת מודל
- לתרגום: הגדרת פרדיקטים ברורים (לדוגמה: S(x): "x הוא סטודנט", D(x): "x לומד מתמטיקה דיסקרטית", E(x): "x מצליח בבחינה", P(x): "x מקבל ציון עובר", H(x): "x הגיש את כל התרגילים"). שימוש נכון בקשרים לוגיים ובכמתים.
- להוכחת טאוטולוגיה: הצגה מסודרת של טבלת אמת עם כל האפשרויות, או שימוש שיטתי בחוקי שקילות לוגית (לדוגמה: P → Q ≡ ¬P ∨ Q).
- להסבר על שיטות הוכחה: הוכחה בדרך השלילה מתאימה כאשר המסקנה היא שלילה, או כאשר קל יותר לשלול את המסקנה ולהוכיח את שלילת ההנחה. הוכחה בדרך הסתירה מתאימה כאשר הנחת השלילה של הטענה מובילה לסתירה ברורה עם עובדה ידועה או עם הנחה אחרת. דוגמאות קלאסיות: הוכחת אי-רציונליות של שורש 2 (סתירה), הוכחת "אם n^2 זוגי אז n זוגי" (שלילה).
- לשלילת פסוק: יישום כללי דה-מורגן לכמתים ולוגיקה פסוקית באופן מדויק: ∃x ∀y (¬P(x,y) ∨ Q(y)).