Jesteś tu: Działy tematyczneLogikaPrawa rachunku zdańMetoda zero-jedynkowa dowodzenia tautologii

Metoda zero-jedynkowa dowodzenia tautologii

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