הבדלים בין גרסאות בדף "תרגול 6 תשעז"
שורה 1: | שורה 1: | ||
חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]]. | חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]]. | ||
− | + | =המשך קבוצות= | |
− | + | ==תרגיל== | |
− | + | הוכיחו כי <math>A\cap (B\setminus C)=(A\cap B) \setminus (A\cap C)</math>. | |
− | + | ===פתרון=== | |
דרך גרירות לוגיות: | דרך גרירות לוגיות: | ||
− | <math>x\in A\cap (B | + | <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> |
שורה 21: | שורה 21: | ||
− | + | הוכחה בעזרת הכלה דו כיוונית: | |
− | (<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 \Leftarrow</math> | <math>x\in A \land x\in B \land x\not\in C \Leftarrow</math> | ||
שורה 29: | שורה 29: | ||
<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 \Leftarrow</math> | <math>x\in A\cap B \land x\not\in A\cap C \Leftarrow</math> | ||
שורה 36: | שורה 36: | ||
<math>x\in A\cap(B\backslash C)\Leftarrow </math> | <math>x\in A\cap(B\backslash C)\Leftarrow </math> | ||
− | + | === משלים === | |
− | '''הגדרה''': תהי קבוצה U, ונביט בתת קבוצה שלה A. ניתן להגדיר את ה'''משלים''' של A כאוסף האיברים | + | '''הגדרה''': תהי קבוצה <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>A\cup A^c = U</math> | * <math>A\cup A^c = U</math> | ||
− | * <math>\ | + | * <math>\varnothing^c = U</math> |
− | * <math>U^c = \ | + | * <math>U^c = \varnothing</math> |
* <math>(A^c)^c = A</math> | * <math>(A^c)^c = A</math> | ||
שורה 50: | שורה 50: | ||
*<math>(A\cup B)^c = A^c \cap B^c</math> | *<math>(A\cup B)^c = A^c \cap B^c</math> | ||
הערה: באופן כללי מתקיים | הערה: באופן כללי מתקיים | ||
− | * <math>(\ | + | * <math>(\bigcap _{i\in I} A_i)^c = \bigcup _{i\in I} A_{i}^c </math> |
− | * <math>(\ | + | * <math>(\bigcup _{i\in I} A_i)^c = \bigcap _{i\in I} A_{i}^c </math> |
− | '''הגדרה''': תהי קבוצה A. נגדיר את '''קבוצת החזקה''' של A בתור אוסף כל | + | '''הגדרה''': תהי קבוצה <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=\{1,2\}</math> אזי <math>P(A)=\{\{\},\{1\},\{2\},\{1,2\}\}</math>. | ||
שורה 62: | שורה 62: | ||
האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה? | האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה? | ||
− | + | ==תרגיל ממבחן== | |
יהיו A,B,C קבוצות. הוכיחו/הפריכו: | יהיו A,B,C קבוצות. הוכיחו/הפריכו: | ||
− | א. אם <math>A \not\subseteq B \cap C</math> אזי <math>(A | + | א. אם <math>A \not\subseteq B \cap C</math> אזי <math>(A\setminus B)\cap(A\setminus C)\neq \varnothing</math> |
− | ב. אם <math>A\subseteq B</math> אזי <math>A\cup(B | + | ב. אם <math>A\subseteq B</math> אזי <math>A\cup (B\setminus A)=B</math> |
− | ג. אם <math>A\cap B=\ | + | ג. אם <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 | + | א. '''הפרכה''': <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> |
שורה 82: | שורה 82: | ||
דרך נוספת: נגדיר את B להיות הקבוצה האוניברסאלית <math>U:=B</math> ואז צריך להוכיח כי | דרך נוספת: נגדיר את B להיות הקבוצה האוניברסאלית <math>U:=B</math> ואז צריך להוכיח כי | ||
− | <math>A\ | + | <math>A\cup A^c =U</math> וזה אכן נכון! |
− | ג. נניח בשלילה ש<math>P(A)\cap P(B)\neq \{\ | + | ג. נניח בשלילה ש<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 מוכל בחיתוך בסתירה לכך שהחיתוך ריק. |
גרסה מ־18:21, 23 בנובמבר 2017
חזרה לדף מערכי התרגול.
תוכן עניינים
המשך קבוצות
תרגיל
הוכיחו כי .
פתרון
דרך גרירות לוגיות:
בצד הימני הוספנו סתירה בעזרת הקשר "או" ולכן נשארנו עם ביטוי שקול. כעת נשתמש בחוק הפילוג של הלוגיקה:
וזה בדיוק מה שרצינו.
הוכחה בעזרת הכלה דו כיוונית:
בכיוון () נניח אזי
בכיוון () נניח אזי
(כי אם אזי סתירה)
משלים
הגדרה: תהי קבוצה , ונביט בתת קבוצה שלה . ניתן להגדיר את המשלים של כאוסף האיברים ב- שאינם ב- (כלומר ההפרש ), המסומן . לא ניתן לדבר על משלים אוניברסלי ללא מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל).
תכונות בסיסיות:
על המשלימים מתקיימים חוקי דה מורגן (הנובעים ישירות מחוקי דה מורגן בלוגיקה):
הערה: באופן כללי מתקיים
הגדרה: תהי קבוצה . נגדיר את קבוצת החזקה של בתור אוסף כל תת הקבוצות של . נסמן .
דוגמה:
אזי .
האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה?
תרגיל ממבחן
יהיו A,B,C קבוצות. הוכיחו/הפריכו:
א. אם אזי
ב. אם אזי
ג. אם אזי
פתרון
א. הפרכה: . אזי ברור שA איננה מוכלת בחיתוך של B וC אבל
ב. נתון שלכל מתקיים . אזי
כעת, הצד הימני הוא טאוטולוגיה וניתן להסיר אותו. מכיוון שנתון ניתן להסיק בקלות ש כפי שרצינו.
דרך נוספת: נגדיר את B להיות הקבוצה האוניברסאלית ואז צריך להוכיח כי וזה אכן נכון!
ג. נניח בשלילה ש. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה השייכת לחיתוך . קבוצות החזקה הן אוסף תת הקבוצות, ולכן . מכיוון שC אינה ריקה קיים בה איבר וקל מאד לראות ש ולכן c מוכל בחיתוך בסתירה לכך שהחיתוך ריק.