====== Logika - Zadanie 76. ======

Najpierw dowód 1-zupełności zbioru $\{\bot, \Leftrightarrow\}$

Mamy 4 funkcje boolowskie jedno argumentowe i wszystkie możemy przedstawić za pomocą tych spójników:

$p$ opisuje funkcję $f(p) = p$ \\
$p \Leftrightarrow \bot$ opisuje funkcję $f(p) = \neg p$ \\
$\bot \Leftrightarrow \bot$ opisuje funkcję $f(p) = T$ \\
$\bot$ opisuje funkcję $f(p) = F$ \\

\\ \\


Dalej trzeba przedstawić, że nie jest to zbiór zupełny, co robimy poprzez wykazanie, że nie da się uzyskać alternatywy.

Na początek weźmy dwie dowolne zmienne $p,q$ i ułóżmy z nich wszystkie możliwe formuły do głębokości 2 i przedstawmy ich tabelkę:

^  p  ^  q  ^  $\bot$  ^  $p <=> q$  ^  $p <=> \bot$  ^  $q <=>  \bot$  ^  $\bot <=> \bot$  ^  $p <=> ~q$  ^
|  1  |  1  |  0  |    1    |    0    |    0    |    1    |    0    |
|  1  |  0  |  0  |    0    |    0    |    1    |    1    |    1    |
|  0  |  1  |  0  |    0    |    1    |    0    |    1    |    1    |
|  0  |  0  |  0  |    1    |    1    |    1    |    1    |    0    |



Łatwo zauważyć, że w każdej kolumnie jest parzysta ilość zer i jedynek.

Będziemy chcieli udowodnić, że każda formuła o głębokości $\geq 1$ będzie miała też tabelkę o parzystej ilość zer i jedynek. Czyli nie będzie dało się w ten sposób uzyskać alternatywy, która ma 3 razy $\top$ i 1 raz $\bot$. Oczywiście rozważamy tylko formuły złożone ze zmiennych $p,q$ oraz zbioru spójników $\{\bot, \Leftrightarrow\}$

Bazę indukcji (dla $n = 1$) już mamy powyżej.

Załóżmy więc, że teza zachodzi dla wszystkich formuł o głębokości od $1$ do $n$. Pokażmy, że zachodzi również dla formuł o głębokości $n+1$

Formuła o głębokości n+1 ma postać:

$\psi \Leftrightarrow \phi$ \\
gdzie $\psi$ oraz $\phi$ są formułami o głębokości mniejszej od $n+1$, czli z założenia indukcyjnego mają parzystą ilość zer i jedynek w swoich tabelkach.

Równoważność dwóch formuł z których każda ma w tabelce parzystą ilość zer i jedynek też ma w tabelce parzystą ich ilość.

Fakt ten łatwo uzasadnić wiedząc, że w tabelce dla równoważności występują 1 wtedy gdy obie formuły mają wartość (0 lub 1) i 0 w p.p (czyli 1 jedynka, 1 zero).

Więc jeśli mamy 1 wiersz

Kod:

^ $\phi$  ^  $\psi$  ^  $\phi <=> \psi$  ^
|  1  |  0  |  0  | 
gdzie $\psi$ oraz $\phi$ są formułami o głębokości mniejszej od $n+1$, czli z założenia indukcyjnego mają parzystą ilość zer i jedynek w swoich tabelkach.

to musi gdzieś wystąpić odpowiadający mu

^ $\phi$  ^  $\psi$  ^  $\phi <=> \psi$  ^
|  0  |  1  |  0  | 


W przeciwnym wypadku mielibyśmy w tabelce dla $\phi$, $\psi$ nieparzystą ilośc zer i jedynek co jest sprzeczne z założeniem.

Tak więc formuła o głębokości $n+1$ też ma parzystą ilość zer i jedynek.

Wniosek z właśnie udowodnionej tezy jest taki, że nie da się uzyskać alternatywy.