Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
