כללי דה מורגן, על-שמן של הלוגיקן מאה ה-19 אוגוסטוס דה מורגן, הם שני כללים בלוגיקה, בתורת הקבוצות ובאלגברה בוליאנית. אלגברה בוליאנית היא ענף שעוסק בערכים של אמת ושקר.
בצורה לוגית הם נכתבים כך:
¬(P ∧ Q) ≡ (¬P) ∨ (¬Q)
¬(P ∨ Q) ≡ (¬P) ∧ (¬Q)
למשל, "היום לא יום ראשון או שלא יורד עכשיו גשם" שקול לוגית ל"לא (היום יום ראשון וגם יורד עכשיו גשם)". ההחלפה מראה איך מעבירים שלילה (שלילה = "לא", כלומר שהמשפט לא נכון) דרך חיבור או חיבור לוגי.
בשפת קבוצות זה מתבטא כך:
המשלים של החיתוך שווה לאיחוד של המשלים.
המשלים של האיחוד שווה לחיתוך של המשלים.
לדוגמה, (A ∩ B)^C = A^C ∪ B^C וכן להפך.
באלגברה בוליאנית משתמשים גם בסימון של גרש או קו עליון:
(p + q)' = p' · q'
(p · q)' = p' + q'
כך שהשוני בין נוסחאות הוא בעיקר בסימון בלבד.
הכללים שימושיים להעברת שלילה על ביטויים מרוכבים. הם מקלים על פישוט נוסחאות ולהוכחות בלוגיקה ובתורת הקבוצות.
אחת ההוכחות נעשית על ידי בדיקת כל צירופי ערכי האמת של P ו-Q. בכל מקרה שמציבים את הערכים, שני הצדדים מקבלים את אותו ערך אמת. עבור הקבוצות, אפשר להוכיח את השוויון על ידי בדיקה של חבר בקבוצה והחלפת ההגדרות של חיתוך, איחוד ומשלים, כפי שמודגם בהוכחה הטיפוסית.
כללי דה מורגן אומרים איך להעביר "לא" במשפטים עם "וגם" ו"או".
"לא (A וגם B)" שווה ל"(לא A) או (לא B)".
"לא (A או B)" שווה ל"(לא A) וגם (לא B)".
זה אומר שאם לא נכון ששני דברים יחד נכונים, אז לפחות אחד מהם לא נכון.
למשל: "לא (היום יום ראשון וגם יורד גשם)" שווה ל"היום לא יום ראשון או שלא יורד גשם".
הכללים עוזרים לפשט מחשבות ולבדוק משפטים. משתמשים בהם בתרגילים ולפעמים בקבוצות של דברים.
כדי להראות שהכלל נכון בודקים את כל האפשרויות: כל פעם שבודקים אם A נכון או לא, הצדדים בכל הכלל נותנים אותו תוצאה.
תגובות גולשים