כללי דה מורגן
כללי דה מורגן, הקרויים על-שמו של המתמטיקאי והלוגיקן בן המאה ה-19, אוגוסטוס דה מורגן, הם שני כללים בלוגיקה, בתורת הקבוצות ובאלגברה בוליאנית (בפרט, לוגיקה בוליאנית), הקושרים את הפעולות הבסיסיות בתחומים אלה.
- לוגיקה: הכללים קושרים את הפעולות "או", "גם", "לא". באופן מילולי בכתיב לא פורמלי, קובעים הכללים כי השלילה של- קיום א' וגם קיום ב', היא אי קיום א' או אי קיום ב'; וכן כי השלילה של קיום א' או קיום ב', היא אי קיום א' וגם אי קיום ב'.
בכתיב פורמלי הם מוצגים כך:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \neg(P\wedge Q)\equiv(\neg P)\vee(\neg Q)}
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \neg(P\vee Q)\equiv(\neg P)\wedge(\neg Q)}
לדוגמה, המשפט "היום לא יום ראשון או שלא יורד עכשיו גשם" שקול לוגית למשפט: "לא נכון ש'היום יום ראשון וגם יורד עכשיו גשם'"
|
קובץ:Venn1010.svg | |
| שגיאה ביצירת תמונה ממוזערת: | ||
| הדגמה של אחד הכללים בעזרת דיאגרמת ון. שתי התמונות העליונות הן המשלימים של הקבוצות המיוצגות על ידי המעגלים. התמונה התחתונה מייצגת את החיתוך שלהן- השטח המשותף שלהן | ||
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A\cap B)^C=A^C\cup B^C}
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A\cup B)^C=A^C\cap B^C}
ובאופן כללי: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\bigcup_{} A_i \right )^C = \bigcap_{} A_i^C} , ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\bigcap_{} A_i \right )^C = \bigcup_{} A_i^C}
- אלגברה בוליאנית: הכללים קושרים את הפעולות "חיבור", "כפל", "שלילה".
- בהתאם להגדרת השלילה, הביטוי '(P+Q) הוא שלילת הביטוי (P+Q), ועל כן יקבל ערך אמת רק אם P+Q הוא בעל ערך 0, כלומר ערך שקרי. כללי דה מורגן קובעים כי שלילת P+Q זהה למכפלת שלילת P בשלילת Q, ואילו שלילת P*Q זהה לחיבור שלילת P עם שלילת Q. בכתיב פורמלי הם מוצגים כך:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (P+Q)^{\prime}=P'\cdot Q'}
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\,(P\cdot Q)'=P'+Q'}
או כך:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \overline{p \cdot q}=\bar{p} + \bar{q}}
למעשה, ההבדל בין הגרסאות השונות לניסוח הכלל אשר הוצגו לעיל הוא בסימון בלבד.
שימוש בכללי דה מורגן
לכללים אלה מספר שימושים, ביניהם:
- פישוט של ביטויים מתחומי הלוגיקה והמתמטיקה המתוארים לעיל.
- פישוט התניות בעת כתיבת תוכניות מחשב.
- שימוש באלקטרוניקה ספרתית (בה במקרים רבים נעשה שימוש בשתי רמות מתח בלבד) לצורכי פישוט תכנונם של מעגלים חשמליים, למשל, כאלה העושים שימוש בשערים לוגיים.
- ניתן לעשות שימוש בכללים אלה לצורך ייצוג של ביטויים על ידי שימוש בסוג אחד בלבד של פעולות, למשל פעולות NAND. להרחבה ראו הערך NAND לוגי.
הוכחה
ההוכחה של כללי דה-מורגן מתבצעת באינדוקציה שלמה. כלומר, הצבה של כל הצירופים האפשריים בכל אחד מהפסוקים, נותנת ערכים שווים. כך, אם נציב ערכי אמת ב-P וב-Q, אזי הביטוי (P+Q) יקבל את הערך "אמת" והביטוי '(P+Q), ערכו יהי שקר, כמו גם ערכו של 'p'*q. לאחר הצבת כל הצירופים האפשריים של P ו-Q מתקבל, למעשה, הכלל.
הכלל בנוגע לתורת הקבוצות, ניתן להוכחה על נקלה בעזרת הכללים הנ"ל, זאת, בהינתן ההגדרות של חיתוך, איחוד ומשלים של קבוצה. ההוכחה היא כדלהלן:
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\in(A\cap B)^C }
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \iff a\not \in (A\cap B) }
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \iff \neg (a\in (A\cap B)) }
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \iff (a\not \in A) \vee (a \not \in B) }
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \iff a \in A^C \vee a \in B^C }
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \iff a \in A^C\cup B^C }ובצורה דומה מוכח גם המשפט השני.
קישורים חיצוניים
- כללי דה מורגן, באתר MathWorld (באנגלית)
