SanchitTaliyan's blog

Boolean Expression Simply and Solve
By SanchitTaliyan, history, 6 years ago, In English

Hi Everyone,

I was wondering, if I can try to solve boolean expression using recurssion in C++. But being a beginner, I am not able to get progress in this. I'll be getting the expression like a string. I have generated a truth table using standard bitwise techniques, but not able to understand how to simplify such complex expressions. eg : (a+(b.c)).(d+e.f)+(g.(t+h)) here, alphabets are boolean var, and + represents bitwise OR , '.' represents bitwise AND. Anyhelp will be appreciated :)

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 19   Vote: I like it 0 Vote: I do not like it

Yes, it is possible. You can create a C++ binary-tree data-structure equivalent to a given Boolean expression f( x1, x2, ...., xn ) in which:

  1. A variable (xi) is a leaf-node with no children nodes, whose value is the binary value assigned it.
  2. An (X OR Y) expression is a non-leaf node with two children nodes representing Boolean expressions X and Y, whose value is true if and only if X is true or Y is true.
  3. An (X AND Y) expression is a non-leaf node with two children nodes representing Boolean expressions X and Y, whose value is true if and only if X is true and Y is true.
  4. The value of the Boolean expression is equal to the value of the root node of the binary-tree representing it when the n-bit vector [ x1, x2, ...., xn ] is assigned to a particular point in the n-dimensional Binary hypercube B(n) = { [ x1, x2, ...., xn ] | xi in B for all i in [1,n] }, where B = {0,1}. The sought value of the root node is computed recursively, where the termination condition for the recursive function is reaching a leaf-node.

Finally, it should be noted that the binary-tree data-structure can be generalized to a tree data-structure with any number of children nodes according to the logic primitives used the the Boolean expression. For example, a (NOT X) Boolean expression can be represented as a non-leaf node with one child node for (X) only. Another example is the Boolean expression (if X then Y else Z), which can be represented as a non-leaf node with three children nodes (X, Y and Z). Boolean algebra can be applied to simplify the tree without evaluating it for a particular point in the n-dimensional Binary hypercube. It is also possible to restrict the logic primitives used in non-leaf nodes the tree data-structure to 2-input AND and 1-input NOT only, check the following Wiki about AND-Inverter Graph AIG.

→ Reply