This is not an urgent question, but something I've been curious about for quite some time.


Consider a Boolean function in *n* inputs: the truth table for this function has 2*n* rows.


There are uses of such functions in, for example, computer graphics: the so-called ROP3s (ternary raster operations) take three inputs: *D* (destination), *S* (source) and *M* (mask). All three are planes of bits, and the result is returned to the destination plane of bits. Now, this is only really applicable to 2-colour (black & white) or 8-colour displays (regarding the red, green, blue planes separately). A given ROP3 is given a code from 0 to 255, a number which represents the pattern of the output bit, down the rows of the table. Similarly, ROP2s have a value from 0 to 15. ROPs may also be given names, especially when the logical connective of which the truth table is an extension is a simple one, such as AND, XOR or SRC (source).


An expression for any truth table (or ROP) may be found in terms of an expressively-complete set of connectives (usually unary or binary, sometimes nullary too). [Well, I suppose this statement is itself a tautology!] For example, the sets {NOT, AND}, {NOT, OR}, {NAND} are each expressively complete.


One commonly used (redundant) expressively complete set is {NOT, AND, OR}. Two particularly common canonical sets of expressions over this set are the conjunctive normal form (CNF) and disjunctive normal form (DNF). Both of these are rather verbose.


There is also a notion of a minimal expression over a set of connectives, defined variously. The count might be of instances of a variable or of connectives. There might be a bound to the depth or breadth of the expression (perhaps).


The Boolean connectives might be extended to the set ***R***[0,1], for fuzzy logic; that is, the connectives are over ***R***[0,1], with the restriction to {0,1} being the usual Boolean function. There are many ways to do this; it is possible to preserve some but not all the usual properties (e.g. associativity, idempotency) of the connectives. [NOT(x) would usually be interpreted as (1−x); AND(x,y) could be (x\*y) or (min{x,y}), or in many other ways.]


Such extensions may be used, for example, to give a meaning to a ROP3 as applied to 256-level monochrome images (to combine or 'mix' such images) or to planes of full-colour images. (Necessarily, some truncation or 'quantisation' must take place.)


However, two expressions have the same function over {0,1} will generally have different functions over ***R***[0,1]. Rather than choosing some arbitrary expression, it would be an advantage to choose some canonical or minimal expression.


How much is known about this field? Are there any good on-line references? I'm particularly interested in definitions of, theorems about, and algorithms for the generation of minimal or canonical expressions.



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. 


