מתמטיקה בדידה: תורת הקבוצות, קומבינטוריקה ותורת הגרפים

ברוכים הבאים ליחידה המבוא ללוגיקה ותורת ההוכחה! יחידה זו היא אבן יסוד בחשיבה המתמטית ובמדעי המחשב. היא מקנה את הכלים להבנה, ניתוח ובנייה של טיעונים לוגיים והוכחות פורמליות – מיומנויות חיוניות בכל תחומי המתמטיקה הדיסקרטית ומעבר לה. נתמקד ביסודות הלוגיקה הפסוקית והפרדיקטית ובטכניקות ההוכחה המרכזיות, תוך שימת דגש על דיוק ופורמליות הנדרשים באקדמיה.

יסודות הלוגיקה הפסוקית

הלוגיקה הפסוקית עוסקת במשפטים שניתן לקבוע לגביהם באופן חד-משמעי אם הם אמת או שקר. היא הבסיס לכל חשיבה לוגית פורמלית.

פסוק (Proposition): משפט הצהרתי שניתן לייחס לו ערך אמת יחיד: אמת (True) או שקר (False). לדוגמה: "השמש זורחת במזרח" (אמת), "2+2=5" (שקר).

קשרים לוגיים (Logical Connectives): אופרטורים המאפשרים לבנות פסוקים מורכבים מפסוקים פשוטים יותר.

טבלת אמת (Truth Table): טבלה המציגה את ערך האמת של פסוק מורכב עבור כל שילוב אפשרי של ערכי האמת של הפסוקים המרכיבים אותו.

טאוטולוגיה (Tautology): פסוק שמקבל ערך אמת "אמת" בכל שילוב אפשרי של ערכי האמת של הפסוקים המרכיבים אותו.

סתירה (Contradiction): פסוק שמקבל ערך אמת "שקר" בכל שילוב אפשרי של ערכי האמת של הפסוקים המרכיבים אותו.

קשרים לוגיים עיקריים

וגם (AND, $\land$)

הפסוק "P וגם Q" אמיתי רק כאשר גם P אמיתי וגם Q אמיתי. אחרת, הוא שקרי.

או (OR, $\lor$)

הפסוק "P או Q" אמיתי כאשר לפחות אחד מהפסוקים P או Q אמיתי (כולל שניהם). הוא שקרי רק כאשר גם P שקרי וגם Q שקרי.

גרירה (IMPLIES, $\to$)

הפסוק "אם P אז Q" (P גורר Q) שקרי רק כאשר P אמיתי ו-Q שקרי. בכל שאר המקרים הוא אמיתי. שימו לב: P שקרי גורר תמיד אמת!

אם ורק אם (IFF, $\leftrightarrow$)

הפסוק "P אם ורק אם Q" אמיתי כאשר ל-P ול-Q יש אותו ערך אמת (שניהם אמת או שניהם שקר). אחרת, הוא שקרי.

לוגיקה של פרדיקטים וכימות

הלוגיקה הפסוקית מוגבלת ביכולתה לבטא טענות על אובייקטים ותכונותיהם. לשם כך אנו זקוקים ללוגיקה של פרדיקטים, המאפשרת לנו לדבר על "לכל" ו"קיים".

פרדיקט (Predicate): תכונה או יחס המכיל משתנים, והופך לפסוק כאשר מציבים בו ערכים ספציפיים למשתנים. לדוגמה: $P(x)$: "$x$ הוא מספר זוגי". $P(4)$ הוא אמת, $P(3)$ הוא שקר.

כמת אוניברסלי (Universal Quantifier, $\forall$): "לכל", "כל". מסמל שטענה מסוימת נכונה לכל האיברים בקבוצה נתונה. לדוגמה: $\forall x \in \mathbb{N}, x \ge 0$.

כמת קיומי (Existential Quantifier, $\exists$): "קיים", "יש". מסמל שקיימים לפחות איבר אחד בקבוצה נתונה שעבורו הטענה נכונה. לדוגמה: $\exists x \in \mathbb{Z}, x^2 = 4$.

שלילת פסוקים מכומתים: זוהי נקודה קריטית ובחינתית! שגיאות נפוצות מתרחשות בשלילת פסוקים המכילים כמתים. זכרו:

שלילת "לכל" הופכת ל"קיים ולא": $\neg (\forall x, P(x)) \equiv \exists x, \neg P(x)$
שלילת "קיים" הופכת ל"לכל ולא": $\neg (\exists x, P(x)) \equiv \forall x, \neg P(x)$

הבנה מדויקת של כללים אלו חיונית לבניית הוכחות בדרך השלילה ולניתוח טענות מורכבות.

שיטות הוכחה בסיסיות

הוכחה מתמטית היא סדרה של טיעונים לוגיים המבססים את אמיתותה של טענה. נכיר את שיטות ההוכחה היסודיות ביותר.

הוכחה ישירה (Direct Proof): מתחילה מההנחות הנתונות ומשתמשת בהגדרות, אקסיומות ומשפטים ידועים כדי להגיע למסקנה באופן ישיר ורציף.

הוכחה בדרך השלילה (Proof by Contradiction): מניחים שהטענה שרוצים להוכיח שקרית, ומראים שהנחה זו מובילה לסתירה לוגית (לדוגמה, סתירה להנחות המקוריות או לעובדה ידועה). מכיוון שההנחה שהטענה שקרית הובילה לסתירה, המסקנה היא שהטענה חייבת להיות אמיתית.

הוכחה בדרך ההיקש הנגדי (Proof by Contrapositive): משמשת להוכחת טענות מהצורה "אם P אז Q" ($P \to Q$). במקום להוכיח את הטענה ישירות, מוכיחים את הטענה השקולה לה לוגית: "אם לא Q אז לא P" ($\neg Q \to \neg P$).

מבנה של הוכחה פורמלית

כל הוכחה צריכה להיות ברורה, מנומקת וקלה למעקב. הקפידו על:

הצהרה ברורה: מה אתם מוכיחים? (משפט, טענה).
הנחות: מה נתון לכם?
שלבים לוגיים: כל שלב בהוכחה חייב לנבוע באופן לוגי מהשלבים הקודמים לו או מהנחות/הגדרות ידועות.
נימוק: ציינו את הסיבה לכל מעבר (הגדרה, משפט קודם, אקסיומה).
מסקנה: סיום ההוכחה בהצהרה שהטענה הוכחה.

שאלות לדיון

הסבירו מדוע הפסוק "אם 2+2=5 אז השמש זורחת במערב" הוא אמיתי מבחינה לוגית. האם זה סותר את האינטואיציה שלכם?
כיצד הייתם מוכיחים שהשורש הריבועי של 2 אינו מספר רציונלי, ואיזו שיטת הוכחה הייתם בוחרים? נמקו את בחירתכם.
תנו דוגמה לפסוק הכולל גם כמת אוניברסלי וגם כמת קיומי, וכתבו את שלילתו הפורמלית. הסבירו במילים את משמעות הפסוק המקורי ומשמעות שלילתו.
האם כל טאוטולוגיה היא טענה "מעניינת" מבחינה מתמטית? הסבירו.

נקודות לתשובת מודל

לגבי השאלה הראשונה: הפסוק הוא אמיתי מכיוון שהגרירה $P \to Q$ שקרית רק כאשר $P$ אמיתי ו-$Q$ שקרי. במקרה זה, $P$ ("2+2=5") הוא שקרי, ולכן הגרירה כולה אמיתית, ללא קשר לערך האמת של $Q$. זה מדגיש את ההגדרה הפורמלית של גרירה לעומת המשמעות האינטואיטיבית.
לגבי השאלה השנייה: הוכחה בדרך השלילה היא המתאימה ביותר. נניח בשלילה ש-$\sqrt{2}$ הוא מספר רציונלי, כלומר ניתן לכתוב אותו כשבר $a/b$ כאשר $a, b$ שלמים וזרים. נגיע לסתירה (לדוגמה, שגם $a$ וגם $b$ חייבים להיות זוגיים, בסתירה לכך שהם זרים).
לגבי השאלה השלישית: דוגמה: $\forall x \in \mathbb{N}, \exists y \in \mathbb{N}, y > x$. (לכל מספר טבעי $x$, קיים מספר טבעי $y$ שגדול מ-$x$). שלילתו: $\neg (\forall x \in \mathbb{N}, \exists y \in \mathbb{N}, y > x) \equiv \exists x \in \mathbb{N}, \neg (\exists y \in \mathbb{N}, y > x) \equiv \exists x \in \mathbb{N}, \forall y \in \mathbb{N}, \neg (y > x) \equiv \exists x \in \mathbb{N}, \forall y \in \mathbb{N}, y \le x$. * משמעות המקור: אין מספר טבעי גדול ביותר. * משמעות השלילה: קיים מספר טבעי $x$ שהוא הגדול ביותר (כלומר, כל מספר טבעי אחר $y$ קטן או שווה לו).
לגבי השאלה הרביעית: לא בהכרח. טאוטולוגיה היא תמיד נכונה מבחינה לוגית, אך לעיתים קרובות היא אינה מוסיפה מידע חדש או תובנה עמוקה על העולם המתמטי. טאוטולוגיות כמו $P \lor \neg P$ הן בסיסיות אך אינן "מעניינות" כמו משפטים מורכבים יותר הדורשים הוכחה יצירתית. העניין המתמטי נובע לרוב מטענות שאינן טאוטולוגיות אך ניתנות להוכחה, ומגלות קשרים חדשים או תכונות לא טריוויאליות.

מצאתם טעות או שחסר משהו?