כללי דה מורגן

מתוך המכלול, האנציקלופדיה היהודית
(הופנה מהדף כללי דה-מורגן)
קפיצה לניווט קפיצה לחיפוש

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

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

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

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align}\neg(P\or Q)&=(\neg P)\and(\neg Q)\\\neg(P\and Q)&=(\neg P)\or(\neg Q)\end{align}}

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

Venn1100.svg Venn1010.svg
Venn1000.svg
הדגמה של אחד הכללים בעזרת דיאגרמת ון.
שתי התמונות העליונות הן המשלימים לקבוצות המעגליות.
התמונה התחתונה מייצגת את חיתוך המשלימים הנ"ל –
השטח המשותף לשניהם, שהוא המשלים לאיחוד שלהם.
הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align}(A\cup B)^c&=A^c\cap B^c\\(A\cap B)^c&=A^c\cup B^c\end{align}}
ובאופן כללי:
  • אלגברה בוליאנית: הכללים קושרים את הפעולות "חיבור", "כפל", "שלילה".
בהתאם להגדרת השלילה, הביטוי הוא שלילת הביטוי , ועל כן יקבל ערך אמת רק אם הוא בעל ערך 0, כלומר ערך שקרי.
כללי דה-מורגן קובעים כי שלילת זהה למכפלת שלילת בשלילת , ואילו שלילת זהה לחיבור שלילת עם שלילת .
או כך:
למעשה, ההבדל בין הגרסאות השונות לניסוח הכלל אשר הוצגו לעיל הוא בסימון בלבד.
שימוש בכללי דה-מורגן

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

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

הוכחה

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

כך, אם נציב ערכי אמת ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P,Q} כאחד, אזי הביטוי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P+Q} יקבל ערך "אמת" והביטוי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (P+Q)'} יקבל ערך "שקר", כמו גם ערכו של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P'\cdot Q'} . לאחר הצבת כל הצירופים האפשריים של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P,Q} מתקבל, למעשה, הכלל.

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

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

הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align} 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\and x\in B)\\ &\iff(x\notin A)\or(x\notin B)\\ &\iff(x\in A^c)\or(x\in B^c)\\ &\iff x\in(A^c\cup B^c) \end{align}}

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

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

  • כללי דה מורגן, באתר MathWorld (באנגלית)   המזהה לא מולא ולא נמצא בוויקינתונים, נא למלא את הפרמטר.
סמל המכלול גמרא 2.PNG
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0