Inconsistent results with booleanfunction and booleantable

Question

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) *)

Answer 1

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