אחיה בר-און (שיחה | תרומות) (←פתרון) |
|||
(9 גרסאות ביניים של 3 משתמשים אינן מוצגות) | |||
שורה 2: | שורה 2: | ||
=המשך קבוצות= | =המשך קבוצות= | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
== משלים == | == משלים == | ||
שורה 61: | שורה 24: | ||
הוכיחו כי <math>A \triangle B = A^c \triangle B^c</math>. | הוכיחו כי <math>A \triangle B = A^c \triangle B^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\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>(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> נגדיר <math>A_n=\{k\in \mathbb{N}|2\leq k\leq 2n-1\}</math> ונגדיר <math>B_n=A_{n+1}\smallsetminus A_n</math>. | ||
+ | |||
+ | א. מצאו את <math>\bigcup_{n\in \mathbb{N}} B_n</math>. | ||
+ | |||
+ | ב. נגדיר <math>D_n=\mathbb{N}\smallsetminus B_n</math>. מצאו את <math>\bigcap_{n\in \mathbb{N}} D_n</math>. | ||
+ | |||
+ | ====פתרון==== | ||
+ | |||
+ | א. התשובה: <math>\mathbb{N}\smallsetminus \{1\}</math>. הוכחה: | ||
+ | |||
+ | <math>\bigcup_{n\in \mathbb{N}} B_n \subseteq \mathbb{N}\smallsetminus \{1\} </math>: הכל תת קבוצות של הטבעיים וכל הקבוצות מוגדרות ע"י איברים הגדולים מ-<math>2</math>. | ||
+ | |||
+ | <math>\mathbb{N}\smallsetminus \{1\} \subseteq \bigcup_{n\in \mathbb{N}} B_n</math>: יהי <math>a\in \mathbb{N}\smallsetminus \{1\}</math> נמצא קבוצה בה הוא נמצא. נשים לב ש-<math>B_n=\{2\leq k\leq 2n+1\}\smallsetminus \{2\leq k\leq 2n-1\}=\{2n,2n+1\}</math>. לכן אם <math>a</math> זוגי הוא נמצא ב- <math>B_{\frac{n}{2}}</math> ואם אי-זוגי אז <math>a\in B_{\frac{n-1}{2}}</math>. | ||
+ | |||
+ | ב. נתייחס ל-<math>\mathbb{N}</math> כקבוצה האוניברסלית לדיוננו. לפי דה-מורגן נקבל:<math>\bigcap_{n\in \mathbb{N}} D_n=\bigcap_{n\in \mathbb{N}} B_n^c=(\bigcup_{n\in \mathbb{N}} B_n)^c=\{1\}</math>. | ||
==קבוצת החזקה== | ==קבוצת החזקה== | ||
'''הגדרה''': תהי קבוצה <math>A</math>. נגדיר את '''קבוצת החזקה''' של <math>A</math> בתור אוסף כל תת הקבוצות של <math>A</math>. נסמן <math>P(A)=\{X:X\subseteq A\}</math>. | '''הגדרה''': תהי קבוצה <math>A</math>. נגדיר את '''קבוצת החזקה''' של <math>A</math> בתור אוסף כל תת הקבוצות של <math>A</math>. נסמן <math>P(A)=\{X:X\subseteq A\}</math>. | ||
− | |||
− | |||
− | |||
האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה? הוכיחו זאת באינדוקציה. | האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה? הוכיחו זאת באינדוקציה. | ||
+ | |||
+ | ===תרגיל=== | ||
+ | הוכיחו או הפריכו: <math>A\cap P(P(A))=\varnothing</math>. | ||
+ | |||
+ | ====פתרון==== | ||
+ | הפרכה : ניקח <math>A=\{1,\{\{1\}\}\}</math>. | ||
+ | |||
+ | ===תרגיל=== | ||
+ | הוכיחו או הפריכו: | ||
+ | |||
+ | א. <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</math> | ||
+ | |||
+ | <math>X\subseteq A\cap B\iff X\in P(A\cap B)</math> | ||
+ | |||
+ | ב. הפרכה: ניקח <math>A=\{1\},B=\{2\}</math>. אז <math>\{1,2\} \in P(A\cup B)</math>, אבל לא ל-<math>P(A)\cup P(B)</math>. | ||
+ | |||
+ | למעשה הוכיחו כי <math>P(A)\cup P(B)=P(A\cup B)</math> אם ורק אם <math>A\subseteq B</math> או <math>B\subseteq A</math>. | ||
===תרגיל ממבחן=== | ===תרגיל ממבחן=== |
גרסה אחרונה מ־19:17, 9 ביולי 2019
חזרה לדף מערכי התרגול.
המשך קבוצות
משלים
הגדרה: תהי קבוצה , ונביט בתת קבוצה שלה
. ניתן להגדיר את המשלים של
כאוסף האיברים ב-
שאינם ב-
(כלומר ההפרש
), המסומן
. לא ניתן לדבר על משלים אוניברסלי ללא
מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל).
תכונות בסיסיות:
על המשלימים מתקיימים חוקי דה מורגן (הנובעים ישירות מחוקי דה מורגן בלוגיקה):
הערה: באופן כללי מתקיים
תרגיל
הוכיחו כי .
פתרון
נשתמש בהצגת ההפרש הסימטרי כאיחוד ההפרשים:
ומחילופיות "וגם" ו"או":
תרגיל
לכל נגדיר
ונגדיר
.
א. מצאו את .
ב. נגדיר . מצאו את
.
פתרון
א. התשובה: . הוכחה:
: הכל תת קבוצות של הטבעיים וכל הקבוצות מוגדרות ע"י איברים הגדולים מ-
.
: יהי
נמצא קבוצה בה הוא נמצא. נשים לב ש-
. לכן אם
זוגי הוא נמצא ב-
ואם אי-זוגי אז
.
ב. נתייחס ל- כקבוצה האוניברסלית לדיוננו. לפי דה-מורגן נקבל:
.
קבוצת החזקה
הגדרה: תהי קבוצה . נגדיר את קבוצת החזקה של
בתור אוסף כל תת הקבוצות של
. נסמן
.
האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה? הוכיחו זאת באינדוקציה.
תרגיל
הוכיחו או הפריכו: .
פתרון
הפרכה : ניקח .
תרגיל
הוכיחו או הפריכו:
א.
ב.
פתרון
א. הוכחה:
ב. הפרכה: ניקח . אז
, אבל לא ל-
.
למעשה הוכיחו כי אם ורק אם
או
.
תרגיל ממבחן
תהינה קבוצות. הוכיחו או הפריכו:
א. אם אזי
ב. אם אזי
ג. אם אזי
פתרון
א. הפרכה: . אזי ברור ש-
איננה מוכלת בחיתוך
אבל
.
ב. נתון שלכל מתקיים
. אזי
כעת, הצד הימני הוא טאוטולוגיה וניתן להסיר אותו. מכיוון שנתון ניתן להסיק בקלות ש-
, כפי שרצינו.
דרך נוספת: נגדיר את להיות הקבוצה האוניברסאלית
ואז צריך להוכיח כי
וזה אכן נכון!
ג. נניח בשלילה ש-. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה, החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה
השייכת לחיתוך
. קבוצות החזקה הן אוסף תת הקבוצות, ולכן
. מכיוון ש-
אינה ריקה קיים בה איבר
וקל לראות ש-
ולכן
מוכל בחיתוך, בסתירה לכך שהחיתוך ריק.