====== Logika - Zadanie 68. ======

Taką formułą jest 
$ f(n) = (p \vee x_1) \wedge (p \vee x_2) \wedge ... (p \vee x_{n+1})$

Dowodzimy indukcyjnie, że zmienna p musi być użyta dokładnie n+1 razy. Przypadek bazowy wynika z wcześniejszego zadania, a krok:

Wiemy z założenia, że aby wyrazić formułę f(n) , potrzebujemy co najmniej n+1 wystąpień zmiennej p. Skoro f(n+1) = f(n) $\wedge (p \vee x_{n+1})$,  to formuła dla n+1 musi wyrażać to, co formuła dla n, oraz dodatkowo jeszcze tę ostatnią alternatywę. Wobec tego zmienna p musi być użyta jeszcze jeden raz, co daje w sumie n+2 użycia.