# How propositional logic minimization and gray codes are connected

In this post I will introduce an interesting connection between gray codes and the problem of minimizing propositional logic formulas in disjunctive normal forms (DNF’s). Both of these concepts are related to the Hamming distance between two binary sequences, which is the amount of bits that need to be flipped in one sequence in order to obtain the other one.

## Boolean functions and n-dimensional cubes

Any boolean function with $n$ variables can be visualized as some subset of vertices in an $n$-dimensional cube. For example, for $n = 3$, the cube looks like this:

In such cubes every edge connects vertices that correspond to variable assignments differing in exactly one variable. In other words, any disjoint $n - 1$-dimensional sub-cubes of an $n$-dimensional cube, viewed as boolean cubes (a. k. a. partial variable assignments), are adjacent.

Variable assignments that have the same number of ones can be grouped together:

It is easy to see that assignments from the blue segment have hamming distance 2 when compared with the assignments from the red segment. Analogously, this is also true for the green and brown segments. It also holds, that assignments in one segment have hamming distance 2 because of the way we grouped them. This leads us to the idea that boolean cubes are bipartite graphs if we draw edges between variable assignments that have hamming distance 1:

With the above described intuition we can now formulate and prove the following statements:

## Theorem 1

Let $g(x) = a_{n-1}\dots a_{0}$ be the gray code for $x := x_{n-1}\dots x_{0}$ and $g(y) = b_{n-1}\dots b_{0}$ be the gray code for $y := y_{n-1}\dots y_{0}$. Assuming $x \neq y$, it holds that:

• $x$ and $y$ are both even $\Rightarrow$ $\Delta_{\mathrm{H}}(g(x), g(y)) \ge 2$.
• $x$ and $y$ are both odd $\Rightarrow$ $\Delta_{\mathrm{H}}(g(x), g(y)) \ge 2$.

Proof: by induction on $B_i$ for all $i \in \mathbb{N}^{+}$ (I’ve defined $B_i$ in this post and proved that this definition is equivalent to another definition of gray codes).

Induction base: ($i = 1$): There is no way of choosing different $x$ and $y$ such that at least one assumption above is true, so the statements hold trivially.

Induction base: ($i = 2$): $\Delta_{\mathrm{H}}(B_2(0), B_2(2)) = \Delta_{\mathrm{H}}(00, 11) = 2 \ge 2 \\ \Delta_{\mathrm{H}}(B_2(1), B_2(3)) = \Delta_{\mathrm{H}}(01, 10) = 2 \ge 2$

Induction step: ($i - 1 \rightarrow i$):

• If both $B_i(x)$ and $B_i(y)$ are in the first half of $B_i$, then the statements hold directly by induction hypothesis.
• If both $B_i(x)$ and $B_i(y)$ are in the second half of $B_i$ (formally: $2^{i-1} \le x, y < 2^i$), then, by definition of $B_i$, we have:
$B_i(x) = 1 \cdot B_{i-1}(2^{i-1} - 1 - (x - 2^{i-1})) = 1 \cdot B_{i-1}(2^i - 1 - x) \\ B_i(y) = 1 \cdot B_{i-1}(2^{i-1} - 1 - (y - 2^{i-1})) = 1 \cdot B_{i-1}(2^i - 1 - y)$
• So, in this case, due to $x \neq y$ it follows that $B_{i-1}(2^i - 1 - x) \neq B_{i-1}(2^i - 1 - y)$ and the statements hold by induction hypothesis.
• Otherwise, without losing generality, we can assume that $B_i(x)$ is in the first half of $B_i$ and $B_i(y)$ — in the second half of $B_i$.
• Formally, this means $0 \le x < 2^{i-1}$ and $2^{i-1} \le y < 2^i$.
• By the definition of $B_i$, it holds that $B_i(x) = 0 \cdot B_{i-1}(x)$.
• By the symmetry theorem I proved in this post:
$B_i(y) = \underbrace{110 \dots 0}_{i} \oplus B_{i-1}(y - 2^{i-1})$
• If $B_{i-1}(y - 2^{i-1}) = B_{i-1}(x)$, then both statements are true, because the first bit of $B_{i-1}(y - 2^{i-1})$ needs to be flipped (see formula above) and the leading 1-bit of $B_i(x)$ should be prepended, meaning that the hamming distance cannot be less than 2.

• Otherwise, because subtracting $2^{i-1}$ doesn’t affect whether $y$ is even or odd, we can use the induction hypothesis for $x$ and $y - 2^{i-1}$ which states that:

$\Delta_{\mathrm{H}}(B_{i-1}(x), B_{i-1}(y - 2^{i-1})) \ge 2$
• Unfortunately, the first bit of $B_{i-1}(y - 2^{i-1})$ gets flipped, so for $y$, from the induction hypothesis we can only conclude that:
$\Delta_{\mathrm{H}}(0 \cdot B_{i-1}(x), \underbrace{010 \dots 0}_{i} \oplus B_{i-1}(y - 2^{i-1})) \ge 1$
• However, by definition of $B_i(y)$ we know that a leading bit gets prepended, which increases the overall hamming distance as $B_i(x) = 0 \cdot B_{i-1}(x)$.

• We therefore conclude that:

\begin{aligned} &\Delta_{\mathrm{H}}(0 \cdot B_{i-1}(x), \underbrace{010 \dots 0}_{i} \oplus B_{i-1}(y - 2^{i-1})) \ge 1 \\ &\Rightarrow \Delta_{\mathrm{H}}(0 \cdot B_{i-1}(x), \underbrace{110 \dots 0}_{i} \oplus B_{i-1}(y - 2^{i-1})) \ge 2 \\ &\Leftrightarrow \Delta_{\mathrm{H}}(B_i(x), B_i(y)) \ge 2 \end{aligned}

## Corollary 1

$n$-dimensional boolean cubes are bipartite graphs — we can partition variable assignments based on whether they are gray codes of even numbers or whether they are gray codes of odd numbers. Theorem 1 guarantees that no edges in the $n$-dimensional cube connect vertices inside one group.

## Hamming distance for boolean cubes

In order to prove the lemma below, we need to define hamming distance for boolean cubes. Intuitively, 2 cubes have hamming distance 1 iff there exist two assignments (vertices) in the $n$-dimensional cube, such that the hamming distance between them is one, or, in other words, the shortest path between the corresponding vertices is 1.

More generally speaking, two cubes have hamming distance $k$ if the shortest path between some assignment of the first cube cube to some assignment from the second one is $k$. For example, the hamming distance between the following boolean cubes inside an $n$-dimensional cube is 2, because the shortest path (one of them is marked red) has length 2 ($\Delta_{\mathrm{H}}(001, 100) = 2$).

Formally, let $\varphi : V \rightarrow \{0, 1, *\}$ and $\psi : V \rightarrow \{0, 1, *\}$ be boolean cubes. We define: $\Delta_{\mathrm{H}}(\varphi, \psi) := |\{v \in V : \varphi(v) \neq *, \psi(v) \neq *, \varphi(v) = 1 - \psi(v)\}|$

We will first need the following statements for the proof of the main theorem (theorem 2) below:

## Lemma 1

A minterm $\alpha : V \rightarrow \{0, 1\}$ is covered by some other implicant $\beta : V \rightarrow \{0, 1, *\}$, $\beta \neq \alpha$ iff there exists some other minterm $\gamma : V \rightarrow \{0, 1\}$, $\gamma \neq \alpha$, such that $\Delta_{\mathrm{H}}(\alpha, \gamma) = 1$.

Proof: ($\Rightarrow$): $\beta$ covers $\alpha$ means $\beta(x) \neq * \Rightarrow \beta(x) = \alpha(x)$ for all $x \in V$. As $\beta \neq \alpha$, there exists at least one variable $z \in V$ such that $\beta(z) = *$. We can thus define $\gamma$ as follows:

• If $\beta(x) \neq *$, define $\gamma(x) := \alpha(x) = \beta(x)$.
• If $\beta(x) = *$ and $x \neq z$, define $\gamma(x) := \alpha(x)$.
• Finally, define $\gamma(z) := 1 - \alpha(z)$.

By construction, it holds that $\Delta_{\mathrm{H}}(\alpha, \gamma) = 1$ and $\gamma \neq \alpha$.

($\Leftarrow$): If there exists a $\gamma \neq \alpha$ with $\Delta_{\mathrm{H}}(\alpha, \gamma) = 1$, then, by definition of $\Delta_{\mathrm{H}}$, there exists exactly one variable $z \in V$ such that $\alpha(z) = 1 - \gamma(z)$ and for all other variables $x \in V$, $x \neq z$ it holds that $\alpha(x) = \gamma(z)$. We define $\beta$ accordingly:

• If $x \neq z$, set $\beta(x) := \alpha(x) = \gamma(z)$.
• Set $\beta(z) := *$.

By construction, $\beta \neq \alpha$ covers $\alpha$.

## Corollary 2

A minterm $\alpha : V \rightarrow \{0, 1\}$ is a prime implicant iff for all other minterms $\gamma : V \rightarrow \{0, 1\}$, $\gamma \neq \alpha$ the hamming distance $\Delta_{\mathrm{H}}(\alpha, \gamma) \ge 2$.

Proof: By definition, a cube is a prime implicant iff it is not covered by any other implicant. Accordingly, a minterm $\alpha : V \rightarrow \{0, 1\}$ (each minterm is also a cube) is a prime implicant iff it is not covered by any other implicant. Not being covered by any other implicant means, by the lemma 1 above, that for all other minterms $\gamma : V \rightarrow \{0, 1\}$, $\gamma \neq \alpha$ the hamming distance $\Delta_{\mathrm{H}}(\alpha, \gamma) \ge 2$.

## Corollary 3

There exist at most $2^{n-1}$ models that are prime implicants.

Proof: Corollary 2, taken in conjunction with the fact that every vertex in the $n$-dimensional cube has $n$ adjacent vertices, implies that it is impossible to choose $k > 2^{n-1}$ models (out of $2^n$ variable assignments) such that no models among them have hamming distance 1. Accordingly, there cannot exist $k > 2^{n-1}$ (different) models that are prime implicants.

## Corollary 4

There are at most $2^{n-1}$ (distinct) essential prime implicants.

Proof:

• Suppose we managed to pick $k > 2^{n-1}$ essential prime implicants — let the set $P$ contain them — $\st P \st = k$.
• Every $p \in P$ is essential. Intuitively, this means that it must contribute at least one model that other essential prime implicants in $P$ cannot contribute.
• Formally, it holds that for every $p \in P$ there exists a model $m_p$, such that there is no other $q \in P$, $q \neq p$, that contains this model ($M(q)$ denotes the set of models $q$ covers):
$\forall p, q \in P : p \neq q : m_p \notin M(q)$
• It follows that models $\{m_p : p \in P\}$ must have hamming distance 1 among each other.
• This means, by corollary 2, that all these models by themselves must be prime implicants.
• We get a contradiction, because corollary 3 states that it is impossible to choose $k > 2^{n-1}$ models that are prime implicants.

## Theorem 2

For any $n \in \mathbb{N}^+$, there exist exactly 2 boolean functions $\varphi$ and $\psi$ with $n$ variables, such that the smallest possible DNF’s describing these functions consist of $2^{n-1}$ terms and each term has exactly $n$ literals. All other boolean functions with $n$ variables have smaller minimal DNF’s.

Moreover, $\varphi$ and $\psi$ have the following properties: \begin{aligned} \varphi(x_{n-1}, \dots, x_0) = 1 &\Leftrightarrow \exists k \in \mathbb{N}_0 : x_{n-1}\dots x_0 = g(2 \cdot k) \\ \psi(x_{n-1}, \dots, x_0) = 1 &\Leftrightarrow \exists k \in \mathbb{N}_0 : x_{n-1}\dots x_0 = g(2 \cdot k + 1) \\ \varphi &\equiv \neg \psi \\ \varphi(x_{n-1}, \dots, x_0) &\equiv x_{n-1} \oplus \dots \oplus x_0 \\ \psi(x_{n-1}, \dots, x_0) &\equiv x_{n-1} \leftrightarrow \dots \leftrightarrow x_0 \end{aligned}

Proof: Each boolean function is a set of models. Clearly, this set is a subset of the set of vertices of an $n$-dimensional cube, built as described at the beginning of this post.

By the theorem 1 above, stating that gray codes for even numbers have hamming distance at least 2 among each other, combined with corollary 2, it follows that all $2^{n-1}$ models of $\varphi$ are prime implicants. Analogously, all $2^{n-1}$ models of $\psi$ are prime implicants. Corollary 3 states, that there exist at most $2^{n-1}$ models that are prime implicants, so we conclude that $\varphi$ and $\psi$ reach this maximum.

We now argue why it also follows that there are no other ways of choosing $2^{n-1}$ models that are prime implicants, apart from the ways models for $\varphi$ and $\psi$$M(\varphi)$ and $M(\psi)$ are chosen:

• Assume we found $2^{n-1}$ models which are prime implicants. Let $A$ be the set of these models.
• Also, assume $A \neq M(\varphi)$ and $A \neq M(\psi)$.
• This means that $A \cap M(\varphi) \neq \varnothing$ and $A \cap M(\psi) \neq \varnothing$, or, in other words, there exist variable models $i,j \in A$, $i \neq j$, such that $i \in M(\varphi)$ and $j \in M(\psi)$.
• As $i \in M(\varphi)$, because a vertex in an $n$-dimensional cube has $n$ adjacent vertices, there exists $N_\psi \subseteq M(\psi)$ with $\st N_\psi \st = n$ and $N_\psi \cap A = \varnothing$.
• If it is not he case, that $N_\psi \cap A = \varnothing$ (for example, if $j \in N_\psi$), then we directly get a contradiction.
• Analogously, there exists $N_\varphi \subseteq M(\psi)$ with $\st N_\varphi \st = n$ and $N_\varphi \cap A = \varnothing$.
• Therefore, it holds that $A \subseteq M \backslash (N_\varphi \cup N_\psi)$, where $M$ is the set of all models. Note that $N_\varphi$ and $N_\psi$ are disjoint. In other words, $A$ contains models from the remaining $2^n - 2 \cdot n$ vertices of the cube.
• Suppose we we know all $2^{n-1} - 2$ vertices apart from $i$ and $j$ that are in $A$ (these nodes are “chosen” out of $2^n - 2 \cdot n - 2$ remaining vertices).
• We now estimate the maximum number of edges that are not inside $A$, i.e. that either connect nodes outside $A$ with each other or connect nodes inside $A$ with nodes outside of $A$:
\begin{aligned} (2^n - 2 \cdot n - 2^{n-1} + n) \cdot n &= (2^n - 2^{n-1} - n) \cdot n \\ &= (2^{n-1} - n) \cdot n \end{aligned}
• There are $2^{n-1} \cdot n$ edges total. So, at least the following amount of edges must connect nodes inside $A$:
\begin{aligned} 2^{n-1} \cdot n - (2^{n-1} - n) \cdot n &= (2^{n-1} - (2^{n-1} - n)) \cdot n \\ &= (2^{n-1} - 2^{n-1} + n) \cdot n \\ &= n^2 \end{aligned}
• We therefore get a contradiction.

The above reasoning can be visualized for $n = 5$ as follows (we consider the worst-case $A$ set in this visualization):

It follows from the above that $\varphi$ and $\psi$ are exactly the boolean functions which have the most models that are prime implicants — all other boolean functions have less.

Now, we will need the Quine’s Theorem, which reads as follows:

Each minimal disjunction of cubes is a disjunction of prime implicants.

In the present context, because of corollary 4 stating that there are at most $2^{n-1}$ essential prime implicants, this means that every minimal DNF has at most $2^{n-1}$ terms (each term satisfies the whole formula iff the variable assignment is described by the corresponding prime implicant).

All (essential) prime implicants of $\varphi$ and $\psi$ are models, so each term in the minimal DNF is guaranteed to have $n$ literals, making it the maximal DNF possible:

• If some other boolean function has less than $2^{n-1}$ essential prime implicants, it will have less than $2^{n-1}$ terms in the minimal DNF.
• If some other boolean function has $2^{n-1}$ essential prime implicants, then there will be at least one cube of order at least 1, making the corresponding term of the minimal DNF have less than $n$ literals.

The properties of the $\varphi$ and $\psi$ functions mentioned in the statement of this theorem hold by construction of the models — gray codes of even numbers have an even number of ones and gray codes of odd numbers have an odd number of ones. This is not hard to prove — but it is also not necessary at this point because of the above argument about the uniqueness of the sets of models. This was also the idea I mentioned at the beginning of the post. It also follows that $\varphi \equiv \neg \psi$, because both $\varphi$ and $\psi$ have $2^{n-1}$ disjoint models out of $2^n$ possible variable assignments.

This completes the proof.

## Example

Consider all boolean functions with $n := 3$ variables. There are $2^{(2^n)} = 2^8 = 256$ such functions. These are the minimal DNF’s of all these 256 functions (I computed them with the Quine-McCluskey algorithm), the first 8 columns of the table represent the right-hand side of the truth table. The order of the assignments in the truth table is the order in which we count in binary. Please note there may be different minimal DNF’s that correspond to a particular boolean function, if that is the case then the corresponding table entry contains one of them.

R1R2R3R4R5R6R7R8Minimal DNF
000000000
00000001a ∧ b ∧ c
00000010a ∧ b ∧ ¬c
00000011a ∧ b
00000100a ∧ ¬b ∧ c
00000101a ∧ c
00000110a ∧ ¬b ∧ c ∨ a ∧ b ∧ ¬c
00000111a ∧ c ∨ a ∧ b
00001000a ∧ ¬b ∧ ¬c
00001001a ∧ ¬b ∧ ¬c ∨ a ∧ b ∧ c
00001010a ∧ ¬c
00001011a ∧ ¬c ∨ a ∧ b
00001100a ∧ ¬b
00001101a ∧ ¬b ∨ a ∧ c
00001110a ∧ ¬b ∨ a ∧ ¬c
00001111a
00010000¬a ∧ b ∧ c
00010001b ∧ c
00010010¬a ∧ b ∧ c ∨ a ∧ b ∧ ¬c
00010011b ∧ c ∨ a ∧ b
00010100¬a ∧ b ∧ c ∨ a ∧ ¬b ∧ c
00010101b ∧ c ∨ a ∧ c
00010110¬a ∧ b ∧ c ∨ a ∧ ¬b ∧ c ∨ a ∧ b ∧ ¬c
00010111b ∧ c ∨ a ∧ c ∨ a ∧ b
00011000a ∧ ¬b ∧ ¬c ∨ ¬a ∧ b ∧ c
00011001a ∧ ¬b ∧ ¬c ∨ b ∧ c
00011010¬a ∧ b ∧ c ∨ a ∧ ¬c
00011011a ∧ ¬c ∨ b ∧ c
00011100¬a ∧ b ∧ c ∨ a ∧ ¬b
00011101a ∧ ¬b ∨ b ∧ c
00011110¬a ∧ b ∧ c ∨ a ∧ ¬b ∨ a ∧ ¬c
00011111b ∧ c ∨ a
00100000¬a ∧ b ∧ ¬c
00100001¬a ∧ b ∧ ¬c ∨ a ∧ b ∧ c
00100010b ∧ ¬c
00100011b ∧ ¬c ∨ a ∧ b
00100100¬a ∧ b ∧ ¬c ∨ a ∧ ¬b ∧ c
00100101¬a ∧ b ∧ ¬c ∨ a ∧ c
00100110a ∧ ¬b ∧ c ∨ b ∧ ¬c
00100111b ∧ ¬c ∨ a ∧ c
00101000¬a ∧ b ∧ ¬c ∨ a ∧ ¬b ∧ ¬c
00101001¬a ∧ b ∧ ¬c ∨ a ∧ ¬b ∧ ¬c ∨ a ∧ b ∧ c
00101010b ∧ ¬c ∨ a ∧ ¬c
00101011b ∧ ¬c ∨ a ∧ ¬c ∨ a ∧ b
00101100¬a ∧ b ∧ ¬c ∨ a ∧ ¬b
00101101¬a ∧ b ∧ ¬c ∨ a ∧ ¬b ∨ a ∧ c
00101110b ∧ ¬c ∨ a ∧ ¬b
00101111b ∧ ¬c ∨ a
00110000¬a ∧ b
00110001¬a ∧ b ∨ b ∧ c
00110010¬a ∧ b ∨ b ∧ ¬c
00110011b
00110100a ∧ ¬b ∧ c ∨ ¬a ∧ b
00110101¬a ∧ b ∨ a ∧ c
00110110a ∧ ¬b ∧ c ∨ ¬a ∧ b ∨ b ∧ ¬c
00110111a ∧ c ∨ b
00111000a ∧ ¬b ∧ ¬c ∨ ¬a ∧ b
00111001a ∧ ¬b ∧ ¬c ∨ ¬a ∧ b ∨ b ∧ c
00111010¬a ∧ b ∨ a ∧ ¬c
00111011a ∧ ¬c ∨ b
00111100¬a ∧ b ∨ a ∧ ¬b
00111101¬a ∧ b ∨ a ∧ ¬b ∨ a ∧ c
00111110¬a ∧ b ∨ a ∧ ¬b ∨ a ∧ ¬c
00111111b ∨ a
01000000¬a ∧ ¬b ∧ c
01000001¬a ∧ ¬b ∧ c ∨ a ∧ b ∧ c
01000010¬a ∧ ¬b ∧ c ∨ a ∧ b ∧ ¬c
01000011¬a ∧ ¬b ∧ c ∨ a ∧ b
01000100¬b ∧ c
01000101¬b ∧ c ∨ a ∧ c
01000110a ∧ b ∧ ¬c ∨ ¬b ∧ c
01000111¬b ∧ c ∨ a ∧ b
01001000¬a ∧ ¬b ∧ c ∨ a ∧ ¬b ∧ ¬c
01001001¬a ∧ ¬b ∧ c ∨ a ∧ ¬b ∧ ¬c ∨ a ∧ b ∧ c
01001010¬a ∧ ¬b ∧ c ∨ a ∧ ¬c
01001011¬a ∧ ¬b ∧ c ∨ a ∧ ¬c ∨ a ∧ b
01001100¬b ∧ c ∨ a ∧ ¬b
01001101¬b ∧ c ∨ a ∧ ¬b ∨ a ∧ c
01001110¬b ∧ c ∨ a ∧ ¬c
01001111¬b ∧ c ∨ a
01010000¬a ∧ c
01010001¬a ∧ c ∨ b ∧ c
01010010a ∧ b ∧ ¬c ∨ ¬a ∧ c
01010011¬a ∧ c ∨ a ∧ b
01010100¬a ∧ c ∨ ¬b ∧ c
01010101c
01010110a ∧ b ∧ ¬c ∨ ¬a ∧ c ∨ ¬b ∧ c
01010111a ∧ b ∨ c
01011000a ∧ ¬b ∧ ¬c ∨ ¬a ∧ c
01011001a ∧ ¬b ∧ ¬c ∨ ¬a ∧ c ∨ b ∧ c
01011010¬a ∧ c ∨ a ∧ ¬c
01011011¬a ∧ c ∨ a ∧ ¬c ∨ a ∧ b
01011100¬a ∧ c ∨ a ∧ ¬b
01011101a ∧ ¬b ∨ c
01011110¬a ∧ c ∨ a ∧ ¬b ∨ a ∧ ¬c
01011111c ∨ a
01100000¬a ∧ ¬b ∧ c ∨ ¬a ∧ b ∧ ¬c
01100001¬a ∧ ¬b ∧ c ∨ ¬a ∧ b ∧ ¬c ∨ a ∧ b ∧ c
01100010¬a ∧ ¬b ∧ c ∨ b ∧ ¬c
01100011¬a ∧ ¬b ∧ c ∨ b ∧ ¬c ∨ a ∧ b
01100100¬a ∧ b ∧ ¬c ∨ ¬b ∧ c
01100101¬a ∧ b ∧ ¬c ∨ ¬b ∧ c ∨ a ∧ c
01100110¬b ∧ c ∨ b ∧ ¬c
01100111¬b ∧ c ∨ b ∧ ¬c ∨ a ∧ b
01101000¬a ∧ ¬b ∧ c ∨ ¬a ∧ b ∧ ¬c ∨ a ∧ ¬b ∧ ¬c
01101001¬a ∧ ¬b ∧ c ∨ ¬a ∧ b ∧ ¬c ∨ a ∧ ¬b ∧ ¬c ∨ a ∧ b ∧ c
01101010¬a ∧ ¬b ∧ c ∨ b ∧ ¬c ∨ a ∧ ¬c
01101011¬a ∧ ¬b ∧ c ∨ b ∧ ¬c ∨ a ∧ ¬c ∨ a ∧ b
01101100¬a ∧ b ∧ ¬c ∨ ¬b ∧ c ∨ a ∧ ¬b
01101101¬a ∧ b ∧ ¬c ∨ ¬b ∧ c ∨ a ∧ ¬b ∨ a ∧ c
01101110¬b ∧ c ∨ b ∧ ¬c ∨ a ∧ ¬c
01101111¬b ∧ c ∨ b ∧ ¬c ∨ a
01110000¬a ∧ c ∨ ¬a ∧ b
01110001¬a ∧ c ∨ ¬a ∧ b ∨ b ∧ c
01110010¬a ∧ c ∨ b ∧ ¬c
01110011¬a ∧ c ∨ b
01110100¬b ∧ c ∨ ¬a ∧ b
01110101¬a ∧ b ∨ c
01110110¬b ∧ c ∨ ¬a ∧ b ∨ b ∧ ¬c
01110111c ∨ b
01111000a ∧ ¬b ∧ ¬c ∨ ¬a ∧ c ∨ ¬a ∧ b
01111001a ∧ ¬b ∧ ¬c ∨ ¬a ∧ c ∨ ¬a ∧ b ∨ b ∧ c
01111010¬a ∧ c ∨ b ∧ ¬c ∨ a ∧ ¬c
01111011¬a ∧ c ∨ a ∧ ¬c ∨ b
01111100¬b ∧ c ∨ ¬a ∧ b ∨ a ∧ ¬b
01111101¬a ∧ b ∨ a ∧ ¬b ∨ c
01111110¬a ∧ c ∨ b ∧ ¬c ∨ a ∧ ¬b
01111111c ∨ b ∨ a
10000000¬a ∧ ¬b ∧ ¬c
10000001¬a ∧ ¬b ∧ ¬c ∨ a ∧ b ∧ c
10000010¬a ∧ ¬b ∧ ¬c ∨ a ∧ b ∧ ¬c
10000011¬a ∧ ¬b ∧ ¬c ∨ a ∧ b
10000100¬a ∧ ¬b ∧ ¬c ∨ a ∧ ¬b ∧ c
10000101¬a ∧ ¬b ∧ ¬c ∨ a ∧ c
10000110¬a ∧ ¬b ∧ ¬c ∨ a ∧ ¬b ∧ c ∨ a ∧ b ∧ ¬c
10000111¬a ∧ ¬b ∧ ¬c ∨ a ∧ c ∨ a ∧ b
10001000¬b ∧ ¬c
10001001a ∧ b ∧ c ∨ ¬b ∧ ¬c
10001010¬b ∧ ¬c ∨ a ∧ ¬c
10001011¬b ∧ ¬c ∨ a ∧ b
10001100¬b ∧ ¬c ∨ a ∧ ¬b
10001101¬b ∧ ¬c ∨ a ∧ c
10001110¬b ∧ ¬c ∨ a ∧ ¬b ∨ a ∧ ¬c
10001111¬b ∧ ¬c ∨ a
10010000¬a ∧ ¬b ∧ ¬c ∨ ¬a ∧ b ∧ c
10010001¬a ∧ ¬b ∧ ¬c ∨ b ∧ c
10010010¬a ∧ ¬b ∧ ¬c ∨ ¬a ∧ b ∧ c ∨ a ∧ b ∧ ¬c
10010011¬a ∧ ¬b ∧ ¬c ∨ b ∧ c ∨ a ∧ b
10010100¬a ∧ ¬b ∧ ¬c ∨ ¬a ∧ b ∧ c ∨ a ∧ ¬b ∧ c
10010101¬a ∧ ¬b ∧ ¬c ∨ b ∧ c ∨ a ∧ c
10010110¬a ∧ ¬b ∧ ¬c ∨ ¬a ∧ b ∧ c ∨ a ∧ ¬b ∧ c ∨ a ∧ b ∧ ¬c
10010111¬a ∧ ¬b ∧ ¬c ∨ b ∧ c ∨ a ∧ c ∨ a ∧ b
10011000¬a ∧ b ∧ c ∨ ¬b ∧ ¬c
10011001¬b ∧ ¬c ∨ b ∧ c
10011010¬a ∧ b ∧ c ∨ ¬b ∧ ¬c ∨ a ∧ ¬c
10011011¬b ∧ ¬c ∨ b ∧ c ∨ a ∧ b
10011100¬a ∧ b ∧ c ∨ ¬b ∧ ¬c ∨ a ∧ ¬b
10011101¬b ∧ ¬c ∨ b ∧ c ∨ a ∧ c
10011110¬a ∧ b ∧ c ∨ ¬b ∧ ¬c ∨ a ∧ ¬b ∨ a ∧ ¬c
10011111¬b ∧ ¬c ∨ b ∧ c ∨ a
10100000¬a ∧ ¬c
10100001a ∧ b ∧ c ∨ ¬a ∧ ¬c
10100010¬a ∧ ¬c ∨ b ∧ ¬c
10100011¬a ∧ ¬c ∨ a ∧ b
10100100a ∧ ¬b ∧ c ∨ ¬a ∧ ¬c
10100101¬a ∧ ¬c ∨ a ∧ c
10100110a ∧ ¬b ∧ c ∨ ¬a ∧ ¬c ∨ b ∧ ¬c
10100111¬a ∧ ¬c ∨ a ∧ c ∨ a ∧ b
10101000¬a ∧ ¬c ∨ ¬b ∧ ¬c
10101001a ∧ b ∧ c ∨ ¬a ∧ ¬c ∨ ¬b ∧ ¬c
10101010¬c
10101011a ∧ b ∨ ¬c
10101100¬a ∧ ¬c ∨ a ∧ ¬b
10101101¬a ∧ ¬c ∨ a ∧ ¬b ∨ a ∧ c
10101110a ∧ ¬b ∨ ¬c
10101111¬c ∨ a
10110000¬a ∧ ¬c ∨ ¬a ∧ b
10110001¬a ∧ ¬c ∨ b ∧ c
10110010¬a ∧ ¬c ∨ ¬a ∧ b ∨ b ∧ ¬c
10110011¬a ∧ ¬c ∨ b
10110100a ∧ ¬b ∧ c ∨ ¬a ∧ ¬c ∨ ¬a ∧ b
10110101¬a ∧ ¬c ∨ b ∧ c ∨ a ∧ c
10110110a ∧ ¬b ∧ c ∨ ¬a ∧ ¬c ∨ ¬a ∧ b ∨ b ∧ ¬c
10110111¬a ∧ ¬c ∨ a ∧ c ∨ b
10111000¬b ∧ ¬c ∨ ¬a ∧ b
10111001¬b ∧ ¬c ∨ ¬a ∧ b ∨ b ∧ c
10111010¬a ∧ b ∨ ¬c
10111011¬c ∨ b
10111100¬b ∧ ¬c ∨ ¬a ∧ b ∨ a ∧ ¬b
10111101¬a ∧ ¬c ∨ a ∧ ¬b ∨ b ∧ c
10111110¬a ∧ b ∨ a ∧ ¬b ∨ ¬c
10111111¬c ∨ b ∨ a
11000000¬a ∧ ¬b
11000001a ∧ b ∧ c ∨ ¬a ∧ ¬b
11000010a ∧ b ∧ ¬c ∨ ¬a ∧ ¬b
11000011¬a ∧ ¬b ∨ a ∧ b
11000100¬a ∧ ¬b ∨ ¬b ∧ c
11000101¬a ∧ ¬b ∨ a ∧ c
11000110a ∧ b ∧ ¬c ∨ ¬a ∧ ¬b ∨ ¬b ∧ c
11000111¬a ∧ ¬b ∨ a ∧ c ∨ a ∧ b
11001000¬a ∧ ¬b ∨ ¬b ∧ ¬c
11001001a ∧ b ∧ c ∨ ¬a ∧ ¬b ∨ ¬b ∧ ¬c
11001010¬a ∧ ¬b ∨ a ∧ ¬c
11001011¬a ∧ ¬b ∨ a ∧ ¬c ∨ a ∧ b
11001100¬b
11001101a ∧ c ∨ ¬b
11001110a ∧ ¬c ∨ ¬b
11001111¬b ∨ a
11010000¬a ∧ ¬b ∨ ¬a ∧ c
11010001¬a ∧ ¬b ∨ b ∧ c
11010010a ∧ b ∧ ¬c ∨ ¬a ∧ ¬b ∨ ¬a ∧ c
11010011¬a ∧ ¬b ∨ b ∧ c ∨ a ∧ b
11010100¬a ∧ ¬b ∨ ¬a ∧ c ∨ ¬b ∧ c
11010101¬a ∧ ¬b ∨ c
11010110a ∧ b ∧ ¬c ∨ ¬a ∧ ¬b ∨ ¬a ∧ c ∨ ¬b ∧ c
11010111¬a ∧ ¬b ∨ a ∧ b ∨ c
11011000¬b ∧ ¬c ∨ ¬a ∧ c
11011001¬b ∧ ¬c ∨ ¬a ∧ c ∨ b ∧ c
11011010¬b ∧ ¬c ∨ ¬a ∧ c ∨ a ∧ ¬c
11011011¬a ∧ ¬b ∨ a ∧ ¬c ∨ b ∧ c
11011100¬a ∧ c ∨ ¬b
11011101¬b ∨ c
11011110¬a ∧ c ∨ a ∧ ¬c ∨ ¬b
11011111¬b ∨ c ∨ a
11100000¬a ∧ ¬b ∨ ¬a ∧ ¬c
11100001a ∧ b ∧ c ∨ ¬a ∧ ¬b ∨ ¬a ∧ ¬c
11100010¬a ∧ ¬b ∨ b ∧ ¬c
11100011¬a ∧ ¬b ∨ b ∧ ¬c ∨ a ∧ b
11100100¬a ∧ ¬c ∨ ¬b ∧ c
11100101¬a ∧ ¬c ∨ ¬b ∧ c ∨ a ∧ c
11100110¬a ∧ ¬c ∨ ¬b ∧ c ∨ b ∧ ¬c
11100111¬a ∧ ¬b ∨ b ∧ ¬c ∨ a ∧ c
11101000¬a ∧ ¬b ∨ ¬a ∧ ¬c ∨ ¬b ∧ ¬c
11101001a ∧ b ∧ c ∨ ¬a ∧ ¬b ∨ ¬a ∧ ¬c ∨ ¬b ∧ ¬c
11101010¬a ∧ ¬b ∨ ¬c
11101011¬a ∧ ¬b ∨ a ∧ b ∨ ¬c
11101100¬a ∧ ¬c ∨ ¬b
11101101¬a ∧ ¬c ∨ a ∧ c ∨ ¬b
11101110¬b ∨ ¬c
11101111¬b ∨ ¬c ∨ a
11110000¬a
11110001b ∧ c ∨ ¬a
11110010b ∧ ¬c ∨ ¬a
11110011¬a ∨ b
11110100¬b ∧ c ∨ ¬a
11110101¬a ∨ c
11110110¬b ∧ c ∨ b ∧ ¬c ∨ ¬a
11110111¬a ∨ c ∨ b
11111000¬b ∧ ¬c ∨ ¬a
11111001¬b ∧ ¬c ∨ b ∧ c ∨ ¬a
11111010¬a ∨ ¬c
11111011¬a ∨ ¬c ∨ b
11111100¬a ∨ ¬b
11111101¬a ∨ ¬b ∨ c
11111110¬a ∨ ¬b ∨ ¬c
111111111

We see that the there exist exactly two longest minimal DNF’s that correspond to the functions that we described in theorem 2 above: \begin{aligned} \varphi &= (\neg a \wedge \neg b \wedge \neg c) \vee (\neg a \wedge b \wedge c) \vee (a \wedge \neg b \wedge c) \vee (a \wedge b \wedge \neg c) \equiv a \oplus b \oplus c \\ \psi &= (\neg a \wedge \neg b \wedge c) \vee (\neg a \wedge b \wedge \neg c) \vee (a \wedge \neg b \wedge \neg c) \vee (a \wedge b \wedge c) \equiv a \leftrightarrow b \leftrightarrow c \\ \varphi &\equiv \neg \psi \end{aligned}