Zadaci iz Osnova matematike
1. Logi~ka operacija ∗ data je tablicom
∗
⊤
⊥
⊤
⊥
⊤
⊥
⊥
⊥
Izraziti pomo}u negacije i operacije ∗ ostale osnovne logi~ke operacije (konjukciju, disjunkciju, implikaciju i ekvivalenciju).
2. Rije{iti po istinitosnoj vrijednosti iskaza p, q, r jedna~inu
τ (p ⇒ (¬q ⇒ r)) = ⊥.
3. Odrediti sve neekvivalentne iskazne formule F = F (p, q) za koje je iskazna
formula
p∧q ⇔p∧F
tautologija.
4. Odrediti sve neekvivalentne iskazne formule F = F (p, q) za koje je iskazna
formula
(q ⇒ p) ⇔ p ∨ F
tautologija.
5. Na}i iskaz F ~ija je istinitosna vrijednost predstavqena tablicom
p
⊤
⊥
⊤
⊥
⊤
⊤
⊥
⊥
q
⊤
⊤
⊥
⊥
⊤
⊥
⊤
⊥
r
⊤
⊤
⊤
⊤
⊥
⊥
⊥
⊥
F
⊤
⊥
⊤
⊤
⊥
⊥
⊥
⊤
6. Neka su A, B, C, D proizvoqne iskazne formule. Ako su formule A ⇒ (B∨C)
i (A ∧ C) ⇒ D tautologije dokazati da je onda tautologija i iskazna formula
(¬D ∧ A) ⇒ B .
7. Ako je iskazna formula A∨B tautologija, a iskazna formula C ∧D kontradikcija, dokazati da je iskazna formula (B ⇒ D) ⇒ (C ⇒ A) tautologija.
1
8. Ispitati ta~nost formula
(a) (∀x ∈ N)(∀y ∈ N)(∃z ∈ N) x + y = z;
(b) (∀x ∈ N)(∃z ∈ N)(∀y ∈ N) x + y = z;
(v) (∃z ∈ N)(∀x ∈ N)(∀y ∈ N) x + y = z;
(g) (∀x ∈ Z)(∀y ∈ Z)(∃z ∈ Z) x + y = z.
9. Dokazati da za sve skupove A, B, C ⊂ X vrijedi:
(a) A\B = A \ (A ∩ B);
(b) A\B = (A ∪ B) \ B.
10. Ispitati da li za sve skupove A, B, C ⊂ X vrijedi:
(a) A\(A\B) = A ∩ B (b) (A ∪ B)\C = (A\C) ∪ (B\C)
(v) (A\B)\C = (A\C)\(B\C)
(g) A ∪ B = A∆B ∪ (A ∩ B) (d) A ∪ B = A∆B∆(A ∩ B)
(|) P(A ∩ B) = P(A) ∩ P(B), gdje je P oznaka za partitivni skup.
(e) (A\B) × C = (A × C)\(B × C) (`) A × (B\C) = (A × B)\(A × C)
(i) f −1 (A) ∩ f −1 (B) = f −1 (A ∩ B)
(z) f (A ∪ B) = f (A) ∪ f (B)
(j) f (A) ∩ B = f (A ∩ f −1 (B))
11. Neka je f : X → Y funkcija. Dokazati ili opovrgnuti tv|ewe:
Za sve A ⊂ X , B ⊂ Y vrijedi
f (A △ f −1 (B)) = f (A) △ B.
12. Pokazati da operacija razlike skupova \ nije asocijativna tj. da ne mora za sve
skupove A, B, C da vrijedi
A \ (B \ C) = (A \ B) \ C.
13. (a) Neka su A, B, C podskupovi skupa X . Dokazati
A ∩ B ⊂ C ako i samo ako A ⊂ B c ∪ C.
(b) Neka je {Ai : i ∈ I} kolekcija skupova indeksirana skupom I . Dokazati da
za proizvoqan skup B vrijedi
B∪(
∩
Ai ) =
i∈I
∩
(B ∪ Ai ).
i∈I
14. (a) Neka su A, B, C podskupovi skupa X . Dokazati
C ⊂ A ∪ B ako i samo ako B c ∩ C ⊂ A.
2
(b) Neka je {Ai : i ∈ I} kolekcija skupova indeksirana skupom I . Dokazati da
za proizvoqan skup B vrijedi
B∩(
∪
Ai ) =
i∈I
∪
(B ∩ Ai ).
i∈I
15. Data je familija skupova {Ai : i ∈ N}, gdje je Ai = {i, i + 1, . . .}, i ∈ N.
Uporediti skupove
100
∪ 100
∩
Ai+j i
j=0 i=0
100
∩ 100
∪
Ai+j .
j=0 i=0
16. Pokazati da za skupove A, B vrijedi
(a) A ⊂ B ⇒ P (A) ⊂ P (B);
(b) P (A) ∪ P (B) ⊂ P (A ∪ B).
Dati primjer skupova A, B tako da u (b) vrijedi stroga inkluzija.
17. Neka su A, B, C skupovi. Dokazati
(A ∩ B) ∪ (B ∩ C) ∪ (C ∩ A) = (A ∪ B) ∩ (B ∪ C) ∩ (C ∪ A).
18. Dokazati da za proizvoqne skupove A, B, C vrijedi
A △ C = B △ C ⇒ A = B.
19. Dokazati da za proizvoqne skupove A, B, C ⊂ X vrijedi:
A ∩ (B △ C) = B ⇔ A ∩ C = ∅ ∧ B ⊂ A.
20. Neka su A, B, C, D skupovi. Ako je A △ B = C △ D pokazati da je tada i
A △ C = B △ D.
21. Bez kori{}ewa karakteristi~nih funkcija dokazati
C ⊂ A ⇒ (A ∩ B) △ C = A ∩ (B △ C).
22. Za kakve skupove A, B, C sqede}i sistemi imaju rje{ewe
(a) A ∪ X = B ∩ X, A ∩ X = C ∪ X ,
(b) A\X = X\B, X\A = C\X ?
[ta je rje{ewe sistema?
3
23. Odrediti relacije R−1 , R ◦ R, R ◦ R−1 , ako je
(a) R = {(x, y) : x, y ∈ N∗ , x|y} ⊂ N∗ × N∗
(b) R = {(x, y) : x, y ∈ R, x + y ≤ 0} ⊂ R × R
(v) R = {(x, y) : x, y ∈ R, 2x ≥ 3y} ⊂ R × R
24. Neka je S neprazan skup i ρ ⊂ P (S)2 relacija definisana sa
def
(∀A, B ⊂ S) AρB ⇔ A ∩ B = ∅.
Ispitati da li je relacija ρ refleksivna,simetri~na, antisimetri~na i tranzitivna.
25. Za x ∈ R, cio dio broja x (u oznaci ⌊x⌋) je najve}i cio broj koji je mawi od x, dok
je razlomqeni dio broja x (u oznaci {x}) definisan sa {x} = x − ⌊x⌋. Neka je
≺⊂ R2 relacija definisana na sqede}i na~in: Za x, y ∈ R
(
)
def
x ≺ y ⇔ {x} < {y} ∨ {x} = {y} ∧ ⌊x⌋ < ⌊y⌋ .
(a) Ispitati refleksivnost, simetri~nost, antisimetri~nost i tranzitivnost
relacije ≺.
(b) Dokazati da za svako x ∈ R ne postoji y ∈ R tako da je x ≺ y ≺ x + 1.
26. Neka je S = (−∞, 0) ⊂ R i neka je ρ ⊂ S 2 relacija koja je definisana na
sqede}i na~in:
x, y ∈ S
def
(x, y) ∈ ρ ⇔ (x2 − y 2 )(x2 y 2 − 1) ≤ 0.
Ispitati refleksivnost, simetri~nost, antisimetri~nost i tranzitivnost
relacije ρ.
27. Neka je S = (0, 1) ⊆ R i ρ ⊂ S 2 relacija koja je definisana na sqede}i na~in:
x, y ∈ S
def
(x, y) ∈ ρ ⇔
x2
y2
≥
.
1 − y2
1 − x2
Ispitati refleksivnost, simetri~nost, antisimetri~nost i tranzitivnost
relacije ρ.
28. Neka je S = R \ {0} i ρ ⊂ S 2 relacija koja je definisana na sqede}i na~in:
x, y ∈ S
def
(x, y) ∈ ρ ⇔
x + 5y
≥ 2.
3y
Ispitati refleksivnost, simetri~nost, antisimetri~nost i tranzitivnost
relacije ρ.
4
29. Neka su ρA ⊂ A2 i ρB ⊂ B 2 tranzitivne relacije pri ~emu je A ∩ B = ∅.
Relacija ρ ⊂ (A ∪ B)2 je definisana na sqede}i na~in: Za a, b ∈ A ∪ B
def
(a, b) ∈ ρ ⇔ (a, b) ∈ ρA ∨ (a, b) ∈ ρB ∨ (a, b) ∈ A × B.
Ispitati da li je ρ tranzitivna relacija.
30. Ako su R, R1 , R2 ⊂ A × B relacije iz A u B , dokazati da je onda:
(a) (R1 ∪ R2 )−1 = R1−1 ∪ R2−1 (b) (Rc )−1 = (R−1 )c .
31. Dokazati da je relacija "biti djeliteq" relacija poretka na N∗ .
32. Dokazati da ako je R relacija poretka da je onda i R−1 relacija poretka.
33. Dokazati da ako su R1 i R2 simetri~ne relacije da su onda i R1 ∪ R2 , R1 ∩
R2 , R1−1 simetri~ne.
34. Neka su R1 i R2 simetri~ne relacije. Dokazati da je R1 ◦ R2 simetri~na ako
i samo ako je R1 ◦ R2 = R2 ◦ R1 .
35. Navesti primjer relacije koja je:
(a) refleksivna, simetri~na i netranzitivna
(b) refleksivna, antisimetri~na i netranzitivna.
36. Koja od sqede}ih relacija je relacija ekvivalencije na S ,
(a) S = N\{0, 1}, x ∼ y ⇔ nzd(x, y) > 1, gdje je nzd najve}i zajedni~ki
djelilac;
(b) S = R, x ∼ y ⇔ (∃n ∈ Z) x = 2n y ?
37. Neka su R1 i R2 relacije ekvivalencije na X . Dokazati:
(a) R1 ◦ R1 = X × X ⇔ R1 = X × X ;
(b) R1 ◦ R2 = X × X ⇔ R2 ◦ R1 = X × X .
38. Dokazati da je ρ ⊂ A2 relacija ekvivalencije ako vrijedi
∆A ⊂ ρ , ρ = ρ−1 , ρ ◦ ρ ⊂ ρ.
39. Neka je na nepraznom skupu A definisana binarna relacija ρ koja ima sqede}a
svojstva
(a) (∀a ∈ A)(∃b ∈ A) bρa ,
(b) (∀a ∈ A)(∀b ∈ A)(∀c ∈ A) (aρb ∧ aρc ⇒ bρc).
Ispitati da li je ρ relacija ekvivalencije.
40. Neka su ρ, σ ⊂ A2 relacije ekvivalencije. Dokazati da j ρ ∩ σ tako|e relacija
ekvivalencije.
5
41. Ako je ρ tranzitivna relacija za koju vrijedi ρ−1 ◦ ρ ⊂ ρ, pokazati da je i
relacija ρ ◦ ρ−1 tranzitivna.
42. Neka je X ̸= ∅ , D ⊂ X i ∼D ⊂ P (X)2 relacija definisana sa
def
A, B ⊂ X , (A, B) ∈∼D ⇔ A △ B ⊂ D.
Ispitati da li je ∼D relacija ekvivalencije.
43. Dokazati da je ρ ⊂ A2 relacija poretka ako vrijedi
∆A ⊂ ρ , ρ ∩ ρ−1 ⊂ ∆A , ρ ◦ ρ ⊂ ρ.
44. Dokazati da svaka particija nepraznog skupa X defini{e jednu relaciju ekvivalencije na tom skupu ~ije su klase ekvivalencije skupovi iz posmatrane
particije.
def
45. Ispitati da li je relacija ρ ⊂ R2 definisana sa xρy ⇔ xn − y n ≥ 0 relacija
poretka za
(a) n = 3;
(b) n = 4.
46. Neka je ≤A relacija poretka na skupu A i ≤B relacija poretka na skupu B . Na
skupu A × B definisana je relacija ≤AB na sqede}i na~in
def
(a1 , b1 ) ≤AB (a2 , b2 ) ⇔ a1 ≤A a2 ∧ b1 ≤B b2 .
(a) Pokazati da je ≤AB relacija poretka na A × B .
(b) Ako su ≤A i ≤B linearna ure|ewa, da li tada i ≤AB mora biti linearno
ure|ewe?
47. Neka je ρ antisimetri~na i tranzitivna relacija na skupu A i f : A → B
funkcija takva da za sve x, y ∈ A vrijedi f (x) = f (y) ⇒ xρy . Na skupu B je
definisana relacija σ na sqede}i na~in: Za b1 , b2 ∈ B
def
b1 σb2 ⇔ (∃a1 , a2 ∈ A)(f (a1 ) = b1 ∧ f (a2 ) = b2 ∧ a1 ρa2 ).
Ispitati da li je relacija σ antisimetri~na.
48. Neka su R1 i R2 antisimetri~ne relacije na skupu A. Dokazati da je R1 ∪ R2
antisimetri~na relacija ako i samo ako vrijedi R1−1 ∩ R2 ⊂△A .
49. Neka je f : A → B injektivno preslikavawe i S ⊂ B 2 relacija poretka.
Pokazati da je relacija R ⊂ A2 definisana sa
def
(∀a, b ∈ A) (a, b) ∈ R ⇔ (f (a), f (b))⟩ ∈ S
6
relacija poretka. Ako je (A, R) linearno ure|ewe da li takvo mora biti i
ure|ewe (B, S)?
50. Neka je ρ ⊂ A2 relacija i f : A → P (A) funkcija definisana sa
f (x) = {y ∈ A : (x, y) ∈ ρ}.
Ako je ρ relacija poretka dokazati da je f injektivno preslikavawe.
51. Dokazati da na nepraznom skupu A jedina relacija koja je istovremeno relacija
ekvivalencije i relacija poretka jeste dijagonalna relacija ∆A .
52. Ako je ρ relacija poretka na skupu A pokazati da je i ρ−1 relacija poretka na
skupu A. Na osnovu toga dokazati da na svakom kona~nom nepraznom skupu ima
neparan broj relacija poretka.
53. Neka je ρ refleksivna i tranzitivna relacija na skupu A i ∼ relacija na skupu
def
A definisana sa x ∼ y ⇔ xρy ∧ yρx. Pokazati da je ∼ relacija ekvivalencije
def
i da je (A/∼ , ≤) ure|en skup ako je relacija ≤ definisana sa a∼ ≤ b∼ ⇔ aρb.
54. Uz pomo} matemati~ke indukcije dokazati:
(a)
(b)
n
∑
k=1
n
∑
1
n
=
(3k − 2)(3k + 1)
3n + 1
(−1)k k 2 = (−1)n
k=1
n(n + 1)
2
n
n
∑
∑
(v) ak ≤
|ak |, gdje su a1 , . . . , an ∈ R proizvoqni;
k=1
(g)
n
∏
k=1
(d)
cos
k=1
sin x
x
= n
, za proizvoqno x ∈ (0, π);
k
2
2 sin 2xn
n+1
n
∏
(
k)
1 − x2
, za sve x ̸= 1;
1 + x2 =
1−x
k=0
(|)
n
∑
√
1
√ < 2 n, za n ≥ 2;
k
k=1
55. Dokazati da za svaki prirodan broj n ≥ 1 vrijedi
1·2·2n +2·3·2n−1 +. . .+n·(n+1)·2+(n+1)·(n+2) = 2n+4 −(n2 +7n+14).
7
56. Dokazati da za svako n ≥ 1 vrijedi
n
∏
4k − 1
≤
4k + 1
√
k=1
3
.
4n + 3
57. Matemati~kom indukcijom dokazati da vrijedi
(∀n ∈ N) 9|(4 22n − 3n − 4).
58. Neka je m neparan prirodan broj. Dokazati da za sve n ≥ 1 broj 2n+2 dijeli
n
broj m2 − 1.
59. Dokazati da za sve n ≥ 2 vrijedi
4n
(2n)!
<
.
n+1
(n!)2
60. Dokazati da za svaki prirodan broj n ≥ 1 vrijedi
1
1
1
+
+ ... +
> 1.
n+1 n+2
3n + 1
61. Neka su a, b ∈ (0, +∞). Dokazati da za sve n ≥ 2 vrijedi
√
an +
√
bn ≤
√
(a + b)n .
62. Matemati~kom indukcijom dokazati da vrijedi
( ) ( )
( )
n
n
n
(∀n ∈ N)
+
+ ... +
= 2n .
0
1
n
63. Dokazati
( ) ( ) ( )
( ) ( ) ( )
n
n
n
n
n
n
(∀n ≥ 1)
+
+
+ ... =
+
+
+ . . . = 2n−1 .
0
2
4
1
3
5
64. Dokazati da se za svako n ≥ 2 i skupove ∅ =
̸ A1 , . . . , An ⊂ X , skup
A1 △ A2 △ . . . △ An
sastoji od onih elementata iz X koji pripadaju Ai za neparno mnogo indeksa
i ∈ {1, . . . , n}.
8
65. Neka je a ∈ R. Dokazati da je
√
|
a2 +
√
√
a2 + . . . + a2 < |a| + 1
{z
}
n
korijena
66. Neka je niz (an ) rekurzivno dat sa
1
a1 = 1, a2 = 1, an =
2
(
an−1 +
2
)
an−2
(n ≥ 3).
Dokazati da je 1 ≤ an ≤ 2, za sve n ∈ N∗ .
67. Neka je niz (an ) rekurzivno dat sa
a1 = 1, a2 = 8, an = an−1 + 2an−2 (n ≥ 3).
Dokazati da je an = 3 · 2n−1 + 2 · (−1)n , za sve n ∈ N∗ .
n
68. Za n ∈ N brojevi fn = 22 + 1 se nazivaju Fermaovi brojevi. Dokazati da za
svako n ∈ N Fermaovi brojevi zadovoqavaju rekurentnu relaciju
fn+1 = f0 · f1 · . . . · fn + 2.
n
69. Dokazati da za sve n ≥ 2 brojevi oblika 22 + 1 imaju cifru jedinica 7.
70. Fibona~ijevi brojevi {fn : n ≥ 1} su brojevi koji zadovoqavaju uslove
f1 = f2 = 1 , fn+2 = fn + fn+1 , n ≥ 1.
Dokazati da za svako n ≥ 1 Fibona~ijevi brojevi zadovoqavaju rekurentnu
relaciju
2
fn · fn+2 = fn+1
+ (−1)n+1 .
71. Fibona~ijevi brojevi {fn : n ≥ 1} su brojevi koji zadovoqavaju uslove
f1 = f2 = 1 , fn+2 = fn + fn+1 , n ≥ 1.
Dokazati da za svako n ≥ 1 vrijedi 5|f5n .
72. Dokazati da je za svaki prirodan broj n
(3 +
√
5)n + (3 −
paran prirodan broj .
9
√
5)n
73. Dokazati da za svako n ≥ 2 postoji n razli~itih prirodnih brojeva, takvih da
je zbir wihovih kvadrata kvadrat prirodnog broja.
74. Neka je niz (an ) rekurzivno dat sa an = 2an−1 + 3an−2 (n ≥ 3). Dokazati:
(a) Ako su a1 , a2 ∈ N neparni, onda su svi (an ) neparni;
(b) a1 = a2 = 1 ⇒ an =
1
2
)
( n−1
3
− (−1)n (n ∈ N∗ ).
75. Dokazati da za svaki prirodan broj n ≥ 2 broj 22
razli~itih prostih djeliteqa.
n+1
n
+ 22 + 1 ima najmawe n
76. Koje od sqede}ih funkcija f : N∗ × N∗ → N∗ je surjektivna, ako je
(a) f (a, b) = a + b (b) f (a, b) = ab (v) f (a, b) =
(g) f (a, b) =
ab(a+b)
2
ab(b+1)
2
(d) f (a, b) = 3a−1 (3b − 1)
77. Koja od sqede}ih funkcija f : A → R je iwektivna, ako je
(a) A = R, f (x) =
x
1+x2
(b) A = (−1, 1), f (x) =
(v) A = R, f (x) =
x2
1+x2
(g) A = [0, ∞), f (x) =
(d) A = R, f (x) =
x
1+x2
x2
1+x2
x3
1+x2 .
78. Ispitati da li je funkcija f : R → R data sa
{
f (x) =
x+1
, za x < 0
1 − 2x , za x ≥ 0
iwektivna. Da li je surjektivna?
79. Neka je funkcija f : R2 → R2 data sa f (x, y) = (4 + x − y, 2y − x − 5).
Pokazati da je f bijekcija i na}i wenu inverznu funkciju.
80. Funkcija f : R → R je definisana sa
{
f (x) =
2x + 1
x
6 +1
, za x ≤ 0
, za x > 0
Pokazati da je f bijekcija i odrediti wenu inverznu funkciju.
10
81. Neka su f : A → B i g : B → C preslikavawa. Pokazati
(a) Ako je g ◦ f iwektivno preslikavawe onda je f iwektivno preslikavawe;
(b) Ako je g ◦ f surjektivno preslikavawe onda je g surjektivno preslikavawe;
(v) Ako je g ◦ f bijektivno preslikavawe onda je f iwektivno preslikavawe, a
g surjektivno preslikavawe.
82. Dokazati da je f : X → Y injektivno preslikavawe ako i samo ako postoji
preslikavawe g : Y → X tako da je g ◦ f = idX .
83. Neka je f : A → B preslikavawe. Ako za preslikavawa g, h : B → A va`i da
je g ◦ f = idA i f ◦ h = idB dokazati da je g = h = f −1 .
84. Neka su f : A → B i g : B → C funkcije. Dokazati da je funkcija g ◦ f :
A → C 1 − 1 preslikavawe ako i samo ako je f 1 − 1 preslikavawe i za svaka
dva elementa b1 , b2 ∈ f (A) vrijedi implikacija g(b1 ) = g(b2 ) ⇒ b1 = b2 .
85. Pokazati da se svako preslikavawe mo`e razlo`iti kao kompozicija dva preslikavawa od kojih je jedno iwektivno a drugo surjektivno.
86. Neka je f : X → X preslikavawe koje ima osobinu da postoji prirodan broj n
tako da je f n = idX (pri ~emu je f n = f n−1 ◦f i idX je identi~ko preslikavawe
na skupu X ). Pokazati da je f bijekcija.
87. Neka je f : X → Y injektivno preslikavawe i F : P (X) → P (Y ) funkcija
data sa: Za A ⊂ X
F (A) = {f (x) : x ∈ A} ⊂ Y
Ispitati da li je F injektivno preslikavawe.
88. Neka je f : X → Y preslikavawe i A ⊂ X , B ⊂ Y . Dokazati
(a) A ⊂ f −1 f (A);
(b) f f −1 (B) ⊂ B;
(v) A = f −1 f (A) ako i samo ako je f "1-1";
(g) f f −1 (B) = B ako i samo ako je f "na".
89. Neka je f : A → B preslikavawe i M, N ⊆ A.
(a) Ako je M ⊆ N , dokazati da je f (M ) ⊆ f (N ).
(b) Ako je f "1-1" i M ( N , dokazati da je f (M ) ( f (N ).
90. Neka je f : A → B preslikavawe i M, N ⊆ B .
(a) Ako je M ⊆ N , dokazati da je f −1 (M ) ⊆ f −1 (N ).
(b) Ako je f "na" i M ( N , dokazati da je f −1 (M ) ( f −1 (N ).
11
91. Preslikavawe f : A → B je "1 − 1" ako i samo ako za sve neprazne skupove S
i sva preslikavawa g : S → A i h : S → A vrijedi f ◦ g = f ◦ h ⇒ g = h.
Dokazati.
92. Preslikavawe f : A → B je "na" ako i samo ako za sve neprazne skupove S i
sva preslikavawa g : B → S i h : B → S vrijedi g ◦ f = h ◦ f ⇒ g = h.
Dokazati.
93. Ako je f : X → Y 1 − 1 preslikavawe, a A i B podskupovi od X takvi da je
A ∩ B = ∅, dokazati da je tada i f (A) ∩ f (B) = ∅.
94. Neka je X skup sa bar tri elementa i f : X → X preslikavawe koje ima osobinu
da za svaka dva dvo~lana skupa A, B ⊆ X vrijedi
f (A) = f (B) ⇒ A = B.
Dokazati da je f ”1 − 1”.
95. Neka je f : X → Y injektivno preslikavawe. Dokazati da za proizvoqne
A, B ⊂ X vrijedi
f (A △ B) = f (A) △ f (B).
96. Za funkciju f : X → Y ka`emo da je netrivijalna ako je |f (X)| > 1 tj. ako
se svi elementi iz X ne slikaju u isti element iz Y . Ako je f : X → Y "na"
i g : Y → Z netrivijalna dokazati da je g ◦ f : X → Z tako|e netrivijalna
funkcija.
97. Neka su f, g : X → X preslikavawa takva da je f ◦ g ◦ f ”1 − 1”, a g ◦ f ◦ g
"na". Ispitati da li funkcije f i g moraju biti bijekcije.
98. Neka je X skup. Pokazati da je funkcija f : P (X) → {0, 1}X data sa f (A) =
χA (gdje je χA karakteristi~na funkcija skupa A) bijekcija.
99. Neka su A, B, C ⊂ X skupovi. Pomo}u funkcija χA , χB i χC izraziti
funkcije χA∪B , χA∩B , χA∪(B∩C) , χX\A i χA△B .
100. Pokazati da broj 2011 nije mogu}e predstaviti kao zbir kvadrata dva prirodna
broja.
101. Pokazati da nijedan broj u nizu
11, 111, 1111, 11111, . . .
nije potpun kvadrat.
102. Dokazati da kvadrat bilo kog prostog broja ve}eg od 3 pri djeqewu sa 12 daje
ostatak 1.
12
103. Neka je n ≥ 1 prirodan broj. Dokazati da je broj
(n + 1)(n + 2) · . . . · (n + n)
djeqiv sa 2n , a nije djeqiv sa 2n+1 .
104. Dokazati da je zbir 2n + 1 uzastopnih prirodnih brojeva djeqiv sa 2n + 1.
105. Ispitati da li postoji prirodan broj n ≥ 1 takav da je broj 2n + n2 djeqiv sa
7.
106. Ako su u trocifrenom broju djeqivim sa 7 posqedwe dvije cifre jednake,
pokazati da je zbir cifra tog broja djeqiv sa 7.
107. Dokazati da je trocifreni broj ~iji je dekadni zapis abc djeqiv sa 7 ako i samo
ako je broj 10a + b + 5c djeqiv sa 7.
108. Zbir cifara trocifrenog broja je jednak 7. Dokazati da je taj broj djeqiv sa 7
ako i samo ako su mu cifre desetica i jedinica jednake.
109. Ako je broj ~ije su sve cifre u dekadnom zapisu jednake jedan prost, dokazati da
je tada i broj cifara tog broja prost. Da li vrijedi obrnuto tvr|ewe?
110. Na}i sve prirodne brojeve koji se zavr{avaju dvjema istim ciframa kojima se
zavr{avaju i wihovi kvadrati.
111. Neka je za prirodan broj n ≥ 2 broj 2n + n2 prost. Dokazati da je broj n − 3
djeqiv sa 6.
112. Neka su a, b, c ∈ N takvi da je a2 + b2 = c2 . Dokazati da je abc djeqiv sa 60.
113. Ako je p > 3 prost broj pokazati da 24|(p2 − 1).
114. Ako su brojevi p i 2p2 + 1 prosti, pokazati da je i 3p2 + 2 tako|e prost broj.
115. Dokazati da ima beskona~no mnogo prostih brojeva oblika 4k − 1, k ∈ N∗ .
116. Za brojeve a, b, c, d ∈ N∗ vrijedi a2 + b2 = c2 + d2 . Pokazati da je a + b + c + d
slo`en broj.
117. Dokazati da za proizvoqne skupove A1 , . . . , An postoje disjunktni skupovi
A′1 , . . . , A′n takvi da je Ai ∼ A′i za i = 1, . . . , n .
118. Neka su A, B, A1 , B1 skupovi. Dokazati:
(a) A × B ∼ B × A (b) A ∼ A1 ∧ B ∼ B1 ⇒ A × B ∼ A1 × B1
(v) A ∼ A1 ∧ B ∼ B1 ⇒ AB ∼ A1 1 .
B
119. Neka su A, B, C skupovi. Dokazati
(a) AC × B C ∼ (A × B)C ;
(b) (AB )C ∼ AB×C .
13
120. Dokazati da je za svaki skup X ispuweno P (X) ∼ {0, 1}X .
121. Neka je X kona~an skup i f : X → X funkcija. Dokazati:
f je bijekcija ⇔ f je ”1 − 1”.
122. Dokazati da ako je S ⊂ N beskona~an, onda S nije ograni~en odozgo.
123. Dokazati da je skup A beskona~an ako i samo ako postoji preslikavawe f : A →
A koje je iwektivno a nije surjektivno.
124. Ako je |A| ≤ |B| tada postoji surjektivno preslikavawe f : B → A. Dokazati.
125. Dokazati da je [a, b] ∩ Q ∼ Q, gdje je a, b ∈ R, a < b.
126. Dokazati da skup (0, 1) × (0, 1) nije prebrojiv.
127. Dokazati da skupovi realnih i iracionalnih brojeva ekvipotentni.
128. Dokazati da kona~nih podskupova od N ima prebrojivo mnogo.
129. Neka je {An : n ∈ N} prebrojiva familija prebrojivih skupova. Dokazati da
∪
je n∈N An prebrojiv skup.
130. Neka su A i B kona~ni skupovi takvi da je B ⊂ A i |B| = n , |A| = m, gdje je
n ≤ m. Dokazati da je broj skupova C za koje vrijedi B ⊂ C ⊂ A jednak 2m−n .
131. Dokazati da su skupovi N i N × {0, 1, 2} ekvipotentni.
132. Dokazati da je skup svih intervala (otvorenih, zatvorenih, poluotvorenih,
poluzatvorenih) u R sa racionalnim granicama prebrojiv.
133. Pokazati da je bilo koja familija disjunktnih otvorenih intervala u R najvi{e
prebrojiva.
134. Neka je A = {A ⊂ N : 2 ∈ A}. Pokazati da je |A| = c.
135. Dokazati da je
[0, 1) ∼ (−∞, 0).
136. Neka su A = {A ⊂ N : 1 ∈ A} i B = {B ⊂ N : 2 ∈
/ B}. Dokazati da je
|A| = |B|.
137. Neka je ≤⊂ N2 relacija definisana na sqede}i na~in: Za m, n ∈ N
def
m ≤ n ⇔ m|n.
(a) Pokazati da je ≤ relacija poretka.
(b) Ako je A ⊂ N kona~an skup na}i (ako postoje) sup A , inf A, max A i min A.
(v) Ako je P N ⊂ N skup prostih brojeva na}i (ako postoje) sup A , inf A, max A
i min A.
14
138. Neka je O = {(−∞, a) : a ∈ R} ⊂ P (R). Pokazati da za svaku familiju
∪
A ⊂ O vrijedi A ∈ O.
139. Ako je ∅ ̸= A ⊂ R i ∅ ̸= B ⊂ R i ako je za sve a ∈ A i sve b ∈ B ispuweno
a ≤ b, pokazati da je sup A ≤ inf B .
140. Neka su A, B ⊂ R ograni~eni skupovi i neka je
A + B = {a + b : a ∈ A, b ∈ B}.
Pokazati
(a) sup(A + B) = sup A + sup B ;
(b) inf(A + B) = inf A + inf B .
141. Neka je A ⊂ R odozdo ograni~en skup i neka je −A = {−a : a ∈ A}. Pokazati
da je sup(−A) = − inf A.
142. Neka su A i B neprazni, odozgo ograni~eni podskupovi od R. Dokazati da je
sup(A ∪ B) = max{sup A, sup B}.
143. Odrediti sup S, inf S, min S, max S , ako je:
(a) S =
{
}
{
: x ∈ R ; (b) S = x +
1
x
:
1
2
}
<x≤2 ;
}
{
}
2m
: n ∈ N ; (g) S = m+n
: m, n ∈ N∗
}
{
}
{
(−1)n
1
− n1 : m, n ∈ N∗
(|) S = 1 + 3 n
: n ∈ N∗ ;
(d) S = m
{
}
{ n
}
4n
3
∗
(e) S = m
n + m : m, n ∈ N , m < 10n (`) S =
m+2n : m, n ∈ N
{
( )
}
n
(z) S = 1 + n+1
· cos nπ
:
n
∈
N
.
2
{
}
1
1
(i) S = n+4
− n+3
:n∈N .
{
}
2
n +1
∗
(j) S = cos(nπ) · 3n
:
n
∈
N
.
2 +n
{
}
n2
(k) S = m2 +m+5n
2 : m, n ∈ N \ {0} .
(v) S =
{
|x|
1+|x|
3n−1
5n+2
144. Ako je A = {x ∈ R, x > 0 : x2 > 2}, na}i inf A.
145. Ako je A = {x ∈ Q : x3 < 4}, na}i sup A.
146. Pokazati da je
(
∩
n∈N∗
)
− n1 , n1 = {0}.
147. Pokazati da je
∩
[1 −
n∈N
15
1
, 1) = ∅.
10n
Download

Zadaci iz Osnova matematike