9. Rachunek zdań jako system aksjomatyczny cz.2
22 grudnia 20109.3. Własności klasycznego rachunku zdań
Własności te wynikają z ostatniego twierdzenia:
1. Każdy schemat będący podstawieniem tautologii jest tautologią.
2. Schemat powstały przez odrywanie z dwóch tautologii jest również tautologią.
Własność 1. wynika z definicji podstawienia, a zwłaszcza z własności tautologii (zawsze prawdziwa). Własność 2. łatwo jest udowodnić.
Przypuśćmy, że schemat a i a → b są tautologiami k.r.z. Gdyby b nie było tautologią, to istniałoby takie podstawienie, że b jest fałszywe. Dokonajmy tego podstawienia w całym schemacie a → b. Skoro a jest tautologią, to przy tym podstawieniu, a przechodzi w zdanie prawdziwe. Otrzymujemy więc, że
1 → 0,
a to oznacza, że a → b nie jest tautologią, co przeczy założeniu, że schemat a → b jest tautologią, czyli b musi być tautologią. Reguła odrywania nie wyprowadza więc poza tautologie.
Definicja. Zbiór Y jest skończenie aksjomatyzowalny wtedy i tylko wtedy, gdy istnieje taki skończony zbiór X, że
Y = Cnq (X).
Twierdzenie. Zbiór tautologii k.r.z. jest skończenie aksjomatyzowalny.
Dowód (szkic). Każdą formułę, będącą schematem zdaniowym, można równoważnościowo sprowadzić do postaci normalnej. Sprowadzenie tego, jak już wiemy, dokonać można za pomocą pewnej skończonej liczby twierdzeń (praw logiki). Jeżeli wyrażenie mające postać normalną jest tautologią, to wynika też ono z pewnej liczby explicite wypisanych tautologii. Ponadto zachodzi równoważność tautologii a i jej postaci normalnej. A więc jeżeli a jest tautologią, to a’ też jest tautologią i a º a’. Równoważność a º a’ jest tautologią, ponieważ powstaje z tautologii, a zbiór tautologii k.r.z. jest teorią. Stąd jeżeli a jest tautologią, to a’ musi być tautologią. Ale skoro a’ jest tautologią, to a jest konsekwencją powyższej skończonej liczby twierdzeń. Zbiór tautologii jest więc skończenie aksjomatyzowalny (A. Grzegorczyk, Zarys logiki matematycznej, PWN, Warszawa, 1969, str. 101-105).
9.4. Aksjomatyka
Terminy (pojęcia) pierwotne:
~ , →
Aksjomaty:
A1: (p → q) → [(q → r) → (p → r)]
A2: p → (~ p → q)
A3: (~ p → p) → ~ p.
A1 – prawo sylogizmu warunkowego stoików
A2 – prawo Dunsa Scotusa
A3 – prawo Claviusa.
Przyjęte aksjomaty, zbudowane z pojęć pierwotnych, nie zawierają funktorów ˅, ˄, i º. Należy więc je zdefiniować za pomocą przyjętych pojęć pierwotnych.
Definicje:
d1. p ˅ q ~ p → q
d2. p ˄ q ~ (p → ~ q)
d3. p º q (p → q) ˄ (q → p).
Uwaga. W definicji równoważności posłużono się koniunkcją, gdyż została ona już wcześniej zdefiniowana.
W powyższym systemie aksjomatycznym przyjmuje się ponadto osobną dyrektywę, mówiącą o stosowaniu definicji, która brzmi:
W dowolnym twierdzeniu k.r.z. można dowolną część równokształtną z jedną ze stron definicji zastąpić przez część równokształtną z drugą ze stron tejże definicji.
Dyrektywa ta zwie się dyrektywą zastępowania definicyjnego. Stosując ją np. do aksjomatu A2, otrzymujemy z niego twierdzenie
T: p → (p ˅ q),
Zastępując wyrażenie (~ p → q) w A2 lewą stroną definicji d1.
Zbiór konsekwencji trzech wymienionych wyżej aksjomatów przy dołączeniu do reguł (pierwotnych) logicznych podstawiania i odrywania jeszcze reguły zastępowania definicyjnego, jest identyczny z klasycznym rachunkiem zdań.
Układ aksjomatów powinien być niezależny, niesprzeczny i zupełny. Aksjomaty powinny być niezależne, tzn. układ aksjomatów, w którym żaden nie wynika z pozostałych, nazywa się niezależnym układem aksjomatów.
Układ aksjomatów powinien być niesprzeczny, tzn. w systemie nie mogą być jednocześnie twierdzeniami dwa wyrażenia sprzeczne. Czyli, jeżeli A jest twierdzeniem prawdziwym, to ~ A musi być fałszywe.
Zupełność oznacza, że wzbogacając system aksjomatów jakimkolwiek wyrażeniem nie będącym twierdzeniem, otrzymujemy system sprzeczny. Mówimy też, że teoria jest pełna, jeśli każde prawdziwe zdanie w tej teorii da się udowodnić na podstawie aksjomatów wedle reguł dowodzenia w niej obowiązujących.