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.