Number of states in an AND-OR DAG Consider a DAG of $N$ nodes, where each node can take on one of two value, either false, $0$ or true, $1$. Additionally, let each non-leaf nodes (nodes with parents) be assigned a type: either an AND node or an OR node.

Under this setting, I define a notion of a feasible state. A state is a feasible if and only if:


for every AND node in the true state, all of its parents are in the true state.  
for every OR node in the true state, at least one of its parents are also in the true state.


(Note that a state can still be feasible even if some AND node is false but all of its parents are true.)

As an example, consider the following DAG. Grey nodes are leaf nodes (nodes 1 and 2), orange nodes are OR nodes (node 3), and red nodes are AND nodes (nodes 4,5, and 6). Note that nodes 4 and 5 can be classified as either AND nodes or OR nodes since they only have one parent.



There are 18 feasible states of this DAG if I counted right, as seen below. Nodes with a dark interior are true; nodes with a white interior are false.



Question: My question is, given a DAG with AND-OR nodes, what is the expression for the total number of feasible states?
Your problem is equivalent to counting the number of satisfying assignments for a monotone Boolean circuit. The restricted version in which the circuit is of the form $(x_{i_1} \lor x_{j_1}) \land \cdots \land (x_{i_m} \lor x_{j_m})$ (where indices can repeat) is known as #Monotone-2SAT and is known to be #P-complete. This means that there is probably no efficient algorithm for solving your problem. In particular, you won't find any closed form.

Roth showed that the number of satisfying assignments is even NP-hard to approximate within $2^{n^{1-\epsilon}}$ for any $\epsilon &gt; 0$. This means that even finding a decent closed-form approximation can be ruled out.