´
Cwiczenie 4
Iloczyn kartezja´
nski. Relacje. Funkcje
4.1
Zadania teoretyczne
4.1.1
Iloczyn kartezja´
nski
1. Znale´z´c iloczyny kartezja´nskie A
× B, B × A dla nast˛epuj ˛acych zbiorów:
(a) A =
{0, 1}, B = {1, 2}
(b) A =
∅, B = {1, 2, 3}
(c) A =
{∅}, B = {1, 2, 3}
2. Znale´z´c iloczyn kartezja´nski A
× B × C dla A = {x, y, z}, B = {1, 2}, C = {u}.
Rozwi ˛
azanie:
Tworzymy wszystkie trójki (a, b, c), w których a ∈ A, b ∈ B i c ∈ C:
A
× B × C = {(x, 1, u) , (x, 2, u) , (y, 1, u) , (y, 2, u) , (z, 1, u) , (z, 2, u)}
3. Niech x, y
∈ R. Poda´c interpretacj˛e geometryczn ˛a iloczynów A × B, B × A dla:
(a) A =
{x : 0 < x}, B = {y : 0 < y}
(b) A =
{x : 0 < x 1}, B = {y : −1 < y < 1}
(c) A =
{x : (0 < x < 1) ∨ (2 < x 3)}, B = {y : (1 < y 2) ∨ (3 < y 4)}
4. Sprawdzi´c, czy prawdziwe s ˛
a równo´sci:
(a) A
× (B ∩ C) = (A × B) ∩ (A × C)
(b) A
− (B × C) = (A − B) × (A − C)
(c) A
∩ (B × C) = (A ∩ B) × (A ∩ C)
(d) A
× (B − C) = (A × B) − (A × C)
Odpowied´z:
Prawdziwe s ˛
a równo´sci: a, d.
4.1.2
Relacje
1. Okre´sli´c dziedzin˛e, przeciwdziedzin˛e i pole relacji:
(a)
{(a, a) , (a, b) , (a, c) , (b, d)}
(b) x jest przeło˙zonym y
(c) x jest wy˙zszy od y
(d) x jest bratem y
2. Okre´sli´c własno´sci relacji:
(a) x jest dzieckiem y
(b) x jest przeciwnej płci ni˙z y
(c) x ma tyle samo lat co y
17
(d) x jest starszy od y
(e) x jest starszy o 10 lat od y
3. Niech U =
{a, b, c, d}. Okre´sli´c własno´sci relacji:
(a)
{(a, a) , (b, b) , (c, c) , (d, d) , (a, b) , (b, a) , (b, c) , (c, b) , (a, c) , (c, a)}
Wskazówka
: Przedstawi´c relacj ˛e w tablicy, gdzie w wierszach mamy poprzedniki par, za´s w kolumnach ich
nast ˛epniki.
a
b
c
d
a
x
x
x
b
x
x
x
c
x
x
x
d
x
Odpowied´z:
Relacja jest zwrotna (własno´s´c 1), symetryczna (3) i przechodnia (6). Jest równowa˙zno´sci ˛
a (8).
(b)
{(a, a) , (c, c) , (a, b) , (b, c)}
(c)
{(b, a) , (a, b) , (c, a) , (a, d) , (c, b) , (b, d) , (d, c)}
4. Poda´c przykłady relacji okre´slonych w zbiorze U =
{a, b, c} o nast˛epuj ˛acych własno´sciach:
(a) zwrotna i symetryczna
(b) zwrotna i przeciwsymetryczna
(c) zwrotna i antysymetryczna
(d) zwrotna i przechodnia
(e) zwrotna i spójna
(f) przeciwzwrotna i symetryczna
(g) przeciwzwrotna i przeciwsymetryczna
(h) przeciwzwrotna i antysymetryczna
(i) przeciwzwrotna i przechodnia
Wskazówka
: W niektórych przypadkach podane własno´sci nie mog ˛
a zachodzi´c równocze´snie.
5. Okre´sli´c własno´sci nast ˛epuj ˛
acych relacji, gdzie x, y
∈ R. Poda´c ich interpretacj˛e geometryczn ˛a:
(a) y > x
(b) y
|x|
4.1.3
Funkcje
1. Dana jest funkcja f : R
→ R, gdzie f (x) = x
2
. Zbada´c, czy f jest injekcj ˛
a, surjekcj ˛
a i bijekcj ˛
a. Je˙zeli nie
jest injekcj ˛
a, poda´c x
1
i x
2
takie, ˙ze x
1
= x
2
i f (x
1
) = f (x
2
). Je˙zeli nie jest surjekcj ˛a, poda´c W
f
.
Rozwi ˛
azanie:
• funkcja nie jest injekcj ˛
a, poniewa˙z istniej ˛a takie x
1
, x
2
∈ R, ˙ze (x
1
= x
2
) ⇒ [f (x
1
) = f (x
2
)], na przykład
x
1
= −1, x
2
= 1,
• funkcja nie jest surjekcj ˛
a, poniewa˙z dla pewnych y nie istnieje takie x ∈ R, ˙ze y = f (x), na przykład dla
y
= −4. Mamy tutaj W
f
= 0, ∞) = R
0
+
(zbiór liczb rzeczywistych nieujemnych), a nie R.
• funkcja nie jest bijekcj ˛
a, poniewa˙z nie jest injekcj ˛
a (nie jest tak˙ze surjekcj ˛
a).
2. Dla danego przekształcenia f : R
→ R zbada´c, czy f jest injekcj ˛a, surjekcj ˛a i bijekcj ˛a. Je˙zeli nie jest
injekcj ˛
a, poda´c x
1
i x
2
takie, ˙ze x
1
= x
2
i f (x
1
) = f (x
2
). Je˙zeli nie jest surjekcj ˛a, poda´c W
f
.
(a) f (x) = 2
x
Odpowied´z:
Funkcja jest injekcj ˛
a i nie jest surjekcj ˛
a poniewa˙z W
f
= (0, ∞) = R
+
(liczby rzeczywiste dodat-
nie), a nie R.
(b) f (x) = x
3
(c) f (x) =
2x + 1
x
− 1
dla x
= 1
0
dla x = 1
Wskazówka:
Wykorzysta´c własno´sci funkcji homograficznej.
18
(d) f (x) = 2
x
+ x
(e) f (x) =
2x
x
2
+ 1
(f) f (x) =
√
x
+ 1 dla x 0
2x
dla x < 0
(g) f (x) = sin x
3. Dana jest funkcja f : R
→ R, gdzie f (x) = sin 2x + 1. Wyznaczy´c obrazy i przeciwobraz:
(a) f (A), gdzie A =
0, π
(b) f (A), gdzie A =
0,
π
2
(c) f
−1
(B), gdzie B =
{0}
Odpowied´z: f
−1
(B) =
x
: x = −
π
4
+ kπ, k ∈ Z
.
4. Niech f : R
→ R, gdzie f (x) = x
2
− 3x + 2. Znale´z´c obrazy i przeciwobrazy:
(a) f (
0, 1)
(b) f (
−2, −1)
(c) f
−1
((
−∞, −6)
(d) f
−1
(
{−3, −4})
(e) f (
{1, 2})
Odpowied´z: f
({1, 2}) = {0}.
4.2
Zadania praktyczne
4.2.1
Wst ˛
ep
Iloczyny kartezja´nskie i relacje s ˛
a zbiorami składaj ˛
acymi si ˛e z par uporz ˛
adkowanych, st ˛
ad w Prologu s ˛
a reprezen-
towane w postaci listy, na przykład:
Zbiór
Lista
{(a, 1) , (a, 2)}
[(a,1),(a,2)]
{(a, b, 1) , (a, b, 2)}
[(a,b,1),(a,b,2)]
Do generowania zbiorów wykorzystuje si ˛e predykat findall.
Definicja
Zapytanie
L
=
{x : P (x)}
findall(X, P(X), L)
L
=
{(x, y) : R (x, y)}
findall((X,Y), R(X,Y), L)
Predykat ten zwraca list ˛e L, która zawiera wszystkie warto´sci zmiennej X lub pary zmiennych (X,Y) spełniaj ˛
ace
funkcj ˛e zdaniow ˛
a P(X) lub R(X,Y).
Uwaga 4.1 Funkcje zdaniowe zło˙zone musz ˛
a by´c zapisane w nawiasie.
4.2.2
Przebieg ´cwiczenia
1. Znale´z´c wszystkie elementy zbioru A =
{2, 3, 1, 7, 8}, które s ˛a wi˛eksze od 2:
?- A = [2,3,1,7,8], findall(X,
(
member(X,A), X>2
)
, L).
L = [3, 7, 8]
2. Dany jest zbiór A =
{2, 3, 1, 7, 8}. Znale´z´c wszystkie elementy x takie, ˙ze:
(a) x
∈ A
(b) x 4 (wskazówka: >=)
(c) 1 < x 7 (wskazówka: =<)
19
(d) x
2
<
9
(e) x jest wi ˛eksze od 1 i kwadrat x jest mniejszy od 9
3. Znale´z´c A
× B dla A = {a, b} i B = {1, 2, 3}:
?- A = [a,b], B = [1,2,3], findall((X,Y),
(
member(X,A), member(Y,B)
)
, L).
L = [(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)]
4. Znale´z´c A
× B oraz B × A dla:
(a) A =
{a}, B = {b}
(b) A =
{a}, B = {1, 2, 3}
(c) A =
{a, b}, B = ∅
(d) A =
{a, b}, B = {∅}
(e) A =
{a, b}, B = {∅, 1}
5. Znale´z´c A
2
dla A =
{a, b}.
6. Dla zbiorów A =
{x, y, z}, B = {1, 2}, C = {u} znale´z´c:
(a) A
× B × C
(b) A
× C × B
7. Dane s ˛
a zbiory A =
{1, 2}, B = {1, 2, 4}. Niech x ∈ A i y ∈ B. Znale´z´c iloczyn kartezja´nski A × B i
relacje R w nim okre´slone:
(a) A
× B = {(x, y)}
(b) R =
{(x, y) : x < y}
(c) R =
{(x, y) : x > y + 1}
(d) R =
{(x, y) : x = y}
(e) R =
{(x, y) : x y}
(f) R =
(x, y) : y = x
2
(wskazówka: Y is X*X)
4.2.3
Zadanie dla dociekliwych
1. Zdefiniowa´c predykat cartprod(A, B, Wynik) (cartesian product) wyznaczaj ˛
acy iloczyn kartezja´nski
zbiorów A i B (patrz punkt 3.2.4).
20
Wyszukiwarka
Podobne podstrony:
więcej podobnych podstron