Matematyka dyskretna cz. I
Logika, teoria mnogości, relacje, moc zbiorów, typy porządkowe,
kongruencje
Zadania dla studentów informatyki
Katarzyna Lubnauer
Maria Wolska
Logika
1. Niech p, q, r następujące zdania logiczne:
p- pada deszcz
q- sÄ… chmury na niebie
r  świeci słońce
Zapisz przy pomocy symboli logicznych następujące zdania:
a) Pada deszcz i świeci słońce.
b) Jeśli pada deszcz to są chmury na niebie.
c) Deszcz pada wtedy i tylko wtedy gdy sÄ… chmury na niebie.
Które z tych zdań są zawsze prawdziwe?
2. Zbadaj wartość logiczną zdań:
a) Jeżeli 2+2=4 to 2+3=4.
b) Jeżeli 2+3=4 to 2+2=4.
c) Jeżeli 2+2=4 i 2+3=6 to 2x = 5.
d) 2+2=5 wtedy i tylko wtedy gdy 2+3 =4.
e) 2+2=4 lub 2+3=5.
3. Zbadaj czy zdanie: Jeśli Ania nie umie liczyć, to jeśli Ania umie liczyć to 2+2=5 jest
prawdziwe.
4. Zbadaj wartość logiczną zdań:
a) p Ô! Źp ,
b) Ź(p '" q),
c) Ź(q (" p),
d) [(p (" q)'" r]Ò! (p '" Źq),
e) (p Ò! q)Ò! [(p (" Źq)Ò! (p '" q)].
5. Sprawdz
które z poniższych zdań są tautologiami:
a) (q Ò! p) Ô! (p '" q),
b) (p '" Źq)Ò! (p Ò! q),
c) (p '" q)Ò! (p (" q),
d) [(p •" q)•" r] Ô! [ p •" (q •" r)] ,
e) (((p Ò! q)Ò! p)Ò! p).
2
6. Określ koniunkcje za pomocą
a) negacji i alternatywy
b) negacji i implikacji.
7. Określ równoważność za pomocą koniunkcji, alternatywy i negacji.
8. ZakÅ‚adajÄ…c iż zdanie p Ò! q jest faÅ‚szywe podaj wartość logicznÄ… zdania q Ò! p .
9. ZakÅ‚adajÄ…c iż zdanie ( p Ò! q) (" r jest faÅ‚szywe podaj wartość logicznÄ… zdania
q '" r Ô! Źp (" (q Ò! r).
10. Niech trójkąt jest prostokątny ,wówczas suma kwadratów długości dwóch krótszych
boków równa jest kwadratowi długości najdłuższego boku. Zapisz twierdzenie w postaci
implikacji. Sformułuj twierdzenie odwrotne, zbadaj jego prawdziwość.
11. Znajdz
twierdzenie przeciwne, odwrotne i przeciwstawne do danego. Zbadaj wartość
logiczną każdego z tych twierdzeń:
a) Jeżeli x > 0 i y > 0 to xy > 0.
b) Jeżeli n jest liczbą naturalną i parzystą to n2 jest liczbą naturalną parzystą.
c) Niech n liczba naturalna. Jeżeli n jest liczbą parzystą to n2 jest liczbą parzystą.
d) Jeżeli x=0 lub y=0 to xy = 0 .
12. Udowodnij iż iloczyn dwóch liczb parzystych jest wielokrotnością 4.
13. Udowodnij iż liczba n2 - n gdzie n " N jest liczbą parzystą. Podaj jaki typ dowodu
zastosowałeś.
14. Udowodnij iż liczba n3 - n gdzie n " N jest liczbą podzielną przez 6. Podaj jaki typ
dowodu zastosowałeś.
15. Udowodnij iż liczba n3 + n gdzie n " N jest liczbą parzystą. Podaj jaki typ dowodu
zastosowałeś.
16. Udowodnij iż liczba n4 - n2 gdzie n " N jest liczbą podzielną przez 3. Podaj jaki typ
dowodu zastosowałeś.
17. Udowodnij wynikania:
x + y
a) Jeżeli > 1 to x > 1 lub y > 1.
2
b) Jeżeli xy < 0 to x < 0 lub y < 0 .
c) Jeżeli średnia arytmetyczna n liczb jest większa od a to przynajmniej jedna z tych
liczb jest większa od a.
18. Udowodnij iż 2 jest liczbą niewymierną. Podaj jaki typ dowodu zastosowałeś.
3
19. Udowodnij iż 3 jest liczbą niewymierną. Podaj jaki typ dowodu zastosowałeś.
20. Udowodnij iż log2 3 jest liczbą niewymierną. Podaj jaki typ dowodu zastosowałeś.
21. Udowodnij iż log3 5 jest liczbą niewymierną. Podaj jaki typ dowodu zastosowałeś.
22. Udowodnij następujące nierówności dla dowolnych x, y " R :
a) x e" x ,
b) x 0 '" y e" 0 Ò! x + y d" max x , y ,
{ }
c) x + y d" x + y ,
d) x - y e" x - y ,
e) x - y d" x + y ,
f) x + y e" x - y ,
g) xy = x y ,
x
x
h) = .
y y
Podaj jaki typ dowodu zastosowałeś.
23. Zapisz następujące zdania w notacji polskiej (beznawiasowej):
a) ((p (" q)(" r)(" s ,
b) (p (" q)Ò! (Źr '" s),
c) (Ź(p (" q)) Ô! (Źp '" Źq).
24. Przekształć zdania z notacji beznawiasowej w notacje nawiasową:
a) pŹqŹ '" pq (" Ź Ô! ,
b) pq '" r '" pqr '" '" Ô! .
4
Zbiory.
1. Niech
U = {0,1,2,3,....,17}, A = {2,4,6,8,10}, B = {1,3,5,17}, C = {1,5,6,8,17}, D = {6,12,13}.
Wyznacz zbiory:
a) A *" B
b) A )" B
c) A - C
d) (A )" C)*" Bc
e) C - D
f) B •" C
g) ile podzbiorów ma zbiór C
2. Niech A = {2,4,5}, B = {n " N : n jest parzyste},
B = { p " Z : p jest nieparzyste (" p < 0}.
a) Wyznacz A )" B, A )" C, B )" C, B •" C
b) Wypisz wszystkie podzbiory zbioru A
c) Nie wyznaczając ich zgadnij, które ze zbiorów są nieskończone:
A *" B, A •" B, A - B, B - A .
3. Wypisz kilka elementów poniższych zbiorów oraz zapisz te zbiory w inny sposób:
a) A = {n " N : n podziel. przez 3}
b) B = {x " R :x2 = 1}
c) C = {x " R : 2x d" 2}
Å„Å‚ 1 üÅ‚
d) D = " R -{ }
òÅ‚x 0 : x + e" 2żł .
x
ół þÅ‚
e) "
4. W przestrzeni R znajdz
następujące zbiory:
a) [1,5))"[- 2,3],
b) [-1,3]*" (2,"),
c) [0,5]-[2,7),
d) [0,5]•"[2,7)
5
c
e) [0,"]
f) [0,4])" "
5. Dla podanych zbiorów A,B wyznaczyć zbiory A *" B, A )" B, A \ B . Wynik zaznacz na osi
liczbowej:
Å„Å‚ üÅ‚
3x2 4x +16
a) A = " R : - = 0żł, B = {x " R : x -1 + x - 5 > 8}
òÅ‚x
x2 -1 x +1
ół þÅ‚
Å„Å‚ üÅ‚
1
b) A = " R :3 log x + 2log = 2żł, B = {x " R : log2(x -1)- 2log(x -1) > 0}
òÅ‚x
x
ół þÅ‚
c) A = {x " R : x +1 + 2 = 2}, B = {x " R : x +1 - x -1 = 1}
1-x
Å„Å‚ üÅ‚
x
1
ôÅ‚ ëÅ‚ öÅ‚
d) A = {x " R : x - 3 + x + 4 = 9}, B = " R : d" 1ôÅ‚
ìÅ‚ ÷Å‚
òÅ‚x żł
2
íÅ‚ Å‚Å‚
ôÅ‚ ôÅ‚
ół þÅ‚
1 1+ x
Å„Å‚ üÅ‚ Å„Å‚
e) A = " R : x < B = " R : > 1üÅ‚
òÅ‚x żł, òÅ‚x żł
x 1- x
ół þÅ‚ ół þÅ‚
Å„Å‚ üÅ‚
x2 +1 x2
f) A = " R : > {x
òÅ‚x żł, B = " R : x + 2 > 3}
x x +1þÅ‚
ół
2
Å„Å‚ üÅ‚
(x + 3) (x2 + x +1)
g) A = " R : > 0 B = {x " R : x -1 d" 5}
òÅ‚x żł,
(4 - x)x
ół þÅ‚
h) A = {x " R :logx-2(x -1) > 1}, B = {x " R : 2x -1 < x + 3}
6. Niech
" = {x, y}, A = {x, y, xx, yy, xxx, yyy}, B = {w " "* :dlug.(w)e" 2}i C = {w " "* :dlug(w) d" 2}
a) Wyznacz zbiory A )" C, A \ C, C \ A, A •" C .
b) Wyznacz zbiory A )" B, B )" C, B *" C, B \ A .
c) Wyznacz zbiory "* -B, "* -A.
d) Wypisz wszystkie podzbiory " .
e) Ile zbiorów należy do 2" .
7. Wykazać, że dla dowolnych zbiorów A,B,C zachodzi równość
a) A \ B = A \ (A )" B)
b) A = (A )" B)*" (A \ B)
c) A \ (A \ B) = A )" B
d) A - C )" B - C = A )" B C
( ) ( ) ( )-
6
e) A \ (B \ C) = (A \ B)*" (A )" C)
f) (A \ B)\ C = A \ (B *" C)
c
c
8. Udowodnij uogólnione prawo De Morgana: (A )" B )" C) = (Ac *" Bc *" C ).
9. Udowodnij prawdziwość następujących zdań nie używając diagramów Venna:
a) A )" B ą" A i A ą" A *" B dla dowolnych zbiorów A,B.
b) Jeśli A ą" B i A ą" C , to A ą" B )" C .
c) Jeśli A ą" C i B ą" C to A *" B ą" C .
d) A Ä…" B wtedy i tylko wtedy gdy Bc Ä…" Ac .
10. Dla dowolnego A okreÅ›lonego w przestrzeni X okreÅ›l zbiór A •" A , A •" " , A •" X .
11. Wykazać, że dla dowolnego A,B,C zachodzą równości:
a) A •" B = B •" A
b) (A •" B)•" C = A •" (B •" C)
12. Podając odpowiednie przykłady wykazać, że równości
a) (A \ B)*" B = A
b) (A *" B)\ B = A
NIE zachodzą dla dowolnych zbiorów A,B. Zilustruj rozwiązanie diagramami Venna.
13. Narysuj diagram Venna dla czterech dowolnych zbiorów A,B,C,D i zaznacz na nim zbiór
Ac *" Bc )"(C )" Dc).
14. Zbadaj czy poniższe zdania są prawdziwe czy fałszywe. Prawdziwe zdania udowodnij a
dla fałszywych znajdz
kontrprzykład.
a) A )" B = A )" C implikuje B=C
b) A *" B = A *" C implikuje B=C
c) A )" B = A )" C i A *" B = A *" C implikuje B=C
d) A *" B Ä…" A )" B implikuje A=B
e) A •" B = A •" C implikuje B=C
f) A ‚" B Ô! Ac )" Bc = B
g) A `" B Ò! C \ A `" C \ B
15. Pokaż, że A *" B jest najmniejszym zbiorem zawierającym jednocześnie zbiory A oraz B.
16. Rozwiąż równanie :
1
îÅ‚-1, öÅ‚
[0,1]•" X =
÷Å‚
ïÅ‚
2
ðÅ‚ Å‚Å‚
7
17. Niech A = {1,3,5}, B = {2,4}i C = {1,5}. Rozwiąż równanie (A •" X )•" B = C .
18. Niech A = {a,b,c} i B = {a,b, d}.
a) Wypisz lub narysuj wszystkie pary uporzÄ…dkowane zbiorów A× A i A× B .
b) Wypisz lub narysuj wszystkie pary uporzÄ…dkowane zbioru
{(x, y)" A× B : x = y}.
19. Niech S = {0,1,2,3} i niech T = {1,3}.
a) Wypisz lub narysuj elementy zbioru S ×T i T × S .
b) Wypisz lub narysuj elementy zbioru {(m, n)" S ×T : m d" n}.
c) Wypisz lub narysuj elementy zbioru {(m, n)"T × S : m e" n}.
d) Wypisz lub narysuj elementy zbioru {(m, n)" S ×T : m + n e" 3}.
e) Wypisz lub narysuj elementy zbioru {(m, n)" S ×T : mn > 5}.
f) .Wypisz lub narysuj elementy zbioru {(m, n)" S × S : m = n}.
20. Narysuj zbiory A× B, B × A dla:
a) A = [0,1], B = [2,3]
b) A = [- 2,1], B = [0,3]
c) A = [0,1], B = {- 2}
d) A = (- ",1), B = (2,").
21. Wypisz wszystkie elementy tych spośród zbiorów które mają nie więcej niż 6 elementów
oraz wypisz 6 elementów z tych zbiorów które mają więcej elementów.
a) {(m, n)" N2 :n > m}
b) {(m, n)" N2 :n + m = 2}
c) {(m,n)" Z2 :nm d" 4}
d) {(x, y)" R2 :x2 > x}
e) {(m,n)" N2 :max{m, n}> 5}
f) {(m, n)" N2 :max{m,n}d" 1}.
22. W prostokątnym układzie współrzędnych zaznaczyć zbiory A,B, A *" B, A )" B :
a) A = {(x, y)" R2 : sin(x - y) = 0}, B = {(x, y)" R2 : tgy = 0}
b) A = {(x, y)" R2 : sin(x + y) = 0}, B = {(x, y)" R2 : cos(x - y) = 0}
c) A = {(x, y)" R2 : tg(x + y) = 0}, B = {(x, y)" R2 : cos(x + y) = 0}
8
d) A = {(x, y)" R2 : tg(x + y) = 0}, B = {(x, y)" R2 : tgx = 0}
Å„Å‚ x üÅ‚
e) A = {(x, y)" R2 : logx y = log x}, B = (x, y)" R2 : = 1żł
òÅ‚
y
y
ół þÅ‚
23. Zaznacz zbiory A× B, B × A w ukÅ‚adzie
współrzędnych: A = {x " R :x d" 2}, B = {y " R : y -1 < 2}
a) A = {x " R : x + 2 e" 1}, B = {y " R : y - 2 < 1}
Å„Å‚ üÅ‚
x2 - 2x +1
b) A = " R : e" 0żł, B = {y " R : 0 < y < 3}
òÅ‚x
4x - x2 þÅ‚
ół
Å„Å‚ üÅ‚
16 - x2
c) A = {y " R :1 < y < 5}, B = " R : e" 0żł
òÅ‚x
x3 + 27
ół þÅ‚
Å„Å‚ 2y -1 üÅ‚
d) A = {x " Z : log2 (x2 -1)< 3}, B = " R : < 1żł
òÅ‚y
y +1
ół þÅ‚
2
Å„Å‚ üÅ‚
ôÅ‚t - 2t + 3t - 5
ôÅ‚
e) A = " R : e" 0 B = {x " R : log0,5 (x2 + 5x + 6)< -1}
òÅ‚ żł,
3 - t -1
ôÅ‚ ôÅ‚
ół þÅ‚
24. Wykaż równości:
a) A×(B *" C) = (A× B)*" (A× C)
b) A×(B )" C) = (A× B))" (A× C)
9
Kwantyfikatory
1. Oceń wartość logiczną zdań i zapisz negacje każdego zdania:
a) " x = 2x
x"R
x2 x + 2
b) " e"
x"N
x +1 x +1
1 1
c) " e"
x"N
x +1 x + 2
3x +1
d) " e" 0
x"N
2x +1
- 2x2 + x - 4
e) " d" 0
x"R
- 3x2 - 2
2x2 - 4x + 2
f) " d" 0
x"R
- 2x2 - 3
g) " y = 3x Ò! x = 3y
x, y"R
h) " x + y `" 3 Ò! y + x = 3, gdzie A = {1,2,3}
x, y"A
i) " " m2 + n2 = 10
m"N n"N
j) " " x d" y
x"Z- y"N
k) " " y = x2 - 4
x"R
y"R+
2. Określ wartość logiczną zdań, dla n, m " N :
a) ""[2n = m]
m n
b) ""[2n = m]
n m
c) ""[2m = n]
m n
d) ""[2m = n]
n m
e) ""[Ź{2n = m}]
n m
3. Określ wartość logiczną zdań, dla x, y " R :
a) ""[xy = 0]
y x
b) ""[xy = 0]
x y
10
c) ""[xy = 1]
y x
d) ""[xy = 1]
x y
4. Niech p(x,y) , p(y) funkcje zdaniowe, znajdz
kontrprzykłady do następujących implikacji:
a) " p(y)Ò! " p(y)
y y
b) "" p(x, y) Ò! "" p(x, y)
y x x y
c) "Źp(y)Ð! Ź" p(y)
y y
5. Wskaż zmienne wolne i związane w następujących wyrażeniach:
a) "ëÅ‚"(x < y)Ò! (x + z d" y)öÅ‚
ìÅ‚ ÷Å‚
x y
íÅ‚ Å‚Å‚
b) "(("Ć(x)Ò!È (x))Ò!È (y))
y x
c) "(x = x)(" x = 0
x
d) " x " A
x
e) f d" g Ô! " ( f (x) d" g(x))
x"X
6. Zapisz posługując się symboliką logiczną następujące zdania:
a) Liczby 2 i 3 nie mają wspólnych dzielników różnych od 1.
b) Istnieje liczba naturalna od której nie jest mniejsza żadna inna liczba naturalna.
c) Układ równań : a + b = 3 i 3a + 3b = 5 nie ma rozwiązań.
7. Podaj przykÅ‚ad takich funkcji zdaniowych Ć(x),È (x), x " X , dla których implikacje sÄ…
fałszywe:
a) " (Ć(x)("È (x))Ò! " Ć(x)(" " È (x)
x"X x"X x"X
b) " Ć(x)'" " È (x)Ò! " (Ć(x)'"È (x))
x"X x"X x"X
8. Niech formuła r(x,y) oznacza, że x jest rodzicem y, niech m(x) oznacza, iż x jest
mężczyzną. Zdefiniuj za pomocą formuł r oraz m następujące zdania:
a)  x jest bratem y
b)  x jest siostrÄ… ciotecznÄ… y
c)  x jest pradziadkiem y
11
Uogólnione sumy i iloczyny zbiorów
1. Policz iloczyn i sumę uogólnioną ciągu zbiorów:
îÅ‚-2n, Å‚Å‚
a) A = 2n ûÅ‚
n
ðÅ‚
1 1
ëÅ‚ öÅ‚
b) B = - ,
n ìÅ‚ ÷Å‚
n n
íÅ‚ Å‚Å‚
n
îÅ‚ öÅ‚
(-1
)
c) Cn = ,2÷Å‚
ïÅ‚
÷Å‚
n
ïÅ‚
ðÅ‚ Å‚Å‚
d) D = 1, 2,...,3n
{ }
n
e) E = [n,n +1]
n
f) Ft = {x " R : x = sin t}, t " R
g) Gt = {x " R : xt d" 1}, t " R -{0}
h) Ht = {x " R : x +1 d" t}, t " R+
i) It = {x " R : x < t}, t " R+
2. Policz granice dolną i górną ciągu zbiorów
a) A =
[-n,n
]
n
1 1
ëÅ‚ öÅ‚
b) B = - ,
n ìÅ‚ ÷Å‚
n n
íÅ‚ Å‚Å‚
n
îÅ‚ öÅ‚
(-1
)
c) Cn = ,2÷Å‚
ïÅ‚
÷Å‚
n
ïÅ‚
ðÅ‚ Å‚Å‚
d) D = 1, 2,...,3n
{ }
n
Zbiór wszystkich liczb naturalnych dodatnich przedstaw jako sume nieskończoną ciągu
zbiorów nieskończonych i parami rozłącznych.
Wskazówka: Z = 2n Å"1, 2n Å"3,2n Å"5,2n Å"7,..., 2n Å" k,... , n" N , k liczba nieparzysta.
{ }
n
3. Udowodnij korzystając z rachunku funkcyjnego następujące twierdzenia algebry zbiorów:
a) A \ B = " Ô! A ‚" B ,
b) At - Bt ‚" (At - Bt ),
t"T t"T t"T
c) (At - Bt ) ‚" At - Bt ,
t"T t"T t"T
12
d) (At )" Bt ) ‚" At )" Bt .
t"T t"T t"T
13
Relacje
1. Niech S = {1,2,3,4} oraz T = {5,6,7,8}, oraz niech R relacja w zbiorze S ×T . Wypisz
wszystkie pary należące do relacji R:
a) (x, y)" R Ô! x + y d" 10
b) (x, y)" R Ô! x + y = 10
c) (x, y)" R Ô! x + y jest parzyste
2. Dla relacji R1, R2 , R3, R4 w zbiorze S = {0,1,2,3,4} określ jakie własności z pośród
poniższych spełniają:
(Z) zwrotność
(PZ) przeciwzwrotność
(S) symetryczność
(AS) antysymetryczność
(P) przechodniość
a) (x, y)" R1 Ô! x + y jest parzyste
b) (x, y)" R2 Ô! x d" y
c) (x, y)" R3 Ô! x - y = 0
d) (x, y)" R4 Ô! x - y jest parzyste .
3. Zbadaj jakie wÅ‚asnoÅ›ci spoÅ›ród wymienionych powyżej ma w zbiorze S = {Ä…, ² , Ç,µ}
relacja określona tabelą:
\ Ä… ² Ç µ
Ä… + + - +
² + + + -
Ç - + + +
µ + - + +
gdzie  + oznacza, że dana para jest w relacji a   , że nie jest.
4. W zbiorze N określone są następujące relacje dwuargumentowe:
a) (x, y)" R1 Ô! x - y parzyste
b) (x, y)" R2 Ô! x - y podziel. przez 3
c) (x, y)" R3 Ô! x - y d" 5
d) (x, y)" R4 Ô! min{x, y}= 2
14
e) (x, y)" R5 Ô! y x gdzie y x oznacza iż y jest podzielne przez x
f) (x, y)" R6 Ô! x + y 2
Zbadaj ich własności i dla relacji równoważności znajdz
klasy abstrakcji.
5. W zbiorze X określone są następujące relacje dwuargumentowe:
a) X zbiór prostych na płaszczyz
nie. Dwie proste l,k sÄ… w relacji gdy sÄ… do siebie
równoległe (ozn. l k )
b) X zbiór prostych na płaszczyz
nie. Dwie proste l,k sÄ… w relacji ðÅ‚ gdy sÄ… do siebie
prostopadÅ‚e (ozn. lðÅ‚k)
c) X zbiór ludzi na ziemi . Dwaj ludzie są w relacji ze sobą gdy mają wspólnego
rodzica (matkÄ™ lub ojca)
d) X zbiór ludzi na ziemi . Dwaj ludzie są w relacji ze sobą gdy mają wspólną matkę.
Zbadaj ich własności i dla relacji równoważności znajdz
klasy abstrakcji.
6. Dla relacji z zadania drugiego narysuj rysunki przedstawiający relacje między
elementami zbioru S. Jeśli element (x,y) należy do relacji to łączymy je strzałką o początku w
x i końcu w y. Jeśli między jakimiś punktami występują strzałki w obu kierunkach to
zastępujemy je linią. Czym wyróżniają się rysunki ilustrujące relacje równoważności? Jakie
własności relacji możesz odczytać z rysunku.
7. Zbiór liczb całkowitych podzieliliśmy na zbiory rozłączne
Z = {4k + n :k = 1,2,3,....}, dla n = 0,1,2,3 . Znajdz
relację dla której są to klasy abstrakcji.
n
8. Niech X = {a,b,c,d} oraz niech S = 2X zbiór wszystkich podzbiorów zbioru X. Niech R
relacja w zbiorze S okreÅ›lona nastÄ™pujÄ…co: (A, B)" R Ô! A = B . Wykaż, że jest to relacja
równoważności i znajdz
klase abstrakcji do której należy element A = {a,b}.
9. Niech X pewien zbiór niepusty oraz niech S = 2X zbiór wszystkich podzbiorów zbioru X.
Niech ponadto a " X oraz R relacja w zbiorze S określona następująco:
(A, B)" R Ô! A = B (" a " A *" B . Wykaż, że jest to relacja równoważnoÅ›ci i znajdz
jej klasy
abstrakcji.
10. W zbiorze par uporządkowanych (x, y)gdzie x równe 0 lub 1 i y jest równe 0 lub 1
okreÅ›lono relacje R w nastÄ™pujÄ…cy sposób (x, y)R(x0 , y0)Ô! x = x0 •" y = y0 . Zbadaj czy jest
to relacja równoważności i jeśli odpowiedz
jest twierdzÄ…ca znajdz
jej klasy abstrakcji.
11. W zbiorze trójek uporządkowanych (x, y, z)gdzie x,y,z równe 0 lub 1 ,określono relacje R
w nastÄ™pujÄ…cy sposób (x1, x2 , x3)R(y1, y2 , y3) Ô! xn = yn dla nieparzystej liczby wskaz
ników
15
n=1,2,3. Zbadaj czy jest to relacja równoważności i jeśli odpowiedz
jest twierdzÄ…ca znajdz
jej
klasy abstrakcji.
12. Niech w zbiorze liczb naturalnych określona będzie relacja mod m w następujący sposób:
def
(a,b)" mod m Ô! a = b(mod m) gdzie a = b(mod m)Ô! " a = b + km .
k"Z
Dla m=3 zbadaj czy jest to relacja równoważności i jeśli odpowiedz
jest twierdzÄ…ca znajdz
jej
klasy abstrakcji.
13. W teorii liczb określa się relację zwaną kongruencją. Wykaż, że jeżeli
a = b(mod m) i c = d(mod m) to
a) a + c = (b + d)(mod m),
b) a - c = (b - d)(mod m),
c) a Å" c = (b Å" d)(mod m).
16
Funkcje
1. Definiujemy funkcję f : R R określoną wzorem :
Å„Å‚
x3, dla x e" 1
ôÅ‚
f (x) = dla 0 < x < 1.
òÅ‚x,
ôÅ‚- x2 dla x d" 0
,
ół
a) Oblicz f(0), f(1), f(-1), f(2).
b) Naszkicuj wykres funkcji f i na jego podstawie określ Im(f).
c) Narysuj funkcje f , - f , f -1.
2. Które z poniższych rysunków przedstawiają
a) wykres funkcji
b) wykres funkcji różnowartościowej
c) wykres funkcji  na przedział [0,1]
17
3. Niech S = {1,2,3,4,5} oraz zdefiniujmy następujące funkcje:
a) f (n) = 6 - n
b) f (n) = max{n,3}
c) f (n) = min{n,2}
d) f (n) = min{5,n}.
Zbadaj które z nich są wzajemnie jednoznaczne z S w S.
4. Wyznacz dziedzinÄ™ funkcji:
x2
a) f (x) =
x +1
1
b) f (x) =
x2 - 4x
c) f (x) = log(sin x)
d) f (x) = ln(ex - e)
1+ x
e) f (x) = x + 3
1- x
2x
f) f (x) = arcsin
1+ x
5. Czy funkcje f i g określone następująco:
a) f (x) = x2 + 2 i g(z) = 2 + z2
b) f (x) = x i g(z) = z2
c) f (x) = x i g(z) = z2
x
d) f (x) = i g(z) = 1
x
e) f (x) = 1 i g(z) = sin2 z + cos2 z
f) f (x) = 1 i g(z) = tgz Å" ctgz
są równe?
6. Określić dziedzinę i zbiory wartości funkcji:
3
a) f (x) = x
b) f (x) = - x2
18
1
c) f (x) = sin
x
1
d) f (x) = x +
x
e) f (x) = sin x + cos x
2x
f) f (x) =
2x - 4
g) f (x) = log(sin x)
2
7. Dane sÄ… funkcje f (x) = x3 - 3x , g(x) = , h(x) = x4 , k(x) = 2x . Znajdz
funkcje:
x2 + 2
a) f g h
b) f h h
c) f k
d) g g
e) h g .
8. Udowodnij iż następujące funkcje są różnowartościowe na wskazanych zbiorach:
a) f (x) = x2 , (- ",0]
b) f (x) = x3, R
c) f (x) = x5 -1, R
1
d) f (x) = , x > 1
x -1
e) f (x) = x, x e" 0
1
f) f (x) = , x " R \ {0}
x
9. Zbadaj różnowartoÅ›ciowość oraz wÅ‚asność na funkcji g : Z × Z Z × Z okreÅ›lonej
wzorem:
a) g(n, m)= (- n,-m)
b) g(n, m) = (2n,3m)
c) g(n, m) = (m + n,-m)
d) g(n, m) = (n,-4)
Dla funkcji odwracalnych znajdz
funkcjÄ™ odwrotnÄ….
19
10. Zbadaj odwracalność poniższych funkcji działających z R w R oraz znajdz
funkcje
odwrotnÄ…:
a) f (x) = 2x + 3
b) f (x) = x3 - 2
3
c) f (x) = (x - 2)
3
d) f (x) = x + 3
11. Definiujemy funkcje f : N N oraz g : N N w następujący sposób: f (n) = 2n ,
n
Å„Å‚
ôÅ‚2 dla n parzyst.
ôÅ‚
g(n) = .
òÅ‚
ôÅ‚n -1 dla n nieparzyst.
ôÅ‚
ół 2
Pokazać, że g f = ™N oraz f g `" ™N .
12. Niech f (x) = x2 . Znajdz
obraz zbioru A oraz przeciwobraz zbioru B względem f:
a) A = [- 2,3], B = (1,4),
b) A = (0,2), B = {9}
c) A = {- 3}, B = (- ",3].
1
13. Niech f (x) = . Znajdz
obraz zbioru A oraz przeciwobraz zbioru B względem f:
x
1
ëÅ‚
a) A = [1,3], B = ,4öÅ‚,
ìÅ‚ ÷Å‚
2
íÅ‚ Å‚Å‚
b) A = (0,2), B = {9}.
14. Niech f (x) = cos2x . Znajdz
obraz zbioru A oraz przeciwobraz zbioru B względem f:
a) A = {x " R : x e" 0},
 3
Å„Å‚
b) A = " R : + n  d" x d"  + n üÅ‚ ,
òÅ‚x żł
4 4
ół þÅ‚
c) B = {y " R : 0 d" y d" 1}
.
15. Niech f (x) = x + 2 . Znajdz
obraz zbioru A oraz przeciwobraz zbioru B względem f:
a) A = [0,1]
b) B = [0,2]
c) B = (- 2,0]
d) B = [2,6]
20
16. Niech f (x) = x2 - 2 . Znajdz
obraz zbioru A oraz przeciwobraz zbioru B względem f:
a) A = [0, 2],
b) A = [0,2],
c) B = [0,2]
d) B = (- 2,0]
e) B = [2,6]
-1
17. Niech f (x) = x + 2 oraz niech A = [2,3]. Znajdz
f(A) oraz f ( f (A)).
21
Równoliczność zbiorów
1. Wykaż, że przedziały:
a) [0,2] i [0,1]
b) [a,b] i [c,d]
c) [0,1] i [0,1)
d) [0,1] i (0,1)
są równoliczne.
2. Wykaż, że zbiór liczb naturalnych i zbiór liczb parzystych są równoliczne.
3. Wykaż równoliczność zbioru liczb naturalnych ze zbiorem liczb całkowitych.
4. Wykaż równoliczność zbioru liczb naturalnych podzielnych przez 6 ze zbiorem liczb
naturalnych podzielnych przez 3.
5. *Wykaż równoliczność zbioru liczb naturalnych ze zbiorem liczb pierwszych.
6. Wykaż, że funkcja
f : N × N N, f (n,m) = (2m -1)2n-1, odwzorowuje wzajemnie jednoznacznie zbiór
N × N na N . (Zbiór liczb naturalnych bez zera)
7. Udowodnić równoliczność zbioru liczb rzeczywistych z przedziałem (0,1).
8. Wykaż, że zbiór wszystkich trójkątów równobocznych na płaszczyz
nie o środku ciężkości w
początku układu współrzędnych i jednym z wierzchołków o współrzędnych całkowitych jest
zbiorem przeliczalnym.
9. Zbadaj moc zbioru wszystkich kół na płaszczyz
nie, majÄ…cych:
a) Środek o współrzędnych wymiernych i r = 1
b) Środek o współrzędnych wymiernych i r = k 2, k " Z .
10. Wykaż, że zbiór liczb wymiernych jest przeliczalny.
11. Wykaż, że zbiór A wszystkich ciągów o wyrazach równych 0 lub 1 jest nieprzeliczalny.
12. *Wykaż, że zbiór liczb rzeczywistych jest nieprzeliczalny.
13. Wykaż, że zbiór liczb niewymiernych jest nieprzeliczalny.
14. Wykaż, że zbiór liczb postaci n + k gdzie n, k " N jest przeliczalny.
22
Typy porzÄ…dkowe
1. Niech R ‚" N × N , i R jest relacjÄ… podzielnoÅ›ci:
(n,m)" R Ô! n / m.
a) Wykazać, że R jest relacją porządkującą.
b) Czy w zbiorze (N, R) jest element maksymalny.
2. RR rodzina funkcji przekształcających zbiór R w R. Określmy relacje d" w RR :
f d" g Ô! " f (x) d" g(x).
x"R
a) Podaj przykłady takich funkcji, które są w relacji d" .
b) Czy jest to relacja porzÄ…dkujÄ…ca.
0,1]
3. [0,1][ rodzina funkcji przekształcających zbiór [0,1] w [0,1]. Określmy relacje d" w
0,1]
[0,1][ :
f d" g Ô! " f (x) d" g(x).
x"R
a) Podaj przykłady takich funkcji, które są w relacji d" .
b) Czy jest to relacja porzÄ…dkujÄ…ca.
0,1]
c) Czy zbiór ([0,1][ ,d") posiada element maksymalny?
4. Niech N1 = N \ {1}; xRy Ô! y / x ,
a) Czy relacja R porzÄ…dkujÄ…ca w N1 ?
b) Wskaż element maksymalny.
c) Wskaż element minimalny (o ile istnieje).
5. Niech A = {1,2,3}, B = {0,1}, oraz niech AB rodzina funkcji określonych na A o
wartościach w wartościach zaś R relacja określona:
fRg Ô! f (i)g(i) = f (i). Udowodnij iż relacja R porzÄ…dkujÄ…ca. Wskaż element maksymalny i
minimalny.
6. Niech X = {1,2,...,7} oraz xRy Ô! 2 / x - y . Udowodnij iż relacja R porzÄ…dkujÄ…ca. Wskaż
element maksymalny i minimalny.
23