השוואת ביטויים בוליאניים
הוצג| English | משמעות |
|---|---|
| equivalent/ɪˈkwɪvələnt/ | שווה ערך |
| De Morgan's Laws/də ˈmɔːɡənz lɔːz/ | חוקי דה מורגן |
דוגמת נגד אחת מנפילה על כתיבת מחזור בוליאנית
- כתיבת מחוקק מציעה משנה !(a && b) ל-!a && !b. הגדר a = true ו-b = false.
- המקורי הוא אמיתי, בעוד שכתיבת המחוקק המוצעת היא שקר. דמורגן דורש !a || !b, שהסכים עם המקורי.
מתי שני תנאים הם בעלי אותו משמעות
- שני ביטויים בוליאניים הם שווים אם הם נותנים את אותה תוצאה לכל קלט. עבור מספר שלם
x,x >= 5ו!(x < 5)הם שווים – שניהם אמת בדיוק כאשרxהוא לפחות5. - עבור משתנים בוליאניים ללא השפעות לוואי, ביטויים שווים ערך מחזירים אותה תוצאה. יש לבדוק גם סדר ביצוע אם הביטויים קוראים למתודות או משנים מצב. טבלת אמת מאשרת שוויון ערך: אותה פלט בכל שורה.
חוקי דה מורגן
- חוקי דמורגן מכתבים מחדש NOT מעל AND/OR:
!(a && b)שווה ל-!a || !b. !(a || b)שווה ל-!a && !b. הדפוס: הזז את ה-!פנימה, והפוך&&↔||.
צמצום תנאים
- השתמש בחוקי דמורגן ובכללי לוגיקה כדי לכתוב ביטוי קצר וברור יותר שקיים ערכו. עבור ציון שלם,
!(score < 60)הופך ל-score >= 60— אותו משמעות, קריא יותר. - הסרת כפילית שלילי או חיצוני
!לעיתים מבהירה את הכוונה. בדוק את תחום הקלט המדויק וההתנהגות הביצוע; מספר תווים פחות אינו מבטיח פחות באגים.
על פי חוק דה מורגן, !(a && b) שקול ל-...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
הכנס את ה-! פנימה והפוך את && ל-||.
על פי חוק דה מורגן, !(a || b) שקול ל-...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
הכנס את ה-! פנימה והפוך את || ל-&&.
עבור ציון של מספר שלם, מהו ערך שקול ל-!(score < 60)?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
לא-פחות-מ-60 פירושו לפחות-60.
שני ביטויים בוליאניים הם שקולים אם הם מחזירים את אותה תוצאה עבור כל כניסה.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
אותה תוצאת יציאה בכל שורת טבלת אמת = שקילות.
באמצעות חוק דה מורגן, !(a && b) הופך ל-!a && !b.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
זה הופך ל-!a || !b — האופרטור חייב להשתנות.
בדיקה עם טבלת אמת
- כדי לבדוק אם שני ביטויים שווים ערך, טבל את שניהם לכל הקלטים. אם כל שורה תואמת, הם שווים ערך; חריגה אחת אומרת שאינם שווים ערך.
- עבור שני משתנים בוליאניים טהורים ישנן ארבע שורות קלט, שמגדירות במלואן את פונקציית האמת. הדבר אינו ממפה את ההשפעות של קריאות מתודה ארביטריות ואינו מוכיח שכל שינוי בערך השוואת גישה (floating-point) תקין.
בעת יישום חוק דה מורגן, יש להפוך גם את האופרטור, ולא רק לפזר את ה-!. !(a && b) הוא !a || !b (AND הופך ל-OR) — כתיבת !a && !b היא שגויה. המפתח: הזז את ה-NOT פנימה והחלף && ↔ ||. בספק, טבלת אמת פותרת זאת בארבע שורות.
עבור a=true ו-b=false, מהם ערכי !(a && b), !a && !b, ו-!a || !b, בסדר זה?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The mismatching middle expression is a counterexample to the proposed equivalence.
עבור דירוג כפול המהווה NaN, !(score < 60) and score >= 60) מחזירה את אותו תוצאה בולית.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
השוואות score < 60 and score >= 60 הן שגויות בשתי הזדמנויות עבור NaN, ולכן הביטוי השלילי הראשון הוא נכון והשני הוא שגוי.
אם f() מחזירה שגויה, כמה פעמים יוצא g() פועל בעת ביצוע !(f() && g())?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
האופרנד השגוי הראשון מקצר את הביצוע ב-&&, ולכן g אינה נקראת. הביטוי המקביל !f() || !g() גם הוא דורש גישה ל-g.
כתיבה מחדש של !(a && b):
- שגוי:
!a && !b. - נכון (חוקי דה מורגן):
!a || !b— AND הופך ל-OR. - בדיקה: אם
a = true, b = false, אז!(true && false) = !false = true, ו-!a || !b = false || true = true. ✓
להעביר את הניתוח למקרה חדש
- עבור משתנים בוליאניים טהורים, כל זוגות הקלט הארבעה מאשרים שוויון ערך. צורות דמורגן שומרות על ביצוע קצר-מעגלי משמאל לימין:
!(f() && g())ו-!f() || !g()שניהם מדלגים על g כאשר f היא שגויה. - החלפת מקדמים היא טרנספורמציה שונה. למרות ש-
a && bו-b && aבעלות טבלת אמת זהה עבור משתנים טהורים,f() && g()ו-g() && f()עשויות לקרוא למתודות שונות. עבור ציון כפול score=NaN,!(score < 60)היא אמת אךscore >= 60היא שגויה; כלל השוואת השלמה אינו חל על NaN.
שתי ביטויים בוליאניים הם שווים ערך אם הם תואמים לכל קלט (ניתן להוכיח זאת עם טבלת אמתיות). חוקי דה מורגן: !(a && b) = !a || !b ו-!(a || b) = !a && !b — דוחפים את ! פנימה ומ-מפנים && ↔ ||. השתמש בחוקים אלו כדי לפשט תנאים לצורות שוות ערך ברורות יותר.