טבלאות אמת#

פונקציה בוליאנית בינארית מקבלת שני קלטים בוליאניים ומחזירה פלט בוליאני אחד. קיימות בדיוק שש־עשרה פונקציות כאלה — זהו 2^(2^2): כל אחד מארבעת צירופי הקלט (0,0) (0,1) (1,0) (1,1) ממופה באופן בלתי תלוי לאחד משני פלטים, כך ש־2 × 2 × 2 × 2 = 16. לא יותר, לא פחות.

החמישה בעלי האופרטור הייעודי ב־Perl (&&, ||, xor, בתוספת שתי הטריוויאליות — תמיד־אמת ותמיד־שקר) הם אלה שכולם מכירים. האחת־עשרה האחרות נמצאות שם בשקט גם הן, מבוטאות כהרכבים קטנים. פרק זה מונה את כל השש־עשרה, נותן להן שמות, ומראה כיצד לכתוב כל אחת מהן ב־Perl.

המוסכמה#

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

 a  b   →  output
 0  0   →  bit 1
 0  1   →  bit 2
 1  0   →  bit 3
 1  1   →  bit 4

קריאת ארבעת ביטי הפלט הללו כמספר בן 4 ביטים נותנת לפונקציה את האינדקס שלה 0..15. כך AND הוא 0001 (רק השורה האחרונה היא אמת), OR הוא 0111, XOR הוא 0110. שלושה רבעים מהטבלה הם פשוט חיפוש השורה הנכונה.

כל השש־עשרה#

#

אמת 00 01 10 11

שם

סימן

Perl ישיר

Perl ניבי

0

0 0 0 0

שקר (סתירה)

⊥

0 / ""

—

1

0 0 0 1

AND

∧

$a && $b

$a and $b

2

0 0 1 0

a AND NOT b

a ∧ ¬b

—

$a && !$b

3

0 0 1 1

a (היטל שמאלי)

a

$a

—

4

0 1 0 0

NOT a AND b

¬a ∧ b

—

!$a && $b

5

0 1 0 1

b (היטל ימני)

b

$b

—

6

0 1 1 0

XOR

⊕

$a xor $b

!$a != !$b / ($a?1:0) != ($b?1:0)

7

0 1 1 1

OR

∨

$a || $b

$a or $b

8

1 0 0 0

NOR

↓ (Pierce)

—

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

9

1 0 0 1

XNOR / שקילות

↔

—

!$a == !$b / ($a?1:0) == ($b?1:0)

10

1 0 1 0

NOT b

¬b

!$b

not $b

11

1 0 1 1

b גורר a

b → a

—

!$b || $a

12

1 1 0 0

NOT a

¬a

!$a

not $a

13

1 1 0 1

a גורר b

a → b

—

!$a || $b

14

1 1 1 0

NAND

↑ (Sheffer)

—

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

15

1 1 1 1

אמת (טאוטולוגיה)

⊤

1

—

לחמש שורות יש אופרטור Perl ישיר (&&, ||, xor, !, בתוספת שני הקבועים). האחת־עשרה האחרות הן הרכבים קצרים שלהם. אין סיבה יסודית לכך ש־Perl מאיית חלק ישירות ואחרים לא — זה היסטורי, ירושה מ־C. כל עמודה בצד הימני היא משהו שאתם יכולים להקליד היום.

שני דברים שווה להוציא מהטבלה.

גרירה: →#

גרירה היא האופרטור שאף אחד לא חושב שהוא משתמש בו, וכולם משתמשים בו ללא הרף. a → b נקרא ״a גורר b״ והוא אמת בכל מקרה למעט כאשר a הוא אמת ו־b הוא שקר. זה הכל.

a

b

a → b

0

0

1

0

1

1

1

0

0

1

1

1

האיות ב־Perl הוא !$a || $b. זהות זו —

a → b ≡ ¬a ∨ b

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

# "if the user is admin, the request must be authenticated"
# admin → authenticated
die unless !$user->is_admin || $req->is_authenticated;

# read aloud: "either not admin, or authenticated, or both"

הצורה unless ... !X || Y היא מסורבלת. הפרק הבא על חוקי דה־מורגן מראה כיצד להפוך אותה למשהו קריא.

זהות שנייה שימושית: גרירה היא השלילה של XOR רק כאשר נכתבת בצורה ספציפית אחת. אל תשננו את זה — שננו במקום זאת את הזה, שהוא טבלת החיפוש בפועל להחלפה בין צורות נפוצות:

מטרה

דרך אחת

דרך שקולה

a → b

¬a ∨ b

¬(a ∧ ¬b)

a ↔ b (XNOR)

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

¬(a ⊕ b)

a ⊕ b (XOR)

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

¬(a ↔ b)

¬a

a ↑ a (NAND עצמי)

a ⊕ 1

העמודה האחרונה היא טיזר לפרק על שלמות פונקציונלית.

שקילות ו־XOR הם דואליים#

XOR הוא אמת בדיוק כאשר a ו־b שונים. שקילות (XNOR) היא אמת בדיוק כאשר הם מסכימים. הם שלילות זה של זה, וזה בדיוק מה ששורות טבלת האמת אומרות (שורה 6 היא 0 1 1 0, שורה 9 היא 1 0 0 1 — שלילה ביטית).

ב־Perl האיות הנקי ביותר עבור שניהם הוא לקַנֵן (canonicalise) כל אופרנד ל־0 או 1 תחילה ואז להשוות עם == או !=:

my $a01 = $a ? 1 : 0;
my $b01 = $b ? 1 : 0;

my $xor  = $a01 != $b01;   # true if they differ
my $xnor = $a01 == $b01;   # true if they agree

מדוע הקאנוניזציה? משום ש־$a ו־$b עשויים להיות ערכי־אמת כלשהם — המחרוזות "yes" ו־5 שתיהן אמת אך אינן שוות. השוואתן ישירות עם == או eq עונה על שאלה אחרת. XOR בוליאני שואל ״האם יש להם אותה אמיתיוּת?״, לא ״האם הם שווים?״.

חלופה קצרה ללא משתני העזר היא !$a != !$b — כל ! מחזיר את ה־1 או "" הקנוניים, ואז != משווה ביניהם. זה עובד אך נקרא בעקיפין; הצורה המפורשת ? 1 : 0 קריאה יותר.

קריאת הטבלה לאחור#

לפעמים תדעו את תבנית האמת הרצויה ותצטרכו למצוא את האופרטור. דוגמה: ״אני רוצה פונקציה שהיא אמת אלא אם כן גם a וגם b הם שקר.״ קראו את השורות: a=0,b=0 → 0, a=0,b=1 → 1, a=1,b=0 → 1, a=1,b=1 → 1. זהו 0 1 1 1 — שורה 7 — OR.

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

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

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

  • לחמש מתוך השש־עשרה יש אופרטור Perl ייעודי. האחת־עשרה האחרות הן הרכבים קצרים והטבלה לעיל היא טבלת החיפוש.

  • גרירה a → b היא ¬a ∨ b. היא מופיעה ללא הרף מתחת לפני השטח של פסוקיות unless ו־if.

  • XOR ו־XNOR הם שלילות זה של זה. האיות הנקי ביותר ב־Perl עבור שניהם מתחיל בקאנוניזציית האופרנדים ל־0 או 1.