Metody logiki. Dedukcja / Andrzej Indrzejczak, Marek Nowak

Metody logiki. Dedukcja to pierwsza publikacja z planowanego cyklu poświęconego najważniejszym metodom i technikom wypracowanym na gruncie nowoczesnej logiki formalnej. W dostępnych monografiach i podręcznikach z zakresu logiki zazwyczaj więcej uwagi poświęcano prezentacji materiału teoretycznego. a zamieszczano zbyt mało wskazówek pokazujących. w jaki sposób konstruować dowody. Niniejsza książka i cały planowany cykl mają wypełnić tę lukę w polskim piśmiennictwie logicznym.

Autorzy opracowania przedstawiają rozmaite sposoby konstrukcji dowodów metodą dedukcji naturalnej (założeniową) w logice klasycznej. arytmetyce liczb naturalnych i teorii mnogości. Dedukcja naturalna zaprezentowana jest najpierw w sposób formalny. na przykładach z logiki klasycznej, a następnie zastosowana w nieformalnej postaci do dowodzenia tez w teoriach matematycznych. Za pomocą bogatego materiału ilustracyjnego omówiono różne strategie i techniki dowodzenia, takie jak: wprost, nie wprost, dowody warunkowe i rozgałęzione oraz dowody z wykorzystaniem indukcji matematycznej.

Wstęp 9

1 Dowodzenie w logice klasycznej 13

1.1 Klasyczny rachunek zdań 13

1.1.1 Język KRZ 13

1.1.2 Aksjomatyzacja KRZ 16

1.1.3 Dowód 17

1.2 Dedukcja naturalna 20

1.2.1 Pierwotne reguły inferencji 20

1.2.2 Proste dedukcje 21

1.2.3 Dowody założeniowe wprost 23

1.2.4 Dowodzenie nie wprost 24

1.2.5 Dowody a dedukcje 26

1.2.6 Równoważności 28

1.3 Zaawansowana dedukcja 29

1.3.1 Stosowanie założeń dodatkowych 29

1.3.2 Poddowody warunkowe 30

1.3.3 Poddowody nie wprost 32

1.3.4 Poddowody wielokrotne i zagnieżdżone 33

1.4 Dodatkowe środki dowodowe 36

1.4.1 Reguły wtórne 36

1.4.2 Reguły obustronne 38

1.4.3 Dodatkowe reguły konstrukcji dowodu 42

1.4.4 Dodatkowe sposoby dowodzenia równoważności 45

1.5 Klasyczny rachunek kwantyfikatorów 47

1.5.1 Języki pierwszego rzędu 48

1.5.2 Zmienne wolne i związane 51

1.5.3 Podstawianie i zastępowanie 52

1.6 Dowodzenie w rachunku kwantyfikatorów 54

1.6.1 Reguły inferencji dla ∀ i ∃ 54

1.6.2 Reguły konstrukcji dowodu dla kwantyfikatorów 58

1.6.3 Reguły wtórne 62

1.6.4 Reguły dla identyczności 64

1.7 Uwagi końcowe 68

1.7.1 Strategie dowodzenia 68

1.7.2 Dowody nieformalne 72

2 Dowodzenie w arytmetyce liczb naturalnych i teorii zbiorów      75

2.1 Arytmetyka elementarna 75

2.1.1 Aksjomaty 75

2.1.2 Dowody indukcyjne 76

2.2 Arytmetyka liczb naturalnych z dodawaniem 77

2.2.1 Aksjomaty i podstawowe własności dodawania 77

2.2.2 Relacja porządku 81

2.3 Arytmetyka z dodawaniem i mnożeniem 84

2.3.1 Aksjomaty i podstawowe własności mnożenia 84

2.4 Teoria mnogości 86

2.4.1 Naiwna teoria zbiorów 86

2.4.2 Paradoks Russella 88

2.5 Teoria zbiorów Zermelo-Fraenkla 89

2.5.1 Aksjomaty teorii mnogości ZF (bez aksjomatów ufundowania i wyboru) 89

2.5.2 Inkluzja zbiorów 93

2.5.3 Zbiór pusty 95

2.5.4 Zbiór potęgowy zbioru 97

2.5.5 Suma zbioru 98

2.5.6 Para zbiorów, zbiór jednoelementowy 99

2.5.7 Operacje boolowskie na zbiorach, zbiór n-elementowy        100

2.5.8 Przekrój zbioru niepustego 105

2.6 Algebra Boole’a zbiorów 107

2.6.1 Ciało zbiorów 107

2.6.2 Algebra Boole’a 110

2.7 Relacje i funkcje 112

2.7.1 Para uporządkowana. Produkt kartezjański dwóch zbiorów 112

2.7.2 Relacje binarne 115

2.7.3 Funkcje 119

2.8 Zbiory ufundowane 126

2.8.1 Teoria ZF − z aksjomatem Ω 127

2.8.2 Aksjomat regularności (ufundowania) 136

2.9 Interpretacja arytmetyki elementarnej w teorii ZF 137

2.9.1 Operacja następnika 137

2.9.2 Indukcja 139

Bibliografia 143