Number of sequnces with given value

Question

Consider a valid string with bitwise operations (AND, OR, XOR), and also placeholders $X$, where each $X$ stands for an arbitrary number from $\{0,1\}$. There are $n$ many $X$s, so there are $2^n$ possible sequences. How many out of the $2^n$ strings have value $0$? How many have value $1$?

My approach to this problem was, I assumed that the interpretation of strings is done by associating left-to-right (that is, $0 \oplus 1 \land 0$ means $(0 \oplus 1) \land 0$). I will use $\lor,\land,\oplus$ for OR, AND, XOR.

Let $s$ be an arbitrary string with $n$ many $X$s that evaluates to 0, and let $t$ be an arbitrary string with $n$ many $X$s that evaluates to 1.

Then, the strings with $n+1$ many $X$s that evaluate to $1$ are: $$ t \lor 0, s \lor 1, t \lor 1, t \land 1, s \oplus 1, t \oplus 0. $$ The ones that evaluate to 0 are: $$ s\lor 0, s\land 1, s\land 0, t\land 0, s\oplus 0, t\oplus 1. $$

Fixing a sequence of operations, let $S(n)$ be the number of strings with $n$ many $X$s that evaluate to 0 with the given operations, and let $T(n)$ be the number that evaluate to 1.

Denote the $i$'th operation by $O_i$. Then, just counting the combinations in the previous paragraph for each operator, I get the following recurrence relations: $$ \begin{align} &S(1)=T(1)=1 \\ &S(n+1),T(n+1) = \begin{cases} S(n), S(n)+2T(n) & \text{if } O_{n+1}=\lor \\ 2S(n)+T(n), T(n) & \text{if } O_{n+1}=\land \\ S(n)+T(n), S(n)+T(n) & \text{if } O_{n+1}=\oplus \end{cases} \end{align} $$

What should I do if my assumption was wrong, that is, if the sequence could contain parentheses, e.g. $(X \lor (X \oplus X))$?

Answer 1

You should first build the binary expression tree of the given boolean expression. You can then do a Depth First Search on this tree, and start computing the answers from the leaves to the root (bottom to top), similar to the way you've done in your approach.

But instead of $S(i)$ denoting the number of assignments of the first $i$ $X$s which evaluate to 0, it will now be $S(u)$ denoting the number of assignments of the $X$s which lie in the subtree of $u$, which evaluate the expression until $u$ to be 0. Here $u$ refers to a node in the tree. Similarly $T(u)$ is defined for evaluation to 1.

The base case would be when $u$ is a leaf (which would happen when it corresponds to an operand), and both $S(u)$ and $T(u)$ would be equal to 1 in that case. Else, if $u$ is an internal node (which corresponds to an operator), you compute the $S$ and $T$ values by looking at the $S$ and $T$ values of its children, $c_1$ and $c_2$, and applying recursion similar to what you had in your answer:

If $u$ is an OR node,

$S(u) = S(c_1) S(c_2)$

$T(u) = S(c_1) T(c_2) + T(c_1) S(c_2) + T(c_1) T(c_2)$

If $u$ is an AND node,

$S(u) = S(c_1) T(c_2) + T(c_1) S(c_2) + S(c_1) S(c_2)$

$T(u) = T(c_1) T(c_2)$

If $u$ is an XOR node,

$S(u) = S(c_1) S(c_2) + T(c_1) T(c_2)$

$T(u) = S(c_1) T(c_2) + T(c_1) S(c_2)$

And the final answer would be $S(\mathit{root})$ and $T(\mathit{root})$.