# Counting number of assignments restricted by implications

Suppose we have $$n$$ boolean variables, $$x_1, \dots, x_n$$. Some boolean variables can have implication relationships, e.g. $$x_2 \implies x_5$$, which means that if $$x_2$$ is true $$x_5$$ must also be true. There are no negations.

How do we efficiently count the number of distinct solutions?

I do have some ideas on how we can simplify the problem:

1. If the implication graph is not connected we can compute the number of valid assignments for all disconnected parts independently and multiply their counts for the final result as they are completely independent.

2. If there is a cycle in the implication graph we can replace all occurrences of all variables that participate in the cycle with a new single variable, as they must all be equal.

3. We can remove all implications of the form $$x_i \implies x_i$$ as they are useless.

Repeating the above operations until fixed point occurs we are left with a bunch of connected directed acyclic graphs. But solving the problem efficiently for the DAG case still eludes me.

• "There are no negations." I.e. despite $x_2\Rightarrow x_5$ there is no $\overline{x_5}\Rightarrow\overline{x_2}$ relation? This, of course, violates the standard rules of logic. Commented Jul 18 at 13:03
• @rus9384 I just mean that the expression only has implications with positive variables $x_i$. $\neg x_i$ is not allowed in the expression. Of course I'm not saying the fundamental laws of logic are to be violated.
– orlp
Commented Jul 18 at 14:48
• Pretty sure #XOR-SAT is the only SAT variation that is not $\#P$-complete. Commented Jul 18 at 16:33

• Thanks for the reference. Does that imply it is hard to choose a valid assignment uniformly at random from the set of all valid assignments, or does there exist an effective algorithm for that regardless? What about an algorithm that allows $\pm \epsilon$ deviation from the true universal random probability any particular element is selected?