Tautologie dowodzimy metodą zero-jedynkową. Polega ona na odpowiednim wypełnianiu tabelki zerami i jedynkami. W pierwszych kolumnach wypisujemy wszystkie możliwe wartości logiczne zdań prostych. W kolejnych kolumnach wyznaczamy wartości coraz bardziej złożonych zdań, tworzących naszą tautologię.
Rozważmy następujące zdanie: \[p \Rightarrow \Bigl( (\sim p) \lor q \Bigr)\]
Metodą zero-jedynkową sprawdzimy, czy jest to tautologia. Zaczynamy od przygotowania tabelki:
| \(p\) | \(q\) | \(\sim p\) | \((\sim p)\lor q\) | \(p \Rightarrow \Bigl( (\sim p) \lor q \Bigr)\) |
| \(1\) | \(1\) | | | |
| \(1\) | \(0\) | | | |
| \(0\) | \(1\) | | | |
| \(0\) | \(0\) | | | |
Wypełniamy pierwszą wolną kolumnę (wyznaczamy wartości logiczne dla zdania \(\sim p\)) korzystając z wartości logicznych z pierwszej kolumny (dla zdania \(p\)):
| \(p\) | \(q\) | \(\sim p\) | \((\sim p)\lor q\) | \(p \Rightarrow \Bigl( (\sim p) \lor q \Bigr)\) |
| \(1\) | \(1\) | \(0\) | | |
| \(1\) | \(0\) | \(0\) | | |
| \(0\) | \(1\) | \(1\) | | |
| \(0\) | \(0\) | \(1\) | | |
Teraz wypełniamy kolejną kolumnę (wyznaczamy wartości logiczne dla zdania
\((\sim p)\lor q\)). W tym celu wykorzystamy wartości logiczne z drugiej i trzeciej kolumny:
| \(p\) | \(q\) | \(\sim p\) | \((\sim p)\lor q\) | \(p \Rightarrow \Bigl( (\sim p) \lor q \Bigr)\) |
| \(1\) | \(1\) | \(0\) | \(1\) | |
| \(1\) | \(0\) | \(0\) | \(0\) | |
| \(0\) | \(1\) | \(1\) | \(1\) | |
| \(0\) | \(0\) | \(1\) | \(1\) | |
Teraz wypełniamy ostatnią kolumnę (wyznaczamy wartości logiczne dla zdania
\(p \Rightarrow \Bigl( (\sim p) \lor q \Bigr)\)). W tym celu wykorzystamy wartości logiczne z pierwszej i czwartej kolumny:
| \(p\) | \(q\) | \(\sim p\) | \((\sim p)\lor q\) | \(p \Rightarrow \Bigl( (\sim p) \lor q \Bigr)\) |
| \(1\) | \(1\) | \(0\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(1\) | \(1\) | \(1\) |
| \(0\) | \(0\) | \(1\) | \(1\) | \(1\) |
Z drugiego wiersza naszej tabelki odczytujemy, że zdanie
\(p \Rightarrow \Bigl( (\sim p) \lor q \Bigr)\) jest fałszywe (przyjmuje wartość logiczną \(0\)) dla \(p=1\) i \(q=0\).
Zatem zdanie
\(p \Rightarrow \Bigl( (\sim p) \lor q \Bigr)\) nie jest tautologią.
W kolejnych rozdziałach udowodnimy metodą zero-jedynkową kilka najważniejszych tautologii.
Aby jakieś wyrażenie okazało się tautolgią, to w ostatniej kolumnie naszej tabelki muszą stać same jedynki (tzn. w każdym przypadku badane zdanie musi okazać się prawdziwe).
Od tej pory będę pokazywał od razu wypełnione wszystkie kolumny danej tabelki (pamiętajmy jednak, że tabelkę wypełniamy kolumna po kolumnie).