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${\displaystyle _{1}}$    ${\displaystyle \alpha \to (\beta \to \alpha )}$	prawo poprzedzania
Ax${\displaystyle _{2}}$   ${\displaystyle [\alpha \to (\beta \to \gamma )]\to [(\alpha \to \beta )\to (\alpha \to \gamma )]}$	sylogizm Fregego
Ax${\displaystyle _{3}}$   ${\displaystyle \alpha \wedge \beta \to \alpha }$	prawo opuszczania koniunkcji, 1.
Ax${\displaystyle _{4}}$   ${\displaystyle \alpha \wedge \beta \to \beta }$	prawo opuszczania koniunkcji, 2.
Ax${\displaystyle _{5}}$   ${\displaystyle (\alpha \to \beta )\to [(\alpha \to \gamma )\to (\alpha \to \beta \wedge \gamma )]}$	prawo wprowadzania koniunkcji
Ax${\displaystyle _{6}}$   ${\displaystyle \alpha \to \alpha \vee \beta }$	prawo wprowadzania alternatywy, 1.
Ax${\displaystyle _{7}}$   ${\displaystyle \beta \to \alpha \vee \beta }$	prawo wprowadzania alternatywy, 2.
Ax${\displaystyle _{8}}$   ${\displaystyle (\beta \to \alpha )\to [(\gamma \to \alpha )\to (\beta \vee \gamma \to \alpha )]}$	prawo łączenia implikacji
Ax${\displaystyle _{9}}$   ${\displaystyle (\alpha \leftrightarrow \beta )\to (\alpha \to \beta )]}$	prawo opuszczania równoważności, 1.
Ax${\displaystyle _{10}}$   ${\displaystyle (\alpha \leftrightarrow \beta )\to (\beta \to \alpha )]}$	prawo opuszczania równoważności, 2.
Ax${\displaystyle _{11}}$   ${\displaystyle (\alpha \to \beta )\to [(\beta \to \alpha )\to (\alpha \leftrightarrow \beta )]}$	prawo wprowadzania równoważności
Ax${\displaystyle _{12}}$   ${\displaystyle \alpha \to (\neg \alpha \to \beta )}$	prawo przepełnienia
Ax${\displaystyle _{13}}$   ${\displaystyle (\alpha \to \neg \alpha )\to \neg \alpha }$	prawo redukcji do absurdu
Ax${\displaystyle _{14}}$   ${\displaystyle \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 ${\displaystyle \{\mathbf {Ax} _{1},\dots ,\mathbf {Ax} _{13}\}}$ o formułę ${\displaystyle \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 ${\displaystyle \mathbf {Ax} _{12}-\mathbf {Ax} _{14}}$ przyjąć

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

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

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

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

Df${\displaystyle _{\leftrightarrow }}$    ${\displaystyle (\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 ${\displaystyle (\neg \alpha \to \beta )\leftrightarrow (\neg \beta \to \alpha ),}$ a dowodliwość praw de Morgana, to dowodliwość formuł

${\displaystyle \neg \neg (\alpha \to \neg \beta )\leftrightarrow (\neg \neg \alpha \to \neg \beta )}$

oraz

${\displaystyle \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:

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

oraz uogólnione twierdzenie o dedukcji:

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

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

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

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

4. ${\displaystyle \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:

${\displaystyle (\neg p\to \neg q)\to (q\to p)}$

oraz prawa wyłączonego środka:

${\displaystyle p\vee \neg p.}$

Prawo kontrapozycji (silne)

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

Prawo wyłączonego środka

1.	${\displaystyle p\to p\vee \neg p\in {\textrm {Cn}}_{c}(\emptyset )}$
2.	${\displaystyle p\vee \neg p\in {\textrm {Cn}}_{c}(\{p\})}$
3.	${\displaystyle {\textrm {Cn}}_{c}(\{p,\neg (p\vee \neg p)\})}$	– sprzeczny
4.	${\displaystyle \neg p\in {\textrm {Cn}}_{c}(\{\neg (p\vee \neg p)\})}$
5.	${\displaystyle \neg p\to p\vee \neg p\in {\textrm {Cn}}_{c}(\emptyset )}$
6.	${\displaystyle p\vee \neg p\in {\textrm {Cn}}_{c}(\{\neg p\})}$
7.	${\displaystyle {\textrm {Cn}}_{c}(\{\neg p,\neg (p\vee \neg p)\})}$	– sprzeczny
8.	${\displaystyle \neg \neg p\in {\textrm {Cn}}_{c}(\{\neg (p\vee \neg p)\})}$
9.	${\displaystyle {\textrm {Cn}}_{c}(\{\neg (p\vee \neg p)\})}$	– sprzeczny
10.	${\displaystyle 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 ${\displaystyle {\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.).