6. Tautologie rachunku zdań

Zadaniem logiki jest — jak już wiemy — dostarczenie narzędzi pozwala-

jących rozpoznawać związki wynikania logicznego między zdaniami w sposób
nie budzący wątpliwości. Ma temu służyć klasyczny rachunek logiczny. Zda-
rza się, że związki takie zachodzą w sposób niezależny od struktury wewnętrz-
nej pewnych zdań, lecz zależą tylko od tego, jak zdania te są powiązane spójni-
kami prawdziwościowymi. Fakt ten pozwala wyodrębnić z klasycznego rachun-
ku logicznego, jako jego fragment, rachunek zdań. Bada się w nim schematy
zbudowane wyłącznie ze spójników i zmiennych zdaniowych. Schematy te no-
szą nazwę formuł rachunku zdań. Ponieważ przyjmuje się tu zasadę nieogra-
niczonej konstrukcji pozwalającej z dowolnych formuł tworzyć nowe przez łą-
czenie ich spójnikami, zatem dla zachowania jednoznaczności struktury skła-
dniowej konieczne jest posł

Jak

już wiemy z rozdziału drugiego, charakteryzując pojęcie wynikania

logicznego można skorzystać z pojęcia tautologii logicznej. Zatem następnym
krokiem przy konstrukcji rachunku zdań powinno być wyróżnienie spośród ogó-
łu formuł zdaniowych, tych, które są tautologiami logicznymi. Z ogólnej, acz
nieścisłej, charakterystyki tautologii logicznych zawartej w rozdziale drugim
wiemy, że są to schematy, z których przez podstawianie odpowiednich wyrażeń
za zmienne uzyskuje się wyłącznie zdania prawdziwe. Za zmienne zdaniowe
można oczywiście podstawiać kolejno dowolne zdania, ale nie jest to droga do
ustalenia czy dana formuła jest tautologią. Korzystając z założenia, że mamy tu
do czynienia wyłącznie ze spójnikami prawdziwościowymi, możemy zamiast
zdań podstawiać symbole wartości logicznych. Powinniśmy jednakże uwzględ-
nić wszystkie możliwe ich kombinacje i ustalać kolejno, jaką wartość logiczną
przy danej kombinacji przybiera cała formuła zdaniowa. Jeśli okaże się, że bę-
dzie nią zawsze prawda, to formułę uznamy za tautologię. Jest to droga, która
bywa dość uciążliwa, ponieważ liczba kombinacji, które powinniśmy brać pod
uwagę rośnie wraz z liczbą zmiennych według wzoru 2

n

.

Dlatego w praktyce

opłaca się nią posłużyć tylko wtedy, gdy liczba zmiennych jest niewielka.

Stosując opisaną powyżej metodę, zwaną powszechnie „zerojedynkową”,

sprawdźmy, czy jest tautologią prosta formuła zdaniowa

¬(p ∧ ¬p).

Ponieważ występuje w niej tylko jedna zmienna, wystarczy rozważyć

dwa przypadki: podstawiając za p najpierw jedynkę, a następnie zero. Oszczę-
dzając miejsca na zapis całej procedury sprawdzania można jej rezultat przed-
stawić następująco:

¬(p ∧ ¬p)

1 1 0 0 1
1 0 0 1 0

Z

astosowano tu zasadę, iż wartość logiczną formuły złożonej należy za-

pisywać pod tworzącym ją spójnikiem głównym, przechodząc kolejno od formuł
najprostszych do bardziej złożonych. Wynik sprawdzenia wskazuje cyfra zapi-
sana pod spójnikiem głównym całej formuły. Dla zaznaczenia, że kolejny etap
sprawdzania został zakończony, warto ją wyróżnić podkreśleniem. W naszym
przykładzie (nietypowo) spójnikiem głównym jest znak negacji występujący na
początku formuły. Podpisane pod nim dwie podkreślone jedynki wskazują, że
sprawdzana formuła okazała się tautologią.
W

formule

(p

⇒ q) ⇒ (¬q ⇒ ¬p)

występują dwie zmienne zdaniowe, zatem proces jej sprawdzenia musi
uwzględniać cztery kombinacje wartości logicznych. Spójnikiem głównym jest
tu znak implikacji, który łączy dwie inne implikacje, mianowicie (p

⇒ q) i (¬q

⇒ ¬p). Proces sprawdzania przebiega tu następująco:

2

(p

⇒ q) ⇒ (¬q ⇒ ¬p)

1 1 1 1 01 1 01
1 0 0 1 10 0 01
0 1 0 1 01 1 10
0 1 0 1 10 1 10

Ponieważ pod spójnikiem głównym czterokrotnie pojawiła się jedynka,

również i tu mamy do czynienia z tautologią. Inaczej kończy się proces spraw-
dzania formuły (p

⇒ q) ⇒ (¬p ⇒ ¬q).

(p

⇒ q) ⇒ (¬p ⇒ ¬q)

1 1 1 1 01 1 01
1 0 0 1 01 1 10
0 1 1 0 10 0 01

Fakt, iż już przy zastosowaniu trzeciej kombinacji wartości logicznych

pod spójnikiem głównym pojawiło się zero wskazuje, że formuła ta nie jest tau-
tologią. Czwarty etap sprawdzania jest zatem zbyteczny.
Wiele

formuł rachunku zdań jest od dawna znanych jako tautologie. Nie-

którym z nich tradycja przypisała rangę „naczelnych praw myślenia”. Znana
nam już tautologia

¬(p ∧ ¬p) to prawo sprzeczności, formuła p ∨ ¬p to prawo

wyłączonego środka, zaś formuła p

⇒p to prawo tożsamości.

Czytelnik

mógłby tu zapytać, na jakiej podstawie jakieś formuły, które nie

są zdaniami, a tylko schematami zdań (zatem nie są ani prawdziwe ani fałszy-
we) nazywa się prawami. Wszak prawo powinno coś stwierdzać, czyli dostar-
czać nam pewnej informacji, którą uznajemy za cenną i oczywiście prawdziwą.
Otóż nie sama tautologia, lecz nasza wiedza, że jest ona tautologią (czyli sche-
matem wyłącznie zdań prawdziwych) jest pewną informacją. W ten oto sposób
tautologia zwana prawem sprzeczności mówi nam pośrednio, że koniunkcja
dwóch zdań sprzecznych jest zawsze fałszywa (innymi słowy: z dwóch zdań
sprzecznych zawsze jedno jest fałszywe). Natomiast prawo wyłączonego środka
mówi, że alternatywa dwóch zdań sprzecznych jest zawsze prawdziwa (inaczej:
z dwóch zdań sprzecznych zawsze jedno jest prawdziwe). Z kolei prawo tożsa-
mości mówi, że każde zdanie wynika logicznie z siebie samego. Zdania wyróż-
nione tu kursywą to metalogiczne odpowiedniki tautologii rachunku zdań. Na-
zywamy je metalogicznymi, ponieważ są to zdania metajęzyka, czyli języka, w
którym mówi się o wyrażeniach (tutaj o zdaniach) innych języków.
Jeśli tautologie rachunku zdań mają służyć jako narzędzia rozpoznawania
związków wynikania logicznego, to bezpośrednie zastosowanie znajdują tu tyl-
ko te, w których spójnikiem głównym jest znak implikacji lub równoważności.
Jest bowiem oczywiste, że ilekroć w takiej tautologii przez podstawianie zdań za
zmienne uzyskamy prawdziwy poprzednik, to jest wykluczone, aby następnik

3

okazał się fałszywy. Dlatego, na przykład, tautologii (p

⇒ q) ⇒ (¬p ⇒ ¬q)

(zwanej prawem transpozycji) odpowiada niezawodny schemat wnioskowania:

p

q

q

p

¬

⇒

¬

⇒

Tautologie, w których spójnikiem głównym jest spójnik równoważności

sygnalizują wynikanie logiczne „w obie strony” czyli logiczną równoważność
zdań. Są one interesujące również z tego względu, iż pokazują jak treść danego
zdania można wyrazić inaczej, między innymi —korzystając z innych spójni-
ków. Na przykład tautologie:

p

∨ q ⇔ ¬p ⇒ q

p

∧ q ⇔ ¬(p ⇒ ¬q)

pokazują, że zamiast spójnikami alternatywy i koniunkcji można posłużyć się
znakiem negacji i spójnikiem implikacji. Z kolei zamiast spójnikiem implikacji
można posłużyć się znakiem negacji i koniunkcji, bądź znakiem negacji i alter-
natywy. Pokazują to tautologie:

p

⇒ q ⇔ ¬(p ∧¬q)

p

⇒ q ⇔ ¬p ∨ q

Kiedy zaprzeczamy zdaniom złożonym, sens tego, co wówczas mamy do

powiedzenia, bywa na ogół trudniej uchwytny, niż wtedy, kiedy negacja odnosi
się do zdań prostych. Dlatego godne uwagi są tautologie, które przenoszą nega-
cję „do wnętrza” zdania złożonego. Na przykład:

¬(p ∧ q) ⇔ ¬p ∨ ¬q
¬(p ∨ q) ⇔ ¬p ∧ ¬q

Te dwie tautologie, na cześć ich odkrywcy, nazywane są prawami De

Morgana.

Czemu jest równoważna negacja implikacji wyjaśnia prawo:

¬(p ⇒q) ⇔ p ∧ ¬q

Nieco bardziej skomplikowane jest prawo negowania równoważności.

Zauważmy wpierw, że ponieważ równoważność jest koniunkcją dwóch impli-
kacji (prostej i odwrotnej), to:

¬(p ⇔ q) ⇔ ¬(p ⇒ q) ∨ ¬(q ⇒ p)

Skorzystaliśmy tu z prawa negowania koniunkcji, zaś korzystając z kolei z
prawa negowania implikacji otrzymamy:

¬(p ⇔ q) ⇔ (p ⇒ ¬q) ∨ (q ⇒ ¬ p).

Poznana powyżej metoda zerojedynkowa jest efektywna. Oznacza to, że

o każdej, a więc dowolnie długiej i dowolnie skomplikowanej, formule rachun-
ku zdań, pozwala ona w skończonej liczbie kroków rozstrzygnąć, czy jest to,
czy też nie jest, tautologia.

Czy istnieją inne metody rozstrzygania tego rodzaju pytań? Istnieją. Są to

jednakże metody „jednostronne”; pozwalają one wykazać, że dana formuła ra-
chunku zdań jest tautologią, ale nie, że nią nie jest.

4

Jedna z takich metod polega na ujęciu zbioru tautologii w system aksjo-

matyczny. Polega to na tym, że pewne nieliczne formuły rachunku zdań, o któ-
rych wiadomo, że są tautologiami, przyjmuje się jako aksjomaty systemu. Po-
nadto formułuje się reguły dowodzenia tak dobrane, aby zastosowane do tauto-
logii prowadziły wyłącznie do tautologii. Zazwyczaj są to dwie proste reguły:
reguła podstawiania i reguła odrywania. Aksjomaty wraz z formułami, które
dają się z nich uzyskać za pomocą tych dwóch reguł w skończonej liczbie kro-
ków nazywane są tezami systemu. Reguła podstawiania pozwala za pewną
zmienną zdaniową występującą w formule zdaniowej będącą tezą systemu pod-
stawić dowolną formułę. Zatem jeśli — na przykład — aksjomatami systemu są
formuły:
(A1) (p

⇒ q) ⇒ ((q ⇒ r) ⇒ (p ⇒ r)),

(A2) p

⇒ (q ⇒p),

to podstawiając w (A1) za zmienną q formułę q

⇒ p otrzymamy:

[p

⇒ (q ⇒ p)] ⇒{[(q ⇒ p) ⇒ r] ⇒ (p ⇒ r)]}

Formuła uzyskana w ten sposób jest tezą systemu, a ponieważ jej po-

przednik jest identyczny z aksjomatem (A2), możemy tu zastosować regułę od-
rywania, która mówi: jeżeli pewna implikacja jest tezą systemu i jej poprzednik
również jest tezą, to tezą jest także jej następnik. W ten sposób ustalamy, że tezą
jest również formuła:

[(q

⇒ p) ⇒ r] ⇒ (p ⇒ r)].

Nadając rachunkowi zdań postać systemu aksjomatycznego logicy starają
się, aby tezami systemu były wszystkie tautologie i — oczywiście — tylko tau-
tologie. Jest to osiągalne i wszystkie znane systemy rachunku zdań warunek ten
spełniają, zaś różnice między nimi polegają na liczbie i doborze aksjomatów.

Gdy celem naszym jest ustalanie związków wynikania logicznego między

zdaniami, to praktyczna użyteczność aksjomatycznych systemów rachunku zdań
jest niewielka. Ustalanie, czy pewna formuła jest tezą, jest tu nie tylko praco-
chłonne, lecz — w odróżnieniu od metody zerojedynkowej — nie jest „mecha-
niczne”, lecz wymaga dużej pomysłowości i wprawy.

Na szczęście istnieją metody ustalania związków wynikania logicznego

łatwiejsze w zastosowaniu. Będzie o nich mowa w rozdziale następnym.

5