Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It's said on Wikipedia page about Post's lattice that DM clone(all monotone self-dual functions) has majority function $(xy + xz + yz)$ as one of its bases. What is the proof of this fact?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

I proved this a few years ago as a homework assignment. Even if it's not your homework assignment, that makes me reluctant to give a complete solution; however, the hints below should be helpful.

Method 1: The proof I submitted is along the following lines: given a monotone self-dual function $f$, show by induction that for all sufficiently small nonnegative integers $l$, there is another function $g_l$ (of the same arity as $f$) such that $||f-g_l||_1 = 2l$ and $g_l$ is in the clone. (Here $||f-g||_1$ is the "$l_1$-norm," which in this case is just the number of $x$ for which $f(x)\neq g(x)$.) The basis case is obvious: pick an arbitrary function you know is in the clone. For the inductive step, you have to figure out how to take $g_l$ and produce $g_{l-1}$, which I'll leave out, but a hint is that there is a $g_{l-1}$ with $||g_l - g_{l-1}||_1 = 2$, i. e., $g_{l-1}$ is almost the same as $g_l$. The conclusion (by induction) is the case $l=0$, but $g_0$ has to be $f$, so $f$ is in the clone. (Informally: you can start at some function in the clone and "walk" by simple steps to any other monotone self-dual function of the same arity, and adjacent functions on the walk can be obtained from one another using the majority function.)

Method 2: However, there's a much neater argument by induction on the arity of $f$. To simplify future notation, let $\bar{x} = (x_4,\ldots,x_n)$, so $f(x_1,\ldots,x_n) = f(x_1,x_2,x_3,\bar{x})$. Observe that if $f:\{0,1\}^n\to \{0,1\}$ is monotone and self-dual and $n> 3$, then the three functions of $n-1$ arguments $$f_1(x,y,\bar{x}) = f(x,y,y,\bar{x}),$$ $$f_2(x,y,\bar{x}) = f(y,x,y,\bar{x}),$$ $$f_3(x,y,\bar{x}) = f(y,y,x,\bar{x}),$$ are monotone and self-dual as well, and moreover, they determine $f$. (Indeed, out of $x_1,x_2,x_3$, at least 2 must be equal, so for example, if $x_1 = x_2$, then $f(x_1,\ldots,x_n) = f_3(x_3,x_2,\bar{x})$.) All you have to do now is reconstruct $f$ from $f_1,f_2,f_3$ using only the majority function. Thankfully, the construction is very simple, although it may not be obvious at first why it works: $$f(x_1,\ldots,x_n) = M(f_1(x_1,x_3,\bar{x}), f_2(x_2,x_1,\bar{x}), f_3(x_3,x_2,\bar{x}))$$ (where $M$ is the majority function). (Hint: prove the case $x_1=1,x_2=x_3=0$, and the rest should become obvious. You need monotonicity here, but surprisingly not self-duality.) The basis case is $n\leq 3$ (where self-duality is needed).

Oh, well; I guess that's almost a complete solution anyway, but I don't feel like going back and removing steps from the argument at the risk of making it cryptic and useless. :-)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.