4
$\begingroup$

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.

$\endgroup$
  • $\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. Feb 8 '16 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$ – user3743825 Feb 8 '16 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$ – user3743825 Feb 8 '16 at 22:38
  • 1
    $\begingroup$ Express the function in terms of its minterms (look this up if the term is unfamiliar). $\endgroup$ – Yuval Filmus Feb 8 '16 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$ – AProgrammer Feb 9 '16 at 14:11
5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
-2
$\begingroup$

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.

$\endgroup$
  • $\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$ – Yuval Filmus Feb 16 '16 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$ – user3743825 Feb 18 '16 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$ – Yuval Filmus Feb 18 '16 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$ – user3743825 Feb 18 '16 at 9:14
  • $\begingroup$ Your inductive step only works if $f$ doesn't depend on the last argument, which it does in general. $\endgroup$ – Yuval Filmus Feb 18 '16 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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