Using your Head is Permitted

November 2010 solution

Not every symmetric formula is expressible in terms of a DNF

Consider the example X1 XOR X2.

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.

Every DNF is expressible in terms of a symmetric formula

A symmetric formula is invariant to the order of the variables given to it, meaning that it is actually a function of the number of inputs that are "true".

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.

Two notes:

  1. For more about this type of reduction, see, for example, "A Complexity Theory Based on Boolean Algebra" by S. Skylum and L.G. Valiant (where the proof given here is stated far more formally).
  2. Usually, one does allow negations in DNFs. However, in the formulation of Skylum and Valiant it is not the DNF that has the negations but rather the reduction (the expression of one formula in terms of another). Sometimes, as in the case of this riddle, the requirement is for a monotone reduction (a reduction without negations), sometimes not.

Back to riddle

Back to main page