Show that any monotone Boolean function is computable by a circuit containing only AND and OR gates

A Boolean function $f : \{0, 1\}^n → \{0, 1\}$ is called monotone if changing any of the $n$ input bits $x_1, \ldots , x_n$ from $0$ to $1$ can only ever change the output $f(x_1, \ldots ,x_n)$ from $0$ to $1$, never from $1$ to $0$.

I know how to do a simple proof of exhaustion for $f : \{0, 1\}^1$ and $f : \{0, 1\}^2$, but I do not know how to prove the following statement for $f:\{0,1\}^n$: any monotone Boolean function is computable by a circuit containing only AND and OR gates.

• Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. – D.W. Feb 8 '16 at 21:27
• Hello! I have tried doing an exhaustive proof using a truth table for one and two variables. So I proved that if n = 1 or n = 2 then the function is monotonic. I also tried to do a proof by contradiction assuming that not all monotonic boolean functions are computable by a circuit containing only AND and OR gates, but could not figure out how to get a contradiction from the assumed statement. – user3743825 Feb 8 '16 at 21:38
• so I assume f{0,1}^n is monotonic. I have already proved f{0,1} is monotonic and can represent f{0,1}^(n+1) as f{0,1}^n {0,1}. Which is monotonic because both f{0,1}^n and {0,1} is monotonic? – user3743825 Feb 8 '16 at 22:38
• Express the function in terms of its minterms (look this up if the term is unfamiliar). – Yuval Filmus Feb 8 '16 at 23:28
• You can also continue on your idea, $f(x_1, ..., x_{n+1})=(f^T(x_1, ..., x_n)\land x_{n+1})\lor(f^F(x_1, ..., x_n)\land\lnot x_{n+1})$ and consider what f being monotonous implies for $f^T$ and $f^F$. – AProgrammer Feb 9 '16 at 14:11

Any Boolean function can be written as a DNF. Each clause in the DNF specifies one truth assignment for which the function holds. For example, the DNF form of XOR is $(x \land \lnot y) \lor (\lnot x \land y)$.

The main observation is that if the function is monotone, you can remove all the negated literals (why?). Once you do that, you get a formula for the function which uses only AND and OR. Some clauses in this formula subsume others (for example, $x$ subsumes $x \land y$). If you drop all the subsumed clauses, you arrive at the minterm representation of the function. (A minterm is a minimal satisfying assignment.)

It's a bit more confusing, but you can also do everything using CNFs. This way you arrive at the maxterm representation.

Assume we operate on $n$ variables $x_1,...,x_n$. Take all sets $S_1,...,S_n$ of variables where assigning those variables 'true' makes the statement 'true'. Build the expression

$$f = or(and(S_1), and(S_2), ..., and(S_n))$$

Now, whenever all of the variables in one of the $S_i$ are true, this expression will be true. However, might we have too many true assignments?

No, because if some assignment to the $x_i$ makes $f$ true, then it makes one of the clauses of the $or$ true (because that's how $or$ works). Let's say it's $and(S_i)$ for some $i$. Then this means all the variables in $S_i$ are true (and maybe some others), and as the function is monotone, that means $f$ must be true.

You can prove this by induction. We will construct a formula with constants, and then you can eliminate the constants (unless the function itself is constant), if you wish, using the simplification rules $$x \land 0 = 0$$, $$x \land 1 = x$$, $$x \lor 0 = x$$, $$x \lor 1 = 1$$.

When $$n = 0$$, the function is just a constant. Given a function $$f$$ on $$n$$ variables, we can construct two functions $$f_b(x_1,\ldots,x_{n-1}) = f(x_1,\ldots,x_n)$$. Inductively, there are formulas for $$f_0,f_1$$. I claim that $$f = f_0 \lor (x_n \land f_1).$$ Indeed, substituting $$x_n = 0$$ we just get $$f_0$$, and substituting $$x_n = 1$$ we get $$f_0 \lor f_1 = f_1$$, since $$f$$ is monotone: if $$f(\vec{x},0)$$ is true then so is $$f(\vec{x},1)$$.

In the expression $OR(x,y)$, if I define x as 0 and y as $f:\{0,1\}^{n-1}$, OR(x,y) is monotone and can represent any monotone function. This statement is in $f:\{0,1\}^{n}$, which means $f:\{0,1\}^{n}$ contains any monotone function.

• I can't follow. While it's true that $OR(0,f) = f$, I don't see how it gets you any closer to solving the exercise. – Yuval Filmus Feb 16 '16 at 9:25
• Hmm... I'm quite new to proofs, but here's my reasoning. Any Monotone boolean function can be represented by OR(x,0) or AND(x,1). I let $x = f : \{0,1\}^{n}$ so any Monotone boolean function can be represented using AND and OR in the set $f: \{0,1\}^n$ – user3743825 Feb 18 '16 at 9:00
• You still need to represent $x$ as a monotone Boolean formula, so you're just pushing the problem somewhere else. – Yuval Filmus Feb 18 '16 at 9:06
• Isn't $OR(f:\{0,1\}^n,0)$ $AND(f:\{0,1\}^n,1)$ $OR(f:\{0,1\}^n,1)$ in the set $f:\{0,1\}^{n+1}$? I feel like I just proved that the n+1 case is monotone in terms of the n case – user3743825 Feb 18 '16 at 9:14
• Your inductive step only works if $f$ doesn't depend on the last argument, which it does in general. – Yuval Filmus Feb 18 '16 at 17:55