Let: enter image description here be given by

enter image description here

Compute Boolean formulas for the following: enter image description here

This is part of my coursework; I have the answers but can't understand them. I want to develop some intuition on how I can solve these or a general framework on how I can approach them.

Some guidance on resources is also appreciated. And sorry I couldn't figure out how to format it in Latex which worked over here.

  • $\begingroup$ Please use LaTeX for mathematics, not images. See here for a short introduction. $\endgroup$
    – D.W.
    Aug 17 at 3:47

1 Answer 1


I'll just consider $\text{MOD}^1_{0,3}$, the other ones are similar. I'm assuming that you want a boolean formula $\phi$ such that $\text{MOD}^1_{0,3}(x_1, \dots, x_n) = 1 \iff \phi(x_1, \dots, x_n) \text{ is true}$.

Note that $\text{MOD}^1_{0,3}(x)$ is true if and only if the number of variables set to $1$ is a multiple of $3$. A first "natural" approach to find a possible $\phi$ is that of explicitly considering all variable assignments with that property and or-ing them together.

The resulting formula wold be: $$ \bigvee_{k=0,\dots,\lfloor n/3 \rfloor} \bigvee_{S \in \binom{\{1, \dots, n\}}{3k}} \left(\bigwedge_{i \in S} x_i \wedge \bigwedge_{i \in \{1, \dots, n\} \setminus S} \overline{x}_i \right). $$

While this works, this formula has exponentially many conjunctive clauses, each of which has $n$ literals.

A second idea is that of examining one input variable at a time and keeping track of the remainder of the division between the number of true variables encountered so far and $3$. To this aim we introduce $2$ new variables $y_i, z_i$ for each $i = 0,\dots,n$ where if we interpret $y_i z_i$ as a binary number, it will be exactly $\left( \sum_{j=1}^i x_j \right) \bmod 3$.

The formula will be a conjunction of sub-formulas.

  • To ensure that $y_0=z_0 = 0$ we can use the sub-formula $\overline{y}_0 \wedge \overline{z}_0$.
  • To correctly compute $y_i$ from $x_i, y_{i-1}, z_{i-1}$ (for $i = 1, \dots, n$) we can can write down a truth table to figure out that $y_i$ should be true if and only if the formula $\mathcal{Y}_i = (\overline{y}_{i-1} \wedge z_{i-1} \wedge x_i) \vee (y_{i-1} \wedge \overline{z}_{i-1} \wedge x_i)$ is true. Using the equivalence between $a \implies b$ and $(\overline{a} \vee b)$ we obtain the sub-formula $(\overline{\mathcal{Y}}_i \vee y_i) \wedge(\mathcal{Y}_i \vee \overline{y}_i)$.
  • To correctly compute $z_i$ from $x_i, y_{i-1}, z_{i-1}$ (for $i = 1, \dots, n$) we can use a similar reasoning to obtain the sub-formula $(\overline{\mathcal{Z}}_i \vee z_i) \wedge(\mathcal{Z}_i \vee \overline{z}_i)$, where $\mathcal{Z}_i = (\overline{y}_{i-1} \wedge \overline{z}_{i-1} \wedge x_i) \vee (\overline{y}_{i-1} \wedge z_{i-1} \wedge \overline{x}_i)$.
  • Finally, we need to check that $y_n$ and $z_n$ encode $0$ (i.e., $\sum_{j=1}^i x_j$ is a multiple of $3$). We can do so by using the sub-formula: $\overline{y}_n \wedge \overline{z}_n$.

Notice that, for each $i=0, \dots, n$, we used a constant number of clauses each with constant-many literals. Overall, $\phi$ has $\Theta(n)$ clauses with $\Theta(1)$ literals each.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.