הבדלים בין גרסאות בדף "תרגול 6 תשעז"
שורה 9: | שורה 9: | ||
דרך גרירות לוגיות: | דרך גרירות לוגיות: | ||
− | <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>x\in A\cap (B\setminus C) \iff</math> |
+ | <math>(x\in A) \and [(x\in B) \and (x\notin C)] \iff</math> | ||
+ | <math>[(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</math> | |
− | + | <math>[(x\in A) \and (x\in B)]\and \neg [(x\in C)\and(x\in 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>\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> | ||
+ | |||
<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> | ||
+ | |||
<math>x\in (A\cap B) \backslash (A\cap C)</math> | <math>x\in (A\cap B) \backslash (A\cap C)</math> | ||
שורה 32: | שורה 33: | ||
<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> | ||
+ | |||
<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> | ||
+ | |||
(כי אם <math>x\in C</math> אזי <math>x\in A\cap C</math> סתירה) | (כי אם <math>x\in C</math> אזי <math>x\in A\cap C</math> סתירה) | ||
+ | |||
<math>x\in A\cap(B\backslash C)\Leftarrow </math> | <math>x\in A\cap(B\backslash C)\Leftarrow </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>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> מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל). | ||
שורה 53: | שורה 57: | ||
* <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</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,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> | ||
שורה 73: | שורה 77: | ||
===פתרון=== | ===פתרון=== | ||
− | א. '''הפרכה''': <math>A=\{1,2\},B=\{1\},C=\{2\}</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)\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> כפי שרצינו. |
גרסה מ־18:36, 23 בנובמבר 2017
חזרה לדף מערכי התרגול.
תוכן עניינים
המשך קבוצות
תרגיל
הוכיחו כי .
פתרון
דרך גרירות לוגיות:
בשורה האחרונה הוספנו סתירה בעזרת הקשר "או" ולכן נשארנו עם ביטוי שקול. כעת נשתמש בחוק הפילוג של הלוגיקה:
וזה בדיוק מה שרצינו.
הוכחה נוספת בעזרת הכלה דו כיוונית:
בכיוון () נניח אזי
בכיוון () נניח אזי
(כי אם אזי סתירה)
משלים
הגדרה: תהי קבוצה , ונביט בתת קבוצה שלה . ניתן להגדיר את המשלים של כאוסף האיברים ב- שאינם ב- (כלומר ההפרש ), המסומן . לא ניתן לדבר על משלים אוניברסלי ללא מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל).
תכונות בסיסיות:
על המשלימים מתקיימים חוקי דה מורגן (הנובעים ישירות מחוקי דה מורגן בלוגיקה):
הערה: באופן כללי מתקיים
קבוצת החזקה
הגדרה: תהי קבוצה . נגדיר את קבוצת החזקה של בתור אוסף כל תת הקבוצות של . נסמן .
דוגמה: נבחר אזי .
האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה? הוכיחו זאת באינדוקציה.
תרגיל ממבחן
תהינה קבוצות. הוכיחו או הפריכו:
א. אם אזי
ב. אם אזי
ג. אם אזי
פתרון
א. הפרכה: . אזי ברור ש- איננה מוכלת בחיתוך אבל
ב. נתון שלכל מתקיים . אזי
כעת, הצד הימני הוא טאוטולוגיה וניתן להסיר אותו. מכיוון שנתון ניתן להסיק בקלות ש כפי שרצינו.
דרך נוספת: נגדיר את B להיות הקבוצה האוניברסאלית ואז צריך להוכיח כי וזה אכן נכון!
ג. נניח בשלילה ש. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה השייכת לחיתוך . קבוצות החזקה הן אוסף תת הקבוצות, ולכן . מכיוון שC אינה ריקה קיים בה איבר וקל מאד לראות ש ולכן c מוכל בחיתוך בסתירה לכך שהחיתוך ריק.