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

<p>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.</p>

<p>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.</p>

<p>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 <em>always</em> evaluate to $1$.</p>

CC BY-SA 3.0
2018-03-19T08:44:30.467Z
Doesn't the argument in the last paragraph (about adding trivial clauses) violate the assumption that all clauses contain exactly n literals with n distinct variables? Maybe one can repeat clauses instead to justify the wlog.
Jan Johannsen
CC BY-SA 3.0
2018-03-19T08:51:53.650Z
It does but what is important for the proof is to have: either the number of clauses evaluating to $1$ is $1 \mod 3$ ($f$ satisfied) or $0 \mod 3$ ($f$ not satisfied). You do not really need it actually, you could work with any constant or just pad your $MOD_3$ gate with $1$ constants. Repeating a clause $C$ will not work as you may thus have $m-2$ clauses not satisfied if you plug the assignment $\neg C$.
holf
CC BY-SA 3.0
2018-03-19T06:32:27.687Z
2018-03-19T06:32:27.687Z
holf
<p>I was reading "Some properties of MOD m circuits computing simple functions" (Amano &amp; 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:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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:</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

<blockquote>
  <p>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.</p>
</blockquote>

<p>So far so good. But then comes the part I get lost at:</p>

<blockquote>
  <p>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$</p>
</blockquote>

<p>Could anyone please explain to me why the sentence </p>

<blockquote>
  <p><strong>If the value of $f$ is 0, then $m-1\equiv 0(\mod 3)$ 
  clauses of $f$ takes value $1$</strong></p>
</blockquote>

<p>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'...</p>

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

CC BY-SA 3.0
2018-03-18T08:07:41.760Z
The key observation is that every clause has exactly $n$ literals which is the number of variables so $f$ is represented as "the list of non-solutions".
holf
CC BY-SA 3.0
2018-03-18T13:52:36.863Z
I don't follow. Could you please give me an example? For instance what happens in the case of $AND$ (we can artificially fill each one-variable clause with $n$ copies of this variable)?
Jules
CC BY-SA 3.0
2018-03-18T15:14:34.190Z
(1) You are right that a cnf can evaluate to 0 with $m-2$ satisfied clauses and that you could artificially add copies of the same variable in a clause to make it of length $n$. (2) What you should read from the proof is that you have clauses having $n$ *distinct* literals. So there is exactly one assignment of not satisfying a given clause (ex $x \vee y \vee z$ is not satisfied by $x=y=z=0$ only. (3) Now I agree that assuming $m=1(3)$ wlog is not completely wlog. But you could still do the same reasoning with $m=c(3)$ for some constant $c$.
holf
CC BY-SA 3.0
2018-03-18T16:04:16.653Z
Pardon my lack of knowledge here then but how do we know that every function can be represented as a CNF with $n$ distinct variables in each clause? I can imagine at least one for which I don't see any construction, say $AND$ that I mentioned.
Jules
CC BY-SA 3.0
2018-03-18T16:40:33.630Z
Do you see how you can do it as a DNF by writing the list of all solutions? Do it for $\neg f$
holf
CC BY-SA 3.0
2018-03-18T16:47:47.553Z
True, fantastic, I understand it now. Thank you!
Jules
CC BY-SA 3.0
2018-03-18T21:44:50.643Z
Since this question wasn't downvoted to hell in the first day, it is safe to assume that it won't be closed.  A proper answer is thus in order.
Michaël Cadilhac
<cc.complexity-theory><circuit-complexity><boolean-functions>
Proof that all Boolean functions can be computed by $(MOD_2-MOD_3)$ circuit
Jules
# Proof that all Boolean functions can be computed by $(MOD_2-MOD_3)$ circuit

(Asked by: username_0 on 2018-03-18)

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).

**Tags:** cc.complexity-theory, circuit-complexity, boolean-functions

> **Comments:**
> **username_1**: The key observation is that every clause has exactly $n$ literals which is the number of variables so $f$ is represented as "the list of non-solutions".  
> **username_0**: I don't follow. Could you please give me an example? For instance what happens in the case of $AND$ (we can artificially fill each one-variable clause with $n$ copies of this variable)?  
> **username_1**: (1) You are right that a cnf can evaluate to 0 with $m-2$ satisfied clauses and that you could artificially add copies of the same variable in a clause to make it of length $n$. (2) What you should read from the proof is that you have clauses having $n$ *distinct* literals. So there is exactly one assignment of not satisfying a given clause (ex $x \vee y \vee z$ is not satisfied by $x=y=z=0$ only. (3) Now I agree that assuming $m=1(3)$ wlog is not completely wlog. But you could still do the same reasoning with $m=c(3)$ for some constant $c$.  
> **username_0**: Pardon my lack of knowledge here then but how do we know that every function can be represented as a CNF with $n$ distinct variables in each clause? I can imagine at least one for which I don't see any construction, say $AND$ that I mentioned.  
> **username_1**: Do you see how you can do it as a DNF by writing the list of all solutions? Do it for $\neg f$  
> **username_0**: True, fantastic, I understand it now. Thank you!  
> **username_2**: Since this question wasn't downvoted to hell in the first day, it is safe to assume that it won't be closed.  A proper answer is thus in order.  

---

## 1 answers

### Answer by username_1 on 2018-03-19. Score: 3 | Accepted answer

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$.

> **Comments:**
> **username_3**: Doesn't the argument in the last paragraph (about adding trivial clauses) violate the assumption that all clauses contain exactly n literals with n distinct variables? Maybe one can repeat clauses instead to justify the wlog.  
> **username_1**: It does but what is important for the proof is to have: either the number of clauses evaluating to $1$ is $1 \mod 3$ ($f$ satisfied) or $0 \mod 3$ ($f$ not satisfied). You do not really need it actually, you could work with any constant or just pad your $MOD_3$ gate with $1$ constants. Repeating a clause $C$ will not work as you may thus have $m-2$ clauses not satisfied if you plug the assignment $\neg C$.  

---

