Simplifying a 9 variable boolean expression

Question

I am trying to create a tic-tac-toe program as a mental exercise and I have the board states stored as booleans like so:

http://i.imgur.com/xBiuoAO.png

I would like to simplify this boolean expression...

(a&b&c) | (d&e&f) | (g&h&i) | (a&d&g) | (b&e&h) | (c&f&i) | (a&e&i) | (g&e&c)

My first thoughts were to use a Karnaugh Map but there were no solvers online that supported 9 variables.

and heres the question:

First of all, how would I know if a boolean condition is already as simple as possible?

and second: What is the above boolean condition simplified?

Answer 1

2. Simplified condition:

The original expression

a&b&c|d&e&f|g&h&i|a&d&g|b&e&h|c&f&i|a&e&i|g&e&c

can be simplified to the following, knowing that & is more prioritary than |

e&(d&f|b&h|a&i|g&c)|a&(b&c|d&g)|i&(g&h|c&f)

which is 4 chars shorter, performs in the worst case 18 & and | evaluations (the original one counted 23) There is no shorter boolean formula (see point below). If you switch to matrices, maybe you can find another solution.

1. Making sure we got the smallest formula

Normally, it is very hard to find the smallest formula. See this recent paper if you are more interested. But in our case, there is a simple proof.

We will reason about a formula being the smallest with respect to the formula size, where for a variable a, size(a)=1, for a boolean operation size(A&B) = size(A|B) = size(A) + 1 + size(B), and for negation size(!A) = size(A) (thus we can suppose that we have Negation Normal Form at no cost). With respect to that size, our formula has size 37.

The proof that you cannot do better consists in first remarking that there are 8 rows to check, and that there is always a pair of letter distinguishing 2 different rows. Since we can regroup these 8 checks in no less than 3 conjuncts with the remaining variable, the number of variables in the final formula should be at least 8*2+3 = 19, from which we can deduce the minimal tree size.

Detailed proof

Let us suppose that a given formula F is the smallest and in NNF format.

1. F cannot contain negated variables like !a. For that, remark that F should be monotonic, that is, if it returns "true" (there is a winning row), then changing one of the variables from false to true should not change that result. According to Wikipedia, F can be written without negation. Even better, we can prove that we can remove the negation. Following this answer, we could convert back and from DNF format, removing negated variables in the middle or replacing them by true.

2. F cannot contain a sub-tree like a disjunction of two variables a|b. For this formula to be useful and not exchangeable with either a or b, it would mean that there are contradicting assignments such that for example F[a|b] = true and F[a] = false, therefore that a = false and b = true because of monotonicity. Also, in this case, turning b to false makes the whole formula false because false = F[a] = F[a|false] >= F[a|b](b = false). Therefore there is a row passing by b which is the cause of the truth, and it cannot go through a, hence for example e = true and h = true. And the checking of this row passes by the expression a|b for testing b. However, it means that with a,e,h being true and all other set to false, F is still true, which contradicts the purpose of the formula.

3. Every subtree looking like a&b checks a unique row. So the last letter should appear just above the corresponding disjunction (a&b|...)&{c somewhere for sure here}, or this leaf is useless and either a or b can be removed safely. Indeed, suppose that c does not appear above, and the game is where a&b&c is true and all other variables are false. Then the expression where c is supposed to be above returns false, so a&b will be always useless. So there is a shorter expression by removing a&b.

4. There are 8 independent branches, so there is at least 8 subtrees of type a&b. We cannot regroup them using a disjunction of 2 conjunctions since a, f and h never share the same rows, so there must be 3 outer variables. 8*2+3 makes 19 variables appear in the final formula. A tree with 19 variables cannot have less than 18 operators, so in total the size have to be at least 19+18 = 37.

You can have variants of the above formula.

QED.