Could anyone check if my proof is ok/ suggest any improvement please? I couldn't find a way to utilise the induction hypothesis so I am not sure if this is ok.

Let $φ$ be a formula built up using the connectives $¬, ∧, ∨$. The dual $φ$' of $φ$ is the formula obtained from $φ$ by replacing all occurrences of $∧$ by $∨$, of $∨$ by $∧$, and all propositional variables by their negations. Show that $φ$' is logically equivalent to $¬φ$.

Induction on occurrence of operator.

Base case: operator occurence of $φ$'=$0$ - this is only possible if double negation elimination has been applied, since if $φ$=$P$ $\to$ $φ$'=$\lnot P$, or $φ$=$\lnot P$ $\to$ $φ$'=$\lnot \lnot P$. $φ$' has at least one operator no matter what. Therefore $φ$ must already have a $\lnot$ and get another $\lnot$ added on when transformed into $φ$', then have them cancelled by double negation. Thus $φ$' $\equiv$ $\lnot φ$.

Hypothesis: Assume that for all $φ$' whose length $\le n$, $φ$' $\equiv φ$.

Since $φ$ is only built up with 3 types of operators, there can only be 3 possible scenarios:

  1. $φ$'=$\psi$ $\land$ $\phi$: Therefore $φ=\lnot \psi \lor \lnot \phi$. Applying DeMorgan then $φ$'$=\lnotφ=\lnot(\lnot\psi\lor\lnot\phi)$.

  2. $φ$'=$\psi$ $\lor$ $\phi$: Similar approach to 1.

  3. $φ$'=$\lnot \psi$:Therefore $φ=\lnot \psi$, and $φ$'$=φ=\lnot \psi$.

  • $\begingroup$ The usual definition of "dual" does not replace propositional variables by their negations. $\endgroup$ Dec 31, 2017 at 22:23

1 Answer 1


I would strongly suggest structural induction. That is, rather than using some unnecessarily convoluted way of doing induction on the length of the statement or number of operators, you can simply follow the recursive definition of statements, which is:

  1. All propositional variables are statements

2a. If $\psi$ is a statement, then $\neg \psi$ is a statement

2b. If $\psi_1$ and $\psi_2$ are statements, then $\psi_1 \land \psi_2$ is a statement

2c. If $\psi_1$ and $\psi_2$ are statements, then $\psi_1 \land \psi_2$ is a statement

  1. Nothing else is a statement

Structural induction mirrors this very recursive definition. That is, in order to show that all statements have some property, show that:

Base: Show that all propositional variables have the property


a. Show that $\neg \psi$ has the property assuming that $\phi$ has the property

b. Show that $\psi_1 \land \psi_2$ has the property assuming that $\psi_1$ and $\psi_2$ have the property

c. Show that $\psi_1 \land \psi_2$ has the property assuming that $\psi_1$ and $\psi_2$ have the property

If we can show these things, and given that nothing else is a statement (that is why 3 in the definition is important to have), we can conclude that all statements haven the property in question.

Also, make sure to clearly and explicitly state what you are trying to prove. Here is what you are trying to prove:


For all statements $\phi$ it is true that $\phi' \Leftrightarrow \neg \phi$

Note that I use $\Leftrightarrow$ here, because that is the symbol typically used for logical equivalence. The $=$ is often used to indicate that some statement is syntactically identical to some other statement, which is not the same as logical equivalence. For example, $P \land Q \Leftrightarrow Q \land P$, but they are not the same symbol string, i.e. $P \land Q \not = Q \land P$

OK, so let's apply structural induction to your problem:

Base case: $\phi$ is some atomic formula $P$. Then $\phi' = P' = \neg P = \neg \phi$, and therefore certainly $\phi' \Leftrightarrow \neg \phi$. Check!

Step: Take any complex $\phi$, i.e. $\phi = \psi_1 \land \psi_2$, $\phi = \psi_1 \lor \psi_2$, or $\phi = \neg \psi$

Let's just do the $\phi = \psi_1 \land \psi_2$ case.

By inductive hypothesis we have $\psi_1' \Leftrightarrow \neg \psi_1$, and $\psi_2'\Leftrightarrow \neg \psi_2$

So then:

$$\phi'=(\psi_1 \land \psi_2)'=(\psi_1' \lor \psi_2') \overset{I.H.}{\Leftrightarrow} (\neg \psi_1 \lor \neg \psi_2) \overset{D.M.}{\Leftrightarrow} \neg (\psi_1 \land \psi_2) = \neg \phi$$

Do you see now how the inductive hypothesis was used?

  • 1
    $\begingroup$ @DanielMak You're welcome! In answer to your follow-up questions: 1) In general: it is indeed not necessary to use the I.H.: if you can prove the desired result without it, than that's just fine. This rarely happens though (and typically when it does happen, it's because there is a perfectly good non-inductive proof). And for this particular problem, you really do need to use the I.H. ... (follow-up comment for 2) ) $\endgroup$
    – Bram28
    Jan 1, 2018 at 15:03
  • 1
    $\begingroup$ @DanielMak For 2). No, your proof has some small issues. For the base case, you can't assume that $\phi'$ is the result of applying a double negation after you have transformed $\phi$ into $\phi'$, because $\phi'$ is defined syntactically, and thus removing a double negation results in something other than $\phi'$; just something that is equivalent to it. So, instead, you should induce over $\phi$: That is, the claim to prove is that for all $\phi$: $\phi'$ is equivalent to $\neg \phi$. So there's a lesson here: get very clear on your theorem to be proven! (...to be continued) $\endgroup$
    – Bram28
    Jan 1, 2018 at 15:07
  • 1
    $\begingroup$ @DanielMak Also, for the step: you really do need to use those I.H.'s in order to justify the 'therefore's you use there. Oh, and the proof as a whole: you say you do induction on 'operator occurrence' ... is that the number of operators? But that is different from how we typically talk about the 'length' of the statement, which is the number of symbols, period (i.e. operators and propositional variables (and often we count parentheses too)). $\endgroup$
    – Bram28
    Jan 1, 2018 at 15:08
  • 1
    $\begingroup$ @DanielMak Couple more. You write: "Hypothesis: Assume that for all $φ$' whose length $\le n$, $φ$' $\equiv φ$." That last part should be $φ$' $\equiv \neg φ$. Also: "$φ$'=$\lnot \psi$:Therefore $φ=\lnot \psi$, and $φ$'$=φ=\lnot \psi$." That last part should also be $φ$' $\equiv \neg φ$ $\endgroup$
    – Bram28
    Jan 1, 2018 at 15:14
  • 1
    $\begingroup$ @DanielMak Thanks for explaining the 'operator occurrence'. It is a bit unusual to call that the 'length' of the statement, but ok, and yes, obviousl;y you can do the induction based on that 'length' as well. But notice how unnecessarily convoluted that gets: in the step, when for example you have $\phi = \psi_1 \land \psi_2$, you first need to point out that the length of $\psi_1$ and $\psi_2$ is smaller than that of $\phi$, that therefore the inductive hypothesis can be applied (and by the way, you are really using a version of strong induction there), and then you move on.... (cont'd) $\endgroup$
    – Bram28
    Jan 2, 2018 at 15:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .