⚡ Smart-World Surf
Sign in Create account

יחידה 2: תורת הקבוצות

הבסיס לבניית מבנים מתמטיים בדידים.

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

יסודות תורת הקבוצות

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

קבוצה (Set): אוסף מוגדר היטב של אובייקטים נפרדים.
איבר (Element): אובייקט השייך לקבוצה. הסימון $x \in A$ מציין ש-$x$ הוא איבר בקבוצה $A$.
שוויון קבוצות (Set Equality): שתי קבוצות $A$ ו-$B$ שוות אם ורק אם הן מכילות בדיוק את אותם האיברים. כלומר, $A = B$ אם ורק אם $A \subseteq B$ וגם $B \subseteq A$.

דרכים להגדרת קבוצות

  • רישום איברים: למשל, $A = \{1, 2, 3\}$.
  • תכונה מאפיינת (Set-builder notation): למשל, $B = \{x \mid x \text{ הוא מספר טבעי ו-} x < 5\}$.

פעולות יסודיות על קבוצות

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

תת-קבוצה (Subset): קבוצה $A$ היא תת-קבוצה של קבוצה $B$ (מסומן $A \subseteq B$) אם כל איבר של $A$ הוא גם איבר של $B$.
תת-קבוצה ממשית (Proper Subset): קבוצה $A$ היא תת-קבוצה ממשית של $B$ (מסומן $A \subset B$) אם $A \subseteq B$ וגם $A \neq B$.
קבוצה ריקה (Empty Set): הקבוצה שאינה מכילה אף איבר. מסומנת $\emptyset$ או $\{\}$.
קבוצה אוניברסלית (Universal Set): קבוצה המכילה את כל האיברים הרלוונטיים בהקשר נתון. מסומנת לרוב $U$.

איחוד (Union)

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

חיתוך (Intersection)

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

הפרש (Difference)

הקבוצה המכילה את כל האיברים הנמצאים ב-$A$ אך לא ב-$B$. מסומן $A \setminus B = \{x \mid x \in A \text{ וגם } x \notin B\}$.

משלים (Complement)

בהינתן קבוצה אוניברסלית $U$, המשלים של $A$ הוא הקבוצה המכילה את כל האיברים ב-$U$ שאינם ב-$A$. מסומן $A^c$ או $\bar{A}$ או $U \setminus A$.

קבוצות מיוחדות וזהויות

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

קבוצת חזקה (Power Set): קבוצת כל תת-הקבוצות של קבוצה נתונה $A$. מסומנת $\mathcal{P}(A)$ או $2^A$. אם $|A|=n$, אז $|\mathcal{P}(A)|=2^n$.
מכפלה קרטזית (Cartesian Product): קבוצת כל הזוגות הסדורים $(a, b)$ כך ש-$a \in A$ ו-$b \in B$. מסומנת $A \times B = \{(a,b) \mid a \in A \text{ וגם } b \in B\}$. אם $|A|=n$ ו-$|B|=m$, אז $|A \times B|=nm$.
הוכחות זהויות קבוצתיות: בבחינות בטכניון, דגש רב מושם על היכולת להוכיח זהויות קבוצתיות באופן פורמלי ומדויק. הוכחות אלו דורשות שימוש בהגדרות הפורמליות של פעולות הקבוצות (למשל, $x \in A \cup B \iff x \in A \text{ או } x \in B$) ושימוש בכללי לוגיקה. הגישה הסטנדרטית להוכחת שוויון קבוצות $A=B$ היא להראות הכלה דו-כיוונית: ראשית להוכיח ש-$A \subseteq B$, ולאחר מכן להוכיח ש-$B \subseteq A$. הימנעו משימוש בדיאגרמות וון כהוכחה פורמלית, הן משמשות רק לאינטואיציה.

זהויות קבוצתיות נפוצות (דוגמאות)

  • חוקי דה-מורגן: $(A \cup B)^c = A^c \cap B^c$ וגם $(A \cap B)^c = A^c \cup B^c$.
  • חוקי הפילוג: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ וגם $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$.
  • חוקי בליעה: $A \cup (A \cap B) = A$ וגם $A \cap (A \cup B) = A$.

שאלות לדיון

  • בהינתן קבוצות $A=\{1,2\}$, $B=\{2,3,4\}$ ו-$C=\{3,5\}$, חשבו את $\mathcal{P}(A \cap B)$, $(A \cup C) \setminus B$ ואת $A \times (B \cap C)$.
  • הוכיחו פורמלית את חוק הפילוג: $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$.
  • הסבירו את ההבדל המהותי בין $x \in A$ לבין $\{x\} \subseteq A$. תנו דוגמה.
  • כיצד ניתן להשתמש בזהויות קבוצתיות כדי לפשט ביטויים מורכבים? תנו דוגמה.

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

  • הוכחות פורמליות: תמיד התחילו מהגדרות האיברים והפעולות. עבור שוויון קבוצות, הוכיחו הכלה דו-כיוונית (לדוגמה, $x \in LHS \implies \dots \implies x \in RHS$ ואז בכיוון ההפוך).
  • דיוק בסימון: הקפידו על שימוש נכון בסימונים $\in, \notin, \subseteq, \subset, \cup, \cap, \setminus, \mathcal{P}, \times$.
  • הבנת מושגים: ודאו שאתם מבינים את ההבדל בין איבר לקבוצה, ובין קבוצה לתת-קבוצה. למשל, $A \in \mathcal{P}(A)$ תמיד נכון, אך $A \subseteq A$ הוא גם נכון.
  • שימוש בלוגיקה: הוכחות קבוצתיות מתבססות על כללי לוגיקה בסיסיים (וגם, או, אם-אז, לא).
  • בדיקת קצוות: שקלו תמיד מקרים מיוחדים כמו הקבוצה הריקה או הקבוצה האוניברסלית.
מצאתם טעות או שחסר משהו?
→ הקודמת
לוגיקה מתמטית ושיטות הוכחה
הבאה ←
יחסים