
Circular Logic
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)$?