Using your Head is Permitted

and an (inclusive) OR operation as addition:

A formula in Disjunctive Normal Form (DNF) is a formula that is a sum of products of the basic variables:

(Note: we do not allow negations.)

A Symmetric Formula is a Boolean function that yields the same output regardless of the order of its input operands.

We say that "A is expressible in terms of B", if it is possible to take a formula of type A and write an equivalent formula of type B, by taking each variable in the type B formula and assigning to it one of the input variables of the original formula, or a constant. The same variable can be substituted in several times, but, again, negations are not allowed.

Here is an example that will make it clearer.

The function MAJ(X₁,X₂,X₃), giving the majority vote of three variables, is a symmetric formula, because it doesn't matter in which order the variables appear. It can also be expressed in terms of a DNF. This is done as follows:

Suppose that we take the DNF

We can assign Y₁=X₁, Y₂=X₂, Y₃=X₁, Y₄=X₃, Y₅=X₂ and Y₆=X₃ in order to get

Thus, we've expressed MAJ as a DNF. (Note: the final formula we reached for MAJ is, itself, a DNF with three variables. There was no need, in this example, to start with a DNF with six variables. This was only given as an example to clarify the idea of substituting in the same variable multiple times. Here, each of the three input variables to MAJ was used twice in order to express MAJ in terms of f.)

This month's riddle is composed of two questions. For credit, answer both.

1. Is every symmetric formula expressible in terms of a DNF?
2. Is every DNF expressible in terms of a symmetric formula?

List of solvers: