ברוכים הבאים ליחידה "לוגיקה מתמטית ויסודות ההוכחה" בקורס "אשנב למתמטיקה". יחידה זו היא אבן יסוד בהבנת השפה הפורמלית של המתמטיקה ובפיתוח היכולת לבנות ולהבין הוכחות מתמטיות. נלמד כיצד לנסח טענות באופן מדויק, לנתח את נכונותן, ולהשתמש בשיטות הוכחה בסיסיות כדי להסיק מסקנות תקפות. שליטה בחומר זה חיונית להצלחה בכל קורס מתמטיקה עתידי.
השפה הפורמלית: פסוקים וקשרים לוגיים
המתמטיקה, כשפה, דורשת דיוק מוחלט. פסוקים לוגיים וקשרים ביניהם הם אבני הבניין הבסיסיות של כל טענה מתמטית.
לדוגמה: "2+2=4" הוא פסוק אמת. "השמש כחולה" הוא פסוק שקר. "מה השעה?" אינו פסוק לוגי.
קשרים לוגיים בסיסיים
באמצעות קשרים לוגיים, אנו יכולים לבנות פסוקים מורכבים מפסוקים פשוטים יותר.
קשר "וגם" (AND, ∧)
הפסוק "P וגם Q" נכון אם ורק אם גם P נכון וגם Q נכון. אחרת, הוא שקר.
קשר "או" (OR, ∨)
הפסוק "P או Q" נכון אם ורק אם לפחות אחד מהם (P או Q או שניהם) נכון. הוא שקר רק אם גם P שקר וגם Q שקר.
קשר "לא" (NOT, ¬)
הפסוק "לא P" נכון אם ורק אם P שקר. אם P נכון, אז "לא P" שקר.
קשר "גרירה" (IMPLIES, →)
הפסוק "אם P אז Q" (או "P גורר Q") שקר רק במקרה ש-P נכון ו-Q שקר. בכל שאר המקרים הוא נכון. P נקרא הרישא ו-Q נקרא הסיפא.
קשר "אם ורק אם" (IFF, ↔)
הפסוק "P אם ורק אם Q" נכון אם ורק אם ל-P ול-Q יש את אותו ערך אמת (שניהם נכונים או שניהם שקרים).
קוונטורים: הכמתים של המתמטיקה
קוונטורים מאפשרים לנו לנסח טענות לגבי קבוצות של איברים, ולא רק לגבי איבר בודד.
סוגי קוונטורים
- כמת לכל (∀ - "לכל", "עבור כל"): מציין שטענה מסוימת מתקיימת עבור כל איבר בקבוצה נתונה.
דוגמה: ∀x ∈ ℝ, x² ≥ 0 (לכל מספר ממשי x, ריבועו אי-שלילי).
- כמת קיים (∃ - "קיים", "ישנו לפחות אחד"): מציין שקיים לפחות איבר אחד בקבוצה נתונה שעבורו טענה מסוימת מתקיימת.
דוגמה: ∃x ∈ ℕ, x+1 = 5 (קיים מספר טבעי x כך ש-x+1=5).
שלילת פסוקים עם קוונטורים היא נקודה חשובה: שלילת "לכל" הופכת ל"קיים" עם שלילת הטענה הפנימית, ושלילת "קיים" הופכת ל"לכל" עם שלילת הטענה הפנימית. לדוגמה: ¬(∀x, P(x)) שקול ל-∃x, ¬P(x).
טבלאות אמת וטאוטולוגיות: כלי לאימות טענות
טבלאות אמת הן כלי שיטתי לבדיקת ערכי האמת של פסוקים מורכבים תחת כל צירופי האמת האפשריים של הפסוקים הפשוטים המרכיבים אותם.
שיטות הוכחה בסיסיות
הוכחה מתמטית היא טיעון לוגי המבסס את נכונותה של טענה מסוימת על סמך אקסיומות, הגדרות ומשפטים שכבר הוכחו. נתמקד בשתי שיטות הוכחה מרכזיות.
הוכחה ישירה
בהוכחה ישירה, אנו מניחים שהרישא (ההנחה) של המשפט "אם P אז Q" נכון, ומתוך הנחה זו, באמצעות סדרת צעדים לוגיים תקפים, אנו מסיקים שהסיפא (המסקנה) Q חייב להיות נכון. זוהי השיטה הישירה והפשוטה ביותר.
הוכחה בדרך השלילה (הוכחה עקיפה)
בהוכחה בדרך השלילה, כדי להוכיח שטענה P נכונה, אנו מניחים בשלילה שהטענה P אינה נכונה (כלומר, ¬P נכון). מתוך הנחה זו, אנו מגיעים לסתירה לוגית (למשל, סתירה לאקסיומה, להגדרה, או לטענה שכבר הוכחה). מכיוון שההנחה שהטענה אינה נכונה הובילה לסתירה, אנו מסיקים שההנחה שגויה, ולכן הטענה המקורית P חייבת להיות נכונה.
דוגמאות קצרות:
- הוכחה ישירה: הוכח שאם n מספר זוגי, אז n² מספר זוגי.
הוכחה: נניח ש-n מספר זוגי. לכן, קיים שלם k כך ש-n=2k. אז n² = (2k)² = 4k² = 2(2k²). מכיוון ש-2k² הוא מספר שלם, n² הוא כפולה של 2, ולכן n² הוא מספר זוגי. מ.ש.ל.
- הוכחה בדרך השלילה: הוכח ששורש 2 אינו מספר רציונלי.
הוכחה: נניח בשלילה ששורש 2 הוא מספר רציונלי. לכן, ניתן לכתוב אותו כשבר p/q כאשר p ו-q שלמים, q≠0, והשבר מצומצם (אין להם גורם משותף גדול מ-1). מכאן נובע ש-2 = p²/q², כלומר 2q² = p². מכאן ש-p² הוא מספר זוגי, ולכן גם p חייב להיות זוגי. נכתוב p=2k עבור שלם כלשהו k. נציב: 2q² = (2k)² = 4k². נחלק ב-2 ונקבל q² = 2k². מכאן ש-q² הוא מספר זוגי, ולכן גם q חייב להיות זוגי. קיבלנו שגם p וגם q זוגיים, כלומר שניהם מתחלקים ב-2. זו סתירה להנחה ש-p/q הוא שבר מצומצם. לכן, ההנחה ששורש 2 רציונלי שגויה, ומכאן ששורש 2 אינו מספר רציונלי. מ.ש.ל.
שאלות לדיון
- הסבירו את ההבדל המהותי בין פסוק לוגי לבין משפט שאינו פסוק לוגי. תנו שתי דוגמאות לכל אחד.
- כיצד משפיעה שלילת קוונטור "לכל" על מבנה הפסוק? תנו דוגמה מתמטית.
- הסבירו מדוע טאוטולוגיות חשובות כל כך בתחום ההוכחות המתמטיות. תנו דוגמה לטאוטולוגיה וכיצד ניתן להשתמש בה.
- השוו בין הוכחה ישירה להוכחה בדרך השלילה. מתי עדיף להשתמש בכל אחת מהשיטות?
נקודות לתשובת מודל
- פסוק לוגי: טענה עם ערך אמת חד-משמעי (אמת/שקר). דוגמאות: "3>10" (שקר), "כל הריבועים הם מלבנים" (אמת). לא פסוק: "סגור את הדלת", "האם יורד גשם?".
- שלילת קוונטור "לכל": שלילת ∀x, P(x) היא ∃x, ¬P(x). כלומר, אם לא נכון שלכל x מתקיים P(x), אז קיים לפחות x אחד שעבורו P(x) אינו מתקיים. דוגמה: ¬(∀x ∈ ℝ, x² ≥ 0) שקול ל-∃x ∈ ℝ, x² < 0.
- חשיבות טאוטולוגיות: הן עקרונות לוגיים נכונים תמיד, המשמשים ככללי היסק תקפים. הן מאפשרות לנו לבצע מעברים לוגיים בטוחים בהוכחות. דוגמה: חוק אי-הסתירה (P ∧ ¬P)¬ היא טאוטולוגיה, המהווה בסיס להוכחה בדרך השלילה.
- השוואת שיטות הוכחה:
- ישירה: מניחים P נכון, מסיקים Q נכון. פשוטה וישירה, עדיפה כשהקשר בין P ל-Q ברור.
- בדרך השלילה: מניחים ¬P נכון, מגיעים לסתירה. שימושית במיוחד כאשר קשה להוכיח ישירות, או כאשר הטענה כוללת שלילה ("אינו", "לא קיים"). למשל, הוכחת אי-רציונליות או אי-קיום.