כללי דה מורגן – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ הוספת קישור לאלגברה בוליאנית (מבנה אלגברי) |
הסרת קישורים עודפים |
||
שורה 1:
'''כללי דה מורגן''', הקרויים על-שמו של ה[[מתמטיקאי]] וה[[לוגיקן]] בן [[המאה ה-19]], [[אוגוסטוס דה מורגן]], הם שני כללים ב[[לוגיקה]], ב[[תורת הקבוצות]] וב[[אלגברה בוליאנית]] (בפרט, [[לוגיקה בוליאנית]]), הקושרים את הפעולות הבסיסיות בתחומים אלה.
* '''לוגיקה''': הכללים קושרים את הפעולות "[[או (לוגיקה)|או]]", "[[וגם (לוגיקה)|גם]]", "[[לא (לוגיקה)|לא]]". באופן מילולי בכתיב לא פורמלי, קובעים הכללים כי השלילה של קיום א' '''וגם''' קיום ב', היא אי קיום א' '''או''' אי קיום ב'; וכן כי השלילה של קיום א' '''או''' קיום ב', היא אי קיום א' '''וגם''' אי קיום ב'.
▲* '''לוגיקה''': הכללים קושרים את הפעולות "[[או (לוגיקה)|או]]", "[[וגם (לוגיקה)|גם]]", "[[לא (לוגיקה)|לא]]". באופן מילולי בכתיב לא פורמלי, קובעים הכללים כי השלילה של קיום א' '''וגם''' קיום ב', היא אי קיום א' '''או''' אי קיום ב'; וכן כי השלילה של קיום א' '''או''' קיום ב', היא אי קיום א' '''וגם''' אי קיום ב'.
בכתיב פורמלי הם מוצגים כך:
:<math>\neg(P\wedge Q)\equiv(\neg P)\vee(\neg Q)</math>
שורה 16 ⟵ 15:
|colspan="3"| הדגמה של אחד הכללים בעזרת [[דיאגרמת ון]]. שתי התמונות{{ש}} העליונות הן המשלימים של הקבוצות המיוצגות על ידי המעגלים.{{ש}} התמונה התחתונה מייצגת את החיתוך שלהן- השטח המשותף{{ש}} לשתיהן, שהוא המשלים של האיחוד שלהן.
|}
* '''תורת הקבוצות''': הכללים קושרים את הפעולות "[[איחוד (מתמטיקה)|איחוד]]", "[[חיתוך (מתמטיקה)|חיתוך]]", "[[משלים (מתמטיקה)|משלים]]". בכתיב פורמלי הם מוצגים כך:
:<math>(A\cap B)^C=A^C\cup B^C</math>
שורה 23 ⟵ 21:
ובאופן כללי: <math>\ \left(\bigcup_{} A_i \right )^C = \bigcap_{} A_i^C</math>, ו-<math>\ \left(\bigcap_{} A_i \right )^C = \bigcup_{} A_i^C</math>
* '''[[אלגברה בוליאנית (מבנה אלגברי)|אלגברה בוליאנית]]''': הכללים קושרים את ה[[פעולה בוליאנית|פעולות]] "חיבור", "כפל", "שלילה".
:בהתאם להגדרת השלילה, הביטוי '(P+Q) הוא שלילת הביטוי (P+Q), ועל כן יקבל ערך אמת רק אם P+Q הוא בעל ערך 0, כלומר ערך שקרי. כללי דה מורגן קובעים כי שלילת P+Q זהה למכפלת שלילת P בשלילת Q, ואילו שלילת P*Q זהה לחיבור שלילת P עם שלילת Q. בכתיב פורמלי הם מוצגים כך:
שורה 45 ⟵ 42:
# פישוט התניות בעת כתיבת [[תוכנית מחשב|תוכניות מחשב]].
# שימוש ב[[אלקטרוניקה ספרתית]] (בה במקרים רבים נעשה שימוש בשתי רמות מתח בלבד) לצורכי פישוט תכנונם של [[מעגל חשמלי|מעגלים חשמליים]], למשל, כאלה העושים שימוש ב[[שער לוגי|שערים לוגיים]].
# ניתן לעשות שימוש בכללים אלה לצורך ייצוג של ביטויים על ידי שימוש בסוג אחד בלבד של פעולות, למשל [[NAND לוגי|פעולות NAND]]. להרחבה ראו הערך
==הוכחה==
שורה 51 ⟵ 48:
הכלל בנוגע לתורת הקבוצות, ניתן להוכחה על נקלה בעזרת הכללים הנ"ל, זאת, בהינתן ההגדרות של [[חיתוך (מתמטיקה)|חיתוך]], [[איחוד (מתמטיקה)|איחוד]] ו[[משלים (מתמטיקה)|משלים]] של [[קבוצה (מתמטיקה)|קבוצה]].
ההוכחה היא כדלהלן:
<div style="direction: ltr;">
<math>
שורה 85 ⟵ 82:
[[קטגוריה:משפטים בלוגיקה|דה מורגן]]
[[קטגוריה:לוגיקה בוליאנית]]
[[קטגוריה:משפטים בתורת הקבוצות|דה מורגן]]
| |||