# Simplifying expressions containing binary variables

Consider an expression with two binary variables, $$a,b\in\left\{ 0,1\right\}$$, given by $$F=(1-a-b)^{3}(1-b)$$, with truth table:

{a,b}={0,0} -> F=1
{a,b}={0,1} -> F=0
{a,b}={1,0} -> F=0
{a,b}={1,1} -> F=0


A simpler way of writing this would be $$F=G=(1-a-b)(1-b)$$, which can be seen to produce the same truth table. However, if I try to do this with the following Mathematica input

FullSimplify[(1-a-b)^3 (1-b), {a, b} ∈ {0, 1}]


it doesn't do the trick. How can we do this in general and for more complicated expressions with more than 2 variables? I looked into this question but it doesn't seem to be dealing with the same problem I'm presenting here.

You can use the assumptions that a^2 == a to do this:

Simplify[F, a^2==a && b^2==b]


(-1 + a) (-1 + b)

• Thank you. It's simple and it does the job. – almagy Sep 21 '20 at 14:16

The earlier Q/A to which you linked provides a simpler form for F than what you proposed.

Clear["Global*"]

binarySimplify[eq_, vars_] := Module[{rels, gb}, rels = (#^2 - # &) /@ vars;
gb = GroebnerBasis[Join[{eq /. Equal -> Subtract}, rels], vars];

bs = binarySimplify[F == (1 - a - b)^3 (1 - b), {a, b, F}]

(* {1 + a b == a + b + F, a F == 0, b F == 0} *)


Working from the first equation

sol = Solve[bs[[1]], F][[1]] // Simplify

(* {F -> (-1 + a) (-1 + b)} *)


This definition of F is simpler than what you proposed and produces the same binary table.

Table[{a, b, F /. sol}, {a, 0, 1}, {b, 0, 1}] // Flatten[#, 1] & //
Prepend[#, {a, b, F}] & //
Grid[#, Frame -> All] &


So the simplified form for F is

F == (F /. sol)

(* F == (-1 + a) (-1 + b) *)

• Thank you. I should have looked more carefully into this. – almagy Sep 21 '20 at 14:16

Maybe the following is not exactly what you want, but may be useful for larger problems.

First, convert your function F to a boolean function G:

F[a_, b_] = (1 - a - b)^3 (1 - b);
# -> F @@ # & /@ Tuples[{0, 1}, 2]
(*    {{0, 0} -> 1, {0, 1} -> 0, {1, 0} -> 0, {1, 1} -> 0}    *)

G = # -> F @@ # & /@ Tuples[{0, 1}, 2] /. {0 -> False, 1 -> True} // BooleanFunction
(*    BooleanFunction[...]    *)


Now we can work with this BooleanFunction object: there are many functions available, for example

BooleanConvert[G][a, b]
(*    ! a && ! b    *)


(note that BooleanConvert can output many different formats).

Try to convert the result back to an algebraic expression:

BooleanConvert[G][a, b] //. {! x_ -> 1 - x,
x_ && y_ -> x y,
x_ || y_ -> x + y - x y}
(*    (1 - a) (1 - b)    *)
`
• Thank you for providing this. How would you say this compares against Carl Woll's solution? – almagy Sep 21 '20 at 14:21
• @almagy I don't really know, but I have a feeling that some simplifications may require stronger tools than $a^2=a$ and $b^2=b$. Boolean conversions may offer such stronger tools. Maybe you can show some examples where the results differ? – Roman Sep 21 '20 at 19:42
• I'm using this to simplify a few expressions where some variables are kept as general parameters (so, it's a bit different from the example above where all variables are binary). I think your current solution doesn't handle such a situation, right? – almagy Sep 21 '20 at 20:31
• Yes that's right. – Roman Sep 22 '20 at 11:49