This is clearly a symmetric formula. However, it is not a monotone function. AND and OR are monotone functions, therefore all their compositions (and, in particular, all DNFs) are monotone functions.
It is true, however, that every monotone formula, symmetric or not, is expressible in terms of a DNF.
Suppose we take a DNF with n variables. We will express it as a symmetric function with 2n-1 variables. Specifically, variable Xi will be substituted 2i-1 times into the symmetric function.
Notably, each of the 2n possible assignments of the inputs to the DNF now yields a different number of "true" values in the input to the symmetric function, so we can simply assign the symmetric function to yield the same output as the original DNF. Thus, the symmetric function can be used to express any DNF, and, in fact, it can be used to express any function.
Back to riddle
Back to main page