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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
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)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you. It's simple and it does the job. $\endgroup$
    – almagy
    Commented Sep 21, 2020 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) *)
Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you. I should have looked more carefully into this. $\endgroup$
    – almagy
    Commented Sep 21, 2020 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)    *)
Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for providing this. How would you say this compares against Carl Woll's solution? $\endgroup$
    – almagy
    Commented Sep 21, 2020 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
    Commented Sep 21, 2020 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
    Commented Sep 21, 2020 at 20:31
  • $\begingroup$ Yes that's right. $\endgroup$
    – Roman
    Commented Sep 22, 2020 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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