5600235752

Matematyka dyskretna

Mariusz Żynel 26 maja 2015

Spis treści

1    Relacje    2

1.1    Własności................................. 2

1.2    Iloczyn kartezjański ........................... 2

1.3    Relacje................................... 3

1.4    Własności relacji............................. 3

1.5    Relacje równoważności i klasy abstrakcji................ 4

2    Funkcje    7

3    Równoliczność zbiorów    8

4    Indukcja matematyczna    8

4.1    Zasada minimum............................. 8

4.2    Zasada indukcji.............................. 9

4.3    Zasada indukcji zupełnej......................... 10

4.4    Zasada maksimum............................ 10

5    Rekurencja    11

5.1    Ciąg arytmetyczny............................ 11

5.2    Ciąg geometryczny............................ 11

5.3    Silnia ................................... 12

5.4    Ciąg Fibonacciego............................ 12

5.5    Wieże Hanoi ............................... 12

6    Metody zliczania zbiorów i funkcji    13

6.1    Zasada mnożenia............................. 13

6.2    Zasada dodawania............................ 14

6.3    Metoda włączania-wyłączania...................... 14

6.4    Zasada szufladkowa Dirichleta...................... 15

6.5    Zliczanie funkcji ............................. 16

6.6    Zliczanie podzbiorów........................... 17

7    Per mutacje    17

7.1    Cykle ................................... 18

7.2    Transpozycje............................... 19

1