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.

  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Feb 8, 2016 at 21:27
  • $\begingroup$ 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. $\endgroup$ Commented Feb 8, 2016 at 21:38
  • $\begingroup$ 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? $\endgroup$ Commented Feb 8, 2016 at 22:38
  • 1
    $\begingroup$ Express the function in terms of its minterms (look this up if the term is unfamiliar). $\endgroup$ Commented Feb 8, 2016 at 23:28
  • 1
    $\begingroup$ 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$. $\endgroup$ Commented Feb 9, 2016 at 14:11

4 Answers 4


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.


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$ of $n$ variables $f(x_1,\ldots,x_n)$, we can always construct two functions of the previous consecutive $(n-1)$ variables $f_0(x_1,\ldots,x_{n-1}) = f(x_1,\ldots,x_{n-1},0)$ and $f_1(x_1,\ldots,x_{n-1}) = f(x_1,\ldots,x_{n-1},1)$, and both $f_0,f_1$ are monotone by the inductive hypothesis. Also there must be well-formed formulas representing Boolean functions $f_0,f_1$, respectively. I claim that $$ f = f_0 \lor (x_n \land f_1). $$ because substituting $x_n = 0$ we just get $f_0$, and substituting $x_n = 1$ we get $f_0 \lor f_1 = f_1$. Now we can conclude indeed $f$ is monotone since if $f(\vec{x},0)=f_0$ is true then so is $f(\vec{x},1)=f_1$ by above stated inductive hypothesis, and this finishes the inductive step.


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.


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.

  • $\begingroup$ 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. $\endgroup$ Commented Feb 16, 2016 at 9:25
  • $\begingroup$ 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$ $\endgroup$ Commented Feb 18, 2016 at 9:00
  • $\begingroup$ You still need to represent $x$ as a monotone Boolean formula, so you're just pushing the problem somewhere else. $\endgroup$ Commented Feb 18, 2016 at 9:06
  • $\begingroup$ 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 $\endgroup$ Commented Feb 18, 2016 at 9:14
  • $\begingroup$ Your inductive step only works if $f$ doesn't depend on the last argument, which it does in general. $\endgroup$ Commented Feb 18, 2016 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.