כללי דה מורגן

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

  • לוגיקה: הכללים קושרים את הפעולות "או", "גם", "לא". בכתיב פורמלי הם מוצגים כך:
\neg(P\wedge Q)=(\neg P)\vee(\neg Q)
\neg(P\vee Q)=(\neg P)\wedge(\neg Q)
  • תורת הקבוצות: הכללים קושרים את הפעולות "איחוד", "חיתוך", "משלים". בכתיב פורמלי הם מוצגים כך:
(A\cap B)^C=A^C\cup B^C
(A\cup B)^C=A^C\cap B^C
  • אלגברה בוליאנית: הכללים קושרים את הפעולות "חיבור", "כפל", "שלילה".
בהתאם להגדרת השלילה, הביטוי '(P+Q) הוא שלילת הביטוי (P+Q), ועל כן יקבל ערך אמת רק אם P+Q הוא בעל ערך 0, כלומר ערך שקרי. כללי דה מורגן קובעים כי שלילת P+Q זהה למכפלת שלילת P בשלילת Q, ואילו שלילת P*Q זהה לחיבור שלילת P עם שלילת Q. בכתיב פורמלי הם מוצגים כך:
(P+Q)^{\prime}=P'\cdot Q'
\!\,(P\cdot Q)'=P'+Q'
למעשה, קשר זה זהה לחלוטין לכללי דה-מורגן הלוגיים, כשההבדל המרכזי הוא בסימונים.

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

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

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

[עריכה] הוכחה

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

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

a\in(A\cap B)^C

\iff a\not \in (A\cap B)

\iff \neg (a\in (A\cap B))

\iff \neg (a\in A \wedge a\in B)

\iff (a\not \in A) \vee (a \not \in B)

\iff a \in A^C \vee a \in B^C

\iff a \in A^C\cup B^C ובצורה דומה מוכח גם המשפט השני.

[עריכה] מיתוג ואלקטרוניקה ספרתית

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


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

\overline{p + q}=\bar{p}\cdot \bar{q}

\overline{p \cdot q}=\bar{p} + \bar{q}

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