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

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

1. (א ∩ ב)^ג = א^ג U ב^ג.
2. (א U ב)^ג = א^ג ∩ ב^ג.

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

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

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

• צומת הסטים א ו ב מורכב מכל האלמנטים המשותפים לשניהם א ו ב. צומת מצוין על ידי א ∩ ב.
• איחוד הסטים א ו ב מורכב מכל האלמנטים שבאף אחד מהם א או ב, כולל האלמנטים בשתי הקבוצות. הצומת נקרא על ידי A U B.
• השלמת הסט א מורכב מכל האלמנטים שאינם אלמנטים של א. השלמה זו מציינת על ידי A^ג.

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

1. (א ∩ ב)^ג = א^ג U ב^ג
2. (א U ב)^ג = א^ג ∩ ב^ג

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

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

• ההשלמה א^ג = [0, 1) U (3, 5]
• ההשלמה ב^ג = [0, 2) U (4, 5]
• האיחוד א U ב = [1, 4]
• הצומת א ∩ ב = [2, 3]

אנו מתחילים בחישוב האיחוד א^ג U ב^ג. אנו רואים שהאיחוד של [0, 1) U (3, 5] עם [0, 2) U (4, 5] הוא [0, 2) U (3, 5]. הצומת א ∩ ב הוא [2, 3]. אנו רואים כי השלמה של קבוצה זו [2, 3] היא גם [0, 2) U (3, 5]. בדרך זו הוכחנו א^ג U ב^ג = (א ∩ ב)^ג.

כעת אנו רואים את הצומת של [0, 1) U (3, 5] עם [0, 2) U (4, 5] הוא [0, 1) U (4, 5]. אנו רואים גם כי השלמה של [1, 4] היא גם [0, 1) U (4, 5]. בדרך זו הוכחנו א^ג ∩ ב^ג = (א U ב)^ג.

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

חוקי דה מורגן נקראים על שם אוגוסטוס דה מורגן, שחי בין השנים 1806-1871. אף על פי שלא גילה חוקים אלה, הוא היה הראשון שהציג הצהרות אלה באופן רשמי באמצעות ניסוח מתמטי בלוגיקה הצעתית.