2
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

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

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

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

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];
  Simplify@Thread[Complement[gb, rels] == 0]]

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] &

enter image description here

So the simplified form for F is

F == (F /. sol)

(* F == (-1 + a) (-1 + b) *)
$\endgroup$
1
  • $\begingroup$ Thank you. I should have looked more carefully into this. $\endgroup$ – almagy Sep 21 '20 at 14:16
1
$\begingroup$

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)    *)
$\endgroup$
4
  • $\begingroup$ Thank you for providing this. How would you say this compares against Carl Woll's solution? $\endgroup$ – almagy Sep 21 '20 at 14:21
  • 1
    $\begingroup$ @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? $\endgroup$ – Roman Sep 21 '20 at 19:42
  • $\begingroup$ 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? $\endgroup$ – almagy Sep 21 '20 at 20:31
  • $\begingroup$ Yes that's right. $\endgroup$ – Roman Sep 22 '20 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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