כללי דה מורגן

כללי דה מורגן, הקרויים על-שמו של המתמטיקאי והלוגיקן בן המאה ה-19, אוגוסטוס דה מורגן, הם שני כללים בלוגיקה, בתורת הקבוצות ובאלגברה בוליאנית (בפרט, לוגיקה בוליאנית), הקושרים את הפעולות הבסיסיות בתחומים אלה.
* לוגיקה: הכללים קושרים את הפעולות "או", "גם", "לא". באופן מילולי בכתיב לא פורמלי, קובעים הכללים כי השלילה של- קיום א' וגם קיום ב', היא אי קיום א' או אי קיום ב'; וכן כי השלילה של קיום א' או קיום ב', היא אי קיום א' וגם אי קיום ב'.
בכתיב פורמלי הם מוצגים כך:
:<math>\neg(P\wedge Q)\equiv(\neg P)\vee(\neg Q)</math>

:<math>\neg(P\vee Q)\equiv(\neg P)\wedge(\neg Q)</math>
לדוגמה, המשפט "היום לא יום ראשון או שלא יורד עכשיו גשם" שקול לוגית למשפט: "לא נכון ש'היום יום ראשון וגם יורד עכשיו גשם'"
{|class="wikitable" style="float:left; text-align:center;"
|-
150px
|-

|-
|colspan="3"| הדגמה של אחד הכללים בעזרת דיאגרמת ון. שתי התמונות העליונות הן המשלימים של הקבוצות המיוצגות על ידי המעגלים. התמונה התחתונה מייצגת את החיתוך שלהן- השטח המשותף שלהן
|}
* תורת הקבוצות: הכללים קושרים את הפעולות "איחוד", "חיתוך", "משלים". בכתיב פורמלי הם מוצגים כך:
:<math>(A\cap B)^C=A^C\cup B^C</math>

:<math>(A\cup B)^C=A^C\cap B^C</math>

ובאופן כללי: <math>\ \left(\bigcup_{} A_i \right )^C = \bigcap_{} A_i^C</math>, ו-<math>\ \left(\bigcap_{} A_i \right )^C = \bigcup_{} A_i^C</math>
* אלגברה בוליאנית: הכללים קושרים את הפעולות "חיבור", "כפל", "שלילה".
:בהתאם להגדרת השלילה, הביטוי '(P+Q) הוא שלילת הביטוי (P+Q), ועל כן יקבל ערך אמת רק אם P+Q הוא בעל ערך 0, כלומר ערך שקרי. כללי דה מורגן קובעים כי שלילת P+Q זהה למכפלת שלילת P בשלילת Q, ואילו שלילת P*Q זהה לחיבור שלילת P עם שלילת Q. בכתיב פורמלי הם מוצגים כך:
:<math>(P+Q)^{\prime}=P'\cdot Q'</math>

:<math>\!\,(P\cdot Q)'=P'+Q'</math>

או כך:

:<math>\overline{p + q}=\bar{p}\cdot \bar{q}</math>

:<math>\overline{p \cdot q}=\bar{p} + \bar{q}</math>

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

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

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

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

==הוכחה==
ההוכחה של כללי דה-מורגן מתבצעת באינדוקציה שלמה. כלומר, הצבה של כל הצירופים האפשריים בכל אחד מהפסוקים, נותנת ערכים שווים. כך, אם נציב ערכי אמת ב-P וב-Q, אזי הביטוי (P+Q) יקבל את הערך "אמת" והביטוי '(P+Q), ערכו יהי שקר, כמו גם ערכו של 'p'*q. לאחר הצבת כל הצירופים האפשריים של P ו-Q מתקבל, למעשה, הכלל.

הכלל בנוגע לתורת הקבוצות, ניתן להוכחה על נקלה בעזרת הכללים הנ"ל, זאת, בהינתן ההגדרות של חיתוך, איחוד ומשלים של קבוצה.
ההוכחה היא כדלהלן:
<div style="direction: ltr;">
<math>
a\in(A\cap B)^C
</math>

<math>
\iff a\not \in (A\cap B)
</math>

<math>
\iff \neg (a\in (A\cap B))
</math>

<math>
\iff \neg (a\in A \wedge a\in B)
</math>

<math>
\iff (a\not \in A) \vee (a \not \in B)
</math>

<math>
\iff a \in A^C \vee a \in B^C
</math>

<math>
\iff a \in A^C\cup B^C
</math></div>
ובצורה דומה מוכח גם המשפט השני.
==קישורים חיצוניים==
* 

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