Take the 2-minute tour ×

I'm trying to represent boolean expressions in sum of products form(SOP) in Python with only lists.

For example, I have boolean expression


I need to find a list equivalent of the expression above, so by reading the list or nested list and following certain rules to read the list, the program/programmer reading the list will be able to convert it back to the boolean expression.

One way I thought of doing this is constructing nested lists. Two rules to follow:

  1. elements in the same list are ANDed together
  2. lists are parallel to each other, therfore ORed together.

So for the example above, it will translate to:


But this set of rules conflicts itself in some cases. For example, given [[E,F],[D,C]], it can either mean EF+DC or EFDC, as [E,F] and [D,C] are in the same list so they should be anded, but lists are parallel so they should be ORed too.

I feel like I need to set some precedence between the 2 rules above, or add another rule to make it more clear.

Any thoughts or suggestions are welcome. Also it's not homework, just something for fun. Thanks in advance!!

share|improve this question
You might want to accept answers from more of the questions you ask or at least indicate if you have an acceptable answer. –  Paddy3118 Jul 20 '12 at 11:02

5 Answers 5

up vote 3 down vote accepted

You could go the LISPy route and have the first item in each list be the operator. For example, the expression you gave


would become

['or', ['and', A, B, C], ['and', D, E, ['or', ['and', F, G], ['and', I, H]]]]

Which is pretty readable, considering. Cheers!

share|improve this answer
tuples instead of lists would resemble lisp more closely –  georg Jul 13 '12 at 23:20

Why lists and not trees?

OR = 0
AND = 1

class OpNode:
   def __init__(self, op, left, right):
       self.op = op
       self.left = left
       self.right = right

class LeafNode:
    def __init__(self, name, value):
       self.name = name
       self.value = value

A = LeafNode("A", True)
B = LeafNode("B", True)

exp = OpNode(OR, A, OpNode(AND, B, 
                                          LeafNode("C", False), 
                                          LeafNode("D", True))))

exp would be the equivalent of A+B(C+D)

share|improve this answer
I believe it is just a matter of fun! –  rlinden Jul 13 '12 at 20:50
This can actually be a good idea. Use a binary tree to represent a boolean expression, all the leaf nodes are the variables, and their parent nodes being the operation –  turtlesoup Jul 13 '12 at 21:00

I think that you can add an additional rule that when the basic elements beside the comma are lists, then they are ORed together. Hence, you will not get this conflicted interpretation.

Therefore [A,B] has both elements as singletons, so they and ANDed, but [[A,B],[C,D]] has ANDs between singletons and ORs between lists, resulting in AB+CD.

In a way, that means that your rule #2 has precedence over rule #1.

share|improve this answer
That might solve part of the problem, but it fails when there are both lists and basic variables in the same list. What's [[A,B],C] then? –  turtlesoup Jul 13 '12 at 20:52
[[A,B], C] would be AND, [[A,B], [C]] would be OR. –  Luke Jul 13 '12 at 20:54
But then how would you write (A AND B) AND (C AND D) ? Maybe [[A,B], [C,D], True] ? –  Luke Jul 13 '12 at 20:56
@Luke how do you AND two lists together then? for example express (A+B)(C+D)? –  turtlesoup Jul 13 '12 at 20:58
@Luke just about to ask that. that one is actually what got me stuck –  turtlesoup Jul 13 '12 at 20:59

You could have the outermost list mean "OR all direct entries", then swap the meaning of nested lists between OR and AND direct entries. If you count levels of nesting from the outermost being 1 then the terms in odd levels of nesting should be OR'd and the terms in even levels of nesting should be AND'd together.


Becomes [[A,B,C],[D,E,[[F,G],[I,H]]]]

Here's some Python code:

It returns an expression from the list form:

def to_bool(lst, depth=0, or_them=True):
    if type(lst) == str:
        return lst
        partial = ( '+' if or_them else ''
                  ).join( to_bool(x, depth+1, not or_them) for x in lst)
        if or_them and depth > 0:
            # Mixture of variables and sublists so parenthesize
            return '(' + partial + ')'
            return partial

def main():
    print('The list form of the boolean expression:', e)
    print('The boolean expression:', to_bool(e))

if __name__ == '__main__':

Its output:

The list form of the boolean expression: [['A', 'B', 'C'], ['D', 'E', [['F', 'G'], ['I', 'H']]]]
The boolean expression: ABC+DE(FG+IH)
share|improve this answer

Use lists for AND, tuples for OR.

share|improve this answer

Your Answer


