Given a language L how can I derive its Boolean formula?

Question

Let: be given by

Compute Boolean formulas for the following:

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.

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.