« poprzedni punkt | następny punkt » |
Definicja 3.2
Powiemy, że funkcja f : X ® Y jest odwzorowaniem różnowartościowym, krótko f : X ® 1-1Y, jeżeli różnym argumentom przypisuje różne wartości, tzn.
jeśli x1¹ x2, to f(x1)¹ f(x2) dla dowolnych x1, x2 Î X.
Tę samą własność możemy zapisać inaczej w postaci warunku: dla dowolnych x1, x2 Î X,
jeśli f(x1) = f(x2), to x1= x2 dla dowolnych x1, x2 Î X.
Funkcje różnowartościowe nazywamy inaczej injekcjami. Przykładem funkcji różnowartościowej jest funkcja przedstawiona na rysunku 3.4a. Natomiast funkcja schodkowa przedstawiona na rysunku 3.4b nie jest różnowartościowa, bo np. dla wszystkich argumentów z przedziału (0,1] przyjmuje tę samą wartość 1.
Zwróćmy uwagę, że aby udowodnić, że dana funkcja f jest różnowartościowa, musimy wykazać, że dla dowolnej pary elementów x1, x2 z dziedziny funkcji, f(x1) ma inną wartość niż f(x2). Natomiast dowód, że funkcja nie jest różnowartościowa, wymaga znalezienia tylko jednej pary (tzw. kontrprzykładu), która nie spełnia warunku definicji.
Pytanie 2: Która z funkcji przedstawionych w przykładzie 3.1 jest różnowartościowa?
Definicja 3.3
Powiemy, że funkcja f : X ® Y jest odwzorowaniem "na" zbiór Y wtedy i tylko wtedy, gdy każdy element zbioru Y jest wartością funkcji, tzn.
dla dowolnego y Î Y istnieje x Î X, że f(x) = y.
Inaczej mówiąc, funkcja jest "na", jeżeli jej zbiorem wartości jest zbiór Y, Im(f) = Y. O takiej funkcji mówimy, że jest surjekcją i zapisujemy ten fakt krótko w postaci f : X ® naY.
Przykład 3.4
-(x2 + 1) £ 2x oraz 2x £ x2 + 1
z czego wynika, że -1 £ 2x/(x2 +1) £ 1. Ponieważ 2x/(x2 +1) jest funkcją ciągłą, zatem przyjmuje wszystkie wartości z przedziału [-1, 1].
Funkcję f: X ® Y, która jest równocześnie różnowartościowa i "na" nazywamy wzajemnie jednoznaczną lub bijekcją.
W dalszym ciągu wykładu będą nas interesowały pewne szczególne funkcje (ciągi) różnowartościowe i "na" określone na zbiorze X i o wartościach w zbiorze X. Na przykład ciąg p = (3,4,5,6,0,1,2) jest funkcją p określoną na zbiorze {0,1,2,...,6}, której wartości określone wzorem p(i) = (i+3) mod 7 wyczerpują zbiór {0,1,2,...,6}. Tego typu funkcje nazywać będziemy permutacjami.
Przykład 3.5
Każdą liczbę naturalną możemy przedstawić w postaci ciągu cyfr w systemie dziesiętnym lub w innym, np. dwójkowym(binarnym), ósemkowym itd. Na przykład 12 = (1100)2 = (14) 8 = (110) 3. Funkcja bin : N® {0,1}* , która każdej liczbie naturalnej przypisuje jej reprezentację w systemie dwójkowym, jest funkcją wzajemnie jednoznaczną :
if n=0 then bin(n):= (0) else
i := 0; while n >0 do ai := n mod 2; n := n div 2; i := i+1 od;
bin(n):= (ai-1, ai-2,..., a0);
fi
Pytanie 3: Czy funkcja f : N-{0} ® N określona wzorem f(n) = n * ë lg nû dla n>0 jest odwzorowaniem "na" zbiór liczb naturalnych (ë lg nû oznacza część całkowitą logarytmu przy podstawie 2 z n)?
Zadanie 2
Zaprojektuj algorytm, który znajduje reprezentację trójkową dowolnej liczby naturalnej.
« poprzedni punkt | następny punkt » |