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