Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 2n 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.

share|improve this question
1  
Okay, wait a minute. Your ultimate goal is to extend the boolean function to real values in a canonical way, right? The whole discussion about finding a minimal expression being just a means to that end? If you already have a truth table for the function, then it's actually easier to work directly with the truth table rather than first trying to produce a minimized boolean expression. In particular, you can just use the recursive algorithm given in my reply below. There's no reason not to, if you already have the truth table! –  Darsh Ranjan Nov 11 '09 at 20:37
add comment

5 Answers 5

up vote 8 down vote accepted

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.

share|improve this answer
    
It was difficult to choose a best answer here. Many of the answers were useful. Thanks to all. –  Rhubbarb Nov 15 '09 at 18:32
add comment

See Karnaugh maps

share|improve this answer
    
Yes, we used this all the time in my Telecommunications degree; they provide a fairly straight algorithm that efficiently reduces any boolean function to its minimal expression, given its table. –  Jose Brox Nov 11 '09 at 9:24
add comment

For mor information, you should look at any book about Electronic Design Technology. When you manufacture a microchip, you want to keep it as simple as possible while integrating all the functions you are interested on. Thus, you want to minimize the number of transistors you use (i.e., to minimize the number of logic gates which implement your functions), which gets you to develop general techniques to achieve this.

Although I have not read it, I think you can give a try to the following book:

"Principles of CMOS VLSI Design: A System Perspective (2nd edition)", N. WESTE and K. ESHRAGHIAN, Addison-Wesley, 1993.

share|improve this answer
add comment

By way of clarifying the question to the point where it might get a definite answer, or at least a parametric set of answers, I think it would help to draw the distinction between the language-fixed and the language-variable sides of the problem a little more sharply. Rhubbarb alluded to this distinction in asking the question, but it could be formalized further by introducing a parameter $L$ for the particular calculus or formal language that is used to describe the object domain $O$, which I'm guessing is something like a union over sets of boolean functions of types $\mathbb{B}^k \to \mathbb{B}$, where $\mathbb{B} = \lbrace 0, 1 \rbrace$ and $k$ is a positive integer.

share|improve this answer
add comment

I doubt if there's anything like the best of all possible formal languages for boolean expressions, but there are many ways of coming up with calculi that are more efficient than most of the ones currently in common use.

You might enjoy exploring the possibilities of using minimal negation operators as the fundamental primitives of a propositional calculus.

A calculus that is very efficient from both conceptual and computational standpoints is based on just two types of logical connectives, both of variable $k$-ary scope. The formulas of this calculus parse into a family of graph-theoretical data structures whose underlying graphs are called "painted and rooted cacti" (PARCs). Hence the name "cactus language" for this style of propositional calculus, in either its traversal string or parse graph forms.

  • The first kind of propositional expression is a parenthesized sequence of propositional expressions, written as $⦗ ~ e_1 ﹐ e_2 ﹐ \ldots ﹐ e_{k-1} ﹐ e_k ~ ⦘$ and read to say that exactly one of the propositions $e_1, e_2, \ldots, e_{k-1}, e_k$ is false, in other words, that their minimal negation is true. A clause of this form maps into a PARC structure called a lobe, in this case, one that is painted with the colors $e_1, e_2, \ldots, e_{k-1}, e_k$ as shown below.

    Cactus Graph Lobe Connective

  • The second kind of propositional expression is a concatenated sequence of propositional expressions, written as $e_1 ~ e_2 ~ \ldots ~ e_{k-1} ~ e_k$ and read to say that all of the propositions $e_1, e_2, \ldots, e_{k-1}, e_k$ are true, in other words, that their logical conjunction is true. A clause of this form maps into a PARC structure called a node, in this case, one that is painted with the colors $e_1, e_2, \ldots, e_{k-1}, e_k$ as shown below.

    Cactus Graph Node Connective

All other propositional connectives can be obtained through combinations of these two forms. Strictly speaking, the parenthesized form is sufficient to define the concatenated form, making the latter formally dispensable, but it is convenient to maintain it as a concise way of expressing more complicated combinations of parenthesized forms. While working with expressions solely in propositional calculus, it is easiest to use plain parentheses for logical connectives. In contexts where ordinary parentheses are needed for other purposes an alternate typeface — for example, $⦗ ~ ﹐ ~ ⦘$ — may be used for logical operators.

See above links for further details.

share|improve this answer
    
Jon, please remember that when you edit this post, the question is moved to the top of the homepage. Unless you're making a substantive edit to your post, this can become very annoying. So please only try testing various things when you're also adding meaningful substance. All the editing also explains why the post was made community wiki; after a certain number of edits, a post is automatically converted to wiki (see mathoverflow.net/faq#communitywiki). –  Anton Geraschenko Nov 12 '09 at 2:25
    
Sorry, we don't have a sandbox aside from the preview you get before making the post (which is very buggy, I know; we're pushing to make it better). I don't think there is a way to center images or text. See mathoverflow.net/editing-help for a list of available markdown syntax and meta.stackexchange.com/questions/1777/… for a list of allowed html tags. –  Anton Geraschenko Nov 12 '09 at 2:56
    
Please scale down the images yourself before uploading them to your image host. Also, please don't make incremental edits. Any time your edit comment is "continuing exposition", you should not submit the edit. Just work on your answer until you're done, and then submit the edit. MO is not meant to be a notebook, and it disturbs other users when you use it as one. If your answer is so long and involved that it requires such extensive editing, you should probably just make it into a blog post and make your MO answer a summary and a link to the blog post. –  Anton Geraschenko Nov 12 '09 at 4:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.