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

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.

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

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.