Klasyczny rachunek zdań

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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[edytuj | edytuj kod]

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    prawo poprzedzania
Ax    sylogizm Fregego
Ax    prawo opuszczania koniunkcji, 1.
Ax    prawo opuszczania koniunkcji, 2.
Ax    prawo wprowadzania koniunkcji
Ax    prawo wprowadzania alternatywy, 1.
Ax    prawo wprowadzania alternatywy, 2.
Ax    prawo łączenia implikacji
Ax    prawo opuszczania równoważności, 1.
Ax    prawo opuszczania równoważności, 2.
Ax    prawo wprowadzania równoważności
Ax    prawo przepełnienia
Ax    prawo redukcji do absurdu
Ax    silne prawo podwójnego przeczenia

Związek z intuicjonistycznym rachunkiem zdań[edytuj | edytuj kod]

W tej formie aksjomatyka ta jest rozszerzeniem aksjomatyki intuicjonistycznego rachunku zdań, którą stanowią formuły o formułę

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 przyjąć

Ax    prawo kontrapozycji
Ax    prawo podwójnego przeczenia

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

Df   
Df   
Df   

Wówczas np. wykazanie prawa przemienności alternatywy sprowadza się do dowodliwości formuły a dowodliwość praw de Morgana, to dowodliwość formuł

oraz

Twierdzenia o dedukcji[edytuj | edytuj kod]

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

oraz uogólnione twierdzenie o dedukcji:

gdzie oznacza zbiór formuł dowodliwych w KRZ ze zbioru założeń

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

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

4.

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

oraz prawa wyłączonego środka:

Prawo kontrapozycji (silne)[edytuj | edytuj kod]

1.
2. jest sprzeczny
3.
4.
5.

Prawo wyłączonego środka[edytuj | edytuj kod]

1.
2.
3. – sprzeczny
4.
5.
6.
7. – sprzeczny
8.
9. – sprzeczny
10.

Związek z algebrą Boole’a[edytuj | edytuj kod]

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 czyli nie jest ona tautologią klasyczną.

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]