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?