חוקי דה־מורגן

שתי זהויות, מאת אוגוסטוס דה־מורגן, כתובות מזה למעלה ממאה שנה בכל ספר לימוד של לוגיקה פורמלית, וצמד המשוואות השימושי ביותר שמתכנת עובד יכול להכיר.

¬(a ∧ b) ≡ ¬a ∨ ¬b

¬(a ∨ b) ≡ ¬a ∧ ¬b

במילים: דחיפת not דרך ביטוי בסוגריים הופכת כל אופרטור בפנים (∧ הופך ל־∨, ∨ הופך ל־∧) ושוללת כל אופרנד. באופן שקול: משיכת not החוצה הופכת כל אופרטור ומסירה את השלילות על האופרנדים.

מדוע זה חשוב ב־Perl

unless הוא המקרה הקנוני. unless (X) הוא if (!X) — וברגע ש־X הוא בעצמו מורכב, יש לכם not מקדים מעל ביטוי בסוגריים: בדיוק המערך של דה־מורגן.

unless ($a == $x && $b == $y) { ... }

התנאי תחת ה־unless הוא !($a == $x && $b == $y). החילו את דה־מורגן: זהו !($a == $x) || !($b == $y). כל != הוא השלילה של ה־== המתאים, כך שהצורה הנקייה היא:

if ($a != $x || $b != $y) { ... }

שלוש טרנספורמציות התרחשו, כל אחת מכנית:

1. unless הפך ל־if (ה־not החיצוני).

2. && הפך ל־|| (דה־מורגן, בפנים).

3. == הפך ל־!= על כל אופרנד (השלילות שדה־מורגן הניח על האופרנדים מתבטלות לכדי ההשוואה ההפוכה).

זוהי לא העדפה סגנונית. כל מתכנת שאי־פעם איתר באג בתנאי שגוי בהה ב־unless (! ... && ...) דקה אחת יותר מדי; ה־if השטוח נקרא במעבר אחד.

דוגמה מפותחת

צורה אמיתית, מסובכת מעט:

unless ($x !~ /^\d+$/ && $y !~ /^[a-z]+$/) {
    print "at least one of \$x and \$y looks valid\n";
}

זה אומר: אלא אם $x לא־מספרי ו־$y לא־אלפביתי, הדפס. חמש שלילות ערוכות על פני שתי שורות. עברו על זה:

התנאי תחת ה־unless הוא

!( $x !~ /^\d+$/  &&  $y !~ /^[a-z]+$/ )

דה־מורגן הופך את ה־&& ל־|| ושולל כל צד:

!($x !~ /^\d+$/)  ||  !($y !~ /^[a-z]+$/)

!($x !~ ...) הוא פשוט $x =~ ... (שלילה כפולה של התאמת regex). אותו דבר עבור הצד הימני:

$x =~ /^\d+$/  ||  $y =~ /^[a-z]+$/

אז הגרסה המנוקה היא:

if ($x =~ /^\d+$/ || $y =~ /^[a-z]+$/) {
    print "at least one of \$x and \$y looks valid\n";
}

חמש שלילות הצטמצמו לאפס. התנאי כעת נקרא בדיוק כפי שההערה אמרה: אם $x הוא מספרי או $y הוא אלפביתי.

אותו טריק עבור OR

הצורה השנייה של החוק היא המקרה הסימטרי:

unless ($a == 0 || $b == 0) { divide($a, $b) }

הופך ל

if ($a != 0 && $b != 0) { divide($a, $b) }

— אותם צעדים מכניים, רק שהפעם האופרטור הפנימי הוא || המתהפך ל־&&.

NAND, NOR — אותה זהות, נקראת בכיוון השני

שורת ה־NAND בטבלת האמת מהפרק הקודם מכילה שני ערכים בעמודה ״Perl ניבי״:

14  NAND   !($a && $b)   /   !$a || !$b

אלה שווים בגלל החוק הראשון של דה־מורגן. NAND הוא בדיוק השלילה של AND, ודחיפת השלילה פנימה הופכת את האופרטור ושוללת את האופרנדים. שורת ה־NOR פועלת באותה דרך עבור החוק השני:

8   NOR    !($a || $b)   /   !$a && !$b

אז דה־מורגן אינו עובדה נפרדת שצריך לזכור לצד NAND ו־NOR — הוא הוא הזהות ההופכת איות אחד לאחר.

המכניקה, בפסקה אחת

שלילה מתחלקת על פני ∧ ו־∨ על ידי היפוך הקשר ושלילת כל אופרנד. שלילה גם מבטלת את עצמה: ¬¬x ≡ x. שני הכללים יחד מאפשרים לכם לדחוף not עמוק כרצונכם, או למשוך אותו החוצה כרצונכם, מכל ביטוי הבנוי מ־∧, ∨, ו־¬. זהו כל התוכן של חוקי דה־מורגן — כל ״unless מסובך״ שאי־פעם שכתבתם הוא יישום אחד של שני כללים אלה בתוספת ביטול שלילה כפולה.

פרוצדורה מעשית

כשאתם בוהים בתנאי שאינכם אוהבים:

1. אם מילת המפתח החיצונית היא unless, הוסיפו not מנטלית והפכו אותה ל־if.

2. אם ה־not המקדים נמצא מעל && או || בסוגריים, חלקו אותו: הפכו את הקשר, שללו כל אופרנד.

3. אם תת־ביטוי הוא !(x == y), החליפו ב־x != y. אותו דבר עבור !~ ↔ =~, !defined ↔ defined, וכו«.

4. עצרו כשאין יותר שלילות מקדימות לדחוף או יותר שלילות כפולות לבטל.

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

מה כדאי לזכור מהפרק הזה

• שתי זהויות: דחיפת ¬ דרך ∧ הופכת אותו ל־∨ (ולהפך) ושוללת כל אופרנד.

• רוב ״ה־unless המכוערים״ נמצאים היפוך דה־מורגן מכני אחד מ־if נקי.

• NAND ו־NOR אינם עובדות נוספות; הם חוקי דה־מורגן הנקראים כצמד איותים שקולים.

ראו גם

• perlop — לוגי — מלווה מדריך העיון של האופרטורים. הטרנספורמציות של דה־מורגן כאן חלות על כל ביטוי Perl המשתמש ב־&&, ||, !, ובמילת המפתח unless.