כללי דה מורגן

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

כללי דה-מורגן, הקרויים על-שמו של המתמטיקאי והלוגיקן בן המאה ה-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 \left(\bigcup A_i\right)^c=\bigcap A_i^c\ ,\ \left(\bigcap A_i\right)^c=\bigcup A_i^c}
  • אלגברה בוליאנית: הכללים קושרים את הפעולות "חיבור", "כפל", "שלילה".
בהתאם להגדרת השלילה, הביטוי הפענוח נכשל (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} הוא בעל ערך 0, כלומר ערך שקרי.
כללי דה-מורגן קובעים כי שלילת הפענוח נכשל (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 Q} , ואילו שלילת זהה לחיבור שלילת עם שלילת .
או כך:
למעשה, ההבדל בין הגרסאות השונות לניסוח הכלל אשר הוצגו לעיל הוא בסימון בלבד.
שימוש בכללי דה-מורגן

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

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

הוכחה

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

כך, אם נציב ערכי אמת ב- כאחד, אזי הביטוי יקבל ערך "אמת" והביטוי יקבל ערך "שקר", כמו גם ערכו של הפענוח נכשל (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