ZACHODNIOPOMORSKI UNIWERSYTET TECHNOLOGICZNY
W SZCZECINIE
MATEMATYKA DYSKRETNA
Wykład 4: Funkcje
Prowadzący Wykłady: dr inż. Larisa Dobryakova
2011
Funkcje jako relacje (1)
Relację binarną �� �� X ��Y nazywamy funkcją, jeśli spełnia ona następujący
warunek:
"�x �� X $�y ��Y :x ��y
.
"�x �� X "�y1,y ��Y :�� x ��y1 Ł� x ��y �� y1 =� y ł�
(� )�
2 2 2
����
Tradycyjnie dla oznaczenia funkcji używamy liter f ,g,h i zamiast pisać x ,y ��f
piszemy f x =� y .
(� )�
Przykład
Niech A =� a,b,c ,B =� 1,2,3 . Jakie z relacji f ,g,h są funkcjami?
{� }� {� }�
f =� a,1 , a,2 , b,3 , c,2
{� }�
g =� a,1 , b,2 , c,1
{� }�
h =� a,1 , c,2
{� }�
2
Funkcje jako relacje (2)
Dziedziną funkcji f (zbiorem argumentów funkcji) nazywamy zbiór Df lub D f
(� )�
określony warunkiem:
Df =� X =� x �� X : $�y y =� f x .
(� )�
{� }�
Przeciwdziedziną funkcji f (zbiorem wartości funkcji) nazywamy zbiór Wf lub
-�1
D f określony warunkiem:
(� )�
Wf =� y ��Y : $�x �� X y =� f x .
(� )�
{� }�
Oznaczenie f :X ��Y jest skrótem stwierdzenia:  f jest funkcją o dziedzinie X i
wartościach w zbiorze Y  . Czasami funkcję f nazywamy odwzorowaniem lub
przekształceniem i mówimy, ze przekształca ona zbiór X w zbiór Y .
3
Sposoby przedstawienia funkcji. Liczba funkcji
�� opis słowny
�� zbiór par
�� graf funkcji
�� tabelka
�� wykres
�� wzór
Dla niepustych, skończonych zbiorów X i Y jeśli zbiór X ma n elementów, a
zbiór Y ma m elementów, to istnieje mn różnych odwzorowań ze zbioru X do
zbioru Y , dlatego też zbiór wszystkich odwzorowań ze zbioru X do zbioru Y
X
oznaczany jest symbolem Y .
Przykład
Wyznaczyć wszystkie odwzorowania ze zbioru w zbiór .
A =� 1,2,5 B =� 4,7
{� }� {� }�
Ile ich jest?
4
Injekcja, surjekcja, bijekcja (1)
Odwzorowanie f :X ��Y nazywamy odwzorowaniem różnowartościowym
(funkcją różnowartościową, injekcją), jeżeli:
"�x1 �� X ,"�x2 �� X :��x1 ą� x2 �� f x1 ą� f x2 ł�
(� )� (� )���.
��
Równoważnie, korzystając z prawa kontrapozycji, można zapisać:
.
"�x1 �� X ,"�x2 �� X :��f x1 =� f x2 �� x1 =� x2 ł�
(� )� (� )�
����
Piszemy wtedy:
1-�1
f : X ����Y ,
czyli dla każdej wartości poprzednika x znajduje się w relacji f tylko jedna wartość
następnika y , i różne poprzedniki mają różne następniki.
UWAGA: Dla niepustych skończonych zbiorów X i Y aby istniała injekcja z X w Y ,
liczba elementów zbioru Y musi być nie mniejsza niż liczba elementów zbioru X .
5
Injekcja, surjekcja, bijekcja (2)
Odwzorowanie f :X ��Y nazywamy odwzorowaniem "na" (surjekcją), jeżeli:
"�y ��Y $�x �� X :��y =� f x .
��ł�
(� )���
Inaczej, odwzorowanie f :X ��Y jest "na ", gdy .
Wf =�Y
Oznacza się wzorem:
f :X ����Y ,
na
czyli relacja zachodzi dla wszystkich argumentów x ze zbioru X i dla wszystkich
wartości y ze zbioru Y .
UWAGA: Dla niepustych skończonych zbiorów X i Y aby istniała surjekcja z X
na Y , liczba elementów zbioru Y musi być nie większa niż liczba elementów
zbioru X .
6
Injekcja, surjekcja, bijekcja (3)
Odwzorowanie f :X ��Y , które jest jednocześnie różnowartościowe i "na "
nazywamy wzajemnie jednoznacznym (bijekcją).
Piszemy wtedy:
1-�1
f :X ����Y .
na
UWAGA: Dla niepustych skończonych zbiorów X i Y aby istniała bijekcja z X w Y ,
liczba elementów zbioru Y musi być równa liczbie elementów zbioru X .
Jeśli zbiory X i Y są skończone i liczba elementów zbioru X wynosi n , zaś liczba
elementów zbioru Y wynosi m,m ł� n to istnieje:
m !
m �� m -�1 ��...�� m -� n +� 1 =�
(� )� (� )�
m -� n !
(� )�
funkcji różnowartościowych (injekcji) z X do Y .
Jeśli zbiory X i Y są skończone i liczba elementów każdego ze zbiorów X i Y
wynosi n, to istnieje
n �� n -�1 ��...�� n -� n +�1 =� n !
(� )� (� )�
funkcji wzajemnie jednoznacznych (bijekcji) z X do Y .
7
Injekcja, surjekcja, bijekcja (4)
Przykład
Określić :
�� jakie relacje są funkcjami
�� jakie funkcje są injekcjami (odwzorowaniem różnowartościowym), surjekcjami
(odwzorowaniem "na "), bijekcjami (odwzorowaniem wzajemnie
jednoznacznym)?
(a) (b) (c) (d) (e)
a
a
a a a
1
1
1 1 1
b 2
b 2
b
b 2 2 b 2
c c c
3
c
3 3 3
8
Obraz i przeciwobraz
Niech f :X ��Y .
Jeśli x �� X , to element y =� f x , czyli wartość funkcji f na elemencie x nazywa się
(� )�
obrazem elementu x poprzez f .
Jeśli A �� X , to obrazem zbioru A w odwzorowaniu f nazywa się podzbiór
f A ��Y (albo: , f * A, Af ), wszystkich obrazów elementów tego zbioru, tzn.:
f A
[� ]� (� )�
f A =� y ��Y :$�x �� A y =� f x =� f x : x �� A .
[� ]� (� )� (� )�
{� }� {� }�
Jeśli B ��Y , to przeciwobrazem zbioru B w odwzorowaniu f nazywa się podzbiór
-�1 -�1 -�1
f B �� X (albo: f B , f * B ) elementów zbioru X , których obrazy należą do
[� ]� (� )�
zbioru B , tzn.:
-�1
f B =� x �� X :$�y ��B y =� f x .
[� ]� (� )�
{� }�
-�1
W przypadku, gdy zbiór B zawiera jeden element, np., , zbiór f B ma
B =� y
{� }� [� ]�
-�1
bardziej proste oznaczenie f y .
[� ]�
Przykład
Niech f : Ą� �� Ą� określona wzorem f x =� 2 �� x oraz A =� 3,4,7,11 ,B =� 1,4,5,8,14 .
(� )� {� }� {� }�
Wyznaczyć obraz zbioru A i przeciwobraz zbioru B .
9
Złożenie odwzorowań
Niech dane będą funkcję f : X ��Y oraz g :Y �� Z .
Dla każdego elementu x �� X istnieje dokładnie jeden element z �� Z , taki że:
z =� g f x .
(� )�
(� )�
Funkcje f i g wyznaczają nową funkcję h :X �� Z określoną w następujący sposób:
h x =� g f x dla "�x �� X .
(� )� (� )�
(� )�
Funkcję h nazywamy superpozycją lub złożeniem funkcji i oznaczamy
symbolem g o�f . Funkcję f przyjęto nazywać funkcją wewnętrzną, g zaś funkcją
zewnętrzną funkcji g o�f .
Złożenie funkcji ma takie same własności jak złożenie relacji, między innymi jest
łączne, tzn.: , i nie jest przemienne, czyli g o�f ą� f o� g .
h o� g o�f =� h o� g o�f
(� )� (� )�
Przykład
2
Niech f : Ą� �� Ą�,f x =� x i .
g : Ą� �� Ą�, g x =� 4 �� x +� 3
(� )� (� )�
Znalez
ć g o�f ,f o� g,f o�f ,g o� g.
10
Odwzorowanie odwrotne
Dla odwzorowania f : X ��Y określa się odwzorowanie odwrotne (funkcję
-�1
odwrotną) f :Y �� X , takie, że:
-�1
"�x �� X "�y ��Y f x =� y �� f y =� x .
(� )� (� )�
Twierdzenie. Funkcja f ma funkcję odwrotną wtedy i tylko wtedy, gdy jest ona
bijekcją.
UWAGA: pojęcie funkcji odwrotnej pokrywa się z pojęciem przeciwobrazu wtedy i
tylko wtedy, gdy odwzorowanie f jest wzajemnie jednoznaczne (bijekcją).
Przykład
x
Niech i f : A �� A, f x =� .
A =� x :x �� Ą� Ł� x ą� 1
(� )�
{� }�
x -�1
Pokazać, że f jest odwzorowaniem wzajemnie jednoznacznym (bijekcją) i znalez
ć
funkcję odwrotną.
11
Zasada Dirichleta
Niech A i B będą dowolnymi zbiorami skończonymi, przy czym A >� B .
Wówczas dla dowolnej funkcji f : A �� B co najmniej jedna wartość f pojawi się
więcej, niż jeden raz.
Inaczej mówiąc, istnieje co najmniej jedna para elementów ai ,a �� A, dla których
j
f ai =� f a .
(� )�
(� )�
j
Przykład 1
W autobusie jadą 15 osób. Pokazać, że u co najmniej dwóch z nich urodziny są w
tym samym miesiącu.
Przykład 2
Pokazać, że wybierając przypadkowo pięć cyfry z 1,2,3,4,5,6,7,8, znajdzie się wśród
nich co najmniej dwie, suma których jest równa 9.
12
Uogólnienie zasady Dirichleta
Niech f : A �� B , gdzie A i B są zbiory skończone.
Jeśli A >� k �� B ,k �� Ą�
, to znajdzie się taka wartość funkcji f , którą funkcja ta będzie
przyjmować co najmniej k +�1 razy.
Nie zawsze można łatwo obliczyć liczbę elementów w zbiorach, więc istnieją
specjalne metody obliczenia mocy zbiorów skończonych, elementy których wybierają
się pewnymi sposobami. Zajmuje się tym Kombinatoryka.
13