[Math] Why are Duals of Two Equivalent compound propositions Equivalent

Question

I know that if we have two equivalent propositions p and q then p* and q* will also be equivalent where p* and q* are duals of p and q respectively. I am looking for some explanation to why duals of equivalent propositions also equivalent?
Reference
Discrete Mathematics by K.H Rosen 7th edition
Exercise 1.3 question no 39

Why are the duals of two equivalent compound propositions also
equivalent, where these compound propositions contain only the
operators ∧,∨, and ¬?

Regards

Answer 1

Let us start by reconsidering the definition of the dual $\phi^*$ for a given propositional formula $\phi$. It can be summarised by the correspondences: \begin{align} \phi \land \psi &\overset*\iff\phi \lor \psi\\ \mathbf F &\overset*\iff \mathbf T \end{align}

We reuse a fundamental idea of the earlier exercises in the mentioned chapter, namely that $\phi \leftrightarrow \psi$ precisely when $\phi$ and $\psi$ are satisfied by exactly the same lines in a truth table.

Observation 1: A line of a truth table is nothing more than a function $v$ which assigns to each propositional variable a value $\mathbf T$ or $\mathbf F$ and subsequently evaluates the definitions of the connectives for this assignment.

Such a $v$ is known in the literature as a valuation or a boolean interpretation. Abstracting this notion away from the intuitive use in truth tables is a big asset in proving generic theorems. This is because it allows us to discuss rigorously an "arbitrary line of a truth table".

For example, by considering the two possibilities $v(p)=\mathbf T$ and $v(p)=\mathbf F$, it is not hard to see that $v(p\lor \neg p)= \mathbf T$ for every valuation of $\{p\}$. Similarly one can show that $v(p\to q) = v(\neg p \lor q)$ for each valuation of $\{p,q\}$, thus proving equivalence of these statements.

Observation 2: $\phi$ and $\psi$ are equivalent precisely when $v(\phi) =v(\psi)$ for all valuations $v$.

We need one final ingredient before turning to the main result.

Definition: Given a valuation $v$, the valuation $v^*$ is defined by: $$v^*(p) = \begin{cases}\mathbf T&\text{ if $v(p) = F$}\\\mathbf F&\text{ if $v(p) = T$}\end{cases}$$

The desired result will follow from the following:

Theorem: For any formula $\phi$ and valuation $v$, we have: $$v(\phi^*) = v^*(\neg\phi)$$

By assumption $\phi$ will have one of the following forms:

• $\phi = p$
• $\phi = \mathbf F$
• $\phi = \mathbf T$
• $\phi = \neg \tau$
• $\phi = \tau \lor \tau'$
• $\phi = \tau \land \tau'$

I will only prove the assertion for the last possibility $\tau \land \tau'$; the other options are similar or easier. We assume that the result has been proven for $\tau$ and $\tau'$.

Note that this decomposition of $\phi$ into possible forms is known formally as structural induction; it allows us to reason about an arbitrary formula in a structural manner, similar to proving an implication like $(\phi \lor \psi)\to \tau$: we first assume $\phi$ and show $\tau$ from it, and then do the same for $\psi$.

Now for the proof:

\begin{align} v(\phi^*) &= v((\tau\land\tau')^*)\\ &= v(\tau^* \lor \tau'^*)\\ &= f^\lor(v(\tau^*),v(\tau'^*))\\ &= f^\lor(~v^*(\neg\tau),v^*(\neg\tau')~)\\ &= v^*(\neg \tau \lor \neg\tau')\\ &= v^*(\neg(\tau\land\tau'))\\ &= v^*(\neg\phi) \end{align}

where $f^\lor$ denotes the definition of $\lor$ in terms of truth values (so $f^\lor(\mathbf F,\mathbf F) = \mathbf F$, otherwise $f^\lor$ yields $\mathbf T$). In the second-to-last step, a De Morgan equivalence is used.

---

Intuitively, the above result states that for every line of a truth table for $\phi^*$, we can mechanically construct one with the same value for $\neg\phi$. Because $\neg\phi$ and $\neg\psi$ are also equivalent, this means that the constructed valuations agree on $\neg\phi$ and $\neg\psi$. Additionally, it is not hard to see that every valuation on $\neg\phi$ can be constructed in this way, and we can transform them back to valuations of $\phi^*$ since $v^{**}=v$. These ingredients together establish equivalence of $\phi^*$ and $\psi^*$.