תורת הקבוצות/פעולות בסיסיות

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

תוכן עניינים

1 מושג הקבוצה
2 יחסים בין קבוצות
3 קבוצות חשובות
- 3.1 הקבוצה הריקה
- 3.2 קבוצות נוספות
4 פעולות על קבוצות

[עריכה] מושג הקבוצה

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

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

קבוצה ניתן להגדיר ע"י שתי דרכים עיקריות. אחת היא למנות את כל איברי הקבוצה כש "{}" הוא הסימון המקובל ובין איבר לאיבר נהוג לשים ",". לדוגמא: {שולחן, כיסא, בית}, {a,b,c,d,e,f} ,{1,2,3,4}. יש לציין שאין חשיבות לסדר כך ש {1,2,3} = {3,2,1} = {1,3,2} = {2,3,1} וכו'. כמו כן, אם איבר מופיע פעמיים באותו קבוצה אין לכך כל משמעות, שכן איבר שייך לקבוצה או שאינו שייך לקבוצה, אך אין משמעות למושג שייך כמה פעמים לקבוצה. כך ש {1,2,3} = {1,1,2,3} = {2,1,2,1,3,3,1,1,1,2} וכו.

צורה נוספת להגדרת קבוצה היא על ידי למנות כלל כפי שראינו קודם. לדוגמא: {כל המספרים הגדולים מ 1} {כל הילדים בישראל מתחת לגיל 10} {כל החפצים בבית שלי}. יש כמובן לדאוג שהקבוצה מוגדרת היטב. לעיתים בהגדרת קבוצות אין סופיות אנו רושמים מספר איברים ראשונים כך שהכלל המגדיר את הקבוצה ברור ובסוף מוסיפים "...". לדוגמא: ברור ש {,1,2,3,4...} היא קבוצת כל המספרים הטבעיים (המספרים השלמים החיובים). אם זאת עבור {1,3,5...} לא נוכל לדעת האם מדובר בכל המספרים האי זוגיים או אולי בכל המספרים האי זוגיים הראשוניים. על כן גם כשאנו מתארים קבוצה בצורה כזאת יש לשים לב שהקבוצה מוגדרת היטב.

חשוב לציין שאיברי הקבוצה יכולים למעשה להיות כל דבר - אפילו קבוצות אחרות. כך לדוגמה, נוכל להגדיר את הקבוצה ${1,2,{3,4}}$ , שהיא קבוצה המכילה שלושה איברים - המספרים 1 ו-2, והקבוצה ${3,4}$ . באותו אופן נוכל להגדיר קבוצות של קבוצות, כמו "קבוצת כל הקבוצות בעלות מספר סופי של איברים", או "קבוצת כל הקבוצות המכילות אך ורק מספרים".

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

לדוגמא: {כל המספרים השלמים בין 1 ל- 5} = {2,3,4} וכפי שציינו קודם = {2,2,4,3}. כך גם {כל החזירים בעלי הכנפיים} = {כל המספרים השלמים בין 1 ל 0} שכן בשני הקבוצות אין איברים.

כפי שציינו עבור כל קבוצה A כלשהי ועבור כל עצם x כלשהוא מתקיים אחד מהשנים:
x איבר ב A, ומסמנים: $x \in A$ .
.( נאמר גם שx שייך ל- A או x ב- A.)

x אינו איבר ב A, ומסמנים: $x \not\in A$
. ( נאמר גם שx אינו שייך ל- A או x אינו ב- A.)

נהוג לסמן קבוצות באותיות לטיניות גדולות A B C ואיברים כאותיות לטיניות קטנות a b c.

לבסוף נראה צורה נוספת לכתיבת הגדרה של קבוצה שמקובלת במתמטיקה:
הקבוצה {x מספר שלם הגדול מ 1| 2x} היא קבוצת כל המספרים 2x כאשר x הוא מספר שלם הגדול מ 1 והוא שווה לקבוצה {2,4,6,8...} ולקבוצה {כל המספרים הזוגיים החיוביים}.

[עריכה] יחסים בין קבוצות

נגדיר כמה יחסים בין קבוצות: הכלה, הכלה ממש ושיוויון.

[עריכה] שוויון קבוצות

הגדרה 1.1: תהיינה קבוצות A,B. אז נאמר כי A שווה ל-B אם לכל איבר x מתקיים: $x\in A \iff x \in B$ .

ברור לנו לפי ההגדרה שאכן A = A עבור כל קבוצה A. בנוסף ניתן לראות שכדי להוכיח ש A שווה ל B ניתן להראות שכל איבר של A הוא איבר של B, כלומר A חלקית ל B ולהראות גם ש B חלקית ל A. ובכדי להראות ששתי קבוצות אינן שוות מספיק להצביע על איבר כלשהו השייך לאחת הקבוצות אך לא לשניה.

דוגמא: הראנו קודם לכן כמה דוגמאות לקבוצות שוות. כעת נוכל ע"פ ההגדרה המדיוקת לבחון שאכן אלו קבוצות שוות. לדוגמא אמרנו שהקבוצה {1,2,3,4} = {כל המספרים השלמים בין 0 ל-5}. עכשיו נוכל לבחון את הטענה לפי ההגדרה. אנו רואים ש $1 \in\{ 1,2,3,4 \}$ וגם ש $2 \in \{ 1,2,3,4 \}$ וכך גם 3 ו-4. נבחן את {כל המספרים השלמים בין 0 ל- 5 (הגדולים מ 0 וקטנים מ 5)} ולשם הנוחיות נסמן קבוצה זו ב- Q. נבחן את 1 ונראה ש- 1 הוא אכן מספר שלם הגדול מ 0 וקטן מ 5, לכן $1 \in Q$ . נבדוק ונראה שגם $2,3,4 \in Q$ . אז כל איבר ב {1,2,3,4} הוא גם איבר ב Q לכן נאמר ש- $\{ 1,2,3,4 \} \subseteq Q$ .נבדוק אילו הם האיברים השלמים בין 0 ל-5 ונראה שאלו אך ורק 1,2,3 ו-4 וכמובן $1,2,3,4 \in\{ 1,2,3,4 \}$ כלומר $Q \subseteq \{1,2,3,4\}$ אז לפי ההגדרה של קבוצות שוות אם $\{1,2,3,4\} \subseteq Q$ וגם $Q \subseteq \{1,2,3,4\}$ אז ${1,2,3,4} = Q$ כמו ששיערנו בהתחלה.

[עריכה] קבוצה חלקית (הכלה)

הגדרה 1.2: יהיו A ו-B קבוצות כלשהן. נאמר ש A היא קבוצה חלקית ל B אם ורק אם עבור כל x כלשהו:
אם $x \in A$ אז $x \in B$ .
נסמן A חלקית ל B ב $A \subseteq B$ . נאמר גם A מוכלת ב- A, B תת-קבוצה של B ו B מכילה את A.

במילים אחרות אם $A \subseteq B$ אז כל איבר ב A הוא איבר ב -B, או A הוא חלק מ- B. נדגיש כמה דברים המסתמנים מההגדרה. אם $A \subseteq B$ ואם ידוע שאיבר כלשהוא הוא איבר ב- A אז ידוע גם שהוא איבר ב-B. יש לשים לב שההפך אינו נכון, כלומר אם $A \subseteq B$ ואיבר שייך ל- B אז הוא לא בהכרח גם שייך ל A.

אם A אינה חלקית ל- B נסמן $A \not\subseteq B$ . שים לב שמספיק למצוא איבר אחד ב A שאינו איבר ב- B על מנת להוכיח ש $A \not\subseteq B$ .

משפט 1.1: תהי קבוצה כלשהי A. אז $A \subseteq A$ . במילים אחרות כל קבוצה חלקית לעצמה.

הוכחה 1.1: תהיה A קבוצה כלשהי. אם $x \in A$ כלשהי, אז בוודאי ש $x \in A$ על כן $A \subseteq A$ , לפי הגדרת קבוצה חלקית.

משפט 1.2: תהיינה קבוצות A,B. אז $A = B$ אם ורק אם $A\subseteq B \wedge B\subseteq A$ . במילים אחרות, על מנת להוכיח שוויון בין קבוצות, מספיק להוכיח שכל אחת מהקבוצות מוכלת באחרת.

הוכחה 1.2: המשפט נובע ישירות מההגדרות של שוויון ושל הכלה. אם $A = B$ אז לכל $x\in A$ מתקיים $x\in B$ , כלומר $A\subseteq B$ , ובאותו אופן גם $B\subseteq A$ . מצד שני, אם $A\subseteq B$ וגם $B\subseteq A$ , אז לכל $x\in A$ מתקיים $x\in B$ ולהיפך, ולכן $A = B$ .

[עריכה] הכלה ממש

הגדרה 1.3: נאמר על שתי קבוצות כלשהן A ו- B ש A חלקית ממש ל- B אם ורק אם: $A \subseteq B$ וגם $A \neq B$ . נסמן $A \subset B$ . נאמר גם A מוכלת ממש ב- B, או B מכילה ממש את A.

שימו לב שפירוש הדבר הוא שאם $A \subset B$ אז בהכרח $B \not\subseteq A$ . כלומר אם נרצה להראות ש $A \subset B$ נראה שכל איבר ב A הוא איבר B אבל שקיים איבר אחד לפחות ב- B שאינו איבר ב- A.

כמובן שגם כאן נוכל לדבר על שתי קבוצות כך ש B אינה מכילה ממש את A. נסמן $A \not\subset B$ . מהגדרת קבוצה חלקית ממש מסתמן שקבוצה A אינה חלקית ממש ל B אם ורק אם $A \not\subseteq B$ או $A \ne B$ .

[עריכה] ההבדל בין שייכות והכלה

נשים לב שקיים הבדל משמעותי בין שייכות של איבר לקבוצה, ובין הכלה של קבוצה בקבוצה אחרת. נביט לדוגמה על הקבוצה שהבאנו בדוגמה קודם: $A = {1,2,{3,4}}$ . כפי שאמרנו, קבוצה זו מכילה שלושה איברים - המספרים 1 ו-2, והקבוצה ${3,4}$ . המספר 3, לדוגמה, אינו איבר ב-A (הוא איבר בקבוצה שהיא איבר ב-A).

לכן, מתקיים $\{3,4\}\in A$ , אך לא מתקיים $\{3,4\}\subseteq A$ , משום שאיברים הקבוצה ${3,4}$ אינו איברים ב-A.

כמובן, ייתכן מצב שקבוצה גם תהיה מוכלת בקבוצה אחרת, וגם תהיה איבר בה. לדוגמא, נגדיר את הקבוצה $A = {1,{1}}$ . קל לראות ש- $\{1\}\in A$ וגם $\{1\}\subseteq A$ .

[עריכה] קבוצות חשובות

ישנן קבוצות במתמטיקה שעושים בהם שימוש תדיר, על כן הוגדרו להן סימנים מיוחדים.

[עריכה] הקבוצה הריקה

הגדרה 1.4: הקבוצה הריקה המסומנת באות היוונית $\empty$ היא הקבוצה ללא איברים. עמדנו קודם לכן שהקבוצה {כל המספרים השלמים בין 0 ל- 1} = {כל החזירים בעלי הכנפיים}. לפי הגדרת שיוון קבוצות ניתן לראות שאכן קבוצות אלו שוות שכן אין בהם כל איבר אז וודאי שכל איבר באחד הוא איבר בשני. שני קבוצות אלו שוות ל- $\empty$ . נדגיש שאין אנו מדברים על קבוצות ריקות אלה על הקבוצה הריקה $\empty$ , כל קבוצה ללא איברים היא הקבוצה הריקה.

משפט (משפט 1.2): עבור כל קבוצה A אז $\empty \subseteq A$ , ועבור כל קבוצה B כך ש $B \ne \empty$ אז $\empty \subset B$ , או במילים כל קבוצה מכילה את הקבוצה הריקה, וכל קבוצה שאינה הקבוצה הריקה מכילה ממש את הקבוצה הריקה.
הוכחה (משפט 1.2): תהיה A קבוצה כלשהי. נניח בשלילה ש $\empty \not\subseteq A$ אז קיים איבר כלשהו ב $\empty$ שאינו איבר ב A. אבל זה עומד בסתירה להגדרתו של $\empty$ כקבוצה ללא איברים, לכן לא יתכן ש $\empty \not\subseteq A$ שכן זה יוצר סתירה, אז אנו מסיקים שבהכרח עבור כל קבוצה A מתקיים $\empty \subseteq A$ .
תהיה B קבוצה כך ש $\empty \ne B$ . הראנו קודם ש $\empty \subseteq B$ . לפי הגדרת $\empty$ אנו מסיקים של- B יש איבר כלשהו שאינו איבר ב $\empty$ , אז $B \not\subseteq \empty$ , ולכן בוודאי $\empty \ne B$ . לפי הגדרת קבוצה חלקית ממש אם $\empty \subseteq B$ וגם $B \ne \empty$ אז $\empty \subset B$ .

[עריכה] קבוצות נוספות

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

קבוצת כל המספרים הטבעיים: היא קבוצת כל המספרים השלמים החיוביים, והיא מסומנת $\mathbb{N}$ ומוגדרת {x מספר שלם חיובי |x} או {1, 2, 3, 4, 5, 6...}. שים לב שלפי ההגדרה $0 \not\in \mathbb{N}$ , (נציין שיש מקומות שםמקובל ש O הוא כן איבר בקבוצה.) את קבוצת המספרים הטביעיים ואפס נרשום: $\mathbb{N}^0$ המוגדר {x מספר חיובי שלם או x שווה ל-0 |x} או {...0,1,2,3,4,5}.

קבוצת כל המספרים השלמים: היא קבוצת כל המספרים השלמים (חיובים, שליליים ואפס). היא מסומנת $\mathbb{Z}$ ומוגדרת { x מספר שלם |x} או {...- 4,-3,-2 ,-1, 0, 1, 2, 3, 4...}.

קבוצת כל המספרים הרציונאלים: מספר רציונלי הוא מספר שניתן להציגו כ $\frac{x}{y}$ כאשר $x,y \in \mathbb{Z}$ . את קבוצת המספרים הרציונלים מסמנים ב $\mathbb{Q} = \left\{\frac{x}{y}\ |\ x,y \in \mathbb{Z}, y\ne 0\right\}$ .

קבוצת כל המספרים הרציונאלים החיוביים: היא הקבוצה $\mathbb{Q}^+ = \left\{\frac{x}{y}\ | \frac{x}{y}\ > 0\ and\ x,y \in \mathbb{Z}, y\ne 0 \right\}$

קבוצת כל המספרים הממשיים: הגדרה של קבוצה זו בצורה פורמלית היא לא פשוטה. נאמר בקצרה שמספר ממשי הוא מספר רציונלי או אי-רציונלי. בהפשטה מספר אי רציונלי הוא מספר שאנחנו יכולים לכתוב אותו בתור שבר עשרוני אין-סופי ( כשבכתיבתו אין מבנה ) אך לא כשבר פשוט. כל מספר אי-רציונלי נמצא בין שני מספרים שלמים. דוגמאות למספרים אי רציונלים הם $\sqrt{2}$ , $π$ . קבוצת המספרים הממשיים מסומנת ב- $\mathbb{R}$

קבוצת כל המספרים הממשיים מלבד 0: $\mathbb{R}^0$

קבוצת כל המספרים הממשיים החיוביים: $\mathbb{R}^+$

קבוצת כל המספרים הממשיים החיוביים בלי הספרה 0: $\mathbb{R}^++$

קבוצת כל המספרים המרוכבים: $\mathbb{C}$

[עריכה] פעולות על קבוצות

[עריכה] איחוד קבוצות

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

הגדרה 1.5: תהיינה A,B קבוצות כלשהן. לכל איבר x, מתקיים: $x\in A\cup B$ אם ורק אם $x\in A$ או $x\in B$ . בניסוח מתמטי: $A\cup B = \{x|x\in A \vee x\in B\}$ .

מעצם ההגדרה, ברור כי אין חשיבות לסדר הקבוצות. כלומר, $A\cup B = B\cup A$ .

משפט 1.3: תהיינה A,B קבוצות כלשהן. מתקיים: $A\subseteq A\cup B$ וגם $B\subseteq A\cup B$ .

הוכחה 1.3: נחזור להגדרה של הכלה (הגדרה 1.1). עלינו להראות שלכל x, אם $x\in A$ אז $x\in A\cup B$ . אך טענה זו נובעת ישירות מההגדרה של איחוד, ולכן $A\subseteq A\cup B$ . ההוכחה עבור B זהה.

משפט 1.4: תהיינה A,B קבוצות כלשהן, המקיימות $A\subseteq B$ . מתקיים: $A \cup B = B$ .

הוכחה 1.4: על מנת להוכיח שוויון בין קבוצות, עלינו להראות הכלה משני הכיוונים, כלומר $B\subseteq A\cup B$ וגם $A\cup B\subseteq B$ . הכיוון הראשון נובע ממשפט 1.3. על מנת להוכיח את הכיוון השני, יהי איבר x המקיים $x\in A\cup B$ . לפי הגדרת האיחוד (הגדרה 1.5), מתקיים $x\in A$ או $x\in B$ . כיוון ש- $A\subseteq B$ , אם $x\in A$ אז $x\in B$ , ולכן בשני המקרים $x\in B$ . לכן $A\cup B\subseteq B$ .

מסקנה 1.5: לכל קבוצה A, מתקיים: $A\cup A = A\cup \emptyset = A$ .

הוכחה 1.5: ממשפט 1.2 מתקיים $\emptyset \subseteq A$ , ולכן לפי משפט 1.4 מתקיים $A\cup \emptyset = A$ . ממשפט 1.1 מתקיים $A\subseteq A$ , ולכן שוב לפי משפט 1.4 מתקיים $A\cup A = A$ .

[עריכה] איחוד מורחב

כפי שהגדרנו איחוד של שתי קבוצות, נוכל גם להגדיר איחוד של שלוש קבוצות: $A\cup B\cup C = (A\cup B) \cup C = \{x|x\in A \vee x\in B\vee x\in C\}$ . באופן זה ניתן להרחיב את ההגדרה גם לאיחוד של 4 קבוצות, 5 קבוצות וכן הלאה.

בהינתן אוסף של קבוצות $\mathfrak{F}$ , נגדיר את האיחוד של הקבוצות כקבוצת האיברים שמופיעים באחת מהקבוצות. כלומר: $\bigcup_{A \in \mathfrak{F}} A = \{x : \exists A\in\mathfrak{F}: x\in A\}$ .

[עריכה] חיתוך קבוצות

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

הגדרה 1.6: תהיינה A,B קבוצות כלשהן. לכל איבר x, מתקיים: $x\in A\cap B$ אם ורק אם $x\in A$ וגם $x\in B$ . בניסוח מתמטי: $A\cap B = \{x|x\in A \wedge x\in B\}$ .

מעצם ההגדרה, ברור כי אין חשיבות לסדר הקבוצות. כלומר, $A\cap B = B\cap A$ .

משפט 1.6: תהיינה A,B קבוצות כלשהן. מתקיים: $A\cap B\subseteq A$ וגם $A\cap B\subseteq B$ .

הוכחה 1.6: נחזור להגדרה של הכלה (הגדרה 1.1). עלינו להראות שלכל x, אם $x\in A\cap B$ אז $x\in A$ . טענה זו נובעת ישירות מההגדרה של חיתוך, ולכן $A\cap B\subseteq A$ . ההוכחה עבור B זהה.

משפט 1.7: תהיינה A,B קבוצות כלשהן, המקיימות $A\subseteq B$ . מתקיים: $A \cup B = A$ .

הוכחה 1.7: על מנת להוכיח שוויון בין קבוצות, עלינו להראות הכלה משני הכיוונים, כלומר $A\subseteq A\cap B$ וגם $A\cap B\subseteq A$ . הכיוון השני נובע ממשפט 1.6. על מנת להוכיח את הכיוון הראשון, יהי איבר $x\in A$ . כיוון ש- $A\subseteq B$ , מתקיים $x\in B$ , ולכן לפי הגדרת האיחוד $x\in A\cap B$ .

מסקנה 1.8: לכל קבוצה A, מתקיים: $A\cap \emptyset = \emptyset, A\cap A = A$ .

הוכחה 1.8: ממשפט 1.2 מתקיים $\emptyset \subseteq A$ , ולכן לפי משפט 1.7 מתקיים $A\cap \emptyset = \emptyset$ . ממשפט 1.1 מתקיים $A\subseteq A$ , ולכן שוב לפי משפט 1.7 מתקיים $A\cap A = A$ .

[עריכה] חיתוך מורחב

כפי שהגדרנו חיתוך של שתי קבוצות, נוכל גם להגדיר חיתוך של שלוש קבוצות: $A\cap B\cap C = (A\cap B) \cap C = \{x|x\in A \wedge x\in B\wedge x\in C\}$ . באופן זה ניתן להרחיב את ההגדרה גם לחיתוך של 4 קבוצות, 5 קבוצות וכן הלאה.

בהינתן אוסף של קבוצות $\mathfrak{F}$ , נגדיר את החיתוך של הקבוצות כקבוצת האיברים שמופיעים בכל אחת מהקבוצות. כלומר: $\bigcup_{A \in \mathfrak{F}} A = \{x : \forall A\in\mathfrak{F}: x\in A\}$ .

[עריכה] הפרש בין קבוצות

[עריכה] כללי דה מורגן

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

$\overline{A\cap {B}}=\overline{A}\cup\overline{B}$
$\overline{A\cup {B}}=\overline{A}\cap\overline{B}$

[עריכה] הוכחת חוקי דה-מורגן

כעת נדגים הוכחה בתורת הקבוצות, ובד בבד, גם נוכיח את הכללים החשובים של דה-מורגן.
הוכחה: נתחיל בחוק הראשון. נבחר אבר כלשהו, $x\in \overline{A\cap{B}}$ (כלומר איבר במשלים של קבוצת החיתוך). לפי ההגדרה, $\;x$ אינו בד-בבד ב- $\;A$ וב- $\;B$ (כי הוא במשלים) אז יש רק 3 אופציות.

יתכן ש- $\;x\in {A}$ וגם $\;x\not\in {B}$ .
יתכן ש- $\;x\in {B}$ וגם $\;x\not\in {A}$ .
יתכן ש- $\;x\not\in {A}$ וגם $\;x\not\in {B}$ .

מתוך 1 נובע ש- $\;x \in \overline{B}$ ולכן בפרט גם באיחוד $\overline{A}\cup{\overline{B}}$ .
מתוך 2 נובע ש- $\;x\in {\overline{A}}$ ולכן בפרט גם באיחוד $\overline{A}\cup{\overline{B}}$ .
מתוך 3 ברור ש - $x\in\overline{A}\cup{\overline{B}}$ ממש מתוך ההגדרה.
מה שקיבלנו זה ש- $\overline{A \cap{B}}\subseteq{\overline{A}\cup\overline{B}}$ . לא נותר אלא להראות את ההכלה בכיוון השני.
נבחר אבר כלשהו, $x\in \overline{A}\cup\overline{B}$ . לפי ההגדרה, $x\in \overline{A}$ או $x\in \overline{B}$ (או שניהם) ולכן יש 3 אופציות:

יתכן ש- $\;x\in \overline{A}$ .
יתכן ש- $\;x\in \overline{B}$ .
יתכן ש-1 וגם 2 מתקיימים בו-זמנית.

אם מתקיים 1, אז בהכרח $\;x\not\in A$ מכאן בפרט, $\;x\not\in A\cap{B}$ (למה?). לכן ברור ש- $x\in \overline{A\cap{B}}$ . באופן סימטרי גם עבור 2 ו-3 $x\in \overline{A\cap{B}}$ מאותם שיקולים. הראנו הכלה בכיוון ההפוך כלומר, $\overline{A\cap{B}}\supseteq{\overline{A}\cup{\overline{B}}}$ ולכן לפי ההגדרה גם $\overline{A\cap{B}}=\overline{A}\cup{\overline{B}}$ כנדרש.