Software! Math! Data! The blog of R. Sean Bowman
The blog of R. Sean Bowman
June 22 2016

In the course of working on some propositional logic/SAT applications, I came across an interesting identity I don’t think I knew of before. It seems related to all kinds of stuff, but I guess that’s not unusual for math… Anyhow, this particular identity made it very easy to transform some assertions I needed from disjunctive normal form to conjunctive normal form. It’s also beautiful on its own, so I thought I’d write it down.

I’ll write this down as a formula in propositional logic, but of course you could just as easily write it in Boolean algebra form or any number of other ways. Let \(X_m=\set{x_1, x_2,\dots x_m}\) be a set of \(m\) variables. Let \(C_n(X)\) denote the set of all subsets of \(X\) of size \(n\), \(\allsuchthat{Y\subseteq X}{|Y| = n}\). Then

\[ \bigvee_{S\in C_n(X_m)}\bigwedge_{s\in S} s = \bigwedge_{S\in C_{m-n+1}(X_m)}\bigvee_{s\in S} s. \]

An example, for \(m=4, n=3\):

\[ \begin{multline} (x_1\wedge x_2\wedge x_3) \vee (x_1\wedge x_2\wedge x_4) \vee (x_1\wedge x_3\wedge x_4) \vee (x_2\wedge x_3\wedge x_4) \\ = (x_1\vee x_2) \wedge (x_1\vee x_3) \wedge (x_1\vee x_4) \wedge (x_2\vee x_3) \wedge (x_2\vee x_4) \wedge (x_3\vee x_4). \end{multline} \]

Note that these correspond to symmetric polynomials over the field with two elements. There’s probably some general result that this falls out of, but my proof is much more mundane.

Idea of proof: let \(\phi\) be the left hand side of the above equation and \(\psi\) be its right hand side. If we can show that \(\phi\oplus\psi\) is false, where \(\oplus\) is the exclusive or operation, then we will have shown that \(\phi\) and \(\psi\) are satisfied by the same truth assignments. By completeness of propositional logic, the two are syntactically equivalent.

Using the identity \(\phi\oplus\psi = (\phi\wedge\neg\psi)\vee(\neg\phi\wedge\psi)\) and expanding first term, we get

\[ \left(\bigvee_{S\in C_n(X_m)}\bigwedge_{s\in S} s\right) \wedge \left(\bigvee_{S\in C_{m-n+1}(X_m)}\bigwedge_{s\in S} \neg s\right). \]

After a lot of distribution, we come to a formula which has many terms of the form

\[ x_{i_1}\wedge x_{i_2}\wedge\dots\wedge x_{i_n}\wedge\neg x_{i_{n+1}}\wedge\dots\wedge\neg x_{i_{m+1}}, \]

where the \(i_1,\dots,i_n\) are distinct, the \(i_{n+1},\dots,i_{m+1}\) are distinct, and (clearly) there are a total of \(m + 1\) variables. But notice that since \(X_m\) contains only \(m\) variables, we must have \(x_j\) and \(\neg x_j\) in the formula for some \(j\). Therefore every term in our disjunction is false, qed.

Obviously there are some details there, but hey, pretty identity! Nifty!

Approx. 388 words, plus code