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

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

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

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

פסוקים וקשרים לוגיים

פסוק (Proposition): טענה שניתן לקבוע באופן חד-משמעי אם היא אמת או שקר, אך לא שניהם יחד.

פסוקים מורכבים נבנים מפסוקים פשוטים באמצעות קשרים לוגיים:

וגם (AND, $\land$)

נכון רק אם שני הפסוקים נכונים. לדוגמה: "ירד גשם וגם השמש זורחת".

או (OR, $\lor$)

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

לא (NOT, $\neg$)

הופך את ערך האמת של הפסוק. לדוגמה: "לא ירד גשם".

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

P גורר Q. נכון תמיד, למעט המקרה ש-P נכון ו-Q שקר. לדוגמה: "אם ירד גשם אז הרצפה רטובה".

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

נכון כאשר לשני הפסוקים אותו ערך אמת (שניהם נכונים או שניהם שקר). לדוגמה: "המספר זוגי אם ורק אם הוא מתחלק ב-2".

טבלאות אמת ושקילות לוגית

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

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

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

שקילות לוגית (Logical Equivalence): שני פסוקים P ו-Q שקולים לוגית (מסומן $P \equiv Q$) אם הם בעלי אותה טבלת אמת. כלומר, $P \leftrightarrow Q$ היא טאוטולוגיה.

כמתים (Quantifiers)

כמתים מאפשרים לנו לבטא טענות על קבוצות של איברים.

כמת לכל (Universal Quantifier, $\forall$): "לכל", "עבור כל". מציין שתכונה מסוימת מתקיימת עבור כל האיברים בקבוצה נתונה.

כמת קיים (Existential Quantifier, $\exists$): "קיים", "ישנו לפחות אחד". מציין שתכונה מסוימת מתקיימת עבור לפחות איבר אחד בקבוצה נתונה.

מושגי יסוד בתורת הקבוצות

תורת הקבוצות היא השפה הבסיסית למתמטיקה ולמדעי המחשב.

הגדרת קבוצה ואיברים

קבוצה (Set): אוסף של איברים מובחנים היטב, ללא חשיבות לסדר.

איבר (Element): אובייקט השייך לקבוצה. מסומן $x \in A$ (x שייך ל-A).

קבוצה ריקה (Empty Set, $\emptyset$ או {}): קבוצה שאינה מכילה אף איבר.

קבוצה אוניברסלית (Universal Set, U): קבוצה המכילה את כל האיברים הרלוונטיים לדיון מסוים.

יחסים בין קבוצות

תת-קבוצה (Subset, $\subseteq$): קבוצה A היא תת-קבוצה של קבוצה B אם כל איבר של A הוא גם איבר של B. מסומן $A \subseteq B$. (תת-קבוצה ממש: $A \subset B$ אם $A \subseteq B$ וגם $A \ne B$).

שוויון קבוצות (Set Equality): שתי קבוצות A ו-B שוות אם ורק אם הן מכילות בדיוק את אותם איברים. כלומר, $A \subseteq B$ וגם $B \subseteq A$.

קבוצת החזקה (Power Set, $\mathcal{P}(A)$): קבוצת כל תת-הקבוצות של A, כולל הקבוצה הריקה ו-A עצמה. אם $|A|=n$, אז $|\mathcal{P}(A)|=2^n$.

פעולות על קבוצות וזהויות

באמצעות פעולות אלו ניתן לבנות קבוצות חדשות מקבוצות קיימות.

פעולות בסיסיות

איחוד (Union, $\cup$)

$A \cup B = \{x \mid x \in A \text{ or } x \in B\}$. כל האיברים שנמצאים ב-A או ב-B (או בשניהם).

חיתוך (Intersection, $\cap$)

$A \cap B = \{x \mid x \in A \text{ and } x \in B\}$. כל האיברים שנמצאים גם ב-A וגם ב-B.

הפרש (Difference, $\setminus$ או $-$)

$A \setminus B = \{x \mid x \in A \text{ and } x \notin B\}$. כל האיברים שנמצאים ב-A אך לא ב-B.

משלים (Complement, $A^c$ או $\overline{A}$)

$A^c = \{x \mid x \in U \text{ and } x \notin A\}$. כל האיברים בקבוצה האוניברסלית שאינם ב-A. (שקול ל- $U \setminus A$).

מכפלה קרטזית (Cartesian Product, $\times$)

$A \times B = \{(a,b) \mid a \in A \text{ and } b \in B\}$. קבוצת כל הזוגות הסדורים שבהם האיבר הראשון מ-A והשני מ-B.

זהויות קבוצתיות

קיימות זהויות רבות המקבילות לחוקי הלוגיקה, כגון חוקי דה-מורגן:

$(A \cup B)^c = A^c \cap B^c$
$(A \cap B)^c = A^c \cup B^c$

וכן חוקי הפילוג, האסוציאטיביות והקומוטטיביות.

טיפים למבחן ונקודות קריטיות

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

תרגלו הוכחות של שקילויות לוגיות באמצעות טבלאות אמת וזהויות לוגיות. תרגלו הוכחות של שוויון קבוצות באמצעות זהויות קבוצתיות או על ידי הוכחה דו-כיוונית ($A \subseteq B$ וגם $B \subseteq A$).

שאלות לדיון

הסבירו את ההבדל בין "או" כוללני ל"או" מוציא (XOR), ומתי כל אחד מהם רלוונטי יותר בתיאור מצבים יומיומיים.
כיצד ניתן להוכיח ששני פסוקים לוגיים שקולים לוגית? תארו שתי שיטות שונות.
תנו דוגמה לקבוצה A, וחשבו את קבוצת החזקה שלה, $\mathcal{P}(A)$. מהו הקשר בין מספר האיברים ב-A למספר האיברים ב-$\mathcal{P}(A)$?
הסבירו את חשיבותה של הקבוצה האוניברסלית בהקשר של פעולת המשלים. האם קבוצה אוניברסלית תמיד מוגדרת באופן חד-משמעי?

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

הבדל בין "או" כוללני ל"או" מוציא: "או" כוללני ($\lor$) נכון אם לפחות אחד מהפסוקים נכון (כולל שניהם). "או" מוציא (XOR, $\oplus$) נכון אם בדיוק אחד מהפסוקים נכון. ביום-יום, "או" כוללני נפוץ יותר (למשל, "אפשר לשלם במזומן או באשראי" - אפשר גם בשניהם אם הקנייה גדולה). "או" מוציא מתאים למצבים של בחירה בלעדית ("או שתאכל תפוח או שתאכל בננה" - לא שניהם).
הוכחת שקילות לוגית:
1. טבלאות אמת: בניית טבלאות אמת לשני הפסוקים והשוואת עמודות האמת הסופיות שלהם. אם הן זהות, הפסוקים שקולים.
2. שימוש בזהויות לוגיות: התחלה מפסוק אחד וביצוע סדרת טרנספורמציות (החלפת חלקים שקולים בזהויות ידועות) עד הגעה לפסוק השני.

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