תרגול 6 תשעז

תרגיל

נתון $A=\{\phi\}$ ונתון $B=\{\phi,\{\phi\}\}$. סמן את הביטויים הנכונים:

1. $\phi\subseteq B$ (כן)
2. $\phi\in \phi$ (לא)
3. $\phi \subseteq \phi$ (כן)
4. $A\subseteq B$ (כן)
5. $A\in B$ (כן)
6. $A\cup B = B$ (כן)
7. $A\cap B=\phi$ (לא)

תרגיל

הוכח כי $A\cap (B/C)=(A\cap B) / (A\cap C)$

פתרון

דרך גרירות לוגיות:

$x\in A\cap (B/C)\iff (x\in A) \and [(x\in B) \and (x\notin C)]\iff [(x\in A) \and (x\in B) \and (x\notin C)] \or [(x\in A) \and (x\in B) \and (x\notin A)]$

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

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

וזה בדיוק מה שרצינו.

דרך הכלה דו כיוונית:

($\subseteq$) נניח $x\in A\cap(B\backslash C)$ אזי

$x\in A \land x\in B \land x\not\in C \Leftarrow$ $x\in A\cap B \land x\not\in A\cap C \Leftarrow$ $x\in (A\cap B) \backslash (A\cap C)$

($\supseteq$) נניח $x\in (A\cap B) \backslash (A\cap C)$ אזי

$x\in A\cap B \land x\not\in A\cap C \Leftarrow$ $x\in A \land x\in B \land x\not\in C \Leftarrow$ (כי אם $x\in C$ אזי $x\in A\cap C$ סתירה) $x\in A\cap(B\backslash C)\Leftarrow$

תרגיל

נתונות $A=\{2m+1:m\in\mathbb{Z}\}$, ו $B=\{2m+3:m\in\mathbb{Z}\}$. הוכח שA=B.

פתרון

נוכיח הכלה דו כיוונית. נניח $x\in A$ לכן קיים מספר שלם m כך ש $x=2m+1$. קל לראות שמתקיים $x=2(m-1)+3$ אבל אז מכיוון ש m-1 הינו מספר שלם מתקיים $x\in B$ כפי שרצינו.

ההכלה בכיוון ההפוך דומה.

משלים

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

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

• $A\cup A^c = U$
• $\emptyset^c = U$
• $U^c = \emptyset$
• $(A^c)^c = A$

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

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

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

• $(\cap _{i\in I} A_i)^c = \cup _{i\in I} A_{i}^c$
• $(\cup _{i\in I} A_i)^c = \cap _{i\in I} A_{i}^c$

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

דוגמא:

$A=\{1,2\}$ אזי $P(A)=\{\{\},\{1\},\{2\},\{1,2\}\}$.

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

תרגיל ממבחן

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

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

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

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

פתרון

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

ב. נתון שלכל $a\in A$ מתקיים $a \in B$. אזי $x\in [A\cup(B/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\cap A^c =U$ וזה אכן נכון!

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