RACHUNEK ZDAC
7
Reguła podstawiania:
Jeżeli dana formuła rachunku zdań jest tautologią i wszystkie wystąpienia pewnej
zmiennej zdaniowej w tej tautologii zastąpimy pewną ustaloną formułą, to otrzymana
w ten sposób formuła również będzie tautologią.
Reguła zastępowania:
Jeżeli w danej formule zastąpimy pewną jej podformułę zdaniem logicznie
równoważnym tej podformule, to otrzymana w ten sposób formuła będzie logicznie
równoważna danej formule.
W szczególności, jeśli dana formuła jest tautologią, to formuła wynikowa również
będzie tautologią.
Reguła odrywania:
Dla każdej tautologii w formie implikacji, której poprzednik również jest tautologią,
następnik także jest tautologią.
Jak widać, stosując trzy w.w. reguły, zarówno osobno jak i łącznie, będziemy zawsze
przechodzić od tautologii do tautologii.
Sformalizowany aksjomatyczny system rachunku zdań składa się z:
1. zbioru symboli zwanego alfabetem,
2. zbioru słów nad tym alfabetem, które nazywamy formułami,
3. wyróżnionego podzbioru formuł, które nazywamy aksjomatami,
4. zbioru reguł wnioskowania.
Jako reguły wnioskowania przyjmuje się zwykle regułę podstawiania i regułę
odrywania, ewentualnie regułę zastępowania.
Pojęcie dowodu definiuje się analogicznie jak w systemach założeniowych:
Dowodem formuły jest kończący się tą formułą ciąg formuł, w którym występują
jedynie aksjomaty, wcześniej udowodnione twierdzenia oraz formuły otrzymane z
formuł poprzedzających je w tym ciągu przez zastosowanie do nich reguł
wnioskowania.
Twierdzenia danego systemu to te formuły, dla których istnieje ich dowód; przy czym
aksjomaty nazywa się też twierdzeniami pierwotnymi, zaś pozostałe dowodliwe
formuły  twierdzeniami pochodnymi (albo wtórnymi).
Historycznie pierwszą aksjomatyką logiki klasycznej był układ aksjomatów
zaproponowany przez Gottloba Fregego:
(1) p(qp)
(2) (p(qr)) ((pq)(pr))
(3) (p(qr)) (q(pr))
(4) (pq) (<"q<"p)
(5) p<"<"p
(6) <"<"pp
1
RACHUNEK ZDAC
7
Jan A
ukasiewicz zaproponował  oszczędniejszy system, bo wymagający tylko trzech
aksjomatów:
(A1) (pq) ((qr)(pr))
(A2) (<"pp) p
(A3) p (<"pq)
Z kolei system A.N. Whiteheada i B. Russella z ich fundamentalnej pracy  Principia
mathematica nie jest implikacyjno-negacyjny, jak dwa powyższe systemy, lecz
alternatywno-negacyjny:
(1) <"(p("p) (" p
(2) <"p (" (p("q)
(3) <"(p("q) (" (q("p)
(4) <"(<"p("q) (" (<"(r("p) (" (r("q))
Terminy stałe występujące w aksjomatach (np. w systemie A
ukasiewicza symbole
implikacji i negacji) zwane są terminami pierwotnymi. Za ich pomocą możemy
definiować nowe, zwane terminami pochodnymi lub wtórnymi. Definicje tworzymy w
oparciu o prawa zastępowania (eliminacji), np.:
(D1) (A (" B) = (<"A B)
(D2) (A '" B) = <"(A <"B)
(D3) (A "! B) = <"[(A B) <"(B A)]
Stosując wówczas regułę zastępowania, która pozwala zastąpić podformułę jej
równoważnikiem definicyjnym, zyskujemy możliwość dowodzenia twierdzeń ze
spójnikami, które nie występują w aksjomatach.
Można to też uzyskać budując bogatszy system: przyjmując obszerniejszy alfabet
oraz aksjomaty zawierające wszystkie interesujące nas terminy stałe. Rozbudowując
aksjomatykę, unikniemy definicji i reguły zastępowania, upraszczając zarazem
dowody. Oto przykład takiej aksjomatyki:
(1) (pq) ((qr) (pr))
(2) (p(pq)) (pq)
(3) p (qp)
(4) p'"q p
(5) p'"q q
(6) (pq) ((pr) (p (q'"r)))
(7) p (p("q)
(8) q (p("q)
(9) (pr) ((qr) ((p("q) r)))
(10) (p"!q) (pq)
(11) (p"!q) (qp)
(12) (pq) ((qp) (p"!q))
(13) (<"q<"p) (pq)
___________________________________________________________________
2
RACHUNEK ZDAC
7
Metalogika, metamatematyka  działy nauki, w ramach których bada się własności
systemów dedukcyjnych, odpowiednio logicznych i matematycznych (bywa jednak,
że określeń tych używa się wymiennie).
System dedukcyjny nazywamy semantycznie pełnym, gdy można w nim udowodnić
każdą tautologię, tj. gdy dla dowolnej formuły A zachodzi:
^% A Ą# A
Dla każdego (z osobna) z omawianych przez nas wcześniej systemów można w
ramach metalogiki udowodnić tzw. twierdzenie o pełności:
Formuła A systemu dedukcyjnego rachunku zdań jest jego twierdzeniem
witw, gdy jest tautologią:
Ą# A "! ^% A
Zatem wszystkie te systemy są semantycznie pełne.
Jak widać, w przypadku rachunku zdań prawdziwość (jako własność semantyczna) i
dedukowalność (jako własność syntaktyczna) pokrywają się.
System dedukcyjny nazywamy systemem niesprzecznym, gdy wśród jego
twierdzeń nie ma dwóch formuł sprzecznych  czyli nie ma takiej formuły, że zarówno
ją jak i jej negację można udowodnić w ramach danego systemu.
A
atwo jest udowodnić twierdzenie następujące:
Każdy semantycznie pełny system rachunku zdań jest systemem
niesprzecznym.
Wniosek: omawiane przez nas systemy, jako semantycznie pełne, są również
niesprzeczne.
System dedukcyjny nazywamy zupełnym, gdy każda formuła niedowodliwa w tym
systemie dołączona do niego jako aksjomat czyni go systemem sprzecznym.
Własność ta, zwana też syntaktyczną zupełnością (albo mocną zupełnością, albo
zupełnością w sensie Posta) oznacza, że w pewnym sensie system jest maksymalny.
Udowadnia się następujące twierdzenie:
Każdy semantycznie pełny system rachunku zdań z regułą odrywania i
regułą podstawiania jest zupełny.
Wniosek: omawiane przez nas systemy są zupełne.
Dwa systemy dedukcyjne nazywamy równoważnymi, gdy mają identyczne zbiory
formuł i twierdzeń oraz dowolna reguła pierwotna każdego z systemów jest regułą
(pierwotną lub wtórną) drugiego systemu.
Systemy równoważne mają identyczne własności (pełność, niesprzeczność itd.).
Można pokazać, że poznane przez nas systemy są równoważne.
3
RACHUNEK ZDAC
7
Mówimy, że system dedukcyjny rachunku zdań jest funkcjonalnie zupełny (albo
definicyjnie pełny), gdy za pomocą jego terminów pierwotnych może być zdefiniowany
każdy funktor prawdziwościowy rachunku zdań (o dowolnej liczbie argumentów).
Można udowodnić np., że system z koniunkcją i negacją jest funkcjonalnie zupełny, a
system z koniunkcją i alternatywą (jako jedynymi terminami pierwotnymi)  nie jest
funkcjonalnie zupełny. Co więcej, z takich dowodów widać, że własność funkcjonalnej
zupełności nie zależy wcale od aksjomatyki czy reguł wnioskowania, a jedynie od
samych terminów pierwotnych.
System dedukcyjny jest rozstrzygalny, jeżeli istnieje efektywna metoda pozwalająca
w skończonej liczbie kroków rozstrzygnąć dla dowolnej formuły pytanie, czy ta formuła
jest czy też nie jest twierdzeniem tego systemu.
Systemy dedukcyjne rachunku zdań są rozstrzygalne, gdyż dysponujemy np. metodą
zerojedynkową (a także innymi, jak sprowadzanie formuły do postaci normalnej czy
metoda drzew semantycznych).
Zbiór aksjomatów jest niezależny, jeżeli żaden z nich nie da się wywieść z
pozostałych (według przyjętych w systemie reguł wnioskowania).
Zbiór terminów pierwotnych jest niezależny, gdy żaden z tych terminów nie może być
zdefiniowany przez pozostałe.
Np. aksjomatyki systemów A
ukasiewicza czy Whiteheada są niezależne.
Systemy implikacyjno-negacyjne czy alternatywno-negacyjne mają terminy pierwotne
niezależne.
____________________________________________________________________
Dualność formuł rachunku zdań.
Niech formuła F zawiera jedynie spójniki negacji, koniunkcji i alternatywy.
Niech Fd oznacza formułę powstającą z F przez zastąpienie w niej wszędzie symbolu
koniunkcji przez symbol alternatywy i odwrotnie. Formułę Fd nazywamy dualną
względem formuły F.
Niech F" oznacza formułę otrzymaną z formuły F przez zastąpienie w niej każdej
zmiennej przez jej negację.
Prawo dualności mówi, że:
Formuły F" i <"Fd są logicznie równoważne (tzn. formuła <"Fd "! F" jest
tautologią).
Inne użyteczne twierdzenia dotyczące formuł dualnych mówią, że:
Jeżeli formuła FQ jest tautologią, to formuła QdFd też jest tautologią.
Jeżeli formuła F"!Q jest tautologią, to formuła Fd"!Qd też jest tautologią.
4