Jak rozstrzygać tautologie rachunku zdań?

11 paź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 2

n

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ądź
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. Weź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