Zadanie 52.

\phi_n = (\dots((p_1 \Rightarrow p_2) \Rightarrow p_3) \Rightarrow \dots \Rightarrow p_{n-1}) \Rightarrow p_n

Dowód indukcyjny po n.

1. n = 2. \phi_2 = p_1 \Rightarrow p_2. Formuła jest fałszywa dla \frac{2^2-(-1)^2}{3} = 1 wartościowania.
2. n > 2.
   \phi_n = \phi_{n-1} \Rightarrow p_n.
   \phi_{n-1} jest fałszywa dla \frac{2^{n-1}-(-1)^{n-1}}{3}.
   Implikacja jest fałszywa, gdy \phi_{n-1} jest prawdziwe, a p_n fałszywe.
   Różnych wartościowań \phi_n jest 2^n, więc \phi_n jest fałszywa dla 2^{n-1}-\frac{2^{n-1}-(-1)^{n-1}}{3} = \frac{2*2^{n-1}+(-1)^{n-1}}{3} = \frac{2^n-(-1)^n}{3}.

\psi_n = p_n \Rightarrow (p_{n-1} \Rightarrow (p_{n-2} \Rightarrow \dots \Rightarrow (p_2 \Rightarrow p_1)\dots) = p_n \Rightarrow \psi_{n-1}.

\psi_2 jest fałszywa dla jednego wartościowania. Można łatwo zauważyć, że żeby dla większych n \psi_n było fałszywe, to p_k dla k>1 musi mieć wartościowanie \top. Czyli jest tylko jedno wartościowanie niespełniające \psi_n.