כללי דה מורגן

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

• לוגיקה: הכללים קושרים את הפעולות "או", "גם", "לא". באופן מילולי בכתיב לא פורמלי, קובעים הכללים כי השלילה של קיום א' וגם קיום ב', היא אי-קיום א' או אי-קיום ב'; וכן כי השלילה של קיום א' או קיום ב', היא אי-קיום א' וגם אי-קיום ב'.

בכתיב פורמלי הם מוצגים כך:

${\begin{aligned}\neg (P\lor Q)&=(\neg P)\land (\neg Q)\\\neg (P\land Q)&=(\neg P)\lor (\neg Q)\end{aligned}}$

למשל, המשפט "היום לא יום ראשון או שלא יורד עכשיו גשם" שקול לוגית למשפט: "לא נכון ש'היום יום ראשון וגם יורד עכשיו גשם'"

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

• תורת הקבוצות: הכללים קושרים את הפעולות "איחוד", "חיתוך", "משלים":

${\begin{aligned}(A\cup B)^{c}&=A^{c}\cap B^{c}\\(A\cap B)^{c}&=A^{c}\cup B^{c}\end{aligned}}$

ובאופן כללי: $\left(\bigcup A_{i}\right)^{c}=\bigcap A_{i}^{c}\ ,\ \left(\bigcap A_{i}\right)^{c}=\bigcup A_{i}^{c}$

• אלגברה בוליאנית: הכללים קושרים את הפעולות "חיבור", "כפל", "שלילה".

בהתאם להגדרת השלילה, הביטוי $(P+Q)'$ הוא שלילת הביטוי $P+Q$ , ועל כן יקבל ערך אמת רק אם $P+Q$ הוא בעל ערך 0, כלומר ערך שקרי.

כללי דה-מורגן קובעים כי שלילת $P+Q$ זהה למכפלת שלילת $P$ בשלילת $Q$ , ואילו שלילת $P\cdot Q$ זהה לחיבור שלילת $P$ עם שלילת $Q$ .

${\begin{aligned}(P+Q)'&=P'\cdot Q'\\(P\cdot Q)'&=P'+Q'\end{aligned}}$

או כך:

${\begin{aligned}{\overline {P+Q}}&={\bar {P}}\cdot {\bar {Q}}\\{\overline {P\cdot Q}}&={\bar {P}}+{\bar {Q}}\end{aligned}}$

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

שימוש בכללי דה-מורגן

לכללים אלה מספר שימושים, ביניהם:

1. פישוט של ביטויים מתחומי הלוגיקה והמתמטיקה המתוארים לעיל.
2. פישוט התניות בעת כתיבת תוכניות מחשב.
3. שימוש באלקטרוניקה ספרתית (בה במקרים רבים נעשה שימוש בשתי רמות מתח בלבד) לצורכי פישוט תכנונם של מעגלים חשמליים, למשל, כאלה העושים שימוש בשערים לוגיים.
4. ניתן לעשות שימוש בכללים אלה לצורך ייצוג של ביטויים על ידי שימוש בסוג אחד בלבד של פעולות, למשל פעולות NAND. להרחבה ראו הערך NAND לוגי.

הוכחה

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

כך, אם נציב ערכי אמת ב-$P,Q$ כאחד, אזי הביטוי $P+Q$ יקבל ערך "אמת" והביטוי $(P+Q)'$ יקבל ערך "שקר", כמו גם ערכו של $P'\cdot Q'$ . לאחר הצבת כל הצירופים האפשריים של $P,Q$ מתקבל, למעשה, הכלל.

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

ההוכחה היא כדלהלן:

$${\begin{aligned}x\in (A\cap B)^{c}&\iff x\notin (A\cap B)\\&\iff \neg {\big (}x\in (A\cap B){\big )}\\&\iff \neg (x\in A\land x\in B)\\&\iff (x\notin A)\lor (x\notin B)\\&\iff (x\in A^{c})\lor (x\in B^{c})\\&\iff x\in (A^{c}\cup B^{c})\end{aligned}}$$

ובצורה דומה מוכח גם המשפט השני.

קישורים חיצוניים

• כללי דה מורגן, באתר MathWorld (באנגלית)   

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0