Converting conditions with parentheses to equivalents with no parentheses

Question

I am developing an app where a user is able to add conditions to certain tasks.

For example he could have conditions a, b, c, d and combine them in a way where in the end it looks like :

(a AND b) OR ( c AND d )
OR
(a AND b AND c) or d
OR
(a AND !b) AND c OR !d

etc.

How can I convert these conditions to equivalents by removing parentheses?

Answer 1

Every expression in Boolean Algebra can be converted into an equivalent expression, without parenthesis, using only AND, OR, and ! (unary NOT).

Here is a simple but inefficient algorithm:

Using the example expression (a OR !b) AND c,

1. Build a truth table for every combination of truth values of the variables:

   | a | b | c | (a OR !b) AND c  |
   | 0   0   0 | 0                |
   | 0   0   1 | 1                |
   | 0   1   0 | 0                |
   | 0   1   1 | 0                |
   | 1   0   0 | 0                |
   | 1   0   1 | 1                |
   | 1   1   0 | 0                |
   | 1   1   1 | 1                |
   

2. For every set of values where the expression is true (every row with 1 in the rightmost column), create an expression using ANDs and ! that evaluates to true only for that specific set of values.

   | a | b | c | (a OR !b) AND c  |
   | 0   0   0 | 0                |
   | 0   0   1 | 1                |  (!a AND !b AND c )
   | 0   1   0 | 0                |
   | 0   1   1 | 0                |
   | 1   0   0 | 0                |
   | 1   0   1 | 1                |  (a  AND !b AND c )
   | 1   1   0 | 0                |
   | 1   1   1 | 1                |  (a  AND b  AND c )
   

3. Join the expressions with OR.

   (!a AND !b AND c ) OR (a  AND !b AND c ) OR (a  AND b  AND c )
   

4. The resulting expression is rarely minimal, so you may want to apply some minimization techniques afterward.

   (!a AND !b AND c) OR (a AND !b AND c) OR (a AND b AND c)
   =
   (!a AND !b AND c) OR (a AND c)
   =
   (!b AND c) OR (a AND c)
   

Ta-da!

It is important to note that building the truth table in step 1 is an O(2^n) operation (in number of variables), which is terrible. For cases with nontrivial numbers of variables, you'll probably want to use a different technique. The primary advantage of this algorithm is that it makes it very obvious how ANY expression can be transformed into the form you wanted.

Edit: To be clear, if you are using normal precedence rules you can remove the parenthesis in the final expression.