EP and positive boolean circuits

A positive Boolean circuit is an acyclic graph with

sources, each one corresponding to a variable

, and a root representing the output. The intermediate vertices represent the Boolean operator $\wedge$ (and).

The size of the circuit is the number of vertices, while the depth is the maximum length of a path in the graph. It can be easily observed that every positive Boolean function, by using its irredundant PDNF (see Sec. 2), can be represented through a Boolean circuit with depth . As an example, consider the positive Boolean function $\varphi _1$ . Its irredundant PDNF (4) corresponds to the Boolean circuit represented in Fig. 1.

**Figure 1:** Circuit representing the irredundant PDNF of the function $\varphi _1$ .
$\begin{figure}\setlength{\unitlength}{2000sp} \begin{center} \begin{pictur... ...0){\makebox(0,0)[lb]{$\bigwedge$}} \end{picture} \end{center} \end{figure}$

Note that the circuit has depth and size (i.e. the number of logical AND).

An EP circuit is defined as an acyclic graph of two levels with:

sources that represent the input variables $z_1,\dots ,z_r$ ;
intermediate vertices. Each vertex represents an ES i.e. collects all the input variables (the genes) belonging to the ES. Moreover, it contains the number of genes that need to be modulated in order to make the ES active;
A root representing the coefficient , i.e. the number of ESs that have to be active for verifying the EP.

The size of an EP circuit is defined, likewise the positive Boolean circuit, as the number of vertices, i.e., in this case, the number of ESs.

As an example, consider the EP circuit in Fig. 2, representing the function $\varphi _1$ described in (5).

**Figure 2:** EP Circuit representing the function $\varphi _1$ .
$\begin{figure}\setlength{\unitlength}{2000sp} \begin{center} \begin{pictur... ...-1780){\makebox(0,0)[lb]{$q_2=2$}} \end{picture} \end{center} \end{figure}$

We can note that the two circuits in Fig. 1 and in Fig. 2 are similar and that, in general, it is very simple to pass from a Boolean positive circuit to an EP circuit. In fact, it is sufficient to substitute each logical AND ( $\bigwedge$ ) with a vertex having , where is the number of input variables for the th vertex, and the logical OR ( $\bigvee$ ) with a root having . This observation directly shows that every Boolean positive function can be represented through an EP circuit whose size is equal to that of the corresponding Boolean positive circuit.