# Are there any Truth Table to Boolean expression converters? [closed]

I am working on Bent functions that are of interest in cryptography. I developed an algorithm that construct such functions. However, I need some tools to calculate boolean expression from the truth table. Is there such a application or applet available? (Actually I am interested in expressions without any NOTs).

• How many boolean inputs/outputs are we talking about? sontrak.com can handle up to 16 if I'm not mistaken. – orlp Oct 28 '13 at 8:59
• For relatively small number of variables it might be simpler just to construct your own? A naive method would be to iterate based on the fact $f(x,y,z)=z*f(x,y,1)+(1-z)f(x,y,0)$ – Cryptographeur Oct 28 '13 at 10:43
• @nightcracker That was nice, thanks. But I need one that return an expression without any NOTs. – Mahdi Khosravi Oct 28 '13 at 11:00
• karnaugh maps will help – ratchet freak Oct 28 '13 at 11:34
• This question appears to be off-topic because it is about Boolean circuits/formal logic in general, not cryptography, and because it is a reference recommendation/request, which is off-topic here. – Reid Oct 28 '13 at 19:47

It depends on what you are interested in, when building your expression. If you want to optimize for speed and/or expression size, then the problem is hard, and no good solution is known. You can either try to enumerate all expressions, looking for a match with your table (this is exponential in the size of the expression, so it becomes prohibitive real fast); or you can start with a generic expression as a tree of multiplexers then try to find local shortcuts.

You can often work with the "fake multiplexer": for inputs $a$ and $b$, and control $c$, output $a \oplus (b \wedge c)$: in this way, the bit $c$ selects between values $a$ (if $c = 0$) and $a \oplus b$ (if $c = 1$). For a function $f : n \rightarrow 1$ ($n$ input bits, $1$ output bit), you work recursively:

• An expression with no input is either $0$ or $1$ (it is a constant).
• You define $f_0 : n - 1 \rightarrow 1$ such that $f_0(x_1, x_2,... x_{n-1}) = f(x_1, x_2,... x_{n-1}, 0)$ (that's the function $f$ when the last bit is $0$).
• You define $f_1 : n - 1 \rightarrow 1$ such that $f_1(x_1, x_2,... x_{n-1}) = f(x_1, x_2,... x_{n-1}, 1)$ (that's the function $f$ when the last bit is $1$).
• You compute the boolean expression $e_0$ for $f_0$, and the boolean expression $e_1$ for $f_0 \oplus f_1$.
• The expression for $f$ is now $e_0 \oplus (x_n \wedge e_1)$.

(Note: if you have only bitwise AND, OR and XOR, and not access to constants, then you cannot build all functions; in particular, you won't be able to make a $1$ out of an all-$0$ input. If you really don't want a NOT or the equivalent "$\oplus 1$", and the output of your function for an all-zero input is $1$, then there is no solution. On the other hand, if the function output for an all-zero input is $0$, then you can make a serviceable $1$ by ORing all input bits together.)