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?
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 ¬?


  • $\begingroup$ I'm not really sure where to start or what tools to use to solve this. This is in chapter $1$ of a $2000$ level discrete math book, so we haven't been introduced to induction or any other proof techniques. I tried drawing up logic tables for some propositions and their duals, and found that if a proposition s is true in $x$ instances and false in $y$ instances (where $x+y$ is of course a power of $2$), then $s^{*}$ is false in $x$ instances and true in $y$ instances $\endgroup$ – Ovi May 30 '16 at 17:09

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^*$.


Why are Duals of Two Equivalent compound propositions Equivalent?

Let p and q be equivalent compound propositions involving only the operators , , and ¬, and T and F. Note that ¬p and ¬q are also equivalent. Use De Morgan’s laws as many times as necessary to push negations in as far as possible within these compound propositions, changing s to s, and vice versa, and changing Ts to Fs, and vice versa. This shows that ¬p and ¬q are the same as p∗ and q∗ except that each atomic proposition pi within them is replaced by its negation. From this, we can conclude that p∗ and q∗ are equivalent because ¬p and ¬q are.


Discrete Mathematics by K.H Rosen 7th edition

Exercise 1.3 question no 39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.