Kazimierz Trzęsicki
Logika
i
teoria mnogości
Ujęcie systematyczno-historyczne
Białystok 2001
2 Spis treści
Spis treści
Przedmowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
0. O logice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
0.1. Nazwa  logika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
0.2. Podstawowe pojęcia i problemy logiki . . . . . . . . . . . . 11
0.2.1. Pojęcie zdania i prawdziwości . . . . . . . . . . . . . . . . . . . . . . . . 11
0.2.2. Pojęcie wynikania semantycznego, syntaktycznego
i rachunku logicznego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1. Klasyczna logika zdań . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.0. Założenia klasycznego rachunku zdań . . . . . . . . . . . . 19
1.1. Tautologie i zdania logicznie prawdziwe . . . . . . . . . 20
1.1.1. Pojęcie spójnika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.1.2. Alfabet języka klasycznej logiki zdań . . . . . . . . . . . . . . . . .21
1.1.3. Definicja zdania (wyrażenia poprawnie zbudowanego
logiki zdań) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22
1.1.3.1. Zdanie w notacji standardowej . . . . . . . . . . . . . . . . . . . . 22
1.1.3.2. Notacja łukasiewiczowska . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.1.3.3. Indukcyjny charakter definicji zdania . . . . . . . . . . . . . . 28
1.1.4. Model i prawdziwość . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.1.5. Tautologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.1.6. Wybrane tautologie klasycznej logiki zdań . . . . . . . . . . . 40
1.1.7. Tablice semantyczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
1.1.8. Elektronowa interpretacja spójników zdaniowych . . . .56
1.1.9. Tautologia a zdanie logicznie prawdziwe . . . . . . . . . . . . . 58
1.1.10. Spójniki prawdziwościowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
1.1.11. Funkcjonalna pełność . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
1.1.12. Postacie normalne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .65
1.2. Wynikanie syntaktyczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
1.2.1. Dowód w rachunku zdań . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71
1.2.2. Operacja konsekwencji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
1.2.3. Twierdzenie o dedukcji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
1.2.4. Sprzeczne i niesprzeczne zbiory zdań . . . . . . . . . . . . . . . . . 78
1.2.5. Maksymalne niesprzeczne zbiory zdań . . . . . . . . . . . . . . . 83
1.3. Wynikanie syntaktyczne a wynikanie seman-
tyczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
1.3.1. Pełność rachunku zdań . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .89
1.3.2. Wynikanie semantyczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91
1.3.3. Reguły, schematy i prawa logiki . . . . . . . . . . . . . . . . . . . . . . 94
1.4. Systemy logiki zdań . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .100
1.4.1. Aksjomatyczny system rachunku zdań . . . . . . . . . . . . . . 101
1.4.2. Dedukcja naturalna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
1.4.3. Rachunek sekwentów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
2. Klasyczna logika predykatów . . . . . . . . . . . . . . . . . . . . . . . . 115
2.1. Język rachunku predykatów . . . . . . . . . . . . . . . . . . . . . . . . 115
2.1.1. Dziedzina . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .115
2.1.2. Stałe i zmienne indywiduowe . . . . . . . . . . . . . . . . . . . . . . . . 119
2.1.3. Litery funkcyjne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
2.1.4. Definicja termu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
2.1.5. Litery predykatowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
2.1.6. Definicja formuły . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
2.1.7. Podstawialność . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .128
2.2. Klasyczny rachunek predykatów . . . . . . . . . . . . . . . . . . 131
2.2.1. Dowód w rachunku predykatów . . . . . . . . . . . . . . . . . . . . . 131
4 Spis treści
2.2.2. Niesprzeczność rachunku predykatów . . . . . . . . . . . . . . . 140
2.2.3. Twierdzenie o dedukcji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
2.2.4. Tablice semantyczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
2.2.5. Dedukcja naturalna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
2.2.6. Rachunek sekwentów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
2.3. Model i prawdziwość . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
2.3.1. Pojęcie interpretacji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
2.3.2. Definicja modelu i spełniania . . . . . . . . . . . . . . . . . . . . . . . .158
2.3.3. Reguły rachunku predykatów a prawdziwość . . . . . . . 179
2.4. Pełność rachunku predykatów . . . . . . . . . . . . . . . . . . . . . 186
2.5. Twierdzenia interpolacyjne . . . . . . . . . . . . . . . . . . . . . . . . . 196
3. Definiowanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
3.0. Pojęcie definiowania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
3.1. Definiowanie liter predykatowych . . . . . . . . . . . . . . . . .206
3.2. Definiowanie stałych indywiduowych . . . . . . . . . . . . 210
3.3. Definiowanie liter funkcyjnych . . . . . . . . . . . . . . . . . . . . .215
3.4. Definiowalnośc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
4. Systemy sformalizowanie i arytmetyka . . . . . . . . . . . 229
4.1. Pojęcie systemu sformalizowanego . . . . . . . . . . . . . . . . . . . . . . 229
4.2. Liczby naturalne i indukcja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
4.2.1. Aksjomatyka Peano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
4.2.2. Indukcja matematyczna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
4.2.3. Definicja indukcyjna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .250
5. Algebra zbiorów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
5.0. Początki teorii mnogości . . . . . . . . . . . . . . . . . . . . . . . . . . . . .253
5.1. Zbiór i element zbioru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
5.2. Równość zbiorów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
5.3. Zawieranie się zbiorów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .265
5.4. Operacje na zbiorach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
5.4.1. Dopełnienie zbioru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
5.4.2. Suma zbiorów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
5.4.3. Iloczyn zbiorów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
5.4.4. Różnica i różnica symetryczna zbiorów . . . . . . . . .273
5.4.5. Związki między działaniami teoriomnogościowymi
274
5.4.6. Uogólnione suma i iloczyn zbiorów . . . . . . . . . . . . . 275
5.5. Aksjomaty algebry zbiorów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
6. Produkty kartezjańskie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
6.0. Pojęcie produktu kartezjańskiego zbiorów . . . . . . . . . . 289
6.1. Relacja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
6.1.1. Pojęcie relacji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
6.1.2. Relacja zwrotna i przeciwzwrotna . . . . . . . . . . . . . . . . 300
6.1.3. Relacje symetryczna, przeciwsymetryczna i anty-
symetryczna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
6.1.4. Relacja przechodnia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .303
6.1.5. Relacja równoważności . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
6.1.6. Rachunek relacji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
6.2. Funkcja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .320
6.2.1. Pojęcie funkcji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
6.2.2. Funkcja odwrotna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .326
6.2.3. Superpozycja funkcji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
6.2.4. Obrazy i przeciwobrazy . . . . . . . . . . . . . . . . . . . . . . . . . . 332
6.3. Uogólnione produkty kartezjańskie . . . . . . . . . . . . . . . . . .345
7. Moce zbiorów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
7.1. Zbiory równoliczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .347
7.2. Zbiory przeliczalne i nieprzeliczalne . . . . . . . . . . . . . . . . . 354
6 Spis treści
7.3. Arytmetyka liczb kardynalnych . . . . . . . . . . . . . . . . . . . . . 362
7.4. Zbiory mocy continuum. Zbiór potęgowy . . . . . . . . . . . 371
8. Uporządkowanie zbiorów . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
8.1. Zbiory uporządkowanee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .379
8.2. Zbiory liniowo uporządkowane . . . . . . . . . . . . . . . . . . . . . . 392
8.2.1. Relacje liniowo porządkujące . . . . . . . . . . . . . . . . . . . . . 392
8.2.2. Podobieństwo zbiorów liniowo uporządkowanych . 394
8.2.3. Uporządkowanie liniowe gęste . . . . . . . . . . . . . . . . . . . . 398
8.2.4. Uporządkowanie liniowe ciągłe . . . . . . . . . . . . . . . . . . . 400
8.3. Zbiory dobrze uporządkowane . . . . . . . . . . . . . . . . . . . . . . . 402
8.3.1. Relacje dobrze porządkujące . . . . . . . . . . . . . . . . . . . . . 402
8.3.2. Porównywanie liczb porządkowych . . . . . . . . . . . . . . . 404
Bibliografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ???
Indeks rzeczowy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ???
Aneks: Projekt MIZAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413