Note, that $\gamma\vee\delta$ is tautologically equivalent to $\neg\gamma\rightarrow\delta$ , and $\gamma\wedge\delta$ is tautologically equivalent to $\neg(\gamma\rightarrow\neg\delta)$ . By tautologically equivalent we do not imply that one uses these first-order tautologies in the proves of the above equations (for example, you cannot use tautologies to substitute subformulas of quantified formulas), but rather that these connectives are defined this way.

(a) We need to show that $\vdash(\neg\exists x\alpha\rightarrow\exists x\beta)\rightarrow\exists x(\neg\alpha\rightarrow\beta)$ and $\vdash\exists x(\neg\alpha\rightarrow\beta)\rightarrow\neg\exists x\alpha\rightarrow\exists x\beta$ . By deduction and contraposition theorems, it is sufficient to show that $\forall x\neg(\neg\alpha\rightarrow\beta)\vdash\neg(\forall x\neg\alpha\rightarrow\neg\forall x\neg\beta)$ and $\neg(\forall x\neg\alpha\rightarrow\neg\forall x\neg\beta)\vdash\forall x\neg(\neg\alpha\rightarrow\beta)$ .

For the first one it is sufficient to show that $\forall x\neg(\neg\alpha\rightarrow\beta)\vdash\forall x\neg\alpha$ and $\forall x\neg(\neg\alpha\rightarrow\beta)\vdash\forall x\neg\beta$ (using Rule T for $\gamma,\delta\vDash\neg(\gamma\rightarrow\neg\delta)$ ). By MP, it is sufficient to show that $\vdash\forall x\neg(\neg\alpha\rightarrow\beta)\rightarrow\forall x\neg\alpha$ and $\vdash\forall x\neg(\neg\alpha\rightarrow\beta)\rightarrow\forall x\neg\beta$ , and, by axiom group 3, MP and generalization theorem, it is sufficient to show that $\vdash\neg(\neg\alpha\rightarrow\beta)\rightarrow\neg\alpha$ and $\vdash\neg(\neg\alpha\rightarrow\beta)\rightarrow\neg\beta$ . Both are tautologies.

For the second one, by the generalization and contraposition theorems, it is sufficient to show that $\neg\alpha\rightarrow\beta\vdash\forall x\neg\alpha\rightarrow\neg\forall x\neg\beta$ . By the deduction theorem, it is sufficient to show that $\forall x\neg\alpha;\neg\alpha\rightarrow\beta\vdash\neg\forall x\neg\beta$ . By RAA, it is sufficient to conclude that $\{\forall x\neg\alpha,\neg\alpha\rightarrow\beta,\forall x\neg\beta\}$ is inconsistent. Now, by axiom group 2, $\vdash\forall x\neg\alpha\rightarrow\neg\alpha$ and $\vdash\forall x\neg\beta\rightarrow\neg\beta$ , and, by MP, $\{\forall x\neg\alpha,\neg\alpha\rightarrow\beta,\forall x\neg\beta\}\vdash\{\beta,\neg\beta\}$ .

(b) We need to show that $\vdash(\neg\forall x\alpha\rightarrow\forall x\beta)\rightarrow\forall x(\neg\alpha\rightarrow\beta)$ . By deduction, generalization and contraposition theorems, it is sufficient to show that $\neg(\neg\alpha\rightarrow\beta)\vdash\neg(\neg\forall x\alpha\rightarrow\forall x\beta)$ . For this, it is sufficient to show that $\neg(\neg\alpha\rightarrow\beta)\vdash\neg\forall x\alpha$ and $\neg(\neg\alpha\rightarrow\beta)\vdash\neg\forall x\beta$ (using Rule T for $\gamma,\neg\delta\vDash\neg(\gamma\rightarrow\delta)$ ), or that both $\{\neg(\neg\alpha\rightarrow\beta),\forall x\alpha\}$ and $\{\neg(\neg\alpha\rightarrow\beta),\forall x\beta\}$ are inconsistent. By axiom group 2, $\vdash\forall x\alpha\rightarrow\alpha$ and $\vdash\forall x\beta\rightarrow\beta$ , and $\neg(\neg\alpha\rightarrow\beta)\rightarrow\neg\alpha$ and $\neg(\neg\alpha\rightarrow\beta)\rightarrow\neg\beta$ are tautologies, so that, by Rule T, $\{\neg(\neg\alpha\rightarrow\beta),\forall x\alpha\}\vdash\{\alpha,\neg\alpha\}$ and $\{\neg(\neg\alpha\rightarrow\beta),\forall x\beta\}\vdash\{\beta,\neg\beta\}$ .