2
$\begingroup$

Can someone please explain the inconsistent results I'm getting from BooleanTable and BooleanFunction?

Using the following truth table:

tt = {{1, 1, 1, 1} -> 1, {1, 1, 1, 0} -> 1, {1, 1, 0, 1} -> 1,
      {1, 1, 0, 0} -> 0, {1, 0, 1, 1} -> 1, {1, 0, 1, 0} -> 1,
      {1, 0, 0, 1} -> 0, {1, 0, 0, 0} -> 0, {0, 1, 1, 1} -> 1,
      {0, 1, 1, 0} -> 0, {0, 1, 0, 1} -> 0, {0, 1, 0, 0} -> 0,
      {0, 0, 1, 1} -> 0, {0, 0, 1, 0} -> 0, {0, 0, 0, 1} -> 0,
      {0, 0, 0, 0} -> 0};

I can produce the following boolean expression:

bb = BooleanFunction[tt, {a1, a0, b1, b0}]
(* (a0 && a1 && b0) || (a0 && b0 && b1) || (a1 && b1) *)

However, if I compute the truth values from this expression, I get different values from the original truth table:

tt1 = Boole[BooleanTable[bb]]
(* {1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0} *)

If I turn this into a truth table and compute its boolean expression, I get a different boolean expression from the first one computed:

tt1Full = MapThread[Rule,
  {Keys[BooleanTable[Boole[{a1, a0, b1, b0}] -> 0, {a1, a0, b1, b0}]], tt1}
 ]
(* {{1, 1, 1, 1} -> 1, {1, 1, 1, 0} -> 1, {1, 1, 0, 1} -> 1,
    {1, 1, 0, 0} -> 0, {1, 0, 1, 1} -> 1, {1, 0, 1, 0} -> 0,
    {1, 0, 0, 1} -> 0, {1, 0, 0, 0} -> 0, {0, 1, 1, 1} -> 1,
    {0, 1, 1, 0} -> 0, {0, 1, 0, 1} -> 1, {0, 1, 0, 0} -> 0,
    {0, 0, 1, 1} -> 0, {0, 0, 1, 0} -> 0, {0, 0, 0, 1} -> 0,
    {0, 0, 0, 0} -> 0} *)

bb1 = BooleanFunction[tt1Full, {a1, a0, b1, b0}]
(* (a0 && a1 && b1) || (a0 && b0) || (a1 && b0 && b1) *)

However, if I repeat this process, I end up with the original truth table and boolean expression it produces:

tt2 = Boole[BooleanTable[bb1]]
(* {1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0} *)

tt2Full = MapThread[Rule,
  {Keys[BooleanTable[Boole[{a1, a0, b1, b0}] -> 0, {a1, a0, b1, b0}]], tt2}
 ]
(* {{1, 1, 1, 1} -> 1, {1, 1, 1, 0} -> 1, {1, 1, 0, 1} -> 1,
    {1, 1, 0, 0} -> 0, {1, 0, 1, 1} -> 1, {1, 0, 1, 0} -> 1,
    {1, 0, 0, 1} -> 0, {1, 0, 0, 0} -> 0, {0, 1, 1, 1} -> 1,
    {0, 1, 1, 0} -> 0, {0, 1, 0, 1} -> 0, {0, 1, 0, 0} -> 0,
    {0, 0, 1, 1} -> 0, {0, 0, 1, 0} -> 0, {0, 0, 0, 1} -> 0,
    {0, 0, 0, 0} -> 0} *)

bb2 = BooleanFunction[tt2Full, {a1, a0, b1, b0}]
(* (a0 && a1 && b0) || (a0 && b0 && b1) || (a1 && b1) *)
$\endgroup$
  • $\begingroup$ My guess is that it is some behind-the-scenes sorting somewhere. Note that your original bb = BooleanFunction[tt, {a1, a0, b1, b0}] evaluates to a different function than if you switch the order of the symbols: bb = BooleanFunction[tt, {a1, b1, a0, b0}]. Then Boole[BooleanTable[bb]] is different in the two cases. $\endgroup$ – march Aug 24 '16 at 20:40
  • $\begingroup$ Indeed. If you use {a0, a1, b0, b1} (the canonical Mathematica ordering of those symbols) throughout, everything is consistent. $\endgroup$ – march Aug 24 '16 at 20:45
  • $\begingroup$ Further evidence that it is a sorting issue. When you evaluate Cases[BooleanTable[bb] // Trace, {a0, a1, b0, b1}, Infinity] with your original bb, you find many instances of {a0, a1, b0, b1}, but if you evaluate Cases[BooleanTable[bb] // Trace, {a1, a0, b1, b0}, Infinity], you get nothing back. The point, I think, is that BooleanTable cannot know the original ordering of the symbols, and so it uses the canonical ordering, which messes things up. $\endgroup$ – march Aug 24 '16 at 20:53
2
$\begingroup$

The issue here is sorting of the list {a1, a0, b1, b0} that is going on under the hood in the evaluation of BooleanTable. For evidence of this, if we "spelunk" the evaluation of BooleanTable using your original tt and bb, the following occurs:

tt = ... (*as defined in the OP*);
bb = BooleanFunction[tt, {a1, a0, b1, b0}]
(* (a0 && a1 && b1) || (a0 && b0) || (a1 && b0 && b1) *)

Then,

Through[{Length, Union}@Cases[BooleanTable[bb] // Trace, {a0, a1, b0, b1}, Infinity]]
(* {13, {{a0, a1, b0, b1}}} *)

and

Cases[BooleanTable[bb] // Trace, {a1, a0, b1, b0}, Infinity]
(* {} *)

The point is that BooleanTable cannot know the original ordering {a1, a0, b1, b0} of the list, because you have not specified it, and so it must use the canonical ordering {a0, a1, b0, b1}. This introduces sorting errors relative to your original list of symbols, and thus the following results aren't consistent.

My best guess for why doing it twice recovered the original list is because {a1, a0, b1, b0} and {a0, a1, b0, b1} are related by an order-2 permutation, and so doing the same thing twice "undid" the original sorting.

Finally, the solution.

  • Always use a list of symbols in canonical ordering, by using for instance Sort@{a1, a0, b1, b0} or an automatically sorted list like Array[a, 4], or

  • Use the second argument of BooleanTable that specifies the symbols, and keep the same ordering throughout, e.g.

    bb = BooleanFunction[tt, {a1, a0, b1, b0}];
    BooleanTable[bb, {a1, a0, b1, b0}];
    

    This fixes the inconsistency. Notice that

    lst = {a0, a1, b0, b1};
    BooleanTable[BooleanFunction[tt, Sort@lst]] === BooleanTable[BooleanFunction[tt, lst], lst]
    (* True *)
    

    For a pretty simple example of this, evaluate the following and note that the results are different:

    BooleanTable[a || (b && c), {a, b, c}]
    BooleanTable[a || (b && c), {b, c, a}]
    
$\endgroup$
  • $\begingroup$ Thanks for taking the time to explain this, particularly the reason why providing a variable list in BooleanTable makes such a difference. $\endgroup$ – BCott Aug 24 '16 at 21:12
  • $\begingroup$ @BCott. I recommend taking my answer with a slight grain of salt. This is the very first time I have looked into these functions, so I could easily have missed something. Nonetheless, I'm pretty sure that this is the issue. $\endgroup$ – march Aug 24 '16 at 21:17

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.