5 Klasyczny rachunek zdań (KRZ)
1. Wprowadzenie do klasycznego rachunku zdań¶
Klasyczny Rachunek Zdań (KRZ), znany również jako: - Logika zdań - Logika propozycjonalna
Jest to podstawowy system logiczny analizujący zależności między całymi zdaniami (propozycjami) za pomocą spójników logicznych.
Główne cechy KRZ: - Jest logiką klasyczną dwuwartościową - Każde zdanie oznajmujące ma jedną z dwóch wartości logicznych: prawdę (1) lub fałsz (0) - Semantyka logiczna przypisuje każdej formule jedną z dwóch wartości
Cele rachunku zdań: - Przekład wyrażeń języka naturalnego na język logiki - Sprawdzanie poprawności rozumowania wyrażonego poprzez zdania
Formuła atomowa (formuła prosta)
- Formuła, która nie ma żadnych właściwych podformuł (p,q).
- Formuły, które nie są atomowe nazywamy złożonymi.
2. Spójniki logiczne¶
Podstawowe elementy KRZ to spójniki logiczne, które funkcjonują jako funkcje prawdziwościowe - ich wartość wynika wyłącznie z wartości zdań składowych.
| Nazwa spójnika | Symbol | Odpowiednik w języku naturalnym | Przykładowe zastosowanie | Działanie |
|---|---|---|---|---|
| Negacja | ~ | nieprawda, że | ~ p | odwraca 0 i 1 |
| Koniunkcja | ∧ | i | p ∧ q | żeby było 1 muszą być same 1 |
| Alternatywa | ∨ | lub | p ∨ q | żeby było 1 musi być przynajmniej jedno 1 |
| Implikacja | ⇒ | jeśli, to | p ⇒ q | 0 tylko jeśli poprzednik to 1 a następnik 0 |
| Równoważność | ⇔ | wtedy i tylko wtedy, gdy | p ⇔ q | kiedy są same 0 albo same 1 |
3. Tabele prawdziwościowe (zero-jedynkowe)¶
Definicje spójników przedstawione w formie tabelarycznej:
Negacja (¬)¶
| p | ~p |
|---|---|
| 0 | 1 |
| 1 | 0 |
Negacja zmienia wartość logiczną zdania na przeciwną.
Koniunkcja (∧)¶
| p | q | p∧q |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Koniunkcja jest prawdziwa tylko wtedy, gdy oba człony są prawdziwe.
Alternatywa (∨)¶
| p | q | p∨q |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Alternatywa jest prawdziwa, gdy co najmniej jeden z członów jest prawdziwy.
Implikacja (→)¶
| p | q | p⇒q |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Implikacja jest fałszywa tylko wtedy, gdy poprzednik jest prawdziwy, a następnik fałszywy.
Równoważność (↔)¶
| p | q | p⇔q |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Równoważność jest prawdziwa, gdy oba człony mają tę samą wartość logiczną.
4. Tautologie i kontrtautologie¶
Tautologia¶
- Formuła, która jest prawdziwa przy wszystkich możliwych wartościach zdań składowych
- Zawsze przyjmuje wartość 1
- Formalnie nazywana "prawem rachunku zdań"
- Według Wittgensteina, tautologie są puste semantycznie (nic nie mówią o faktach), ale ujawniają strukturę logiczną języka
Kontrtautologia¶
- Formuła, która zawsze przyjmuje wartość 0 (jest zawsze fałszywa)
- Niezależna od wartości zdań składowych
5. Prawa logiczne¶
Najważniejsze tautologie traktowane jako prawa logiczne:
- Prawo tożsamości: p → p
- Prawo sprzeczności: ¬(p ∧ ¬p)
- Prawo wyłączonego środka: p ∨ ¬p
- Prawa de Morgana:
- ¬(p ∧ q) ↔ (¬p ∨ ¬q)
- ¬(p ∨ q) ↔ (¬p ∧ ¬q)
6. Zastosowania KRZ¶
Klasyczny rachunek zdań stanowi:
- Podstawę dla kursów logiki jako dobrze zbadany system
- Teoretyczny rdzeń elektroniki cyfrowej
- Bramki logiczne wykonują operacje wynikające z zastosowania spójników
- Podstawę dla języków programowania
- System zero-jedynkowy jest fundamentem binarnego charakteru języków programowania
- Fundament dla bardziej zaawansowanych systemów:
- Rachunek predykatów
- Logiki modalne
7. Logiki nieklasyczne¶
Poza KRZ istnieją również inne rodzaje logik:
Logika trójwartościowa Łukasiewicza¶
- Wprowadza trzecią wartość logiczną: nieokreśloność
Logika rozmyta (fuzzy logic)¶
- Wartości prawdziwości wyrażane liczbami z przedziału od 0 do 1
- Pozwala na stopniowanie prawdziwości i fałszywości
- Przydatna do modelowania nieprecyzyjnych pojęć
Logika modalna¶
- Rozwijana przez Lewisa i Kripkego
- Rozszerza język o operatory modalne: "zawsze", "koniecznie", "możliwe, że"
Logika intuicjonistyczna¶
- Odrzuca ogólną akceptację prawa wyłączonego środka
- Wymaga konstruktywnego uzasadnienia istnienia
8. Wkład historyczny¶
- George Boole - opracował algebraiczną teorię zdań (logika Boole'owska) w XIX wieku
- Ludwig Wittgenstein - spopularyzował analizę tabelaryczną w "Traktacie logiczno-filozoficznym" (1921)
- Emil Post - niezależnie zaprojektował metodę wartościowania zdań
- Twierdzenie Gödla o zupełności - tautologie da się wyprowadzić z aksjomatów za pomocą określonych reguł dowodzenia
- System aksjomatów Hilberta, Rachunek sekwensów Gentzena - komplementarne systemy aksjomatyczne