# How to effectively determine if given truth table is equal to another one (when we take into account that they can differ at order of inputs)

I'm working on some project which is not really related to digital circuits but rather boolean algebra analysis.

In some point I stucked at algorithmic or maybe data structure problem: How to effectively determine if given truth table is equal to another one (when we take into account that they can differ at order of inputs).

For now I hold truth tables in bitvectors for example nand truth table will be stored as: 1110 because:

A | B | R
0 | 0 | *1*
0 | 1 | *1*
1 | 0 | *1*
1 | 1 | *0*


However for some circuits thruth table in my representation might look tottaly different for the same circuit when inputs order is changed. For example: simulate this circuit – Schematic created using CircuitLab

Truth table:

A | B | C | R
0 | 0 | 0 | 0
0 | 0 | 1 | 1
0 | 1 | 0 | 0
0 | 1 | 1 | 1
1 | 0 | 0 | 0
1 | 0 | 1 | 1
1 | 1 | 0 | 1
1 | 1 | 1 | 1


but when we change A <-> C inputs like: simulate this circuit

truth table become:

A | B | C | R
0 | 0 | 0 | 0
0 | 0 | 1 | 0
0 | 1 | 0 | 0
0 | 1 | 1 | 1
1 | 0 | 0 | 1
1 | 0 | 1 | 1
1 | 1 | 0 | 1
1 | 1 | 1 | 1


So at it is visible I cannot just compare my "raw" form of truth tables for this case because 01010111 != 00011111 while from my perspective these truth tables represent exactly the same circuits with only inputs order difference.

Is there any smart representation of truth tables which will allow me to check this kind of equality and tell me which inputs from first thruth table maps to which inputs from second one?

For now I only have idea to generate all "raw" thruth tables based on inputs order permutations for given "start" truth table and during comparation check if any of these permutations is equal, but this is very memory consuming and slow method.

Do you have any idea how to solve this problem? Maybe there are existing scientific papers about this?

• Turn the truth tables into gates and compare the gate setup. That is the only thing that is exactly identical in both of your cases. Or turn it into boolean algebra "A&B+C" vs "B&C+A" and compare two text strings where you swap the signals around until your text matches. – Harry Svensson Nov 14 '17 at 10:27
• Put your formulas into DNF or CNF and permute the input order. – PlasmaHH Nov 14 '17 at 10:28
• @PlasmaHH: thank you for idea that DNF or CNF can help. I figured out that after conversion of both truth tables to CNF or DNF it's fairly easy to find if variable in one expression can be variable in second expression and recursively check if after choosen variable substitution next one can be substituted by ellimination. Suppose CPU complexity of this algorithm is not so big, while memory complexity is negligible. When I finish my implementation, I will try to show it here bacause I couldn't find any materials about this for a long time. – Tomasz Frydrych Nov 14 '17 at 12:46
• @TomaszFrydrych I'm guessing that this topic you've brought up is probably a fairly hot topic in the area of cryptography. This is exactly the kind of question they'd be asking themselves to solve. I'd be looking at publications related to "mod 2", Galois fields, Walsh, spectral analysis, and probably also anything related to algebraic normal forms (there are several sub areas here.) – jonk Nov 14 '17 at 18:27

Consider the case where ABC = 100: in the first circuit it yields 0, in the second it yields 1. So the logic is different even though the gates are the same. If the order of the inputs did not matter, how would you differentiate between ABC = 100 and ABC = 001 since they produce different output in your case?