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 (\mathrm{\neg }\alpha \to \beta )$	prawo przepełnienia
Ax${}_{13}$   $(\alpha \to \mathrm{\neg }\alpha )\to \mathrm{\neg }\alpha$	prawo redukcji do absurdu
Ax${}_{14}$   $\mathrm{\neg }\mathrm{\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 $\{{𝐀𝐱}_1,\dots ,{𝐀𝐱}_{13}\}$ o formułę ${𝐀𝐱}_{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 ${𝐀𝐱}_{12}-{𝐀𝐱}_{14}$ przyjąć

Ax${}_{1^{\prime }2}$    $(\alpha \to \beta )\to (\mathrm{\neg }\beta \to \mathrm{\neg }\alpha )$	prawo kontrapozycji
Ax${}_{1^{\prime }3}$    $\alpha \leftrightarrow \mathrm{\neg }\mathrm{\neg }\alpha$	prawo podwójnego przeczenia

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

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

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

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

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

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

oraz

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

Twierdzenia o dedukcji

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

$\alpha \to \beta \in {\text{Cn}}_c(X)⟺\beta \in {\text{Cn}}_c(X\cup \{\alpha \})$

oraz uogólnione twierdzenie o dedukcji:

1. ${\text{Cn}}_c(X\cup \{\alpha \vee \beta \})={\text{Cn}}_c(X\cup \{\alpha \})\cap {\text{Cn}}_c(X\cup \{\beta \})$
2. ${\text{Cn}}_c(X\cup \{\alpha \wedge \beta \})={\text{Cn}}_c(X\cup \{\alpha ,\beta \})$
3. $\mathrm{\neg }\alpha \in {\text{Cn}}_c(X)⟺X\cup \{\alpha \}\text{ jest sprzeczny}$

gdzie ${\text{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 {\text{Cn}}_c(X)⟺X\cup \{\mathrm{\neg }\alpha \}\text{ jest sprzeczny}$

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

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

oraz prawa wyłączonego środka:

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

Prawo kontrapozycji (silne)

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

Prawo wyłączonego środka

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

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 ${ℬ}_2,$ czyli nie jest ona tautologią klasyczną.

Zobacz też

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

Linki zewnętrzne

• Szablon:SEP