שינויים
יצירת דף עם התוכן "===תרגיל=== נתון <math>A=\{\phi\}</math> ונתון <math>B=\{\phi,\{\phi\}\}</math>. סמן את הביטויים הנכונים: #<math>\phi\subseteq..."
===תרגיל===
נתון <math>A=\{\phi\}</math> ונתון <math>B=\{\phi,\{\phi\}\}</math>. סמן את הביטויים הנכונים:
#<math>\phi\subseteq B</math> (כן)
#<math>\phi\in \phi</math> (לא)
#<math>\phi \subseteq \phi</math> (כן)
#<math>A\subseteq B</math> (כן)
#<math>A\in B</math> (כן)
#<math>A\cup B = B</math> (כן)
#<math>A\cap B=\phi</math> (לא)
===תרגיל===
הוכח כי <math>A\cap (B/C)=(A\cap B) / (A\cap C)</math>
====פתרון====
דרך גרירות לוגיות:
<math>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)] </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>\subseteq</math>) נניח <math>x\in A\cap(B\backslash C)</math> אזי
<math>x\in A \land x\in B \land x\not\in C \Leftarrow</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>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>A=\{2m+1:m\in\mathbb{Z}\}</math>, ו <math>B=\{2m+3:m\in\mathbb{Z}\}</math>. הוכח שA=B.
====פתרון====
נוכיח הכלה דו כיוונית. נניח <math>x\in A</math> לכן קיים מספר שלם m כך ש <math>x=2m+1</math>. קל לראות שמתקיים <math>x=2(m-1)+3</math> אבל אז מכיוון ש m-1 הינו מספר שלם מתקיים <math>x\in B</math> כפי שרצינו.
ההכלה בכיוון ההפוך דומה.
==== משלים ====
'''הגדרה''': תהי קבוצה U, ונביט בתת קבוצה שלה A. ניתן להגדיר את ה'''משלים''' של A כאוסף האיברים בU שאינם בA (כלומר ההפרש <math>U\setminus A</math>), מסומן <math>A^c</math>. לא ניתן לדבר על משלים אוניברסאלי ללא U מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל).
תכונות בסיסיות:
* <math>A\cup A^c = U</math>
* <math>\emptyset^c = U</math>
* <math>U^c = \emptyset</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>(\cap _{i\in I} A_i)^c = \cup _{i\in I} A_{i}^c </math>
* <math>(\cup _{i\in I} A_i)^c = \cap _{i\in I} A_{i}^c </math>
'''הגדרה''': תהי קבוצה A. נגדיר את '''קבוצת החזקה''' של A בתור אוסף כל תתי הקבוצות של A. מסומן <math>P(A)=\{X:X\subseteq A\}</math>
דוגמא:
<math>A=\{1,2\}</math> אזי <math>P(A)=\{\{\},\{1\},\{2\},\{1,2\}\}</math>.
האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה?
===תרגיל ממבחן===
יהיו A,B,C קבוצות. הוכיחו/הפריכו:
א. אם <math>A \not\subseteq B \cap C</math> אזי <math>(A/B)\cap(A/C)\neq \phi</math>
ב. אם <math>A\subseteq B</math> אזי <math>A\cup(B/A)=B</math>
ג. אם <math>A\cap B=\phi</math> אזי <math>P(A)\cap P(B) = \{\phi\}</math>
====פתרון====
א. '''הפרכה''': <math>A=\{1,2\},B=\{1\},C=\{2\}</math>. אזי ברור שA איננה מוכלת בחיתוך של B וC אבל <math>(A/B)\cap(A/C)=\{2\}\cap\{1\}=\phi</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)\rightarrow (x\in B)</math> ניתן להסיק בקלות ש<math>(x\in A)\or (x\in B) \iff (x\in B)</math> כפי שרצינו.
דרך נוספת: נגדיר את B להיות הקבוצה האוניברסאלית <math>U:=B</math> ואז צריך להוכיח כי
<math>A\cap A^c =U</math> וזה אכן נכון!
ג. נניח בשלילה ש<math>P(A)\cap P(B)\neq \{\phi\}</math>. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה <math>\phi \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 מוכל בחיתוך בסתירה לכך שהחיתוך ריק.
נתון <math>A=\{\phi\}</math> ונתון <math>B=\{\phi,\{\phi\}\}</math>. סמן את הביטויים הנכונים:
#<math>\phi\subseteq B</math> (כן)
#<math>\phi\in \phi</math> (לא)
#<math>\phi \subseteq \phi</math> (כן)
#<math>A\subseteq B</math> (כן)
#<math>A\in B</math> (כן)
#<math>A\cup B = B</math> (כן)
#<math>A\cap B=\phi</math> (לא)
===תרגיל===
הוכח כי <math>A\cap (B/C)=(A\cap B) / (A\cap C)</math>
====פתרון====
דרך גרירות לוגיות:
<math>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)] </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>\subseteq</math>) נניח <math>x\in A\cap(B\backslash C)</math> אזי
<math>x\in A \land x\in B \land x\not\in C \Leftarrow</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>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>A=\{2m+1:m\in\mathbb{Z}\}</math>, ו <math>B=\{2m+3:m\in\mathbb{Z}\}</math>. הוכח שA=B.
====פתרון====
נוכיח הכלה דו כיוונית. נניח <math>x\in A</math> לכן קיים מספר שלם m כך ש <math>x=2m+1</math>. קל לראות שמתקיים <math>x=2(m-1)+3</math> אבל אז מכיוון ש m-1 הינו מספר שלם מתקיים <math>x\in B</math> כפי שרצינו.
ההכלה בכיוון ההפוך דומה.
==== משלים ====
'''הגדרה''': תהי קבוצה U, ונביט בתת קבוצה שלה A. ניתן להגדיר את ה'''משלים''' של A כאוסף האיברים בU שאינם בA (כלומר ההפרש <math>U\setminus A</math>), מסומן <math>A^c</math>. לא ניתן לדבר על משלים אוניברסאלי ללא U מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל).
תכונות בסיסיות:
* <math>A\cup A^c = U</math>
* <math>\emptyset^c = U</math>
* <math>U^c = \emptyset</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>(\cap _{i\in I} A_i)^c = \cup _{i\in I} A_{i}^c </math>
* <math>(\cup _{i\in I} A_i)^c = \cap _{i\in I} A_{i}^c </math>
'''הגדרה''': תהי קבוצה A. נגדיר את '''קבוצת החזקה''' של A בתור אוסף כל תתי הקבוצות של A. מסומן <math>P(A)=\{X:X\subseteq A\}</math>
דוגמא:
<math>A=\{1,2\}</math> אזי <math>P(A)=\{\{\},\{1\},\{2\},\{1,2\}\}</math>.
האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה?
===תרגיל ממבחן===
יהיו A,B,C קבוצות. הוכיחו/הפריכו:
א. אם <math>A \not\subseteq B \cap C</math> אזי <math>(A/B)\cap(A/C)\neq \phi</math>
ב. אם <math>A\subseteq B</math> אזי <math>A\cup(B/A)=B</math>
ג. אם <math>A\cap B=\phi</math> אזי <math>P(A)\cap P(B) = \{\phi\}</math>
====פתרון====
א. '''הפרכה''': <math>A=\{1,2\},B=\{1\},C=\{2\}</math>. אזי ברור שA איננה מוכלת בחיתוך של B וC אבל <math>(A/B)\cap(A/C)=\{2\}\cap\{1\}=\phi</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)\rightarrow (x\in B)</math> ניתן להסיק בקלות ש<math>(x\in A)\or (x\in B) \iff (x\in B)</math> כפי שרצינו.
דרך נוספת: נגדיר את B להיות הקבוצה האוניברסאלית <math>U:=B</math> ואז צריך להוכיח כי
<math>A\cap A^c =U</math> וזה אכן נכון!
ג. נניח בשלילה ש<math>P(A)\cap P(B)\neq \{\phi\}</math>. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה <math>\phi \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 מוכל בחיתוך בסתירה לכך שהחיתוך ריק.
