Circular Logic
Problem 209
A $k$-input binary truth table is a map from $k$ input bits (binary digits, $0$ [false] or $1$ [true]) to $1$ output bit. For example, the $2$-input binary truth tables for the logical $\mathbin{\text{AND}}$ and $\mathbin{\text{XOR}}$ functions are:
| $x$ | $y$ | $x \mathbin{\text{AND}} y$ |
|---|---|---|
| $0$ | $0$ | $0$ |
| $0$ | $1$ | $0$ |
| $1$ | $0$ | $0$ |
| $1$ | $1$ | $1$ |
| $x$ | $y$ | $x\mathbin{\text{XOR}}y$ |
|---|---|---|
| $0$ | $0$ | $0$ |
| $0$ | $1$ | $1$ |
| $1$ | $0$ | $1$ |
| $1$ | $1$ | $0$ |
How many $6$-input binary truth tables, $\tau$, satisfy the formula $$\tau(a, b, c, d, e, f) \mathbin{\text{AND}} \tau(b, c, d, e, f, a \mathbin{\text{XOR}} (b \mathbin{\text{AND}} c)) = 0$$ for all $6$-bit inputs $(a, b, c, d, e, f)$?
Copied to Clipboard