Wstep.pdf

Wykłady ze Wst epu do Matematyki

Jacek Cicho n

WPPT, Politechnika Wrocławska

WRZESIE N 2010

Spis tresci

1 Rachunek Zda n 7

1.1 Zdania i waluacje . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2 Przegl ad tautologii . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3 Metody dowodzenia twierdze n . . . . . . . . . . . . . . . . . . . . . 12

1.4 Notacja polska . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.5 Cwiczenia i zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 Zbiory 19

2.1 Aksjomat ekstensjonalnosci . . . . . . . . . . . . . . . . . . . . . . . 19

2.2 Operacje mnogosciowe . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3 Diagramy Venna . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.4 Cwiczenia i zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3 Kwantyﬁkatory 31

3.1 Deﬁnicja kwantyﬁkatorów . . . . . . . . . . . . . . . . . . . . . . . 31

3.2 Własnosci kwantyﬁkatorów . . . . . . . . . . . . . . . . . . . . . . . 32

3.3 Kwantyﬁkatory ograniczone . . . . . . . . . . . . . . . . . . . . . . 36

3.4 Działania uogólnione . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.5

4 Relacje i funkcje 42

4.1 Podstawowe klasy relacji . . . . . . . . . . . . . . . . . . . . . . . . 43

4.2 Reprezentacja macierzowa . . . . . . . . . . . . . . . . . . . . . . . 44

4.3 Funkcje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.4 Funkcje logiczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.5 Obrazy i przeciwobrazy . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.6 Indeksowane rodziny zbiorów . . . . . . . . . . . . . . . . . . . . . 50

4.7 Produkty kartezja nskie . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.8 Funkcje charakterystyczne . . . . . . . . . . . . . . . . . . . . . . . 51

4.9 Cwiczenia i zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5 Relacje równowaznosci 55

5.1 Rozbicia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.2 Konstruowanie obiektów matematycznych . . . . . . . . . . . . . . . 57

5.3 Cwiczenia i zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6 Czesciowe porz adki 62

6.1 Wyróznione elementy . . . . . . . . . . . . . . . . . . . . . . . . . . 63

6.2 Porz adki na rodzinach funkcji . . . . . . . . . . . . . . . . . . . . . 65

Cwiczenia i zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

6.3 Liniowe porz adki . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.4 Lemat Kuratowskiego-Zorna . . . . . . . . . . . . . . . . . . . . . . 69

6.5 Dobre porz adki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

6.6 Cwiczenia i zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

7 Indukcja matematyczna 75

7.1 Deﬁnicje rekurencyjne . . . . . . . . . . . . . . . . . . . . . . . . . 75

7.2 Zbiory sko nczone . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

7.3 Permutacje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

7.4 Symbol Newtona . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

7.5 Zasada Dirichleta . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

7.6

8 Teoria mocy 87

8.1 Twierdzenia Cantora . . . . . . . . . . . . . . . . . . . . . . . . . . 88

8.2 Zbiory przeliczalne . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

8.3 Zbiory mocy continuum . . . . . . . . . . . . . . . . . . . . . . . . 92

8.4 Algebra mocy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

8.5 Funkcje obliczalne . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

8.6 Cwiczenia i zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

9 Drzewa i relacje ufundowane 100

9.1 Relacje ufundowane . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

9.2 Systemy przepisuj ace . . . . . . . . . . . . . . . . . . . . . . . . . . 101

9.3 Drzewa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

9.4 Cwiczenia i zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

A Algebry Boole’a 107

A.1 Ciała zbiorów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

A.2 Ideały i ﬁltry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

A.3 Twierdzenie o reprezentacji . . . . . . . . . . . . . . . . . . . . . . . 115

A.4

B Kraty i drzewa 118

B.1 Kraty zupełne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

B.2 Tablice semantyczne . . . . . . . . . . . . . . . . . . . . . . . . . . 121

B.3 Cwiczenia i zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

C Aksjomaty teorii mnogosci 126

C.1 Aksjomaty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

C.2 O niesprzecznosci . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

C.3 Zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

D Liczby porz adkowe i kardynalne 132

D.1 Indukcja pozasko nczona . . . . . . . . . . . . . . . . . . . . . . . . 134

D.2 Funkcja Hartogsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

D.3 Liczby kardynalne . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

D.4 Potegowanie liczb kardynalnych . . . . . . . . . . . . . . . . . . . . 140

D.5 Zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

E Wskazówki do zada n

146

Cwiczenia i zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

Cwiczenia i zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

Bibliograﬁa

151

Indeks

152

Wstep

Ksi azka zawiera dziewiec wykładów poswieconych omówieniu oraz uporz adkowaniu

podstawowych pojec matematycznych. Ich tresc odpowiada w przyblizeniu wykła-

dom ze “Wstepu do Matematyki”, które autor wielokrotnie prowadził dla studentów

Instytutu Matematycznego Uniwersytetu Wrocławskiego oraz Wydziału Podstawo-

wych Problemów Techniki Politechniki Wrocławskiej. Autor pragnie gor aco podzie-

kowac prof. B. Weglorzowi oraz prof W. Kordeckiemu za szereg uwag, które pomogły

uporz adkowac i unowoczesnic materiał. Dziekuje równiez studentom WPPT PWr za

pomoc w eliminowaniu usterek z wczesniejszych wersji tej ksi azki.

Główna czesc ksi azki odpowiada zakresowi materiału który obowi azywał wszy-

stkich studentów i ten zakres materiału powinien dobrze opanowac kazdy student in-

formatyki i matematyki. Czesci ksi azki umieszczone w dodatkach stanowi a rozsze-

rzenie podstawowego kursu.

1. W wykładzie pierwszym omawiamy podstawowe pojecia Rachunku Zda n. Wy-

kład opieramy na pojeciu waluacji, ze wzgledu na liczne, zwłaszcza w informa-

tyce, zastosowania uogólnie n tego pojecia. Głównym celem tego wykładu jest

przegl ad podstawowych tautologii oraz wprowadzeniu pojecia reguły wniosko-

wania.

2. W wykładzie drugim zajmujemy sie Rachunkiem Zbiorów. Rozwazania opie-

ramy o Aksjomat Ekstensjonalnosci. Pierwszym dowodzonym przez nas faktem

jest twierdzenie Russell’a o nie istnieniu zbioru wszystkich zbiorów. Nastepnie

omawiamy własnosci sumy, przekroju i róznicy zbiorów. Wszystkie dowody

sprowadzamy do Rachunku Zda n.

3. W wykładzie trzecim zajmujemy sie własnosciami kwantyﬁkatorów W tym

miejscu wykład traci nieco na precyzji. Interpretacje kwantyﬁkatorów redu-

kujemy do Rachunku Zbiorów. Z bardziej precyzyjnym wprowadzenie do Ra-

chunku Predykatów studenci zapoznaj a sie na wykładzie z Logiki Matematycz-

nej lub Logiki Algorytmicznej. Elementem wymagaj acym szczególnej uwagi s a

uzasadnienia zaleznosci pomiedzy wyrazeniami zbudowanymi z bloku dwóch

kwantyﬁkatorów. W wykładzie tym omawiamy równiez pojecie sumy i prze-

kroju dowolnej rodziny zbiorów.

4. Wykład czwarty poswiecamy relacjom. Deﬁniujemy podstawowe klasy rela-

cji, w tym pojecie funkcji. Zajmujemy sie obrazami i przeciwobrazami zbio-

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: