HINT
First, get some precise definitions going, so you can refer to those in your proof.
So, relative to any expression or function $\phi$ built up from $\neg$, $\lor$, and $\land$, define the expression $\phi^D$ to be the result of changing all $\land$'s into $\lor$'s and vice versa. Formally and recursively:
- $A^D = A$ if $A$ is an atomic sentence
- $(\neg \phi)^D = \neg \phi^D$
- $(\phi \land \psi)^D = \phi^D \lor \psi^D$
- $(\phi \lor \psi)^D = \phi^D \land \psi^D$
OK, so what you are asked to prove is that for any $\phi$ and $\psi$ built up from $\neg$, $\lor$, and $\land$: If $\phi \Leftrightarrow \psi$ then $\phi^D \Leftrightarrow \psi^D$
Now, how do you prove this? Here is one strategy:
Relative to any expression or function $\phi$ built up from $\neg$, $\lor$, and $\land$, define the expression $\phi’$ to be the sentence that one obtains by putting a negation in front of every atomic sentence occurring in $\phi$. Formally and recursively:
- $A’ = \neg A$ if $A$ is an atomic sentence
- $(\neg \phi)’ = \neg \phi’$
- $(\phi \land \psi)' = \phi' \land \psi'$
- $(\phi \lor \psi)' = \phi' \lor \psi'$
Use this to prove (using induction) the following Lemma's:
For any $\phi$ built up from $\neg$, $\lor$, and $\land$: $\phi^D \Leftrightarrow \neg \phi'$
For any $\phi$ and $\psi$ built up from $\neg$, $\lor$, and $\land$: If $\phi \Leftrightarrow \psi$ then $\phi' \Leftrightarrow \psi'$
The result you have to prove follows quickly from these two Lemma's.