Substituting conjunction and disjunction symbols in equivalent propositional formulas

Question

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?

Answer 1

Something to check (I should comment but I currently can't :| ):

1. $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?

2. 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.

Answer 2

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')$.