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

This is a problem of combinatorics and boolean logic in computer science.

The first important consideration here is that, in an AND operation, if any input is zero, then the result is always zero.

That is, for any i, j:
(i AND 0) = 0
(0 AND j) = 0

Because of the AND operation in the formula, for the formula to be always 0, it is necessary that, at all times, either τ(a, b, c, d, e, f) = 0, or τ(b, c, d, e, f, a XOR (b AND c)) = 0.

Let’s analyze that first:
There are 2^64 possible 6-input binary truth tables, as there are 64 (i.e., 2^6) different combinations of inputs, each of which can map to either 0 or 1, hence 2^64.

In order for τ(a, b, c, d, e, f) to be 0 for all possible inputs, there is exactly 1 possible truth table, i.e., the table where all inputs map to 0.

Now, let’s consider the second part, τ(b, c, d, e, f, a XOR (b AND c)):

For the input to be always zero, it is essential that for every case where a XOR (b AND c) = 1, τ(b, c, d, e, f, 1) should equal to zero. This halves the number of available output combinations because the tables where τ(b, c, d, e, f,1) equals 1 don’t satisfy the conditions. This would leave us with 2^(64-1) = 2^63 possibilities.

Thus, the total number of possible 6-input binary truth tables, τ, that satisfy the formula is the sum from the two possibilities:

1 (from the case where τ always returns 0) + 2^63 = 2^63 + 1.

So, that is the final answer: there are 2^63 + 1 possible 6-input binary truth tables, τ that satisfy the formula.

More Answers: