5. Tautologie klasycznego rachunku zdań
21 grudnia 2010
Ważną rolę w poprawnym wnioskowaniu odgrywają takie schematy zdań złożonych, że każde zdanie podpadające pod taki schemat jest zawsze zdaniem złożonym prawdziwym. Schematy takie zwiemy tautologiami klasycznego rachunku zdań lub po prostu twierdzeniami (prawami) klasycznego rachunku zdań.
Jako przykład tautologii klasycznego rachunku zdań służyć może schemat:
p ˅ ~ p,
zwany prawem wyłącznego środka.
Przykładami zdań o tym schemacie są np.:
Dla dowolnej liczby rzeczywistej x:
x = 0 lub x ≠ 0,
x jest liczbą wymierną, lub x nie jest liczbą wymierną.
Dowolne dwie proste na płaszczyźnie są równoległe, lub dowolne dwie proste na płaszczyźnie nie są równoległe.
Tautologią jest też schemat:
(p → q) → (~ q → ~ p),
zwany prawem transpozycji.
Przykład zdania podpadającego pod powyższy schemat:
Jeżeli [(znam język francuski), (to mogę czytać Molliera w oryginale)], to [jeżeli (czytam utwory Molliera w oryginale i nie rozumiem ich treści), to (nie znam języka francuskiego)].
Innym przykładem tautologii jest schemat:
p → ~ ~ p
nazywany prawem podwójnego przeczenia.
Wspomniano, że tautologie (wyrażenia logiczne zawsze prawdziwe, przy dowolnym wartościowaniu zmiennych zdaniowych) odgrywają szczególną rolę w k.r.z., więc powstaje pytanie, jak sprawdzić prawdziwość dowolnych wyrażeń logicznych.
O tautologiach można mianowicie dowieść następującego twierdzenia (o rozstrzygalności k.r.z.).
Istnieje efektywna metoda (algorytm), pozwalająca sprawdzić w skończonej liczbie kroków, czy dowolny schemat a zbudowany ze spójników i zmiennych zdaniowych (liter) oraz nawiasów jest prawem (tautologią) k.r.z., czy też nią nie jest.
Metodę tę nazywa się powszechnie metodą sprawdzania zero – jedynkowego. Sposób jej stosowania jest bardzo prosty. Każdą zmienną w dowolnym schemacie a reprezentuje jakieś zdanie prawdziwe bądź fałszywe: zmienną należy więc w schemacie a zastąpić raz symbolem 0, a drugi raz symbolem 1. Postępując w ten sposób z każdą zmienną, otrzymujemy w schemacie pewną liczbę konkretnych podstawień. Liczba tych podstawień jest skończona.
Dla n zmiennych mamy 2n podstawień.
Przykład: niech wyrażenie a ma postać:
a = [(p → q) → [(q → r) → (p → r)].
Sprawdzić (metodą matrycową) czy wyrażenie a może stanowić w logice schemat wnioskowania budując tablicę zawierającą wszystkie zmienne i elementy składowe.
Tablica prawdziwościowa:
|
p
|
q |
r |
p → q |
q → r |
p → r |
(q → r) → (p → r) |
a |
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
|
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
n = 3 23 = 8 – kombinacji podstawień
a – jest tautologii
Jest to jedno z pierwszych znanych już w starożytnej Grecji praw, które nazywa się prawem sylogizmu warunkowego stoików.
Inną wersję tego prawa podaje się w postaci:
[(p → q) ˄ (q → r)] → (p →r)]
Jeżeli z p wynika q, a r wynika z q, to r wynika też z p.
Przykład. Jeżeli dziś jest poniedziałek, to jutro jest wtorek i jeżeli jutro jest wtorek, to pojutrze jest środa, to jeżeli dziś jest poniedziałek, to pojutrze jest środa.