Jak rozstrzygać tautologie rachunku zdań?
11 paz
dziernika 2008
Poza wykorzystaniem jakiegoś systemu dowodzenia twierdzeń (co będzie omówione bardziej szczegółowo na
wykładzie) dysponujemy trzema głównymi sposobami metodami dowodzenia, że jakaś formuła jest tautologią.
Metoda tabelkowa
Metoda tabelkowa jest najmniej efektywna - wymaga sprawdzenia 2n przypadków. W niektórych sytuacjach można
zakończyć wyliczanie zadania metodą tabelkową wcześniej - jeżeli w trakcie obliczania natkniemy się na dwa wiersze,
z których jeden ma wartość 0, a drugi 1 - wówczas wiemy już, że formuła nie jest ani tautologią, ani kontrtau-
tologią. W ogólności jednak nie możemy liczyć na tego typu ułatwienie - zgadnięcie, które dwa wiersze posiadają
taką własność może być trudne, poza tym nie pomoże nam to szybciej rozstrzygać formuł, które są tautologiami bądz

kontrtautologiami.
Metoda tabelkowa polega na wypisaniu wszystkich kombinacji wartości logicznych dla zmiennych zdaniowych
występujących w formule, a następnie wyliczaniu wartości logicznych coraz to większych składowych, aż do osiągnięcia
formuły końcowej. Przykładowe wyliczenie dla formuły (p q r) (p q) (p r) (oznaczanej skrótowo
jako Ć, oznaczymy także (p q) (p r) jako È):
p q r q r p q r p q p r È Ć
0 0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1
0 1 0 0 1 1 1 1 1
0 1 1 1 1 1 1 1 1
1 0 0 1 1 0 0 1 1
1 0 1 1 1 0 1 1 1
1 1 0 0 0 1 0 0 1
1 1 1 1 1 1 1 1 1
Skrócona metoda tabelkowa
Skrócona metoda tabelkowa bazuje na pewnej własności wszystkich spójników logicznych poza negacją: są one
niesymetryczne; jedna z wartości występuje trzykrotnie, druga - tylko jednokrotnie. Oznacza to, że często wyliczenie
wartości jednej z formuł wystarcza już do wyliczenia wartości całej formuły - wyliczanie drugiego członu jest wówczas
zbędne. Wez
my np. formułę:
p (p (" È)
gdzie È jest jakÄ…Å› bardzo dÅ‚ugÄ… formuÅ‚Ä…. Wiemy jednak, że implikacja jest prawdziwa w jednym z dwóch wypadków:
albo poprzednik i następnik są prawdziwe, albo poprzednik jest fałszywy - wtedy niezależnie od wartości następnika
całość jest prawdziwa. Z kolei alternatywa jest prawdziwa, jeśli jeden z członów jest prawdziwy - niezależnie od
wartości logicznej drugiego członu. Wiedząc to, możemy bardzo szybko rozwiązać ten przykład (niezależnie od tego,
czy È = q, czy È = (p (q '" Źr)) (" ((s (Źq Źq)) '" (Źt Źu))). Zauważamy mianowicie, że jeÅ›li p jest faÅ‚szywe,
to cała implikacja jest prawdziwa bez sprawdzania prawej strony, jeśli zaś p jest prawdziwe, to prawa alternatywa
jest również prawdziwa bez sprawdzania wartoÅ›ci logicznej formuÅ‚y È.
1
Oczywiście istnieją formuły, dla których tak czy owak będziemy zmuszeni sprawdzić wszystkie wartości logiczne,
aby przekonać się, że formuła ta jest tautologią, przykładem takiej formuły jest chociażby:
Ź((p (" q (" r) '" (p (" q (" Źr) '" (p (" Źq (" r) '" (p (" Źq (" Źr)'"
(Źp (" q (" r) '" (Źp (" Źq (" r) '" (Źp (" q (" Źr) '" (Źp (" Źq (" Źr))
Dlaczego ta metoda nazywa się skróconą metodą tabelkową? Przytoczone powyżej przykłady obrazują pewnego
rodzaju skrajności - w ogólności będziemy mogli pewne fragmenty formuły rozstrzygnąć w sposób  skrócony , część
zaś musimy rozpisać w tabelce. Ogólnym schematem takiej formuły będzie np.
((p q) (" (q Ć)) '" È
Metodą skróconą możemy rozstrzygnąć, że lewa strona koniunkcji jest tautologią niezależnie od wartości zmiennych
wystÄ™pujÄ…cych w Ć, nadal jednak być może bÄ™dziemy musieli policzyć metodÄ… tabelkowÄ… formuÅ‚Ä™ È.
Wykorzystywanie znanych tautologii
Jeżeli znamy już pewne tautologie, możemy próbować przekształcić rozważaną formułę do postaci znanej tautologii
wykorzystując równoważności. I tak np. możemy rozstrzygnąć formułę Ź(Źp (" Źq) (p '" q), przekształcając lewą
stronę za pomocą prawa de Morgana do postaci (p'"q), otrzymując (p'"q) (p'"q). Tutaj (a także przy przekształcaniu
za pomocą równoważności) wykorzystujemy także inną regułę: każde podstawienie tautologii jest tautologią. Innymi
słowy, jeśli tautologią jest np. p p, to dowolne podstawienie Ć za p także daje tautologię - w powyższym przypadku
musieliśmy podstawic (p '" q) za p do tautologii p p, aby otrzymać nasz przykład.
2