Using your Head is Permitted

November 2010 riddle

Let X1,... ,Xn be Boolean variables. We will denote an AND operation as multiplication:

Xi AND Xj = XiXj

and an (inclusive) OR operation as addition:

Xi OR Xj = Xi+Xj

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

f(X1,... ,Xn) = XaXbXc... + XiXjXk... + ...

(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(X1,X2,X3), 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

f(Y1,Y2,Y3,Y4,Y5,Y6) = Y1Y2+Y3Y4+Y5Y6

We can assign Y1=X1, Y2=X2, Y3=X1, Y4=X3, Y5=X2 and Y6=X3 in order to get

MAJ(X1,X2,X3) = X1X2+X1X3+X2X3

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:

Joseph DeVincentis (2 November 03:43)
Adam Daire (2 November 08:19)
Oded Margalit (3 November 06:32)
Daniel Bitin (3 November 06:57)
Gaoyuan Chen (3 November 23:31)
Djinn Lu (5 November 14:48)
Jan Fricke (8 November 03:46)
Phil Muhm (11 November 03:00)
Guangda Huzhang (15 November 01:33)
Jin Ruizhang (25 November 06:40)

Elegant and original solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page