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