# Using your Head is Permitted

## November 2010 solution

### Not every symmetric formula is expressible in terms of a DNF

Consider the example *X*_{1} XOR *X*_{2}.
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 2^{n}-1 variables. Specifically,
variable *X*_{i} will be substituted 2^{i-1}
times into the symmetric function.

Notably, each of the 2^{n} 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:

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