Substituting conjunction and disjunction symbols in equivalent propositional formulas I was wondering if someone could help me prove this theorem in propositional logic:
Let $F \equiv G$. Show: if $F'$ and $G'$ are obtained from $F$ respectively $G$ by substituting all occurrences of $\lor$ by $\land$ (and vice versa) then $F' \equiv G'$.
My latest approach has been to formulate it for induction as:
For every formula $F$:
For every formula $G$:
If $F \equiv G$ and $F'$ and $G'$ are obtained from $F$ respectively $G$ by substituting all occurrences of $\lor$ by $\land$ (and vice versa) then $F' \equiv G'$.
Let $F$ be an arbitrary formula.
Let $G$ be an atomic formula.
Prove: If $G \equiv F$ then $G' \equiv F'$,
Since $G'$ is $G$:
Prove: If $G \equiv F$ then $G \equiv F'$.
Let $H$ be such that if $H \equiv F$ then $H' \equiv F'$.
Prove: If $\lnot H \equiv F$ then $(\lnot H)' \equiv F'$.
Since $(\lnot H)'$ is $\lnot H'$:
Prove: If $\lnot H \equiv F$ then $\lnot H' \equiv F'$.
Let $H_{1}$ be such that if $H_{1} \equiv F$ then $H_{1}' \equiv F'$.
Let $H_{2}$ be such that if $H_{2} \equiv F$ then $H_{2}' \equiv F'$.
Prove: If $(H_{1} \lor H_{2}) \equiv F$ then $(H_{1} \lor H_{2})' \equiv F'$.
Since $(H_{1} \lor H_{2})'$ is $(H_{1}' \land H_{2}')$:
Prove: If $(H_{1} \lor H_{2}) \equiv F$ then $(H_{1}' \land H_{2}') \equiv F'$.
Prove: If $(H_{1} \land H_{2}) \equiv F$ then $(H_{1} \land H_{2})' \equiv F'$.
Since $(H_{1} \land H_{2})'$ is $(H_{1}' \lor H_{2}')$:
Prove: If $(H_{1} \land H_{2}) \equiv F$ then $(H_{1}' \lor H_{2}') \equiv F'$.
I am not certain that I have set this up correctly and I have also not been able to prove the subsequent steps. It may be that this is not the best approach?
 A: From the hint provided by Bram28:
Theorem: Let $F \equiv G$. If $F^{D}$ and $G^{D}$ are obtained from $F$ respectively $G$ by substituting all occurrences of $\lor$ by $\land$ (and vice versa) then $F^{D} \equiv G^{D}$.
Proof: Let $\theta'$ denote the result of substituting each atomic formula in $\theta$ by its negation. Let $F \equiv G$. By Lemma 1, $F^{D} \equiv \lnot F'$ and $G^{D} \equiv \lnot G'$. By Lemma 2, $F' \equiv G'$. Then $\lnot F' \equiv \lnot G'$. Then $F^{D} \equiv \lnot F' \equiv \lnot G' \equiv G^{D}$. Hence $F^{D} \equiv G^{D}$.

Lemma 1: Let $\theta^{D}$ denote the result of substituting all occurrences of $\lor$ in $\theta$ by $\land$ and all occurrences of $\land$ in $\theta$ by $\lor$. Let $\theta'$ denote the result of substituting each atomic formula in $\theta$ by its negation. Then for every formula $F$, $F^{D} \equiv \lnot F'$.
Proof:
Induction Base: Let $A_{i}$ be an arbitrary atomic formula. Then $A_{i}^{D}$ is $A_{i}$ and $\lnot A_{i}'$ is $\lnot (\lnot A_{i})$. $\lnot (\lnot A_{i}) \equiv A_{i}$. Hence $A_{i}^{D} \equiv \lnot A_{i}'$.
Induction Hypothesis: For arbitrary, but fixed formulas $\phi$ and $\psi$, $\phi^{D} \equiv \lnot \phi'$ and $\psi^{D} \equiv \lnot \psi'$.
Prove: $(\lnot \phi)^{D} \equiv \lnot (\lnot \phi)'$.
Proof: From the induction hypothesis, $\phi^{D} \equiv \lnot \phi'$. Hence $\lnot (\phi^{D}) \equiv \lnot (\lnot \phi')$. $\lnot (\phi^{D})$ is $(\lnot \phi)^{D}$ and $\lnot (\lnot \phi')$ is $\lnot (\lnot \phi)'$. Hence $(\lnot \phi)^{D} \equiv \lnot (\lnot \phi)'$.
Prove: $(\phi \lor \psi)^{D} \equiv \lnot (\phi \lor \psi)'$.
Proof: $(\phi \lor \psi)^{D}$ is $(\phi^{D} \land \psi^{D})$. By the induction hypothesis and the substitution theorem, $(\phi^{D} \land \psi^{D}) \equiv (\lnot \phi' \land \lnot \psi')$. By deMorgan's law, $(\lnot \phi' \land \lnot \psi') \equiv \lnot (\phi' \lor \psi')$. $\lnot (\phi' \lor \psi')$ is $\lnot (\phi \lor \psi)'$. Hence $(\phi \lor \psi)^{D} \equiv \lnot (\phi \lor \psi)'$.
Prove: $(\phi \land \psi)^{D} \equiv \lnot (\phi \land \psi)'$.
Proof: $(\phi \land \psi)^{D}$ is $(\phi^{D} \lor \psi^{D})$. By the induction hypothesis and the substitution theorem, $(\phi^{D} \lor \psi^{D}) \equiv (\lnot \phi' \lor \lnot \psi')$. By deMorgan's law, $(\lnot \phi' \lor \lnot \psi') \equiv \lnot (\phi' \land \psi')$. $\lnot (\phi' \land \psi')$ is $\lnot (\phi \land \psi)'$. Hence $(\phi \land \psi)^{D} \equiv \lnot (\phi \land \psi)'$.

Lemma 2: Let $\theta'$ denote the result of substituting each atomic formula in $\theta$ by its negation. Then for every formula $F$ and every formula $G$, if $F \equiv G$ then $F' \equiv G'$.
Proof:
Let $F \equiv G$.
Let $\mathcal{A}'$ be any assignment that is suitable for both $F'$ and $G'$.
Let $\mathrm{D}$ be the union of the atomic formulas that occur in $F$ and $G$.
Let $\mathrm{D}'$ be the union of the atomic formulas that occur in $F'$ and $G'$.
Then $\mathrm{D} = \mathrm{D}'$.
Let $A_{i} \in \mathrm{D}$. Then $A_{i} \in \mathrm{D}'$. Then $\mathcal{A}'$ is defined for $A_{i}$.
Define the assignment $\mathcal{A}$ such that for each atomic formula $A_{i} \in \mathrm{D}$, $\mathcal{A}(A_{i}) = \mathcal{A}'(\lnot A_{i})$.
Then $\mathcal{A} : \mathrm{D} \to \{0, 1\}$. Then $\mathcal{A}$ is an assignment that is suitable for both $F$ and $G$. Then since $F \equiv G$, $\mathcal{A}(F) = \mathcal{A}(G)$.
Prove: $\mathcal{A}(F) = \mathcal{A}'(F')$ and $\mathcal{A}(G) = \mathcal{A}'(G')$.
Proof:
Induction Basis: Let $A_{i} \in \mathrm{D}$. Then $\mathcal{A}(A_{i}) = \mathcal{A}'(\lnot A_{i}) = \mathcal{A}'(A_{i}')$.
Induction Hypothesis: For arbitrary, but fixed formulas $\phi$ and $\psi$, $\mathcal{A}(\phi) = \mathcal{A}'(\phi')$ and $\mathcal{A}(\psi) = \mathcal{A}'(\psi')$.
Prove: $\mathcal{A}(\lnot \phi) = \mathcal{A}'((\lnot \phi)')$.
Proof:
If $\mathcal{A}(\lnot \phi) = 0$ then $\mathcal{A}(\phi) = 1$. Then by the induction hypothesis, $\mathcal{A}'(\phi') = 1$. Then $\mathcal{A}'(\lnot \phi') = 0$. Then since $\lnot \phi' = (\lnot \phi)'$, $\mathcal{A}'((\lnot \phi)') = \mathcal{A}'(\lnot \phi') = 0$. Hence $\mathcal{A}(\lnot \phi) = \mathcal{A}'((\lnot \phi)')$.
If $\mathcal{A}(\lnot \phi) = 1$ then $\mathcal{A}(\phi) = 0$. Then by the induction hypothesis, $\mathcal{A}'(\phi') = 0$. Then $\mathcal{A}'(\lnot \phi') = 1$. Then since $\lnot \phi' = (\lnot \phi)'$, $\mathcal{A}'((\lnot \phi)') = \mathcal{A}'(\lnot \phi') = 1$. Hence $\mathcal{A}(\lnot \phi) = \mathcal{A}'((\lnot \phi)')$.
Prove: $\mathcal{A}((\phi \lor \psi)) = \mathcal{A}'((\phi \lor \psi)')$.
Proof:
If $\mathcal{A}(\phi) = 0$ and $\mathcal{A}(\psi) = 0$ then $\mathcal{A}((\phi \lor \psi)) = 0$. Since $\mathcal{A}(\phi) = 0$, then by the induction hypothesis, $\mathcal{A}'(\phi') = 0$. Since $\mathcal{A}(\psi) = 0$, then by the induction hypothesis, $\mathcal{A}'(\psi') = 0$. Since $\mathcal{A}'(\phi') = 0$ and $\mathcal{A}'(\psi') = 0$, then $\mathcal{A}'((\phi' \lor \psi')) = 0$. Since $(\phi' \lor \psi') = (\phi \lor \psi)'$, then $\mathcal{A}'((\phi \lor \psi)') = \mathcal{A}'((\phi' \lor \psi')) = 0$. Then $\mathcal{A}((\phi \lor \psi)) = \mathcal{A}'((\phi \lor \psi)')$.
If $\mathcal{A}(\phi) = 1$ and $\mathcal{A}(\psi) = 0$ then $\mathcal{A}((\phi \lor \psi)) = 1$. Since $\mathcal{A}(\phi) = 1$, then by the induction hypothesis, $\mathcal{A}'(\phi') = 1$. Since $\mathcal{A}(\psi) = 0$, then by the induction hypothesis, $\mathcal{A}'(\psi') = 0$. Since $\mathcal{A}'(\phi') = 1$ and $\mathcal{A}'(\psi') = 0$, then $\mathcal{A}'((\phi' \lor \psi')) = 1$. Since $(\phi' \lor \psi') = (\phi \lor \psi)'$, then $\mathcal{A}'((\phi \lor \psi)') = \mathcal{A}'((\phi' \lor \psi')) = 1$. Then $\mathcal{A}((\phi \lor \psi)) = \mathcal{A}'((\phi \lor \psi)')$.
If $\mathcal{A}(\phi) = 0$ and $\mathcal{A}(\psi) = 1$ then $\mathcal{A}((\phi \lor \psi)) = 1$. Since $\mathcal{A}(\phi) = 0$, then by the induction hypothesis, $\mathcal{A}'(\phi') = 0$. Since $\mathcal{A}(\psi) = 1$, then by the induction hypothesis, $\mathcal{A}'(\psi') = 1$. Since $\mathcal{A}'(\phi') = 0$ and $\mathcal{A}'(\psi') = 1$, then $\mathcal{A}'((\phi' \lor \psi')) = 1$. Since $(\phi' \lor \psi') = (\phi \lor \psi)'$, then $\mathcal{A}'((\phi \lor \psi)') = \mathcal{A}'((\phi' \lor \psi')) = 1$. Then $\mathcal{A}((\phi \lor \psi)) = \mathcal{A}'((\phi \lor \psi)')$.
If $\mathcal{A}(\phi) = 1$ and $\mathcal{A}(\psi) = 1$ then $\mathcal{A}((\phi \lor \psi)) = 1$. Since $\mathcal{A}(\phi) = 1$, then by the induction hypothesis, $\mathcal{A}'(\phi') = 1$. Since $\mathcal{A}(\psi) = 1$, then by the induction hypothesis, $\mathcal{A}'(\psi') = 1$. Since $\mathcal{A}'(\phi') = 1$ and $\mathcal{A}'(\psi') = 1$, then $\mathcal{A}'((\phi' \lor \psi')) = 1$. Since $(\phi' \lor \psi') = (\phi \lor \psi)'$, then $\mathcal{A}'((\phi \lor \psi)') = \mathcal{A}'((\phi' \lor \psi')) = 1$. Then $\mathcal{A}((\phi \lor \psi)) = \mathcal{A}'((\phi \lor \psi)')$.
Prove: $\mathcal{A}((\phi \land \psi)) = \mathcal{A}'((\phi \land \psi)')$.
Proof:
If $\mathcal{A}(\phi) = 0$ and $\mathcal{A}(\psi) = 0$ then $\mathcal{A}((\phi \land \psi)) = 0$. Since $\mathcal{A}(\phi) = 0$, then by the induction hypothesis, $\mathcal{A}'(\phi') = 0$. Since $\mathcal{A}(\psi) = 0$, then by the induction hypothesis, $\mathcal{A}'(\psi') = 0$. Since $\mathcal{A}'(\phi') = 0$ and $\mathcal{A}'(\psi') = 0$, then $\mathcal{A}'((\phi' \land \psi')) = 0$. Since $(\phi' \land \psi') = (\phi \land \psi)'$, then $\mathcal{A}'((\phi \land \psi)') = \mathcal{A}'((\phi' \land \psi')) = 0$. Then $\mathcal{A}((\phi \land \psi)) = \mathcal{A}'((\phi \land \psi)')$.
If $\mathcal{A}(\phi) = 1$ and $\mathcal{A}(\psi) = 0$ then $\mathcal{A}((\phi \land \psi)) = 0$. Since $\mathcal{A}(\phi) = 1$, then by the induction hypothesis, $\mathcal{A}'(\phi') = 1$. Since $\mathcal{A}(\psi) = 0$, then by the induction hypothesis, $\mathcal{A}'(\psi') = 0$. Since $\mathcal{A}'(\phi') = 1$ and $\mathcal{A}'(\psi') = 0$, then $\mathcal{A}'((\phi' \land \psi')) = 0$. Since $(\phi' \land \psi') = (\phi \land \psi)'$, then $\mathcal{A}'((\phi \land \psi)') = \mathcal{A}'((\phi' \land \psi')) = 0$. Then $\mathcal{A}((\phi \land \psi)) = \mathcal{A}'((\phi \land \psi)')$.
If $\mathcal{A}(\phi) = 0$ and $\mathcal{A}(\psi) = 1$ then $\mathcal{A}((\phi \land \psi)) = 0$. Since $\mathcal{A}(\phi) = 0$, then by the induction hypothesis, $\mathcal{A}'(\phi') = 0$. Since $\mathcal{A}(\psi) = 1$, then by the induction hypothesis, $\mathcal{A}'(\psi') = 1$. Since $\mathcal{A}'(\phi') = 0$ and $\mathcal{A}'(\psi') = 1$, then $\mathcal{A}'((\phi' \land \psi')) = 0$. Since $(\phi' \land \psi') = (\phi \land \psi)'$, then $\mathcal{A}'((\phi \land \psi)') = \mathcal{A}'((\phi' \land \psi')) = 0$. Then $\mathcal{A}((\phi \land \psi)) = \mathcal{A}'((\phi \land \psi)')$.
If $\mathcal{A}(\phi) = 1$ and $\mathcal{A}(\psi) = 1$ then $\mathcal{A}((\phi \land \psi)) = 1$. Since $\mathcal{A}(\phi) = 1$, then by the induction hypothesis, $\mathcal{A}'(\phi') = 1$. Since $\mathcal{A}(\psi) = 1$, then by the induction hypothesis, $\mathcal{A}'(\psi') = 1$. Since $\mathcal{A}'(\phi') = 1$ and $\mathcal{A}'(\psi') = 1$, then $\mathcal{A}'((\phi' \land \psi')) = 1$. Since $(\phi' \land \psi') = (\phi \land \psi)'$, then $\mathcal{A}'((\phi \land \psi)') = \mathcal{A}'((\phi' \land \psi')) = 1$. Then $\mathcal{A}((\phi \land \psi)) = \mathcal{A}'((\phi \land \psi)')$.
Then $\mathcal{A}'(F') = \mathcal{A}(F) = \mathcal{A}(G) = \mathcal{A}'(G')$. Hence $\mathcal{A}'(F') = \mathcal{A}'(G')$.
Hence for every assignment $\mathcal{A}'$ that is suitable for both $F'$ and $G'$, $\mathcal{A}'(F') = \mathcal{A}'(G')$. Hence $F' \equiv G'$.
In summary, for every assignment $\mathcal{A}'$ that is suitable for both $F'$ and $G'$, there is an assignment $\mathcal{A}$ that is suitable for both $F$ and $G$ and such that $\mathcal{A}(F) = \mathcal{A}'(F')$ and $\mathcal{A}(G) = \mathcal{A}'(G')$. Since $F$ and $G$ are equivalent, $\mathcal{A}(F) = \mathcal{A}(G)$. Then $\mathcal{A}'(F') = \mathcal{A}(F) = \mathcal{A}(G) = \mathcal{A}'(G')$.
A: Something to check (I should comment but I currently can't :| ):


*

*$F\equiv G$ means $F$ is semantically equivalent to $G$, i.e. $F\vDash G$ and $G\vDash F$, i.e. for all valuation $v$, $v(F)=v(G)$, right?

*The only logical connectives occurring in $F$ and $G$ are $\neg,\vee,\wedge$, right (otherwise let $F=p\to q,G=\neg p \vee q$, we have $F\equiv G$ but $F'\not\equiv G'$)?
Your approach of using structural induction on the main connectives of $F$ and $G$ is right, but seems haven't cover all cases.
