--- name: the sixteen binary truth functions --- # Truth tables A binary boolean function takes two boolean inputs and returns one boolean output. There are exactly **sixteen** such functions — that is `2^(2^2)`: each of the four input combinations `(0,0) (0,1) (1,0) (1,1)` is independently mapped to one of two outputs, so `2 × 2 × 2 × 2 = 16`. No more, no fewer. The five with their own Perl operator (`&&`, `||`, `xor`, plus the two trivial ones — always-true and always-false) are the ones everyone knows. The other eleven are quietly there too, expressed as small compositions. This chapter lists all sixteen, names them, and shows how to write each one in Perl. ## The convention Each function is fully described by its output for the four input rows, written top-to-bottom in this order: ``` a b → output 0 0 → bit 1 0 1 → bit 2 1 0 → bit 3 1 1 → bit 4 ``` Reading those four output bits as a 4-bit number gives the function its index 0..15. So `AND` is `0001` (only the last row is true), `OR` is `0111`, `XOR` is `0110`. Three quarters of the table is just looking up the right row. ## All sixteen | # | Truth `00 01 10 11` | Name | Symbol | Perl direct | Perl idiomatic | |---|---------------------|------------------|-----------------|-----------------------|--------------------------------| | 0 | `0 0 0 0` | false (contradiction)| `⊥` | `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 (left projection)| `a` | `$a` | — | | 4 | `0 1 0 0` | NOT a AND b | `¬a ∧ b` | — | `!$a && $b` | | 5 | `0 1 0 1` | b (right projection)| `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 / equivalence| `↔` | — | `!$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 implies a | `b → a` | — | `!$b \|\| $a` | | 12| `1 1 0 0` | NOT a | `¬a` | `!$a` | `not $a` | | 13| `1 1 0 1` | a implies b | `a → b` | — | `!$a \|\| $b` | | 14| `1 1 1 0` | NAND | `↑` (Sheffer) | — | `!($a && $b)` / `!$a \|\| !$b` | | 15| `1 1 1 1` | true (tautology) | `⊤` | `1` | — | Five rows have a direct Perl operator (`&&`, `||`, `xor`, `!`, plus the two constants). The other eleven are short compositions of those. There is no fundamental reason Perl spells some directly and not others — it is historical, inherited from C. Every column on the right is something you can type today. Two things are worth pulling out of the table. ## Implication: `→` Implication is the operator nobody thinks they use, and everyone uses constantly. `a → b` is read "a implies b" and is true in every case **except** when `a` is true and `b` is false. That is it. | a | b | a → b | |---|---|-------| | 0 | 0 | 1 | | 0 | 1 | 1 | | 1 | 0 | 0 | | 1 | 1 | 1 | The Perl spelling is `!$a || $b`. This identity — > **`a → b` ≡ `¬a ∨ b`** — is so common that it deserves a name; and the name is *material implication*. Once you see it once, you spot it everywhere: ```perl # "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" ``` The `unless ... !X || Y` shape is awkward. The next chapter on De Morgan's laws shows how to flip it into something readable. A second useful identity: implication is **the negation of XOR** *only when written one specific way*. Don't memorise that — memorise this instead, which is the actual lookup table for flipping between common shapes: | Goal | One way | Equivalent way | |-------------------|--------------------|---------------------| | `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 self) | `a ⊕ 1` | The last column is a teaser for the chapter on functional completeness. ## Equivalence and XOR are duals XOR is true exactly when `a` and `b` differ. Equivalence (XNOR) is true exactly when they agree. They are negations of each other, and that is exactly what the truth-table rows say (row 6 is `0 1 1 0`, row 9 is `1 0 0 1` — bitwise negation). In Perl the cleanest spelling for both is to canonicalise each operand to `0` or `1` first and then compare with `==` or `!=`: ```perl 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 ``` Why the canonicalisation? Because `$a` and `$b` may be any truthy values — the strings `"yes"` and `5` are both true but not equal. Comparing them directly with `==` or `eq` answers a different question. Boolean XOR asks "do they have the same *truthiness*?", not "are they equal?". A short alternative without the temporaries is `!$a != !$b` — each `!` returns the canonical `1` or `""`, and then `!=` compares those. It works but reads sideways; the explicit `? 1 : 0` form is more readable. ## Reading the table backwards You will sometimes know the truth pattern you want and need to find the operator. Example: "I want a function that is true unless both `a` and `b` are false." Read the rows: `a=0,b=0 → 0`, `a=0,b=1 → 1`, `a=1,b=0 → 1`, `a=1,b=1 → 1`. That is `0 1 1 1` — row 7 — OR. This sounds trivial here but is exactly how you debug a tangled condition: write down its truth table, read off the four bits, find the row, and you have the canonical name and the simplest spelling. ## What you should remember from this chapter - There are exactly sixteen binary truth functions; every boolean expression in any language computes one of them. - Five of the sixteen have a dedicated Perl operator. The other eleven are short compositions and the table above is the lookup. - Implication `a → b` is `¬a ∨ b`. It shows up constantly under the surface of `unless` and `if` clauses. - XOR and XNOR are negations of each other. The cleanest Perl spelling for both starts by canonicalising operands to `0` or `1`.