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).