מתמטיקה בדידה
מתמטיקה בדידה היא המתמטיקה של דברים נפרדים שאפשר לספור: נכון או לא נכון, בתוך קבוצה או מחוצה לה, המסלול הזה או ההוא. זו המתמטיקה שמחשבים רצים עליה, והיא מתחילה בלוגיקה שאפשר להדליק ולכבות.
עודכן לאחרונה
מתמטיקה בדידה היא המתמטיקה של דברים נפרדים שאפשר לספור. טענה היא נכונה או לא נכונה, איבר נמצא בקבוצה או לא, ברשת יש קשר בין שתי נקודות או שאין. אין שום דבר באמצע, וזה מה שפירוש "בדיד", וזו בדיוק הדרך שבה מחשב רואה את העולם.
קורס ראשון מכסה שישה נושאים: לוגיקה, קבוצות, קומבינטוריקה, גרפים, תורת המספרים והוכחות. לוגיקה באה ראשונה, כי כל שאר הנושאים כתובים בה. בחרו קשר לוגי למטה והחליפו את p ו־q.
טבלת אמת עבור p ∧ q
| p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
החליפו את p ו־q, או לחצו על שורה. השורה המודגשת היא זו שהם בוחרים.
קראו את p כ"x נמצא ב־A" ואת q כ"x נמצא ב־B". האזורים הצבועים הם המקומות שבהם הטענה נכונה; הנקודה היא השורה הנוכחית.
p ∧ q
קוראים את זה כך p וגם q
עם הערכים האלה, p ∧ q נכון.
נכון רק כש־p ו־q נכונים שניהם.
בשפת קבוצות AND הוא חיתוך: x נמצא ב־A ∩ B בדיוק כש־x נמצא ב־A וגם x נמצא ב־B.
לוגיקה: טענות וקשרים
טענה היא משפט שהוא נכון או לא נכון, כמו "7 הוא מספר ראשוני" או "יורד גשם". לוגיקה בונה טענות גדולות יותר מטענות קטנות בעזרת כמה קשרים, וטבלת אמת מפרטת מה התוצאה עבור כל צירוף של קלטים.
| סימן | שם | איך אומרים | נכון כש |
|---|---|---|---|
| ∧ | AND, קוניונקציה | "p וגם q" | שתיהן נכונות |
| ∨ | OR, דיסיונקציה | "p או q" | לפחות אחת נכונה |
| ¬ | NOT, שלילה | "לא p" | p לא נכונה |
| ⊕ | XOR, או מוציא | "p או q, אבל לא שתיהן" | בדיוק אחת נכונה |
| → | IMPLIES, גרירה | "אם p, אז q" | בכל מקרה חוץ מ־p נכונה ו־q לא נכונה |
| ↔ | IFF, שקילות | "p אם ורק אם q" | ל־p ול־q יש אותו ערך |
שניים מהם מפתיעים אנשים. ה־OR הלוגי הוא כולל: "p או q" נכון כששתיהן נכונות, בניגוד ל"תה או קפה?" היומיומי. לגרסה המוציאה יש שם משלה, XOR.
השני הוא IMPLIES. p → q לא נכון רק בשורה אחת, כש־p נכונה ו־q לא נכונה. חשבו על זה כעל הבטחה: "אם ירד גשם, אביא מטרייה". ההבטחה מופרת רק אם יורד גשם ואין מטרייה. ביום יבש ההבטחה לא הופרה, לא משנה מה אתם נושאים, ולכן הטענה נחשבת נכונה.
טענות שקולות
שתי טענות הן שקולות כשטבלאות האמת שלהן זהות בכל שורה. ברכיב, בחרו OR ושללו את p: העמודה של ¬p ∨ q זהה לעמודה של p → q, ולכן שתיהן אומרות אותו דבר.
השקילויות השימושיות ביותר הן חוקי דה מורגן, שאומרים איך NOT עובר דרך AND ו־OR:
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
במילים: "לא שתיהן" זה כמו "אחת מהן לא נכונה", ו"אף אחת" זה כמו "שתיהן לא נכונות". מתכנתים משתמשים בזה כל יום כדי לכתוב מחדש תנאי כמו "לא (מחובר ומאומת)".
לוגיקה וקבוצות הן רעיון אחד
קראו את p כ"x נמצא ב־A" ואת q כ"x נמצא ב־B". אז AND הוא החיתוך, OR הוא האיחוד ו־NOT הוא המשלים, וכל טבלת אמת היא דיאגרמת ון צבועה, ולכן הרכיב משרטט אחת ליד הטבלה. חוקי דה מורגן הופכים לכללים על קבוצות:
(A ∩ B)′ = A′ ∪ B′
העמוד על סימון קבוצות צובע כל אחד מאלה על דיאגרמה שאפשר ללחוץ עליה.
ספירה
ספירה במתמטיקה בדידה פירושה לספור בלי לפרט. שני כללים עושים את רוב העבודה.
עיקרון הכפל. אם בחירה אחת אפשר לעשות ב־m דרכים ובחירה שנייה ב־n דרכים, את הזוג אפשר לעשות ב־m × n דרכים. לקוד PIN בן 4 ספרות יש 10 אפשרויות לכל ספרה, ולכן יש 10^4 = 10000 קודי PIN אפשריים.
צירופים. מספר הדרכים לבחור k דברים מתוך n, כשהסדר לא משנה, נכתב כ־C(n, k). בחירה של 3 תוספות מתוך 8:
C(8, 3) = (8 × 7 × 6) / (3 × 2 × 1) = 56
המונה סופר בחירות עם סדר, והחלוקה ב־3 × 2 × 1 מסירה את 6 הסדרים שבהם אפשר היה לבחור את אותן שלוש תוספות.
התשובה היא 6 × 5 חלקי 2, כלומר 15. אם קיבלתם 30, ספרתם כל זוג פעמיים, פעם אחת בכל סדר.
גרפים
גרף הוא קבוצה של נקודות, שנקראות צמתים, שמחוברות בקווים, שנקראים קשתות. הוא ממדל כל דבר שבנוי מחיבורים: כבישים בין ערים, חברים ברשת חברתית, קישורים בין דפי אינטרנט.
תוצאה ראשונה: אם 5 אנשים לוחצים ידיים זה לזה פעם אחת, יש C(5, 2) = 10 לחיצות ידיים. כל אדם לוחץ 4 ידיים, מה שנותן 5 × 4 = 20 קצוות של לחיצות, ולכל לחיצת יד יש שני קצוות, ולכן 20 / 2 = 10. הטיעון הזה הוא למת לחיצות הידיים: סכום הדרגות של כל הצמתים שווה לפעמיים מספר הקשתות.
תורת המספרים והוכחות
חשבון מודולרי הוא חשבון על שעון. 17 mod 5 הוא 2, השארית כשמחלקים את 17 ב־5. תשע שעות אחרי 8 השעה 5, כי 17 mod 12 הוא 5. אותו רעיון, עם מספרים גדולים מאוד, הוא הדרך שבה עובדת הצפנת RSA שמאחורי אתרים מאובטחים.
הוכחה באינדוקציה מראה שטענה מתקיימת לכל מספר שלם n בשני שלבים: בודקים אותה עבור n = 1, ואז מראים שאם היא מתקיימת עבור n כלשהו היא מתקיימת גם עבור n + 1. כך מוכיחים, למשל, ש־
1 + 2 + ... + n = n(n + 1) / 2
לכל n, ולא רק לערכים שניסיתם.
למה משמשת מתמטיקה בדידה
- תכנות: כל משפט if הוא לוגיקה, וחוקי דה מורגן כותבים תנאים מחדש.
- מסדי נתונים: שאילתה שמצרפת או מסננת טבלאות היא פעולות על קבוצות.
- אלגוריתמים: ספירה אומרת לכם כמה צעדים תוכנית עושה כשהקלט גדל.
- רשתות ומפות: מסלולים קצרים ביותר ורשתות חברתיות הם בעיות גרפים.
- אבטחה: הצפנה נשענת על תורת המספרים ועל חשבון מודולרי.
- חומרה: מעבד בנוי משערים לוגיים, שהם טבלאות אמת בסיליקון.
האם מתמטיקה בדידה קשה?
היא קשה בדרך אחרת מאלגברה ומחשבון דיפרנציאלי ואינטגרלי. יש מעט נוסחאות לשנן והחשבון קטן, אבל שאלות רבות מבקשות מכם להוכיח משהו ולא לחשב אותו, וכתיבת טיעון משכנע היא מיומנות חדשה לרוב הסטודנטים.
מה שעוזר הכי הרבה הוא לפתור מקרים קטנים ביד לפני שמחפשים את הדפוס: שרטטו את דיאגרמת ון, כתבו את טבלת האמת, פרטו כל מקרה. הסימון נראה כבד בהתחלה, אבל רובו הוא הסימנים שבעמוד הזה ובעמוד על סימון קבוצות.
שאלות נפוצות
- מה זו מתמטיקה בדידה?
- הענף במתמטיקה שחוקר עצמים נפרדים שאפשר לספור, ולא גדלים שמשתנים באופן חלק. הנושאים העיקריים שלו הם לוגיקה, קבוצות, קומבינטוריקה, גרפים, תורת המספרים והוכחות. חשבון דיפרנציאלי ואינטגרלי שואל איך דברים משתנים באופן רציף; מתמטיקה בדידה שואלת כמה, אילו, והאם טענה נכונה.
- האם מתמטיקה בדידה קשה?
- היא קשה בדרך אחרת מחשבון דיפרנציאלי ואינטגרלי. יש פחות נוסחאות להפעיל ויותר טיעונים לבנות, ולסטודנטים רבים זה הקורס הראשון שבנוי סביב כתיבת הוכחות. האלגברה בדרך כלל קלה. סטודנטים שמתקשים בה בעיקר מתרגלים להוכחות, וזה משתפר מהר עם תרגול על דוגמאות קטנות.
- למה משמשת מתמטיקה בדידה?
- כמעט לכל דבר במדעי המחשב. לוגיקה היא הדרך שבה מעגלים ומשפטי if עובדים, קבוצות עומדות בבסיס שאילתות במסדי נתונים, קומבינטוריקה אומרת כמה זמן לוקח לאלגוריתם לרוץ, גרפים ממדלים רשתות ומפות, ותורת המספרים היא הבסיס להצפנה שמגינה על תשלומים אונליין.
- אילו נושאים נלמדים במתמטיקה בדידה?
- קורס ראשון טיפוסי מכסה לוגיקה פסוקית וטבלאות אמת, קבוצות ודיאגרמות ון, פונקציות ויחסים, שיטות הוכחה כולל אינדוקציה, ספירה עם תמורות וצירופים, הסתברות בסיסית, גרפים ועצים, וחשבון מודולרי. יש קורסים שמוסיפים נוסחאות נסיגה ואלגברה בוליאנית.
- האם צריך מתמטיקה בדידה למדעי המחשב?
- כן. כמעט כל תואר במדעי המחשב דורש אותה, בדרך כלל בשנה הראשונה או השנייה, כי אלגוריתמים, מבני נתונים ותורת החישוביות כולם מניחים אותה. כדי להתחיל לתכנת אפשר להסתדר בלעדיה, אבל לוגיקה, קבוצות וספירה מופיעות בקוד היומיומי מוקדם יותר ממה שרוב האנשים מצפים.
- מה ההבדל בין מתמטיקה בדידה למתמטיקה רציפה?
- מתמטיקה בדידה עוסקת בערכים שאפשר למנות אחד אחד, כמו מספרים שלמים, נכון ולא נכון, או הצמתים של רשת. מתמטיקה רציפה, כמו חשבון דיפרנציאלי ואינטגרלי, עוסקת בגדלים שיכולים לקבל כל ערך בטווח, כמו זמן, מרחק או טמפרטורה.
- מהי טבלת אמת?
- טבלה שמפרטת כל צירוף של נכון ולא נכון עבור הקלטים של טענה לוגית, ואת ערך הטענה בכל אחד מהם. עם שני קלטים p ו־q יש ארבע שורות. טבלת אמת היא הדרך להוכיח ששתי טענות שקולות: אם העמודות שלהן זהות בכל שורה, הן תמיד מסכימות.
