title: Parsing and computing boolean set definitions
body: <p>Say I have a set <code>S</code> defined as a string, e.g. as follows:</p>
  
  <pre><code>S = '(A or B) and not(A and C)'
  </code></pre>
  
  <p>where A, B and C are finite sets, e.g.:</p>
  
  <pre><code>A = {0, 1}
  B = {0, 2}
  C = {1, 3}
  </code></pre>
  
  <p>If we analyze <code>S</code> step by step, we have:</p>
  
  <pre><code>(A or B)   = {0, 1, 2}
  (A &amp; C)    = {1}
  not(A &amp; C) = {0, 2, 3}
  </code></pre>
  
  <p>which gives us the final result:</p>
  
  <pre><code>S = {0,2}
  </code></pre>
  
  <p>How can I compute the elements of <code>S</code> given its definition as a general boolean formula? </p>
  
  <p>I don't quite know how to start addressing this problem. On one hand I wonder if I need to use a full <strong>lexical parser</strong>. Also, after some reading I also found two concepts that seem that highly related, but don't know how they would apply:</p>
  
  <ul>
  <li><a href="http://en.wikipedia.org/wiki/Canonical_normal_form" rel="noreferrer">Canonical Normal Forms</a> </li>
  <li><a href="http://en.wikipedia.org/wiki/De_Morgan%27s_laws" rel="noreferrer">De Morgan's laws</a></li>
  </ul>