גרסה מ־18:42, 25 בנובמבר 2017

תוכן עניינים

1 המשך קבוצות
- 1.1 משלים
- 1.2 קבוצת החזקה

המשך קבוצות

משלים

הגדרה: תהי קבוצה $U$ , ונביט בתת קבוצה שלה $A$ . ניתן להגדיר את המשלים של $A$ כאוסף האיברים ב- $U$ שאינם ב- $A$ (כלומר ההפרש $U\setminus A$ ), המסומן $A^c$ . לא ניתן לדבר על משלים אוניברסלי ללא $U$ מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל).

תכונות בסיסיות:

$A\cup A^c = U$
$\varnothing^c = U$
$U^c = \varnothing$
$(A^c)^c = A$

על המשלימים מתקיימים חוקי דה מורגן (הנובעים ישירות מחוקי דה מורגן בלוגיקה):

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

הערה: באופן כללי מתקיים

$(\bigcap _{i\in I} A_i)^c = \bigcup _{i\in I} A_{i}^c$
$(\bigcup _{i\in I} A_i)^c = \bigcap _{i\in I} A_{i}^c$

תרגיל

הוכיחו כי $A \triangle B = A^c \triangle B^c$ .

פתרון

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

$x\in A \triangle B \iff (x\in A \land x\notin B)\lor (x\in B \land x\notin A) \iff$

$(x\notin A^c \land x\in B^c)\lor (x\notin B^c \land x\in A^c)$ ומחילופיות "וגם" ו"או":

$(x\notin B^c \land x\in A^c)\lor (x\notin A^c \land x\in B^c) \iff$ $(x\in A^c \land x\notin B^c)\lor (x\in B^c \land x\notin A^c) \iff x\in A^c \triangle B^c$

תרגיל

לכל $n\in \mathbb{N}$ נגדיר

קבוצת החזקה

הגדרה: תהי קבוצה $A$ . נגדיר את קבוצת החזקה של $A$ בתור אוסף כל תת הקבוצות של $A$ . נסמן $P(A)=\{X:X\subseteq A\}$ .

דוגמה: נבחר $A=\{1,2\}$ אזי $P(A)=\{\{\},\{1\},\{2\},\{1,2\}\}$ .

האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה? הוכיחו זאת באינדוקציה.

תרגיל

הוכיחו או הפריכו:

א. $P(A)\cap P(B)=P(A\cap B)$

ב. $P(A)\cup P(B)=P(A\cup B)$

פתרון

א. הוכחה: $X\in P(A)\cap P(B) \iff X\subseteq A\land X\subseteq B\iff X\subseteq A\cap B\iff X\in P(A\cap B)$ .

ב. הפרכה: ניקח $A=\{1\},B=\{2\}$ .

תרגיל ממבחן

תהינה $A,B,C$ קבוצות. הוכיחו או הפריכו:

א. אם $A \not\subseteq B \cap C$ אזי $(A\setminus B)\cap(A\setminus C)\neq \varnothing$

ב. אם $A\subseteq B$ אזי $A\cup (B\setminus A)=B$

ג. אם $A\cap B=\varnothing$ אזי $P(A)\cap P(B) = \{\varnothing\}$

פתרון

א. הפרכה: $A=\{1,2\},B=\{1\},C=\{2\}$ . אזי ברור ש- $A$ איננה מוכלת בחיתוך $B\cap C$ אבל $(A\setminus B)\cap(A\setminus C)=\{2\}\cap\{1\}=\varnothing$ .

ב. נתון שלכל $a\in A$ מתקיים $a \in B$ . אזי

$x\in [A\cup(B\setminus A)] \iff (x\in A) \or [(x\in B)\and (x\notin A)] \iff$

$[(x\in A) \or (x\in B)] \and [(x \in A)\or (x\notin A)]$

כעת, הצד הימני הוא טאוטולוגיה וניתן להסיר אותו. מכיוון שנתון $(x\in A)\rightarrow (x\in B)$ ניתן להסיק בקלות ש- $(x\in A)\or (x\in B) \iff (x\in B)$ , כפי שרצינו.

דרך נוספת: נגדיר את $B$ להיות הקבוצה האוניברסאלית $U:=B$ ואז צריך להוכיח כי $A\cup A^c =U$ וזה אכן נכון!

ג. נניח בשלילה ש- $P(A)\cap P(B)\neq \{\varnothing\}$ . מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה, החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה $C \ne\varnothing$ השייכת לחיתוך $P(A)\cap P(B)$ . קבוצות החזקה הן אוסף תת הקבוצות, ולכן $C\subseteq A \and C\subseteq B$ . מכיוון ש- $C$ אינה ריקה קיים בה איבר $c\in C$ וקל לראות ש- $(c\in A)\and (c\in B)$ ולכן $c$ מוכל בחיתוך, בסתירה לכך שהחיתוך ריק.

@@ שורה 2: / שורה 2: @@
 =המשך קבוצות=
-===תרגיל===
-הוכיחו כי <math>A\cap (B\setminus C)=(A\cap B) \setminus  (A\cap C)</math>.
-===פתרון===
-דרך גרירות לוגיות:
-<math>x\in A\cap (B\setminus C) \iff</math>
-<math>(x\in A) \and [(x\in B) \and (x\notin C)] \iff</math>
-<math>[(x\in A) \and (x\in B) \and (x\notin C)] \or [(x\in A) \and (x\in B) \and (x\notin A)] </math>
-בשורה האחרונה הוספנו סתירה בעזרת הקשר "או" ולכן נשארנו עם ביטוי שקול. כעת נשתמש בחוק הפילוג של הלוגיקה:
-<math>\iff [(x\in A) \and (x\in B)]\and [(x\notin C)\or(x\notin A)]\iff</math>
-<math>[(x\in A) \and (x\in B)]\and \neg [(x\in C)\and(x\in A)]</math>
-וזה בדיוק מה שרצינו.
-הוכחה נוספת בעזרת הכלה דו כיוונית:
-בכיוון (<math>\subseteq</math>) נניח <math>x\in A\cap(B\backslash C)</math>, ולכן
-<math>x\in A \land x\in B \land x\not\in C \Rightarrow</math>
-<math>x\in A\cap B \land x\not\in A\cap C \Rightarrow</math>
-<math>x\in (A\cap B) \backslash (A\cap C)</math>
-בכיוון (<math>\supseteq</math>) נניח <math>x\in (A\cap B) \backslash (A\cap C)</math>. לכן
-<math>x\in A\cap B \land x\not\in A\cap C \Rightarrow</math>
-<math>x\in A \land x\in B \land x\not\in C \Rightarrow</math>
-(כי אם <math>x\in C</math> אז <math>x\in A\cap C</math> סתירה)
-<math>x\in A\cap(B\backslash  C)</math>
 == משלים ==
@@ שורה 71: / שורה 34: @@
 <math>(x\notin B^c \land x\in A^c)\lor (x\notin A^c \land x\in B^c) \iff</math>
 <math>(x\in A^c \land x\notin B^c)\lor (x\in B^c \land x\notin A^c) \iff x\in A^c \triangle B^c</math>
+===תרגיל===
+לכל <math>n\in \mathbb{N}</math> נגדיר
 ==קבוצת החזקה==
@@ שורה 80: / שורה 46: @@
 האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה? הוכיחו זאת באינדוקציה.
+===תרגיל===
+הוכיחו או הפריכו:
+א. <math>P(A)\cap P(B)=P(A\cap B)</math>
+ב. <math>P(A)\cup P(B)=P(A\cup B)</math>
+====פתרון====
+א. הוכחה: <math>X\in P(A)\cap P(B) \iff X\subseteq A\land X\subseteq B\iff X\subseteq A\cap B\iff X\in P(A\cap B)</math>.
+ב. הפרכה: ניקח <math>A=\{1\},B=\{2\}</math>.
 ===תרגיל ממבחן===

הבדלים בין גרסאות בדף "תרגול 6 תשעז"

גרסה מ־18:42, 25 בנובמבר 2017

תוכן עניינים

המשך קבוצות

משלים

תרגיל

פתרון

תרגיל

קבוצת החזקה

תרגיל

פתרון

תרגיל ממבחן

פתרון

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים