שלמות פונקציונלית

קבוצה של אופרטורים בוליאניים היא שלמה פונקציונלית כאשר כל אחת משש־עשרה פונקציות האמת הבינאריות ניתנת לבנייה מאופרטורים בקבוצה זו, באמצעות הרכבה. הקבוצות השלמות הקלאסיות שאתם כבר מכירים הן {∧, ∨, ¬} ו־{→, ⊥}. התוצאה המפתיעה — והשימושית — היא שאופרטור יחיד מספיק, אך רק שתיים מתוך שש־עשרה הפונקציות הבינאריות בעלות תכונה זו: NAND ו־NOR.

NAND קרוי על שם הנרי מ. שפר (Sheffer, 1913) ונכתב ↑; NOR קרוי על שם צ’ארלס סנדרס פירס (Peirce, שתיאר אותו קודם לכן) ונכתב ↓. אלה שני קווי שפר.

בניית הכל מ־NAND

NAND לבדו נותן לכם את כל שש־עשרה הפונקציות. הבנייה להלן מציגה את הארבע השימושיות ביותר — NOT, AND, OR, XOR — במונחי ↑. חשבו על a ↑ b כעל !($a && $b).

מטרה	במונחי NAND	מדוע
¬a	a ↑ a	!(a ∧ a) הוא !a
a ∧ b	(a ↑ b) ↑ (a ↑ b)	NAND ואז שלילת התוצאה, כלומר !!(a ∧ b) ≡ a ∧ b
a ∨ b	(a ↑ a) ↑ (b ↑ b)	דה־מורגן: a ∨ b ≡ ¬(¬a ∧ ¬b) ≡ ¬a ↑ ¬b
a ⊕ b	(a ↑ (a ↑ b)) ↑ (b ↑ (a ↑ b))	XOR הוא AND של (a ∨ b) ו־¬(a ∧ b) — מושאר כתרגיל

אותן בניות קיימות עם NOR; הן הדואלים של דה־מורגן.

ב־Perl

לא תכתבו את הקוד שלכם כך בייצור — (a ↑ a) ↑ (b ↑ b) הוא איות גרוע יותר של OR מאשר ||. אך כדאי לראות את הבניות אכן רצות, מפני שהטענה המופשטת (״הכל מצטמצם לאופרטור אחד״) הופכת לקונקרטית כשאתם מקלידים אותה.

sub nand { !($_[0] && $_[1]) }       # the only primitive

sub not_a { nand($_[0], $_[0]) }                       # ¬a
sub and_  { my $n = nand($_[0], $_[1]); nand($n, $n) } # a ∧ b
sub or_   { nand(nand($_[0], $_[0]), nand($_[1], $_[1])) }   # a ∨ b
sub xor_  {
    my ($a, $b) = @_;
    my $n = nand($a, $b);
    nand(nand($a, $n), nand($b, $n));
}

# Verify across all four input combinations:
for my $a (0, 1) {
    for my $b (0, 1) {
        printf "a=%d b=%d  not=%d and=%d or=%d xor=%d\n",
            $a, $b,
            not_a($a)         ? 1 : 0,
            and_($a, $b)      ? 1 : 0,
            or_($a, $b)       ? 1 : 0,
            xor_($a, $b)      ? 1 : 0;
    }
}

פלט:

a=0 b=0  not=1 and=0 or=0 xor=0
a=0 b=1  not=1 and=0 or=1 xor=1
a=1 b=0  not=0 and=0 or=1 xor=1
a=1 b=1  not=0 and=1 or=1 xor=0

כל שורה תואמת לטבלת האמת מהפרק הקודם.

מדוע זה חשוב

שלושה דברים, בסדר מן המעשי לעמוק:

1. זה מסביר את אוסף הזהויות. NAND, NOR, ואחת־עשרה השורות הלא־ישירות של פרק טבלת האמת אינן גן חיות של עובדות נפרדות. כולן ניתנות לביטוי מאופרטור יחיד; אחת־עשרה האיותים הלא־ישירים ב־Perl הם פשוט קיצורי דרך קריאים להרכבי NAND או NOR קצרים.

2. כך הסיליקון אכן עובד. לוגיקת CMOS סטטית מייצרת NAND ו־NOR בזול יותר מ־AND ו־OR — שער AND בעל שני קלטים נבנה כ־NAND ואחריו inverter. כל שער אחר על שבב הוא הרכב של NANDים (או NORים). התבנית חוזרת על עצמה בפנימיות של פותרי SAT ומנועי אילוצים: פותרי SAT מנרמלים ל־CNF בדיוק משום ש־OR-של-(ליטרלים) ו־AND-של-(פסוקיות) הוא אוצר המילים המינימלי שהם צריכים.

3. זה מלמד את המשמעת של צורה קנונית. לכל ביטוי בוליאני יש צורות שקולות רבות, אך רק מעטות קנוניות. CNF (צורת נורמלית קוניונקטיבית: AND של ORים של ליטרלים שעשויים להיות שלולים) ו־DNF (צורת נורמלית דיסיונקטיבית: OR של ANDים) הן השתיים הנפוצות ביותר. צמצום של סבך ל־CNF או DNF הוא פרוצדורה מכנית טהורה המבוססת על דה־מורגן בתוספת דיסטריבוטיביות, וברגע שהביטוי שלכם בצורה נורמלית ניתן להשוות אותו לביטוי אחר בצורה נורמלית כדי לבחון שקילות — ללא טבלאות אמת, ללא בדיקה.

לא תממשו פותר SAT בשבוע הבא. אך בפעם הבאה שתמצאו את עצמכם כותבים if ((!$a && $b) || (!$c && $b) || ($a && !$c)) ותוהים אם הגרסה הקודמת הייתה שקולה, יש לכם כלי: לחלק, לפרק לגורמים, לנרמל. שני ביטויים המצטמצמים לאותו DNF מחשבים את אותה פונקציה.

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

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

• הבניות קצרות ואתם יכולים לאמת אותן ב־Perl בעשר שורות.

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