Читать книгу Wprowadzenie do teorii obliczeń - Michael Sipser - Страница 21

Funkcje są podstawą matematyki. Funkcja jest obiektem definiującym relację wejście-wyjście. Przyjmuje dane wejściowe (argument) i zwraca wynik (wartość, inaczej wyjście funkcji). W każdej funkcji ten sam argument musi zawsze zwrócić tę samą wartość. Jeśli f jest funkcją, której wartość wyjściowa wynosi b dla argumentu a, zapisujemy to jako

f(a) = b.

Funkcja bywa również nazywana odwzorowaniem: jeśli f(a) = b, mówimy, że f odwzorowuje a na b.

Na przykład funkcja wartości bezwzględnej abs przyjmuje liczbę x jako wejście i zwraca x, jeśli x jest liczbą dodatnią, oraz −x, jeśli x jest ujemne. Tym samym abs(2) = abs(−2) = 2. Innym przykładem funkcji może być dodawanie, które zapiszemy jako add. Wejściem dla funkcji dodawania jest uporządkowana para liczb, a wyjściem (wartością) jest suma tych liczb.

Zbiór możliwych wartości wejściowych funkcji nazywamy jej dziedziną. Wyniki (wartości wyjściowe) należą do zbioru określonego jako przeciwdziedzina (zbiór wartości) funkcji. Stwierdzenie, że f jest funkcją o dziedzinie D i wartościach ze zbioru W, zapisujemy jako

f : D → W.

W przypadku funkcji abs, gdybyśmy ograniczyli się do liczb całkowitych, zarówno dziedziną, jak i przeciwdziedziną jest Z, zatem możemy napisać abs : Z → Z. W przypadku funkcji dodawania liczb całkowitych dziedziną jest zbiór par liczb całkowitych Z × Z, zaś przeciwdziedziną jest Z, zatem napiszemy add : Z × Z → Z. Zauważmy, że funkcja nie musi wykorzystywać wszystkich elementów wskazanego zbioru wartości. Na przykład funkcja abs nigdy nie przyjmuje wartości −1, mimo że −1 ∈ Z. Funkcję, która wykorzystuje wszystkie elementy zbioru wartości, nazywamy funkcją „na” (surjekcją).

Funkcje można przedstawiać na wiele sposobów. Jednym z nich jest procedura obliczania wartości wyjściowej dla podanej wartości wejściowej. Inną metodą jest tablica wyliczająca wszystkie możliwe argumenty i podająca wartości dla każdego z nich.

Przykład 0.8

Rozważmy funkcję f : {0, 1, 2, 3, 4}→{0, 1, 2, 3, 4}.

n	f(n)
0	1
1	2
2	3
3	4
4	0

Funkcja ta dodaje 1 do argumentu i zwraca wynik modulo 5. Przypomnijmy, że liczba modulo m to reszta z dzielenia tej liczby przez m. Na przykład wskazówka minutowa na tarczy zegarowej podaje wartości modulo 60. Przy posługiwaniu się arytmetyką reszty definiujemy Z_m = {0, 1, 2, …, m − 1}. W przypadku tej notacji wspomniana wcześniej funkcja f ma formę f : Z₅ → Z₅.

■

Przykład 0.9

Niekiedy, gdy dziedzina funkcji jest iloczynem kartezjańskim dwóch zbiorów, do przedstawienia jej wartości używa się tablicy dwuwymiarowej. Oto kolejna funkcja, g : Z₄ × Z₄ → Z₄. Komórka tablicy z wiersza oznaczonego i oraz kolumny z etykietą j zawiera wartość g(i, j).

g	0	1	2	3
0	0	1	2	3
1	1	2	3	0
2	2	3	0	1
3	3	0	1	2

Funkcja g to funkcja dodawania modulo 4.

■

Jeśli dziedziną funkcji jest A₁×·…·×A_k dla pewnych zbiorów A₁, … , A_k, wejściem f jest k-krotka (a₁, a₂, … , a_k) i poszczególne a_i nazywamy argumentami funkcji f. Funkcja z k argumentami nazywana jest funkcją k-argumentową, zaś k nazywamy argumentowością (niekiedy arnością) tej funkcji. Jeśli k jest równe 1, f ma pojedynczy argument i nazywamy ją funkcją jednoargumentową (unarną). Jeśli k to 2, f jest funkcją dwuargumentową (binarną). Pewne dobrze znane funkcje dwuargumentowe są zapisywane przy użyciu szczególnej notacji infiksowej, w której symbol funkcji umieszczany jest między dwoma argumentami, a nie ogólnie stosowanej notacji prefiksowej, gdzie symbol funkcji poprzedza argumenty. Na przykład funkcja dodawania add jest zwyczajowo zapisywana w notacji infiksowej z symbolem + między argumentami, czyli a + b, zamiast notacji prefiksowej add(a, b).

Predykat lub własność to funkcja, której przeciwdziedziną jest zbiór {TRUE (prawda), FALSE (fałsz)}. Na przykład niech even będzie własnością przyjmującą wartość TRUE, jeśli argument jest liczbą parzystą, oraz FALSE, gdy jest to liczba nieparzysta. Tak więc even(4) = TRUE i even(5) = FALSE.

Własność, której dziedziną jest zbiór k-krotek A × … × A nazywamy relacją, relacją k-argumentową albo k-argumentową relacją na A. Często spotykanym przypadkiem jest relacja dwuargumentowa, inaczej nazywana relacją binarną. Przy zapisywaniu wyrażeń wykorzystujących relacje dwuargumentowe zwyczajowo używamy notacji infiksowej. Na przykład „mniejsze niż” jest relacją, którą zwyczajowo zapisujemy przy użyciu symbolu infiksowego <. „Równość”, zapisywana przy użyciu symbolu =, to inna dobrze znana relacja. Jeśli R jest relacją binarną, wyrażenie aRb oznacza, że aRb = TRUE. Analogicznie, jeśli R jest relacją k-argumentową, wyrażenie R(a₁, …, a_k) oznacza, że R(a₁, …, a_k) = TRUE.

Przykład 0.10

W grze w kamień, papier, nożyce dwóch graczy jednocześnie wybiera element ze zbioru {NOŻYCE, PAPIER, KAMIEŃ} i prezentuje wybór odpowiednim ułożeniem dłoni. Jeśli wybory są identyczne, gra jest powtarzana. Jeśli wybory się różnią, jeden z graczy wygrywa zgodnie z relacją bije.

bije	NOŻYCE	PAPIER	KAMIEŃ
NOŻYCE	FALSE	TRUE	FALSE
PAPIER	FALSE	FALSE	TRUE
KAMIEŃ	TRUE	FALSE	FALSE

Z tablicy tej możemy wyczytać, że NOŻYCE bije PAPIER jest równe TRUE, zaś PAPIER bije NOŻYCE to FALSE.

■

Czasami wygodniejsze jest przedstawienie predykatów jako zbiorów, a nie jako funkcji. Predykat P : D→{TRUE, FALSE} można zapisać jako (D, S), gdzie S = {a ∈ D : P(a) = TRUE} lub po prostu S, jeśli dziedzina D w sposób oczywisty wynika z kontekstu. Tym samym relację bije można zapisać jako

{(NOŻYCE, PAPIER), (PAPIER, KAMIEŃ), (KAMIEŃ, NOŻYCE)}.

Szczególny typ relacji dwuargumentowej, nazywany relacją równoważności, prezentuje pojęcie równości dwóch obiektów pod pewnym względem. Relacja dwuargumentowa R jest relacją równoważności, jeżeli spełnia trzy warunki:

1 R jest zwrotna, czyli dla każdego x zachodzi xRx;

2 R jest symetryczna, czyli dla każdych x i y z xRy wynika yRx; oraz

3 R jest przechodnia, czyli dla każdych x, y i z, jeżeli xRy i yRz, to xRz.

Przykład 0.11

Zdefiniujmy relację równoważności dla liczb naturalnych, zapisywaną jako ≡₇. Dla i, j Î N niech i ≡₇ j, jeśli i − j jest wielokrotnością 7. Jest to relacja równoważności, gdyż spełnia trzy wymienione warunki. Po pierwsze jest zwrotna, gdyż i − i = 0, co jest wielokrotnością liczby 7. Po drugie jest symetryczna, gdyż jeśli i − j jest wielokrotnością 7, to można sprawdzić, że j − i również jest wielokrotnością 7. Po trzecie jest przechodnia, gdyż jeśli i − j jest wielokrotnością 7 i j − k jest wielokrotnością 7, wówczas i − k = (i − j) + (j − k) jest sumą dwóch wielokrotności 7, a tym samym również jest wielokrotnością 7.

■