Difference between duality and negation in boolean algebra and logic

Question

Suppose we have a statement
A + A' = 1 then it's complement would be A' . A = 0, and dual would be A . A' = 0.

My very first question is complement A' . A = 0 is true when compliment of a true statement A + A' = 1 should be false?

And second question is what is the difference between compliment and dual of any expression.

I searched the internet to see what is the practical use of Principle of duality but failed to get a satisfactory answer.

Answer 1

I will be using more typical notation.

A Boolean algebra is a partial order $\mathcal{B} = (B, \leq)$ such that

• For any $a, b \in B$, the set $\{c \in B \mid c \leq a$ and $c \leq b\}$ has a greatest element, denoted $a \land_{\mathcal{B}} b$
• For any $a, b \in B$, the set $\{c \in B \mid a \leq c$ and $b \leq c\}$ has a least element, denoted $a \lor_{\mathcal{B}} b$.
• For all $a, b, c$ we have $a \land (b \lor c) = (a \land b) \lor (a \land c)$. It follows from this axiom and the previous ones that $a \lor (b \land c) = (a \lor b) \land (a \lor c)$.
• $B$ has a greatest element. The greatest element is denoted $1_{\mathcal{B}}$.
• $B$ has a least element. The least element is denoted $0_{\mathcal{B}}$.
• For all $a$, there is a $b$ such that $a \lor b = 1$ and $a \land b = 0$. This $b$ is necessarily unique and denoted $\neg_{\mathcal{B}} a$.

By convention, we drop the subscript $_{\mathcal{B}}$ when it's clear which Boolean algebra is being discussed.

It's easy to show that $a \leq b$ if and only if $a = a \land b$. So the partial order can actually be recovered from the operations. It turns out that it's also possible to axiomatise a Boolean algebra using $1, 0, \land, \lor, \neg$ and equational identities.

We can also show that if $a \leq b$, then $a \land c \leq b \land c$ and also $a \lor c \leq b \lor c$. Furthermore, $\land$ and $\lor$ are clearly commutative.

The canonical example of a Boolean algebra is the set $2 = \{0, 1\}$, where $0 \leq 1$. This gives us the usual truth tables for $\lor$, $\land$, and $\neg$.

Intriguingly, one can prove that an identity about Boolean algebras holds for all Boolean algebras if, and only if, it holds for $2$. Thus, when one is dealing with Boolean identities, one can always approach the problem by checking whether the identity holds for $2$. This is known as the "truth table" approach.

Here is the useful and intriguing theorem:

Consider a Boolean algebra $\mathcal{B} = (B, \leq)$. Consider its opposite partial order $\mathcal{B}^{op} = (B, \geq)$, where $a \geq b$ iff $b \leq a$. Then $\mathcal{B}^{op}$ is also a Boolean algebra.

To prove this theorem, we can simply define the following:

• $1_{\mathcal{B}^{op}} = 0_{\mathcal{B}}$
• $0_{\mathcal{B}^{op}} = 1_{\mathcal{B}}$
• $a \land_{\mathcal{B}^{op}} b = a \lor_{\mathcal{B}} b$
• $a \lor_{\mathcal{B}^{op}} b = a \land_{\mathcal{B}} b$
• $\neg_{\mathcal{B}^{op}} a = \neg_{\mathcal{B}} b$

It's easy to check that these do indeed satisfy the relevant properties.

This means that any equation which is true in $\mathcal{B}$ has a "dual equation" which is true in $\mathcal{B}^{op}$.

For example, suppose the equation $(a \lor (a \land \neg a)) = a$ is true in $\mathcal{B}$. Then by definition, this is the very same equation as $(a \land_{\mathcal{B}^{op}} (a \lor_{\mathcal{B}^{op}} \neg_{\mathcal{B}^{op}} a)) = a$. You can see this just by looking at the definitions. This means that the dual equation $(a \land (a \lor \neg a)) = a$ is true in $\mathcal{B}^{op}$.

In particular, given any Boolean algebra equation which is true in all Boolean algebras, its complement must also be true in all Boolean algebras. This gives us our first instance of Boolean algebra duality.

Given a term $term$ written using variables, $0$, $1$, $\land$, $\lor$, and $\neg$, we say that the dual of the term, written $dual(term)$, is the term we get by swapping all $\land$s for $\lor$s and vice versa, and by swapping all $1$s for $0$s and vice versa. Then an equation $term_1 = term_2$ holds in $\mathcal{B}$ if and only if the dual equation $dual(term_1) = dual(term_2)$ holds in $\mathcal{B}^{op}$.

Finally, let's explore the properties of $\neg$ a bit. First, I claimed when defining $\neg$ that for all $a$, there is at most one $b$ such that $a \land b = 0$ and $a \lor b = 1$. Let's prove this. Suppose we had $b, b'$ such that $a \land b' = a \land b = 0$ and $a \lor b = a \lor b' = 1$. Then we have $b = b \land 1 = b \land (a \lor b') = (b \land a) \lor (b \land b') = 0 \lor (b \land b')$. Then $b = b \land b'$. Therefore, $b \leq b'$. Simply swapping out $b$ and $b'$ shows us that $b' \leq b$. Therefore, $b = b'$.

Now we can show that $\neg \neg a = a$ for all $a$. For we see that $\neg a \land a = a \land \neg a = 0$. And we see that $\neg a \lor a = a \lor \neg a = 1$. Thus, $a = \neg \neg a$, since $a$ satisfies the defining property of $\neg \neg a$.

Suppose that $a \leq b$. Then we see that $b \land (\neg b \land \neg a) = (b \land \neg b) \land (\neg a) = 0 \land \neg a = 0$. We also see that $b \lor (\neg b \land \neg a) = (b \lor \neg b) \land (b \lor \neg a) = 1 \land (b \lor \neg a) = b \lor \neg a$. Since $a \leq b$, we see that $1 = a \lor \neg a \leq b \lor \neg a$, and thus $b \lor \neg a = 1$.

So we see that $b \land (\neg b \land \neg a) = 0$ and that $b \lor (\neg b \land \neg a) = 1$. Therefore, $\neg b \land \neg a = \neg b$, and thus $\neg b \leq \neg a$.

This proves that $\neg : \mathcal{B} \to \mathcal{B}^{op}$ is an order-preserving map. Dually, it shows that $\neg : \mathcal{B}^{op} \to \mathcal{B}$ is an order-preserving. Since $\neg \neg a = a$ for all $a$, we see that $\neg : \mathcal{B} \to \mathcal{B}^{op}$ is an order isomorphism.

The fact that $\neg$ is an order isomorphism means that it must preserve the entire Boolean algebra structure, since the Boolean algebra structure is defined in terms of the order. In particular, we must have

• $\neg (a \land_{\mathcal{B}} b) = \neg a \land_{\mathcal{B}^{op}} \neg b = \neg a \lor_{\mathcal{B}} \neg b$
• $\neg (a \lor_{\mathcal{B}} b) = \neg a \lor_{\mathcal{B}^{op}} \neg b = \neg a \land_{\mathcal{B}} \neg b$
• $\neg 1_{\mathcal{B}} = 1_{\mathcal{B}^{op}} = 0_{\mathcal{B}}$
• $\neg 0_{\mathcal{B}} = 0_{\mathcal{B}^{op}} = 1_{\mathcal{B}}$
• $\neg (\neg_{\mathcal{B}} a) = \neg_{\mathcal{B}^{op}} (\neg a)$

The first two of these identities are known as "De Morgan's Laws". The remaining properties are rather straightforward.

In fact, using the above rules, it's possible to prove the following extremely general principle:

Let $term$ be a term written using variables and $0, 1, \land, \lor,$ and $\neg$. Let $complement(term)$ be $dual(term)$ with all variables $v$ replaced with $\neg v$. Then $\neg term = complement(term)$ is an identity that always holds in any Boolean algebra.

This is the second aspect of Boolean algebra duality.