משלים וחוקי דה-מורגן

שעור שישי - משלים וחוקי דה-מורגן

כפי שמשתמע מן ההגדרה, לפעולות האיחוד והחיתוך יש משמעות לוגית. האיחוד של קבוצות הוא הקשר הלוגי "או", והחיתוך הוא הקשר "וגם". ביתר פירוט, אם A היא קבוצת האברים המקיימים תנאי מסויים בקבוצה X, ו-B היא קבוצת האיברים המקיימים תנאי אחר, אז האיחוד $\ A\cup B$ הוא קבוצת האיברים המקיימים את התנאי הראשון או את השני, והחיתוך $\ A\cap B$ הוא קבוצת האיברים המקיימים את התנאי הראשון וגם את השני. (ה"או" המתמטי הוא או שאינו מוציא: או זה, או זה, או שניהם).

לצד ה"או" וה"וגם", אנו זקוקים לפעולה בין קבוצות שתחקה את השלילה הלוגית. שימו לב שהשלילה היא פעולה אונארית (היא מתייחסת לטענה בודדת, והופכת אותה), בעוד ששני הקשרים האחרים הם בינאריים (הם קושרים שתי טענות, ולא אחת).

הגדרה. ההפרש $\ A-B$ הוא הקבוצה שאבריה הם האברים של A שאינם שייכים ל-B.

תרגיל. לכל שתי קבוצות A ו-B, ההפרש $\ A-B$ מוכל ב-A.

תרגיל. לכל קבוצה A, $\ A-A=\emptyset$ ו- $\ A-\emptyset =A$.

תרגיל. תן דוגמא המראה שפעולת ההפרש אינה אסוציאטיבית, כלומר, מצא שלוש קבוצות A,B ו-C כך ש- $\ A-(B-C)\neq (A-B)-C$.

ההפרש הוא פעולה בינארית. אם נקבע את ה"מרחב" X של האברים שבהם אנו מעוניינים לצורך הדיון ונחשב תמיד הפרש ביחס אליו, נקבל פעולה אונארית:

הגדרה. המשלים של קבוצה A, ביחס למרחב קבוע X, הוא קבוצת האברים של X שאינם ב-A. מסמנים את המשלים של $\ A$ ב-$\ {\overline {A}}$.

לתפקיד X אפשר לבחור את "קבוצת כל הדברים" (ואז המשלים של A הוא קבוצת כל הדברים שאינם ב-A). כל עוד מדובר בהתאמה הלוגית בין המשלים לבין קשר השלילה, זוהי בחירה סבירה; אבל כפי שנראה בהמשך, אפילו במסגרת תורת הקבוצות הנאיבית, "קבוצת כל הדברים" היא אובייקט מסוכן שיש להמנע ממנו.

תרגיל. המשלים מקיים את התכונות הבאות: $\ {\overline {\overline {A}}}=A$ ("לא לא A" הוא "A"); וכן $\ {\overline {\emptyset }}=X,{\overline {X}}=\emptyset$ (לא אמת הוא שקר, לא שקר הוא אמת).

חוקי דה-מורגן

במקום לומר "חתול אינו שייך לקבוצת הרהיטים, וגם אינו שייך לקבוצת החרקים המעופפים", אפשר לומר "החתול אינו שייך לקבוצת הדברים שהם או רהיטים, או חרקים מעופפים". את השקילות הזו (שיש לה בוודאי דוגמאות שימושיות יותר) אפשר לנסח כך: דבר-מה אינו P וגם אינו Q, אם ורק אם הוא אינו (P או Q). חוקי דה-מורגן מציגים את הכלל הלוגי הזה בשפה של קבוצות, ומבטאים את האופן שבו קושר המשלים את פעולות האיחוד והחיתוך: $\ {\overline {A\cup B}}={\overline {A}}\cap {\overline {B}}$, ו- $\ {\overline {A\cap B}}={\overline {A}}\cup {\overline {B}}$.

תרגיל. צייר דיאגרמות וון המוכיחות את חוקי דה-מורגן.

תרגיל (למשועממים). נסח גרסה של כללי דה-מורגן הנכונה ל-n קבוצות במקום שתיים, והוכח אותה באינדוקציה.

תרגיל (קל יותר). נניח שכל אברי האוסף $\ {\mathcal {A}}$ מוכלים בקבוצה X. הוכח את הגרסה הכללית ביותר של חוק דה-מורגן - המשלים של האיחוד על אברי האוסף הוא חיתוך המשלימים שלהם.

ההפרש הסימטרי

הפעולה הלוגית האחרונה שנתרגם לשפת תורת הקבוצות היא האו המוציא.

הגדרה. ההפרש הסימטרי של הקבוצות A ו-B הוא קבוצת האיברים הנמצאים באחת הקבוצות, אבל לא בשתיהן. את ההפרש הסימטרי מסמנים ב- $\ A\Delta B$.

תרגיל. הוכיחו ש- $\ A\Delta B=(A\cup B)-(A\cap B)=(A-B)\cup (B-A)$.

תרגיל. ההפרש הסימטרי מקיים את התכונות הבאות: $\ (A\Delta B)\Delta C=A\Delta (B\Delta C)$ (אסוציאטיביות); $\ A\Delta \emptyset =A$ (קיום איבר נייטרלי); $\ A\Delta A=\emptyset$ (קיום הופכי); $\ A\Delta B=B\Delta A$ (קומוטטיביות); $\ (A\Delta B)\cap C=(A\cap C)\Delta (B\cap C)$ (דיסטריבוטיביות ביחס לחיתוך).

<< השיעור הקודם - פעולות בין קבוצות

דף הקורס - תורת הקבוצות

השיעור הבא - קבוצת החזקה >>