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},\dots ,\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 np. do $\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 \}{\text{ 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 \}{\text{ 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ż

• algebra ogólna
• intuicjonistyczny rachunek zdań
• matryca logiczna języka zdaniowego

Linki zewnętrzne

• StewartS. Shapiro StewartS., Teresa KouriT.K. Kissel Teresa KouriT.K., Classical Logic [w:] Stanford Encyclopedia of Philosophy [online], CSLI, Stanford University, 11 marca 2018, ISSN 1095-5054 [dostęp 2018-08-11]  (ang.).