(a) This sentence is not valid. Let $\mathfrak{A}=(\{0,1\};Q)$ where $Q^{\mathfrak{A}}=\{<1>\}$ . Then, for any $s:V\rightarrow|\mathfrak{A}|$ , $\not\vDash_{\mathfrak{A}}Qx[s(x|0)]$ and $\vDash_{\mathfrak{A}}Qx[s(x|1)]$ , therefore, $\not\vDash_{\mathfrak{A}}\forall yQy[s]$ , $\not\vDash_{\mathfrak{A}}Qx\rightarrow\forall yQy[s(x|1)]$ , and $\not\vDash_{\mathfrak{A}}\forall x(Qx\rightarrow\forall yQy)[s]$ .

(b) This sentence is valid. We need to show that $\vdash(\exists xPx\rightarrow\forall yQy)\rightarrow\forall z(Pz\rightarrow Qz)$ . By the deduction and generalization theorems, it is sufficient to show that $\exists xPx\rightarrow\forall yQy;Pz\vdash Qz$ . By axiom group 2, MP and contraposition, it is sufficient to show that $Pz;\neg\forall yQy\vdash\neg(\exists xPx\rightarrow\forall yQy)$ . By MP and contraposition rules, using the axiom of group 2 $\vdash\forall x\neg Px\rightarrow\neg Pz$ , we have $Pz\vdash\exists xPx$ . And, using the axiom of group 1 $\vdash\exists xPx\rightarrow\neg\forall yQy\rightarrow\neg(\exists xPx\rightarrow\forall yQy)$ and MP, we have $Pz;\neg\forall yQy\vdash\neg(\exists xPx\rightarrow\forall yQy)$ .

(c) This sentence is not valid. The example of a structure in which it is false is the same as in (a) where $P^{\mathfrak{A}}=Q^{\mathfrak{A}}$ . For any $s:V\rightarrow|\mathfrak{A}|$ , $\vDash_{\mathfrak{A}}Pz\rightarrow Qz[s]$ , $\vDash_{\mathfrak{A}}\neg Px[s(x|0)]$ , $\not\vDash_{\mathfrak{A}}\neg Px[s(x|1)]$ , $\not\vDash_{\mathfrak{A}}Qx[s(x|0)]$ and $\vDash_{\mathfrak{A}}Qx[s(x|1)]$ , therefore, $\vDash_{\mathfrak{A}}\forall z(Pz\rightarrow Qz)[s]$ , $\not\vDash_{\mathfrak{A}}\forall x\neg Px[s]$ , $\vDash_{\mathfrak{A}}\exists xPx[s]$ , $\not\vDash_{\mathfrak{A}}\forall yQy[s]$ , $\not\vDash_{\mathfrak{A}}\exists xPx\rightarrow\forall yQy[s]$ , and $\not\vDash_{\mathfrak{A}}\forall z(Pz\rightarrow Qz)\rightarrow(\exists xPx\rightarrow\forall yQy)[s]$ .

(d) This sentence is valid. We need to show that $\vdash\neg\exists y\forall x(Pxy↔\neg Pxx)$ , or, equivalently, $\vdash\forall y\neg\forall x\neg((Pxy\rightarrow\neg Pxx)\rightarrow\neg(\neg Pxx\rightarrow Pxy))$ (here we use the following definition of $\leftrightarrow$ : $\alpha\leftrightarrow\beta$ means $\neg((\alpha\rightarrow\beta)\rightarrow\neg(\beta\rightarrow\alpha))$ ). By the generalization theorem, it is sufficient to show that $\vdash\neg\forall x\neg((Pxy\rightarrow\neg Pxx)\rightarrow\neg(\neg Pxx\rightarrow Pxy))$ which we denote as $\vdash\neg\forall x\neg\gamma$ . For this, it is sufficient to show that $\vdash\gamma_{t}^{x}$ where $t$ is a term substitutable for $x$ in $\gamma$ . Indeed, by axiom group 2, $\vdash\forall x\neg\gamma\rightarrow\neg\gamma_{t}^{x}$ , and, using MP and contraposition, we have $\gamma_{t}^{x}\vdash\neg\forall x\neg\gamma$ . Now, $y$ is substitutable for $x$ in $\gamma$ , and $\gamma_{y}^{x}$ is simply $(Pyy\rightarrow\neg Pyy)\rightarrow\neg(\neg Pyy\rightarrow Pyy)$ , a tautology.