# How to add variables to boolean expression and get conjunctive normal form?

I have the boolean expression (a && !b). I want to add variables c, d into the expression and then have Mathematica transform the expression into conjunctive normal form. I would like it to go something like this:

a&&!b
= (a && !b && c) || (a && !b && !c)
= (a && !b && c && d) || (a && !b && c && !d) || (a && !b && !c && d) ||
(a && !b && !c && !d)


Although a human can do this easily, how can can I get Mathematica to do it? What are the commands?

• Take a look at BooleanConvert and forms it has available. But I don't know how to use it for your purpose :)
– Kuba
Aug 29, 2013 at 8:40

I don't now that I really understand your question, but from a pure expression manipulation perspective this might be useful:

Or @@ And @@@ Tuples[{{a && ! b}, {c, ! c}, {d, ! d}}]


(a && ! b && c && d) || (a && ! b && c && ! d) || (a && ! b && ! c && d) || (a && ! b && ! c && ! d)

The same operation a bit more concisely:

Or @@ Tuples[{a && ! b} && {c, ! c} && {d, ! d}]

• I still don't believe that this is not automatic :P Are you really going to put && {sym, ! sym} each time? But +1 for Tuples I don't know why I decided to use Outer.:)
– Kuba
Aug 29, 2013 at 10:57
• @Kuba Frankly I don't understand the question so I wasn't sure what operation was to be done. I voted for your answer by the way. I think my code is open ended in that you could have any number of variations in each sublist. Aug 29, 2013 at 10:59
• I have a CNF and BooleanMinimize can simplify it to a&&!b. Now I want to perform the revert process. Aug 29, 2013 at 11:19

Since I don't know how to incorporate BooleanConvert here is a walkaround for this case:

conv = Or @@ Flatten[Outer[
And,
{#1},
Sequence @@ Transpose[{Not /@ #2, #2}]]
, 2] &


.

conv @@ {a && ! b, {c}}

(a && ! b && ! c) || (a && ! b && c)

conv @@ {a && ! b, {c, d}}

(a && ! b && ! c && ! d) || (a && ! b && ! c && d) || (a && ! b && c && ! d) ||
(a && ! b && c && d)