Convert list of Boolean functions into logic circuit

81 Views Asked by At

Assume that I have a list of variables $x_1,...,x_n$ and a list of Boolean functions $f_1(x_1,...,x_n),...,f_m(x_1,...,x_n)$

What I would like to do is create a circuit gate graph $G=(V,E)$ which satisfies:

  1. if $x\in V$ then there must be one of the following cases:
    • $x\in \{x_1,...,x_n\}$ is variable
    • $x$ is an and gate
    • $x$ is an or gate
    • $x$ is a not gate
  2. $E$ is a directed edge set representing the data flow from one node to another
  3. For each Boolean expression $f_i(x_1,...,x_n)$ there must be a node $v_i\in V$ based on the data flow and calculation, where $v_i$ and $f_i$ has the same value
  4. The graph should have the least nodes possible.

I can simplify a single boolean expression, but with many of them, it becomes complicated. Thus, I would like to ask if there is a proper algorithm to do this??

Thanks a lot!