הבדלים בין גרסאות בדף "תרגול 6 תשעז"
שורה 3: | שורה 3: | ||
=המשך קבוצות= | =המשך קבוצות= | ||
− | ==תרגיל== | + | ===תרגיל=== |
הוכיחו כי <math>A\cap (B\setminus C)=(A\cap B) \setminus (A\cap C)</math>. | הוכיחו כי <math>A\cap (B\setminus C)=(A\cap B) \setminus (A\cap C)</math>. | ||
שורה 22: | שורה 22: | ||
הוכחה נוספת בעזרת הכלה דו כיוונית: | הוכחה נוספת בעזרת הכלה דו כיוונית: | ||
− | בכיוון (<math>\subseteq</math>) נניח <math>x\in A\cap(B\backslash C)</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 \ | + | <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 \ | + | <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>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>\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 \ | + | <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 \ | + | <math>x\in A \land x\in B \land x\not\in C \Rightarrow</math> |
− | (כי אם <math>x\in C</math> | + | (כי אם <math>x\in C</math> אז <math>x\in A\cap C</math> סתירה) |
− | <math>x\in A\cap(B\backslash C) | + | <math>x\in A\cap(B\backslash C)</math> |
== משלים == | == משלים == | ||
שורה 56: | שורה 56: | ||
* <math>(\bigcap _{i\in I} A_i)^c = \bigcup _{i\in I} A_{i}^c </math> | * <math>(\bigcap _{i\in I} A_i)^c = \bigcup _{i\in I} A_{i}^c </math> | ||
* <math>(\bigcup _{i\in I} A_i)^c = \bigcap _{i\in I} A_{i}^c </math> | * <math>(\bigcup _{i\in I} A_i)^c = \bigcap _{i\in I} A_{i}^c </math> | ||
+ | |||
+ | ===תרגיל=== | ||
+ | |||
+ | הוכיחו כי <math>A \triangle B = A^c \triangle B^c</math>. | ||
+ | |||
+ | ===פתרון=== | ||
+ | |||
+ | נשתמש בהצגת ההפרש הסימטרי כאיחוד ההפרשים: | ||
+ | |||
+ | <math>x\in A \triangle B \iff (x\in A \land x\notin B)\lor (x\in B \land x\notin A) \iff</math> | ||
+ | |||
+ | <math>(x\notin A^c \land x\in B^c)\lor (x\notin B^c \land x\in A^c)</math> ומחילופיות "וגם" ו"או": | ||
+ | |||
+ | <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> | ||
==קבוצת החזקה== | ==קבוצת החזקה== | ||
שורה 74: | שורה 89: | ||
ג. אם <math>A\cap B=\varnothing</math> אזי <math>P(A)\cap P(B) = \{\varnothing\}</math> | ג. אם <math>A\cap B=\varnothing</math> אזי <math>P(A)\cap P(B) = \{\varnothing\}</math> | ||
− | |||
===פתרון=== | ===פתרון=== | ||
− | א. '''הפרכה''': <math>A=\{1,2\},B=\{1\},C=\{2\}</math>. אזי ברור ש-<math>A</math> איננה מוכלת בחיתוך <math>B\cap C</math> אבל <math>(A\setminus B)\cap(A\setminus C)=\{2\}\cap\{1\}=\varnothing</math> | + | א. '''הפרכה''': <math>A=\{1,2\},B=\{1\},C=\{2\}</math>. אזי ברור ש-<math>A</math> איננה מוכלת בחיתוך <math>B\cap C</math> אבל <math>(A\setminus B)\cap(A\setminus C)=\{2\}\cap\{1\}=\varnothing</math>. |
ב. נתון שלכל <math>a\in A</math> מתקיים <math>a \in B</math>. אזי | ב. נתון שלכל <math>a\in A</math> מתקיים <math>a \in B</math>. אזי | ||
− | <math>x\in [A\cup(B | + | <math>x\in [A\cup(B\setminus A)] \iff (x\in A) \or [(x\in B)\and (x\notin A)] \iff</math> |
− | + | <math>[(x\in A) \or (x\in B)] \and [(x \in A)\or (x\notin A)] </math> | |
− | + | כעת, הצד הימני הוא טאוטולוגיה וניתן להסיר אותו. מכיוון שנתון <math>(x\in A)\rightarrow (x\in B)</math> ניתן להסיק בקלות ש-<math>(x\in A)\or (x\in B) \iff (x\in B)</math>, כפי שרצינו. | |
− | <math> | + | |
+ | דרך נוספת: נגדיר את <math>B</math> להיות הקבוצה האוניברסאלית <math>U:=B</math> ואז צריך להוכיח כי | ||
+ | <math>A\cup A^c =U</math> וזה אכן נכון! | ||
− | ג. נניח בשלילה ש<math>P(A)\cap P(B)\neq \{\varnothing\}</math>. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה <math>\ | + | ג. נניח בשלילה ש-<math>P(A)\cap P(B)\neq \{\varnothing\}</math>. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה, החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה <math>C \ne\varnothing</math> השייכת לחיתוך <math>P(A)\cap P(B)</math>. קבוצות החזקה הן אוסף תת הקבוצות, ולכן <math>C\subseteq A \and C\subseteq B</math>. מכיוון ש-<math>C</math> אינה ריקה קיים בה איבר <math>c\in C</math> וקל לראות ש-<math>(c\in A)\and (c\in B) </math> ולכן <math>c</math> מוכל בחיתוך, בסתירה לכך שהחיתוך ריק. |
גרסה מ־19:22, 23 בנובמבר 2017
חזרה לדף מערכי התרגול.
תוכן עניינים
המשך קבוצות
תרגיל
הוכיחו כי .
פתרון
דרך גרירות לוגיות:
בשורה האחרונה הוספנו סתירה בעזרת הקשר "או" ולכן נשארנו עם ביטוי שקול. כעת נשתמש בחוק הפילוג של הלוגיקה:
וזה בדיוק מה שרצינו.
הוכחה נוספת בעזרת הכלה דו כיוונית:
בכיוון () נניח , ולכן
בכיוון () נניח . לכן
(כי אם אז סתירה)
משלים
הגדרה: תהי קבוצה , ונביט בתת קבוצה שלה . ניתן להגדיר את המשלים של כאוסף האיברים ב- שאינם ב- (כלומר ההפרש ), המסומן . לא ניתן לדבר על משלים אוניברסלי ללא מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל).
תכונות בסיסיות:
על המשלימים מתקיימים חוקי דה מורגן (הנובעים ישירות מחוקי דה מורגן בלוגיקה):
הערה: באופן כללי מתקיים
תרגיל
הוכיחו כי .
פתרון
נשתמש בהצגת ההפרש הסימטרי כאיחוד ההפרשים:
ומחילופיות "וגם" ו"או":
קבוצת החזקה
הגדרה: תהי קבוצה . נגדיר את קבוצת החזקה של בתור אוסף כל תת הקבוצות של . נסמן .
דוגמה: נבחר אזי .
האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה? הוכיחו זאת באינדוקציה.
תרגיל ממבחן
תהינה קבוצות. הוכיחו או הפריכו:
א. אם אזי
ב. אם אזי
ג. אם אזי
פתרון
א. הפרכה: . אזי ברור ש- איננה מוכלת בחיתוך אבל .
ב. נתון שלכל מתקיים . אזי
כעת, הצד הימני הוא טאוטולוגיה וניתן להסיר אותו. מכיוון שנתון ניתן להסיק בקלות ש-, כפי שרצינו.
דרך נוספת: נגדיר את להיות הקבוצה האוניברסאלית ואז צריך להוכיח כי וזה אכן נכון!
ג. נניח בשלילה ש-. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה, החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה השייכת לחיתוך . קבוצות החזקה הן אוסף תת הקבוצות, ולכן . מכיוון ש- אינה ריקה קיים בה איבר וקל לראות ש- ולכן מוכל בחיתוך, בסתירה לכך שהחיתוך ריק.