====== Zadanie 52. ======

==== Pierwsza formuła ====

$\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.

  - $n = 2$. $\phi_2 = p_1 \Rightarrow p_2$. Formuła jest fałszywa dla $\frac{2^2-(-1)^2}{3} = 1$ wartościowania.
  - $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}.$

==== Druga formuła ====

$\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$.