Elementy logiki i teorii mnogosci- ksiazka.pdf

(1368 KB) Pobierz
80398765 UNPDF
Elementy logiki i teorii mnogo±ci
Kazimierz Trz¦sicki
2006
4
Wyd. II poprawione i zmienione. Wersja elektroniczna.
Spis tre±ci
1 Logika zda« 11
1.1 Poj¦cie logiki . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 J¦zyk logiki zda« . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.1 Poj¦cie j¦zyka logiki zda« . . . . . . . . . . . . . . . . 14
1.2.2 Definicja zdania . . . . . . . . . . . . . . . . . . . . . . 15
1.2.3 J¦zyk formalny . . . . . . . . . . . . . . . . . . . . . . 18
1.2.4 J¦zyk a metaj¦zyk . . . . . . . . . . . . . . . . . . . . 23
1.2.5 Rekurencyjny charakter definicji zdania . . . . . . . . . 25
1.2.6 Model i prawdziwo±¢ . . . . . . . . . . . . . . . . . . . 28
1.3 Rachunek zda« . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.3.1 Tautologia . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.3.2 Wybrane tautologie klasycznej logiki zda« . . . . . . . 37
1.3.3 Tablice semantyczne . . . . . . . . . . . . . . . . . . . 41
1.3.4 Tautologia a zdanie logicznie prawdziwe . . . . . . . . 51
1.3.5 Spójniki prawdziwo±ciowe . . . . . . . . . . . . . . . . 53
1.3.6 Funkcjonalna pełno±¢ . . . . . . . . . . . . . . . . . . . 56
1.3.7 Postacie normalne . . . . . . . . . . . . . . . . . . . . 58
1.3.8 Elektroniczna interpretacja spójników . . . . . . . . . . 61
1.3.9 Dowód w rachunku zda« . . . . . . . . . . . . . . . . . 64
1.3.10 Twierdzenie o dedukcji . . . . . . . . . . . . . . . . . . 67
1.3.11 Sprzeczne i niesprzeczne zbiory zda« . . . . . . . . . . 70
1.3.12 Wynikanie syntaktyczne a wynikanie semantyczne . . . 70
1.3.13 Reguły, schematy i prawa logiki . . . . . . . . . . . . . 72
1.3.14 Systemy logiki zda« . . . . . . . . . . . . . . . . . . . . 78
2 Logika predykatów 95
2.1 J¦zyk rachunku predykatów . . . . . . . . . . . . . . . . . . . 95
2.1.1 Dziedzina . . . . . . . . . . . . . . . . . . . . . . . . . 95
5
6
SPIS TRECI
2.1.2 Stałe i zmienne indywiduowe . . . . . . . . . . . . . . . 96
2.1.3 Litery funkcyjne . . . . . . . . . . . . . . . . . . . . . . 97
2.1.4 Term . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
2.1.5 Litery predykatowe . . . . . . . . . . . . . . . . . . . . 99
2.1.6 Formuła . . . . . . . . . . . . . . . . . . . . . . . . . . 100
2.1.7 Podstawialno±¢ . . . . . . . . . . . . . . . . . . . . . . 105
2.2 Rachunek predykatów . . . . . . . . . . . . . . . . . . . . . . 106
2.2.1 Dowód w rachunku predykatów . . . . . . . . . . . . . 106
2.2.2 Twierdzenie o dedukcji . . . . . . . . . . . . . . . . . . 115
2.2.3 Postacie normalne . . . . . . . . . . . . . . . . . . . . 120
2.2.4 Tablice semantyczne . . . . . . . . . . . . . . . . . . . 128
2.2.5 Dedukcja naturalna . . . . . . . . . . . . . . . . . . . . 135
2.2.6 Model i prawdziwo±¢ . . . . . . . . . . . . . . . . . . . 138
2.2.7 Pełno±¢ rachunku predykatów . . . . . . . . . . . . . . 153
2.2.8 Problem rozstrzygalno±ci . . . . . . . . . . . . . . . . . 154
3 Algebra zbiorów 161
3.1 Zbiór i element zbioru . . . . . . . . . . . . . . . . . . . . . . 161
3.2 Równo±¢ zbiorów . . . . . . . . . . . . . . . . . . . . . . . . . 167
3.3 Zawieranie si¦ zbiorów . . . . . . . . . . . . . . . . . . . . . . 170
3.4 Operacje na zbiorach . . . . . . . . . . . . . . . . . . . . . . . 173
3.4.1 Dopełnienie zbioru . . . . . . . . . . . . . . . . . . . . 173
3.4.2 Suma zbiorów . . . . . . . . . . . . . . . . . . . . . . . 175
3.4.3 Przeci¦cie zbiorów . . . . . . . . . . . . . . . . . . . . 177
3.4.4 Ró»nica i ró»nica symetryczna zbiorów . . . . . . . . . 179
3.4.5 Zwi¡zki mi¦dzy działaniami teoriomnogo±ciowymi . . . 180
3.4.6 Uogólnione suma i przeci¦cie zbiorów . . . . . . . . . . 183
3.5 Aksjomaty algebry zbiorów . . . . . . . . . . . . . . . . . . . . 186
4 Relacje i funkcje 191
4.1 Iloczyn kartezja«ski zbiorów . . . . . . . . . . . . . . . . . . . 191
4.2 Relacje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
4.2.1 Poj¦cie relacji . . . . . . . . . . . . . . . . . . . . . . . 196
4.2.2 Relacje zwrotna i przeciwzwrotna . . . . . . . . . . . . 200
4.2.3 Relacje symetryczna, przeciwsymetryczna i antysyme-
tryczna . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
4.2.4 Relacja przechodnia . . . . . . . . . . . . . . . . . . . . 205
4.2.5 Relacja równowa»no±ci . . . . . . . . . . . . . . . . . . 207
SPIS TRECI
7
4.3 Rachunek relacji . . . . . . . . . . . . . . . . . . . . . . . . . . 218
4.4 Funkcja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
4.4.1 Poj¦cie funkcji . . . . . . . . . . . . . . . . . . . . . . . 222
4.4.2 Funkcja odwrotna . . . . . . . . . . . . . . . . . . . . . 228
4.4.3 Superpozycja funkcji . . . . . . . . . . . . . . . . . . . 231
4.4.4 Obrazy i przeciwobrazy . . . . . . . . . . . . . . . . . . 233
4.5 Uogólniony iloczyn kartezja«ski . . . . . . . . . . . . . . . . . 236
4.6 Uporz¡dkowanie zbiorów . . . . . . . . . . . . . . . . . . . . . 237
4.6.1 Zbiory uporz¡dkowane . . . . . . . . . . . . . . . . . . 237
4.6.2 Zbiory liniowo uporz¡dkowane . . . . . . . . . . . . . . 244
4.6.3 Zbiory dobrze uporz¡dkowane . . . . . . . . . . . . . . 247
5 Moce zbiorów 249
5.1 Równoliczno±¢ zbiorów . . . . . . . . . . . . . . . . . . . . . . 249
5.2 Zbiory przeliczalne i nieprzeliczalne . . . . . . . . . . . . . . . 253
5.3 Arytmetyka liczb kardynalnych . . . . . . . . . . . . . . . . . 263
5.4 Zbiory mocy continuum . . . . . . . . . . . . . . . . . . . . . 276
5.5 Zbiór pot¦gowy . . . . . . . . . . . . . . . . . . . . . . . . . . 282

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin