If $\phi$ is a tautology then dual $\phi$ is a contradiction.

Question

If $\phi$ is a statement form, Prove that: $\vDash \phi$ iff $\phi^{d}$ is a contradiction.

where $\phi^{d}$ is the dual of $\phi .$

$\phi^{d}$ is the dual of $\phi $ is defined by:

(i) $A^{d} = A$ for any statement letter A.

(ii)$(\lnot \phi)^{d} = \lnot (\phi^{d})$

(iii)$(\phi \land \psi )^{d} = \phi^{d}\lor \psi^{d}.$ and sililarly for $\vee$

(iv)$(\phi \Rightarrow \psi )^{d} = \lnot (\psi^{d}\Rightarrow \phi^{d}) $

Also, we have taken a theorem that states that: $$(\psi^{d})^{d} = \psi$$

I think it may be solved by induction,Could anyone give me an advice?

Answer 1

Your definition of the dual is not correct.

In general, for any two-place logical operator $\times$, the dual expression of $\phi \times \psi$ is $\phi^d \times^d \psi^d$, where $\times^d$ is the dual operator of $\times$, which you can find by: $\phi \times^d \psi \Leftrightarrow \neg (\neg \phi \times \neg \psi)$.

Thus, we find that:

$(\phi \land \psi )^d = \phi^d \lor \psi^d$

$(\phi \lor \psi )^d = \phi^d \land \psi^d$

$(\phi \rightarrow \psi)^d = \phi^d \not \leftarrow \psi^d$ (= $\neg (\psi^d \rightarrow \phi^d)$)

Etc.

That last one is a little unusual, and makes you wonder if you need to consider and figure out the dual operator for all 16 two-place logical operators. Fortunately, you don't have to: the good news is that in order to prove the desired result, all you need to do is use induction and use the general definition of dual expressions and dual operators as defined above (plus consideration of atomic statements and negations of course).

Now, it turns out that this is still not easy ...

HINT

As you will have noticed $\phi^d \not \Leftrightarrow \neg \phi$! So that's not the way to prove it.

However: Define the complement statement $\phi'$ of a statement $\phi$ to be that statement that puts a negation in front of every atomic statement in $\phi$. Recursively:

$A' = \neg A$ for any atomic $A$

$(\neg \phi)' = \neg (\phi)'$

$(\phi \times \psi)' = \phi' \times \psi'$

Now you should be able to prove (by induction of course) that $\phi^d\Leftrightarrow \neg \phi'$. And from that, the desired result follows fairly quickly.