I implemented logical expressions using a binary tree in C++. Now I want to be able to simplify such an expression using rules like e.g.

but have issues with the commutativity. Assuming the expression is

then the tree would look like this:

     xor b
   xor true
true a

The expression can be simplified:

but I don't know how to apply the above rule to this tree since it is never directly applicable to one of the subtrees. Is there a better way than having to rotate the tree in all possible orders?

  • 1
    $\begingroup$ Convert to list, sort (so that the same variables/values are grouped together), apply rules, convert back to binary tree. $\endgroup$ – Dmitry Aug 21 '20 at 18:15
  • 1
    $\begingroup$ @Dmitry There's no need to sort, using a hashmap you can do it in $O(n)$ by only keeping track of the parity of each element. $\endgroup$ – orlp Aug 21 '20 at 21:45
  • $\begingroup$ @twinrix another idea is to allow ($\lnot a$) in your tree. That way you could use the reduction $true \oplus x = x \oplus true = \lnot x$ ( and ofc $false \oplus x = x$). You would end up with: xor(true, a) => not(a), xor(not(a),true) => a, xor(a,b) as final result. Other rules are $x\oplus \lnot x = true$, $x \oplus x = false$. $\endgroup$ – plshelp Aug 23 '20 at 0:21

Your Answer

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

Browse other questions tagged or ask your own question.