Proof that all Boolean functions can be computed by $(MOD_2-MOD_3)$ circuit

Question

I was reading "Some properties of MOD m circuits computing simple functions" (Amano & Maruoka, 2003) where the authors prove that every Boolean function can be computed by depth $2$ by $(MOD_2-MOD_3)$ circuit. They claim what follows:

It was known that the $OR$ function of $n$ variables, i.e., $\vee_{i=1}^n x_i$ , can be computed by a depth two $(MOD_3-MOD_2)$ circuit.

I agree with the above part and I am able to show a construction for $n$-ary $OR$. Based on this fact they note that:

This implies that every disjunction of $n$ literals, i.e., $\vee_{i=1}^n l_i$ where $l_i\in \{x_i,\overline{x_i}\}$ , also can be computed by a depth two $(MOD_3-MOD_2)$ circuit.

Which I also accept. Afterward, they set up grounds for the main proof:

Let $f$ be an arbitrary Boolean function on $n$ variables. Consider a CNF formula representing $f$, where each clause contains exactly $n$ literals. Without loss of generality, we can assume that the formula has $m\equiv 1(\mod 3)$ clauses.

So far so good. But then comes the part I get lost at:

If the value of $f$ is 0, then $m-1\equiv 0(\mod 3)$ clauses of $f$ takes value $1$, and if the value of $f$ is $1$, then all of the $m\equiv 0(\mod 3)$ clauses takes value $1$. Thus the $MOD_3$ gate, whose inputs are all $(MOD_3-MOD_2)$ circuit computing each clause in the CNF formula, evaluates the func- tion $f$

Could anyone please explain to me why the sentence

If the value of $f$ is 0, then $m-1\equiv 0(\mod 3)$ clauses of $f$ takes value $1$

is true? Isn't it possible for a CNF with $m$ clauses to evaluate to $0$ and have $m-2$ clauses true? Or $m-3$ or $m-113$. What if, for example, my CNF is a big $AND$ of $n$ variables? Then this doesn't hold, any number of clauses might be 'dead'...

(Note this is not the whole proof, you have to show how to transform this bigger circuit to a smaller one).

Answer 1

The key observation is that $f$ is not represented by any CNF but by a CNF where all clauses have $n$ literals with distinct variables where $n$ is the number of variables.

It is easy to see that such a CNF exists. Indeed, let $S$ be the set of solutions of $\neg f$. Each solution $s \in S$ can be seen as a conjunction of $n$ literals. For example, $s = \{x=0, y=1, z=0\}$ may be seen as $\neg x \wedge y \wedge \neg z$. Thus $\neg f = \bigvee_{s \in S} s$ and then $f = \bigwedge_{s \in S} \neg s$ which is a CNF formula.

Now this is important since the clauses of this CNF, let's call it $F$, are in one to one correspondance with assignments of the variables: to each clause $\neg s$ of $F$, we associate $s$, the only assignment that does not satisfy the clause. For instance, the only way not to satisfy $\neg s = x \vee \neg y \vee z$ is $s=\{x=0, y=1, z=0\}$. Thus, given an assignment, at most one clause of $F$ is not satisfied.

Now there is still something to explain. The authors claim that we can assume $m \equiv 1 \mod 3$ wlog. That is not completely true since we cannot grow the number of clauses artificially and still have the previous property. However, for the sake of their argument, it is enough to add trivial clauses such a $x \vee \neg x$ that always evaluate to $1$.