Klasyczny rachunek zdań

Klasyczny rachunek zdań – najpopularniejszy system formalny logiki matematycznej, w którym formuły reprezentujące zdania logiczne mogą być tworzone z formuł atomowych za pomocą wymienionego niżej zbioru aksjomatów.

Definicja

Klasyczny rachunek zdań, KRZ, w wersji inwariantnej — rachunek zdaniowy w języku klasycznego rachunku zdań z regułą odrywania jako jedyną pierwotną regułą wnioskowania oraz aksjomatami następującej postaci:

Ax$_{1}$    $\alpha\to(\beta\to \alpha)$	prawo poprzedzania
Ax$_{2}$   $[\alpha\to(\beta\to \gamma)]\to[(\alpha\to \beta)\to(\alpha\to \gamma)]$	sylogizm Fregego
Ax$_{3}$   $\alpha\wedge \beta\to \alpha$	prawo opuszczania koniunkcji, 1.
Ax$_{4}$   $\alpha\wedge \beta\to \beta$	prawo opuszczania koniunkcji, 2.
Ax$_{5}$   $(\alpha\to \beta)\to[(\alpha\to \gamma)\to(\alpha\to \beta\wedge \gamma)]$	prawo wprowadzania koniunkcji
Ax$_{6}$   $\alpha\to \alpha\vee \beta$	prawo wprowadzania alternatywy, 1.
Ax$_{7}$   $\beta\to \alpha\vee \beta$	prawo wprowadzania alternatywy, 2.
Ax$_{8}$   $(\beta\to \alpha)\to[(\gamma\to \alpha)\to(\beta\vee \gamma\to \alpha)]$	prawo łączenia implikacji
Ax$_{9}$   $(\alpha\leftrightarrow \beta)\to(\alpha\to \beta)]$	prawo opuszczania równoważności, 1.
Ax$_{10}$   $(\alpha\leftrightarrow \beta)\to(\beta\to \alpha)]$	prawo opuszczania równoważności, 2.
Ax$_{11}$   $(\alpha\to \beta)\to[(\beta\to \alpha)\to(\alpha\leftrightarrow \beta)]$	prawo wprowadzania równoważności
Ax$_{12}$   $\alpha\to(\neg \alpha\to \beta)$	prawo przepełnienia
Ax$_{13}$   $(\alpha\to\neg \alpha)\to\neg \alpha$	prawo redukcji do absurdu
Ax$_{14}$   $\neg\neg\alpha\to \alpha$	silne prawo podwójnego przeczenia

Związek z intuicjonistycznym rachunkiem zdań

W tej formie aksjomatyka ta jest rozszerzeniem aksjomatyki intuicjonistycznego rachunku zdań, którą stanowią formuły $\{\mathbf{Ax}_1,\ldots,\mathbf{Ax}_{13}\}$ o formułę $\mathbf{Ax}_{14}$.

Przykłady dowodu w systemie formalnym klasycznego rachunku zdań znaleźć można w artykule dot. intuicjonistycznego rachunku zdań. Ponieważ KRZ jest rozszerzeniem INT tylko o jeden aksjomat, zamieszczone tam dowody są także poprawnymi dowodami w klasycznym rachunku zdań.

Gdyby chcieć uprawiać KRZ w oderwaniu od INT, można zamiast aksjomatów $\mathbf{Ax}_{12}-\mathbf{Ax}_{14}$ przyjąć

Ax$_{12}'$    $(\alpha\to\beta)\to(\neg\beta\to\neg\alpha)$	prawo kontrapozycji
Ax$_{13}'$    $\alpha\leftrightarrow\neg\neg\alpha$	prawo podwójnego przeczenia

Niektórzy autorzy wręcz ograniczają język KRZ do np. $\to$ i $\neg$ traktując pozostałe spójniki jako wtórne:

Df$_{\vee}$    $(\alpha\vee\beta):\equiv(\neg\alpha\to\beta)$

Df$_{\wedge}$    $(\alpha\wedge\beta):\equiv\neg(\alpha\to\neg\beta)$

Df$_{\leftrightarrow}$    $(\alpha\leftrightarrow\beta):\equiv\neg[(\alpha\to\beta)\to\neg(\beta\to\alpha)]$

Wówczas np. wykazanie prawa przemienności alternatywy sprowadza się do dowodliwości formuły $(\neg\alpha\to\beta)\leftrightarrow(\neg\beta\to\alpha)$, a dowodliwość praw de Morgana, to dowodliwość formuł

$\neg\neg(\alpha\to\neg\beta)\leftrightarrow(\neg\neg\alpha\to\neg\beta)$

oraz

$\neg(\neg\alpha\to\beta)\leftrightarrow\neg(\neg\alpha\to\neg\neg\beta)$

Twierdzenia o dedukcji

W KRZ podobnie jak w INT prawdziwe są klasyczne Twierdzenie o dedukcji:

$\alpha\to\beta\in\textrm{Cn}_{c}(X)\;\;\iff\;\;\beta\in\textrm{Cn}_{c}(X\cup\{\alpha\})$

oraz uogólnione twierdzenie o dedukcji:

1. $\textrm{Cn}_{c}(X\cup\{\alpha\lor\beta\})=\textrm{Cn}_{c}(X\cup\{\alpha\})\cap\textrm{Cn}_{c}(X\cup\{\beta\})$
2. $\textrm{Cn}_{c}(X\cup\{\alpha\land\beta\})=\textrm{Cn}_{c}(X\cup\{\alpha,\beta\})$
3. $\neg\alpha\in\textrm{Cn}_{c}(X)\;\;\iff\;\;X\cup\{\alpha\} \mbox{ jest sprzeczny}$

gdzie $\textrm{Cn}_{c}\,(X)$ oznacza zbiór formuł dowodliwych w KRZ ze zbioru założeń $X\,$.

Wynika to z faktu, że w dowodzie obu tych twierdzeń korzysta się z aksjomatów o numerach nie przekraczających liczby $13\,$.

W odróżnieniu jednak od INT, w przypadku KRZ trzeci punkt ostatniego twierdzenia może także przyjąć postać:

4. $\alpha\in\textrm{Cn}_{c}(X)\;\;\iff\;\;X\cup\{\neg\alpha\} \mbox{ jest sprzeczny}$

Jako przykład użycia tej wersji twierdzenia o dedukcji, wykażemy dowodliwość w KRZ tzw. silnego prawa kontrapozycji:

$(\neg p\to \neg q)\to(q\to p)$

oraz prawa wyłączonego środka:

$p\vee\neg p$.

Prawo kontrapozycji (silne)

1.	$q,\neg q\in\textrm{Cn}_c(\{\neg p\to\neg q\,,q,\,\neg p\})$
2.	$\textrm{Cn}_c(\{\neg p\to\neg q\,,q,\,\neg p\})$	jest sprzeczny
3.	$p\in\textrm{Cn}_c(\{\neg p\to\neg q\,,q\})$
4.	$q\to p\in\textrm{Cn}_c(\{\neg p\to\neg q\})$
5.	$(\neg p\to\neg q)\to(q\to p)\in\textrm{Cn}_c(\emptyset)$

Prawo wyłączonego środka

1.	$p\to p\vee\neg p\in\textrm{Cn}_c(\emptyset)$
2.	$p\vee\neg p\in\textrm{Cn}_c(\{p\})$
3.	$\textrm{Cn}_c(\{p,\neg(p\vee\neg p)\})$	– sprzeczny
4.	$\neg p\in\textrm{Cn}_c(\{\neg(p\vee\neg p)\})$
5.	$\neg p\to p\vee\neg p\in\textrm{Cn}_c(\emptyset)$
6.	$p\vee\neg p\in\textrm{Cn}_c(\{\neg p\})$
7.	$\textrm{Cn}_c(\{\neg p,\neg(p\vee\neg p)\})$	– sprzeczny
8.	$\neg\neg p\in\textrm{Cn}_c(\{\neg(p\vee\neg p)\})$
9.	$\textrm{Cn}_c(\{\neg(p\vee\neg p)\})$	– sprzeczny
10.	$p\vee\neg p\in\textrm{Cn}_c(\emptyset)$

Związek z algebrą Boole'a

Formuła języka klasycznego rachunku zdań jest tezą KRZ jeśli jest ona prawdziwa dowolnej algebrze Boole'a.

W szczególności jeśli formuła nie jest tezą KRZ, to można ją obalić w dwuelementowej algebrze Boole'a $\mathcal{B}_2$, czyli nie jest ona tautologią klasyczną.

Zobacz też

• Intuicjonistyczny rachunek zdań
• Matryca logiczna języka zdaniowego
• Algebra ogólna