Finding minimal or canonical expressions for Boolean truth tables

If you play around with this a bit, you'll probably come to the same conclusion that I did a long time ago, namely that there is indeed a one true extension of boolean functions $\{0,1\}^n\to \{0,1\}$ to functions $[0,1]^n\to [0,1]$. There are many simple characterizations of this extension (which tells you that it's important). The most intuitive one for me is to relax boolean logic to probability: take a boolean function of some number of variables, like $$y \text{ or not } (x \text{ and } z).$$ Now suppose we flip possibly biased coins independently to determine the truth values of $x,y,z$. The probability of $x$ being true is $p$, the probability of $y$ being true is $q$, and the probability of $z$ being true is $r$, so we have $0\leq p,q,r \leq 1$. Now consider our expression $y \text{ or not } (x \text{ and } z)$: what is the probability that this will be true? It's some function of $p,q,r$ that takes values in $[0,1]$. If you work it out (which is straightforward), you'll find that the function is $$f(p,q,r) = 1-p(1-q)r.$$ You should check that when you restrict $p,q,r$ to be 0 or 1, this agrees with the original boolean function when the corresponding boolean variables are respectively false or true. One of the other main characterizations of this extension is as the unique multiaffine interpolating polynomial. ("Multiaffine" means that if you set all but one of the variables, say $p$, to constant, then you get a linear function $ap + b$ of $p$ for some constants $a$ and $b$ (which depend on the constants you chose for the other variables)).

Unfortunately, computing this extension for a boolean function of many variables is easily seen to be #P-hard, which means it's one of those hard problems that people hate because they can't solve it efficiently but can't prove that they can't. (Indeed, any easily computable canonical representation (extending to [0,1] or otherwise) applicable to all boolean functions would prove P=NP, so your problem as you stated it is pretty much hopeless. This particular canonical extension happens to be powerful enough to be #P-hard.) However, if your boolean expressions have only a few variables, then there is a very easy recursive algorithm to compute the extension. Here it is: $$f(p\_1,p\_2,\ldots,p\_n) = p\_1f(1,p\_2,\ldots,p\_n) + (1-p\_1)f(0,p\_2,\ldots,p\_n).$$ $f(1,p\_2,\ldots,p\_n)$ and $f(0,p\_2,\ldots,p\_n)$ are respectively the extensions in which you set the first variable to true and to false, which you can compute recursively. The basis case is when $n=0$, in which case you have a nullary function 0 or 1.

[Edit: If your boolean function is actually represented literally as a truth table, then there's no difficulty in computing its canonical extension to real values; actually, the recursive algorithm given above has $O(N)$ complexity, where $N=2^n$ is the number of rows in the truth table. Of course, producing a truth table for a function of many variables is time- and space-consuming, but if you already have the truth table, then you've already committed to it.]

There's actually one special case in which the extension is easy to compute for any number of variables, which may or may not help you: if you can write your boolean expression so each variable only appears once, then you can compute the extension in linear time. You use the transformation rules

• $(\text{not } A)\to (1-A)$,
• $(A \text{ and } B)\to (AB)$,
• $(A \text{ or } B)\to (A + B - AB)$

and simply recurse on the expression. My example $y \text{ or not } (x \text{ and } z)$ has this property, so let's use this procedure on it:

$$ y \text{ or } (\text {not } (x \text{ and } z)) \to y + (1-xz) - y(1-xz), $$ which you can see is the same as $1-x(1-y)z$. This, very unfortunately, fails miserably when you have multiple occurrences of any variable (just try $x \text{ and not } x$). However, the situation is just slightly more general than may appear initially: note that I gave transformation rules for AND, OR, and NOT. I did that because it's often convenient to express boolean expressions in terms of those three. You can in fact formulate a corresponding transformation rule for the boolean function $f$ of your choice (which is identical to the canonical extension of $f$: e. g., $1-x$ is the canonical extension of $\text{not }x$ and $x + y - xy$ is the canonical extension of $x\text{ or }y$), and you can apply that transformation to $f(A\_1,\ldots,A\_n)$ provided that no variable appears in more than one subexpression $A\_1,\ldots, A\_n$. For example, exclusive-or might be a useful boolean function, so you can use the transformation rule

• $(A \text{ xor } B)\to A + B - 2AB$.

This way, you can effectively build up a library of your favorite boolean functions and their canonical extensions, which you can use as transformation rules whenever you apply those functions to subexpressions with disjoint variable sets.

Finally, let me give you one "fun" way to compute the canonical extension based on the transformation rules that is tremendously useful when computing a canonical extension by hand: it turns out that you can apply any canonical transformation rule arbitrarily, even for arguments with non-disjoint sets of variables, expand everything out into a sum of monomials, and use the additional transformation

• $(x^2) \to x$.

as many times as you can until you're left with a multiaffine polynomial. (In fact, you're free to apply that transformation even without expanding your polynomial: e. g., $(1 -xy)^2 \to (1-xy)$ is perfectly valid.) To illustrate, let's apply that to the exclusive-or function:

$$ x \text{ xor } y = (x \text{ or } y) \text{ and not } (x \text{ and } y).$$

If we blindly apply the transformations for AND, OR, and NOT, we get:

$$ x \text{ xor } y \to (x + y - xy)(1-xy). $$ Expand that out into monomials: $$ (x + y - xy)(1-xy) = x + y - xy - x^2y - xy^2 + x^2y^2.$$Now replace $A^2$ by $A$ whenever possible: $$x + y - xy - x^2y - xy^2 + x^2y^2 \to x + y - xy - xy - xy + xy = x + y - 2xy,$$ which agrees with my canonical expression/transformation rule for XOR stated above.

See Karnaugh maps