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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(←‏פתרון)
 
(11 גרסאות ביניים של 3 משתמשים אינן מוצגות)
שורה 3: שורה 3:
 
=המשך קבוצות=
 
=המשך קבוצות=
  
−
==תרגיל==
+
== משלים ==
−
הוכיחו כי <math>A\cap (B\setminus C)=(A\cap B) \setminus  (A\cap C)</math>.
+
  
−
===פתרון===
+
'''הגדרה''': תהי קבוצה <math>U</math>, ונביט בתת קבוצה שלה <math>A</math>. ניתן להגדיר את ה'''משלים''' של <math>A</math> כאוסף האיברים ב-<math>U</math> שאינם ב-<math>A</math> (כלומר ההפרש <math>U\setminus A</math>), המסומן <math>A^c</math>. לא ניתן לדבר על משלים אוניברסלי ללא <math>U</math> מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל).
−
דרך גרירות לוגיות:
+
  
−
<math>x\in A\cap (B\setminus 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)] </math>
+
תכונות בסיסיות:
 +
* <math>A\cup A^c = U</math>
 +
* <math>\varnothing^c = U</math>
 +
* <math>U^c = \varnothing</math>
 +
* <math>(A^c)^c = A</math>
  
 +
על המשלימים מתקיימים חוקי דה מורגן (הנובעים ישירות מחוקי דה מורגן בלוגיקה):
 +
*<math>(A\cap B)^c = A^c \cup B^c</math>
 +
*<math>(A\cup B)^c = A^c \cap B^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>A \triangle B = A^c \triangle B^c</math>.
  
−
<math>\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)] </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>
  
−
בכיוון (<math>\subseteq</math>) נניח <math>x\in A\cap(B\backslash 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>x\in A \land x\in B \land x\not\in C \Leftarrow</math>
+
א. מצאו את <math>\bigcup_{n\in \mathbb{N}} B_n</math>.
−
<math>x\in A\cap B \land x\not\in A\cap C \Leftarrow</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>D_n=\mathbb{N}\smallsetminus B_n</math>. מצאו את <math>\bigcap_{n\in \mathbb{N}} D_n</math>.
  
−
<math>x\in A\cap B \land x\not\in A\cap C \Leftarrow</math>
+
====פתרון====
−
<math>x\in A \land x\in B \land x\not\in C \Leftarrow </math>
+
−
(כי אם <math>x\in C</math> אזי <math>x\in A\cap C</math> סתירה)
+
−
<math>x\in A\cap(B\backslash  C)\Leftarrow </math>
+
  
−
=== משלים ===
+
א. התשובה: <math>\mathbb{N}\smallsetminus \{1\}</math>. הוכחה:
  
−
'''הגדרה''': תהי קבוצה <math>U</math>, ונביט בתת קבוצה שלה <math>A</math>. ניתן להגדיר את ה'''משלים''' של <math>A</math> כאוסף האיברים ב-<math>U</math> שאינם ב-<math>A</math> (כלומר ההפרש <math>U\setminus A</math>), המסומן <math>A^c</math>. לא ניתן לדבר על משלים אוניברסלי ללא <math>U</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>A\cup A^c = U</math>
+
−
* <math>\varnothing^c = U</math>
+
−
* <math>U^c = \varnothing</math>
+
−
* <math>(A^c)^c = A</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\cap B)^c = A^c \cup B^c</math>
+
−
*<math>(A\cup B)^c = A^c \cap B^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>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=\{1,2\}</math> אזי <math>P(A)=\{\{\},\{1\},\{2\},\{1,2\}\}</math>.  
+
===תרגיל===
 +
הוכיחו או הפריכו: <math>A\cap P(P(A))=\varnothing</math>.
  
−
האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה?
+
====פתרון====
 +
הפרכה : ניקח <math>A=\{1,\{\{1\}\}\}</math>.
  
−
==תרגיל ממבחן==
+
===תרגיל===
−
יהיו A,B,C קבוצות. הוכיחו/הפריכו:
+
הוכיחו או הפריכו:
 +
 
 +
א. <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>.
 +
 
 +
===תרגיל ממבחן===
 +
תהינה <math>A,B,C</math> קבוצות. הוכיחו או הפריכו:
  
 
א. אם <math>A \not\subseteq B \cap C</math> אזי <math>(A\setminus B)\cap(A\setminus C)\neq \varnothing</math>
 
א. אם <math>A \not\subseteq B \cap C</math> אזי <math>(A\setminus B)\cap(A\setminus C)\neq \varnothing</math>
שורה 70: שורה 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>. אזי ברור שA איננה מוכלת בחיתוך של B וC אבל <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/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)]  </math>
+
<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>(x\in A)\rightarrow (x\in B)</math> ניתן להסיק בקלות ש-<math>(x\in A)\or (x\in B) \iff (x\in B)</math>, כפי שרצינו.
  
−
דרך נוספת: נגדיר את B להיות הקבוצה האוניברסאלית <math>U:=B</math> ואז צריך להוכיח כי  
+
דרך נוספת: נגדיר את <math>B</math> להיות הקבוצה האוניברסאלית <math>U:=B</math> ואז צריך להוכיח כי  
 
<math>A\cup A^c =U</math> וזה אכן נכון!
 
<math>A\cup A^c =U</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> מוכל בחיתוך, בסתירה לכך שהחיתוך ריק.
−
ג. נניח בשלילה ש<math>P(A)\cap P(B)\neq \{\varnothing\}</math>. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה <math>\varnothing \not=C</math> השייכת לחיתוך <math>P(A)\cap P(B)</math>. קבוצות החזקה הן אוסף תת הקבוצות, ולכן <math>C\subseteq A \and C\subseteq B</math>. מכיוון שC אינה ריקה קיים בה איבר <math>\exists c\in C</math> וקל מאד לראות ש<math>(c\in A)\and (c\in B) </math> ולכן c מוכל בחיתוך בסתירה לכך שהחיתוך ריק.
+

גרסה אחרונה מ־19:17, 9 ביולי 2019

חזרה לדף מערכי התרגול.

המשך קבוצות

משלים

הגדרה: תהי קבוצה 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_n=\{k\in \mathbb{N}|2\leq k\leq 2n-1\} ונגדיר B_n=A_{n+1}\smallsetminus A_n.

א. מצאו את \bigcup_{n\in \mathbb{N}} B_n.

ב. נגדיר D_n=\mathbb{N}\smallsetminus B_n. מצאו את \bigcap_{n\in \mathbb{N}} D_n.

פתרון

א. התשובה: \mathbb{N}\smallsetminus \{1\}. הוכחה:

\bigcup_{n\in \mathbb{N}} B_n \subseteq \mathbb{N}\smallsetminus \{1\} : הכל תת קבוצות של הטבעיים וכל הקבוצות מוגדרות ע"י איברים הגדולים מ-2.

\mathbb{N}\smallsetminus \{1\} \subseteq \bigcup_{n\in \mathbb{N}} B_n: יהי a\in \mathbb{N}\smallsetminus \{1\} נמצא קבוצה בה הוא נמצא. נשים לב ש-B_n=\{2\leq k\leq 2n+1\}\smallsetminus \{2\leq k\leq 2n-1\}=\{2n,2n+1\}. לכן אם a זוגי הוא נמצא ב- B_{\frac{n}{2}} ואם אי-זוגי אז a\in B_{\frac{n-1}{2}}.

ב. נתייחס ל-\mathbb{N} כקבוצה האוניברסלית לדיוננו. לפי דה-מורגן נקבל:\bigcap_{n\in \mathbb{N}} D_n=\bigcap_{n\in \mathbb{N}} B_n^c=(\bigcup_{n\in \mathbb{N}} B_n)^c=\{1\}.

קבוצת החזקה

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

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

תרגיל

הוכיחו או הפריכו: A\cap P(P(A))=\varnothing.

פתרון

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

תרגיל

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

א. 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\}. אז \{1,2\} \in P(A\cup B), אבל לא ל-P(A)\cup P(B).

למעשה הוכיחו כי P(A)\cup P(B)=P(A\cup B) אם ורק אם A\subseteq B או B\subseteq A.

תרגיל ממבחן

תהינה 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 מוכל בחיתוך, בסתירה לכך שהחיתוך ריק.

מקור: https://math-wiki.com/index.php?title=תרגול_6_תשעז&oldid=81701