plik


ÿþRACHUNEK ZDAC ~ ( Øð)  nieprawda, |e (negacja); negacja p ~ p ®ð  je[li & to & (implikacja); Ùð  oraz (koniunkcja); 0 1 Úð  lub (alternatywa); 1 0 «ð  wtedy i tylko wtedy (równowa|no[); koniunkcja Ùð : alternatywa Úð : implikacja ®ð: równowa|no[ «ð : p q p Ùð q p q p Úð q p q p ®ð q p q p «ð q 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1. Ustali, czy podana wypowiedz jest zdaniem logicznym. Je|eli podana wypowiedz jest zdaniem  oceni, jaka jest warto[ logiczna tego zdania. a. 1+ð 4 =ð 6 . b. Zwiat jest pikny. c. Ucz si matematyki! d. 3 jest liczba nieparzyst. e. Rok ma 200 dni. f. Sprawdzi, czy liczba 3 jest mniejsza od 1. g. Suma dwóch liczb nieparzystych jest liczb parzyst. h. 2 +ð1<ð 9 . i. Proste a i b s równolegBe. j. Wieloryb jest ryb. 2. Dane s zdania: p  niebo jest ciemne. q  teraz jest wieczór. r  zbiera si na burz. Zapisa przy u|yciu powy|szych oznaczeD i spójników logicznych zdania: a. Niebo jest ciemne i teraz nie jest wieczór. b. Je[li niebo jest ciemne, to teraz jest wieczór lub zbiera si na burz. c. Niebo nie jest ciemne wtedy i tylko wtedy, gdy nie jest wieczór i nie zbiera si na burz. 3. Dane s zdania: p  teoria Freuda ma prawo do miana nauki. q  teoria Freuda mo|e by potwierdzona przez eksperymenty. r  teoria Freuda mo|e by obalona przez eksperymenty. Odczyta zdania z u|yciem symboli logicznych: a. p Úð q . d. qÙð ~ r ®ð p . (ð )ð b. qÚð ~ r . e. pÙð ~ q «ð p Ùð r . (ð )ð (ð )ð c. ~ r ®ð p Ùð q . (ð )ð f. p ®ð q ®ð r . (ð )ð 4. Dobra warto[ci logicznie zdaD p i q tak, aby zdanie p ®ð~ q Ùð ~ p byBo prawdziwe. (ð )ð 5. U|ywajc symboli przyjtych w rachunku zdaD, zapisa nastpujce zdania: a. Student si uczy i zdaje egzaminy. b. Asia i Piotr studiuj. c. Jeste[ inteligentny i nieprawda, |e masz zB pami. d. Je[li Ziemia jest okrgBa, to z faktu, |e ziemia jest pBaska, wynika, |e ziemia jest gwiazd. Matematyka dyskretna. OpracowaBa L. Dobryakova 1 e. To, |e student si nie uczy i [ciga na kolokwiach jest równowa|ne temu, |e nieprawd jest, |e (si uczy lub nie [ciga na kolokwiach). f. Nie jest prawd, |e je|eli Einstein byB genialny, to Newton byB ograniczony. g. Przeczytam kilka podrczników logiki lub wysBucham wykBadów i rozwi|e kilkadziesit zadaD. h. Nie jest prawd, |e je[li Platon zaBo|yB Akademi, to z faktu, |e Arystoteles byB uczniem Platona wynika, |e Arystoteles nie uczszczaB do Akademii. i. Skoro Ziemia obraca si wokóB SBoDca, to je[li Ziemia nie obraca si wokóB SBoDca, to dostan 5 na egzaminie. j. Je|eli nieprawda, |e twierdzenia matematyki mog okaza si faBszywe, to nieprawda, |e twierdzenia logiki mog okaza si faBszywe. k. Nie posiadasz gruntownej wiedzy o jzyku, je[li sBabo znasz gramatyk i nigdy nie uczyBe[ si logiki. 6. Poda warto[ci logiczne zdaD, je|eli wiadomo, |e zdanie p ®ð q jest faBszywe: a. p Úð q ®ð p . (ð )ð b. q Úð p «ð~ p . (ð )ð c. p ®ð qÙð ~ p . (ð )ð 7. Okre[li warto[ci logiczne nastpujcych zdaD zBo|onych: a. Je[li 4 jest liczb dodatni, to 5 jest liczb ujemn. b. Je[li 4 jest liczb dodatni, to 5 jest liczb dodatni. c. Je[li 4 jest liczb ujemn, to 5 jest liczb ujemn. d. Je[li 4 jest liczb ujemn, to 5 jest liczb dodatni. e. 2 >ð 5 lub 2 <ð 5. f. Romb jest kwadratem lub romb jest czworoktem. g. 3 21®ð 9 21. h. 3 <ð 2 wtedy i tylko wtedy, gdy Ziemia jest planet. 8. Poda zdania odwrotne, kontrapozycj oraz zdania przeciwne dla nastpujcych zdaD: a. Je[li 2 +ð 2 =ð 5 , to 4 +ð 6 =ð 9 . b. Je[li dzisiaj jest 1 wrze[nia, to 5+ð 5 =ð11. c. p Ùð q ®ð r . (ð )ð d. Je[li x +ð y =ð1, to x2 +ð y2 ³ð1. e. Je[li x >ð a i x <ð-ða , to x >ð a . f. Je[li x2 =ð x , to x =ð 0 lub x =ð1. 9. Wyznaczy warto[ logiczn zdania zBo|onego przy podstawieniu w p =ð1, w q =ð 0 . (ð )ð (ð )ð a. ~ p Úð q . h. p ®ð q ®ð q . (ð )ð b. pÙð ~ q . i. p ®ð q ®ð p . (ð )ð c. ~ p ®ð~ q . j. p ®ð q «ð q Úð p . (ð )ð (ð )ð d. ~ p «ð q . (ð )ð k. éð p Úð q ®ð p ùð Úð p «ð q . (ð )ðûð (ð )ð ëð e. p Úð q «ð~ q . (ð )ð l. ~ p Ùð q «ð ~ pÚð ~ q . (ð )ð (ð )ð f. p Ùð q ®ð~ p . (ð )ð g. p ®ð q ®ð p . (ð )ð Matematyka dyskretna. OpracowaBa L. Dobryakova 2 10. Dane s zdania: p  w logice 1 oznacza faBsz. q  liczba 25 dzieli si przez 5. r  86 -ð80 =ð16 . Wyznaczy warto[ logiczn zdania zBo|onego: a. ~ p Ùð q Úð r . g. ~ p ®ð q ®ð r . (ð )ð (ð )ð b. ~ p Úð q Ùð r . h. ~ p ®ð q ®ð r . (ð )ð (ð )ð c. ~ p Ùð q Úð r . i. ~ p «ð q «ð r . (ð )ð (ð )ð d. ~ p Úð q Ùð r . (ð )ð j. éð p ®ð r Úð ~ qùð «ð éð p ®ð rÙð ~ q ùð . (ð )ð (ð )ðûð ëð ûð ëð e. ~ p Úð q Ùð r . (ð )ð k. éð p «ð r Úð ~ pùð «ð éð p «ð r Úð q ùð . (ð )ð (ð )ðûð ëð ûð ëð f. ~ p Ùð q Úð r . (ð )ð 11. Jak warto[ logiczn posiada zdanie oznaczone liter a, je[li jest prawd, |e: a. a tworzy faBszyw koniunkcj z dowolnym zdaniem. b. a tworzy faBszyw koniunkcj tylko z niektórymi zdaniami. c. a tworzy prawdziw koniunkcj z niektórymi zdaniami. d. a tworzy prawdziw alternatyw z dowolnym zdaniem. e. a tworzy prawdziw alternatyw tylko z niektórymi zdaniami. f. a tworzy faBszyw alternatyw z niektórymi zdaniami. g. Implikacja, której pierwszym czBonem (poprzednikiem) jest a, jest zawsze prawdziwa. h. Implikacja, której drugim czBonem (nastpnikiem) jest a, jest zawsze prawdziwa. 12. Udowodni, |e je|eli zdanie p jest faBszywe, to dla ka|dego zdania q mamy: a. p Úð q równowa|ne jest q . b. p Ùð q równowa|ne jest p . 13. Udowodni, |e je|eli zdanie p jest prawdziwe, to dla ka|dego zdania q mamy: a. p Ùð q równowa|ne jest q . b. p Úð q równowa|ne jest p . 14. Wykaza, |e nastpujca formuBa jest tautologi: ~ p Úð q «ð~ pÙð ~ q . (ð )ð 15. Udowodni I prawo de Morgana: Zaprzeczenie koniunkcji jest równowa|ne alternatywie zaprzeczeD. 16. Wykaza, |e nastpujca formuBa jest tautologi: éð p Úð q Úð r ùð «ð éð p Úð q Úð rùð . (ð )ðûð ëð(ð )ð ëð ûð 17. Wykaza, nie wykorzystujc tabeli zerojedynkowej, |e nastpujce wyra|enia s tautologiami: a. ~ p ®ð ( p ®ð q). e. [( p ®ð q) ®ð p] ®ð p . b. p ®ð ( p Úð q) . f. éð p Ùð q ®ð rùð «ð éð p ®ð q ®ð r ùð . (ð )ð (ð )ðûð ëð ûð ëð c. ( p Ùð q) ®ð p . g. ( p ®ð q) «ð (~ p Úð q) . d. ( p ®ð q) «ð (~ q ®ð~ p) . h. (~ p ®ð p) ®ð p . 18. Sprawdzi, nie wykorzystujc tabeli zerojedynkowej, czy nastpujce wyra|enia s tautologiami: a. [( p Úð q)Ùð ~ p] ®ð q . e. [( p Ùð q) Úð ( p ®ð q)] ®ð ( p ®ð q) . b. [( p Úð q) Ùð ( p ®ð q)] ®ð (q ®ð p) . f. ( p ®ð q) ®ð[ p ®ð (q Úð r)] . c. p ®ð[(~ p) Úð q]. g. ~ [ p Ùð (~ p Ùð q)]. d. ( p ®ð q) ®ð[( p Ùð r) ®ð q] . Matematyka dyskretna. OpracowaBa L. Dobryakova 3 19. Czy prawdziwe jest zdanie: a. Je[li liczba naturalna n dzieli si przez 5, to z faktu, |e n nie dzieli si przez 5 wynika, |e n dzieli si przez 3. b. Je[li liczba n dzieli si przez 2 i n dzieli si przez 7, to z faktu, |e n nie dzieli si przez 7 wynika, |e n dzieli si przez 3. c. Je[li figura a jest czworoktem i a ma wszystkie kty równe, to z faktu, |e a jest czworoktem, wynika, |e a ma boki równe. d. Je[li Jan skBamaB lub Piotr skBamaB, to je[li Jan nie skBamaB, to Piotr skBamaB. e. Je[li Kolumb odkryB Ameryk lub Marco Polo byB w Ameryce, to je[li Kolumb odkryB Ameryk, to Marco Polo nie byB w Ameryce. f. Je[li nieprawda, |e Kolumb odkryB Ameryk, a Marco Polo byB w Ameryce, to Kolumb odkryB Ameryk, a Marco Polo nie byB w Ameryce. g. Je[li Kolumb nie odkryB Ameryk lub Marco Polo nie byB w Ameryce, to nieprawda, |e Kolumb odkryB Ameryk i Marco Polo byB w Ameryce. 20. Zapisa zaprzeczenie podanych ni|ej zdaD. a. Liczba naturalna n jest mniejsza od 5 i jest liczb parzyst. b. a ³ð b lub c £ð a . c. Funkcja f x jest cigBa i ró|niczkowalna. (ð )ð d. Trójkt jest prostoktny znaczy to samo co  trójkt speBnia twierdzenie Pitagorasa . e. Je[li liczba koDczy si cyfr parzyst, to liczba jest parzysta. f. Je[li Ala nie ma kota, to Ala ma psa. g. Je[li a =ð b , to a dzieli si przez b i b dzieli si przez a . h. Je[li liczba dzieli si przez 4 , to dzieli si przez 2. 21. Zapisa, u|ywajc symboli kwantyfikatorów nastpujce zdania i oceni warto[ logiczn ka|dego z nich: a. Istnieje liczba caBkowita, warto[ bezwzgldna której jest warto[ci naturaln. b. Istnieje taka liczba rzeczywista mniejsza od zera, |e jej kwadrat jest wikszy od 1000. c. Ka|dy dzielnik liczby caBkowitej jest od niej mniejszy, bdz jest jej równy. d. Istniej liczby naturalne, które dziel si tylko przez 1 i przez siebie. e. Iloraz liczb naturalnych musi by warto[ci naturaln. f. Iloczyn liczb rzeczywistych mo|e by liczb caBkowit. g. Istnieje taka liczba wymierna, |e iloczyn tej liczby i dowolnej liczby caBkowitej jest liczb caBkowit. h. Do ka|dej liczby caBkowitej mo|na dobra tak liczb wymiern, |e iloczyn tych liczb jest liczb caBkowit. i. Midzy liczbami naturalnymi n i 2×ðn istnieje co najmniej jedna liczba pierwsza. 22. Oceni warto[ logiczn nastpujcych zdaD oraz zapisa ich zaprzeczenia. 1 f. "ðxÎð¡ð$ðy Îð¥ð : x2 +ð y ³ð1. a. "ðxÎð¡ð : sin x =ð . 2 g. $ðxÎð¡ð$ðy Îð¡ð : x2 +ð y <ð 0. b. $ðxÎð¡ð : x =ð -ð2 h. "ðxÎð¡ð"ðy Îð¡ð : x <ð 2×ð y Úð y <ð 2×ð x . (ð )ð c. "ðx Îð¡ð : x2 =ð x . d. $ðxÎð¡ð : x2 =ð x. e. "ðxÎð¡ð : -ð4×ð x £ð 0 Matematyka dyskretna. OpracowaBa L. Dobryakova 4 TEORIA ZBIORÓW 1. Czy zbiory A i B s równe: A =ðÆð , B =ð{Æð}? Odpowiedz uzasadni. 2. Z ilu elementów skBada si zbiór? a. xÎð¥ð : x <ð 4 . {ð }ð f. xÎð¢ð :x2 =ð 8 . {ð }ð g. Æð. b. xÎð¥ð : x2 <ð 4 . {ð }ð h. Æð . {ð }ð c. xÎð¢ð :x <ð 4 . {ð }ð i. Æð, Æð . {ð }ð {ð }ð d. xÎð¢ð :x2 <ð 4 . {ð }ð j. Æð,Æð, Æð . {ð {ð }ð }ð e. xÎð¢ð :x2 =ð 4 {ð }ð 3. Udowodni, |e a,b , b,c ¹ð a,b,c . {ð }ð {ð }ð {ð }ð {ð }ð 4. Udowodni, |e je[li A jest zbiorem pierwiastków równania x2 -ð 4×ð x -ð5 =ð 0 i B =ð -ð1,5 , to {ð }ð A =ð B . 5. Dany jest zbiór A =ð a,b,c, a,b , a , a,b,c,d , a,b,c . {ð {ð }ð {ð }ð {ð }ð {ð }ð }ð a. Które elementy tego zbioru s zbiorami? b. Które z nastpujcych wyra|eD maj sens: Øð aÎð A . Øð a Ìð A . {ð }ð Øð a Ìð A. Øð a,b,c,d Îð A . {ð }ð Øð a Îð A. {ð }ð Øð a,b,c,d Ìð A. {ð }ð 6. Która z nastpujcych równo[ci jest prawdziwa, a która faBszywa dla dowolnego zbioru A ? a. AÈðÆð =ð A. d. AÇðÆð =ð A. b. AÇðÆð =ð Æð . e. AÈð A =ð Æð. c. AÈðÆð =ð Æð . f. A \ A =ðÆð. 7. Wyznaczy elementy nastpujcych zbiorów: a. xÎð¥ð :x2 ³ð 0 . h. xÎð¡ð : x2 +ð 4×ð x +ð 4 £ð 0 . {ð }ð {ð }ð b. xÎð¥ð : 5 -ð x £ð1 . i. xÎð¢ð : (x +ð1)2 £ð 0 . {ð }ð {ð }ð c. xÎð¥ð :x <ð 0 . {ð }ð j. 1,2 , 1,2 ,Æð . {ð }ð {ð }ð {ð }ð {ð }ð d. xÎð¥ð :x =ð 4Úð x =ð 7 . {ð }ð k. 1,2 , 1,2 , Æð . {ð }ð {ð }ð {ð }ð {ð {ð }ð }ð e. Æð . {ð }ð l. xÎð£ð: x2 -ð 4×ð x +ð 5 =ð 0 . {ð }ð f. a,b,c . {ð }ð {ð }ð g. Æð . 8. Znalez warunek charakteryzujcy elementy zbiorów: a. A =ð{...,-ð4,-ð3,-ð 2,-ð1,0}. b. B =ð 1,2,4,8, 16,... . {ð }ð c. C =ð 3,8 . {ð }ð 9. Dane s dwa zbiory A i B . Znalez AÇð B , AÈð B , A \ B , B \ A . a. A =ð 0,3,6,8 , B =ð 3,5,8,9, . {ð }ð {ð }ð b. A =ð xÎð¡ð :x2 -ð x -ð12 ³ð 0 , B =ð xÎð¡ð : 2×ð x -ð3 <ð 7 {ð }ð {ð }ð c. A =ð -ð1,1 \ 1/ 2 , B =ð xÎð¢ð : -ðpð £ð x <ð 20 . (ð ]ð {ð }ð {ð }ð Matematyka dyskretna. OpracowaBa L. Dobryakova 5 10. Dana jest przestrzeD U (uniwersum) oraz zbiory A i B . Wyznaczy A i B . a. U =ð ¥ð , A =ð 1,3,5,7,... , B  zbiór liczb naturalnych wikszych od 6. {ð }ð b. U =ð ¢ð , A =ð ¥ð , B  zbiór liczb caBkowitych mniejszych od  5. c. U  zbiór potg liczby 2 o wykBadniku naturalnym, A  zbiór potg liczby 2 o wykBadniku nieparzystym, B =ð 1,2,4,8... . {ð }ð 11. Wyznaczy zbiory: a. ¥ð Çð 4,7 . (ð ]ð b. ¥ð Çð -ð4,7 . (ð ]ð c. ¢ð Çð -ð4,7 . (ð )ð d. ¥ð \ -ð2,4 . (ð )ð e. 5,6 \ ¥ð. [ð ]ð 12. Niech x, y, z, f s ró|ne od zbioru pustego. Jakie zale|no[ci musz zachodzi pomidzy nimi, |eby zachodziBy równo[ci: a. y, z =ð y, z, f . {ð }ð {ð }ð b. x, y, x, x =ð y, x . {ð }ð {ð }ð c. x, y , z =ð x , z . {ð }ð {ð }ð {ð }ð {ð }ð d. y, f , z =ð y, x . {ð }ð {ð }ð {ð }ð {ð }ð {ð }ð e. x,Æð , z =ð Æð . {ð }ð {ð }ð {ð }ð {ð }ð 13. Przyjmujc, |e ró|ne litery oznaczaj ró|ne przedmioty, ewentualnie liczby rzeczywiste, zbada, jakie relacje inkluzji zachodz miedzy nastpujcymi zbiorami A i B : a. A =ð a ,a,0 , B =ð a . {ð }ð {ð }ð {ð }ð b. A =ð a,b , B =ð a,c,d . {ð }ð {ð }ð c. A =ð xÎð¥ð :x >ð 2 , B =ð y Îð¥ð : y >ð 2 . {ð }ð {ð }ð d. A =ð a×ð x +ð b : a, x,bÎð¡ð , B =ð x +ð y :x, y Îð¡ð . {ð }ð {ð }ð e. A =ð xÎð¥ð : x2 >ð 4 , B =ð xÎð¥ð : x >ð 2 . {ð }ð {ð }ð f. A =ð a,b ,a,b,Æð , B =ð a ,b, Æð . {ð }ð {ð }ð {ð }ð {ð }ð {ð }ð g. A =ð xÎð¡ð : x >ð 0 , B =ð y Îð¥ð : y >ð 0 . {ð }ð {ð }ð h. A =ð a,b , c,d ,c,d , B =ð a,b ,c . {ð }ð {ð }ð {ð }ð {ð }ð {ð }ð 14. Czy nastpujca inkluzja jest prawdziwa czy faBszywa dla dowolnych zbiorów A i B ? Rozwiza zadanie za pomoc diagramów Venna. a. (AÇð A) Íð A. b. (A\ B) Íð (AÇð B). c. (AÇð B) Íð A. 15. Za pomoc diagramów Venna sprawdzi, czy poni|sze równo[ci s prawdziwe. Udowodni te, które s prawdziwe. a. A\ (A\ B) =ð AÇð B. e. (AÈð B) =ð AÇð B. b. (AÈð B) \ A =ð B \ (AÇð B). f. AÈð(AÇð B) =ð A. c. A \ B \ C =ð A \ C \ B \ C . g. AÇð(AÈð B) =ð A. (ð )ð (ð )ð (ð )ð d. (AÇð B) =ð AÈð B. Matematyka dyskretna. OpracowaBa L. Dobryakova 6 16. Udowodni: a. A-ð B =ð B -ð A. &ð &ð b. A-ð B =ð Æð®ð A =ð B. &ð c. AÇð(B -ðC) =ð (AÇð B) -ð (AÇðC). &ð&ð 17. Dowie[, |e dla dowolnych zbiorów A, B,C, D zachodz nastpujce implikacje bdz równowa|no[ci: a. éð A Íð B Ùð C Íð D ùð ®ð AÈðC Íð B Èð D . (ð )ð (ð )ðûð (ð )ð ëð b. éð A Íð B Ùð C Íð D ùð ®ð A \ D Íð B \ C . (ð )ð (ð )ðûð (ð )ð ëð c. A Íð B «ð B =ð éðAÈð B \ A ùð . (ð )ð (ð )ðûð (ð )ð ëð 18. Wyznaczy Ai i Ai . Ið Uð iÎðI iÎðI a. I =ð 0,1,2,3 , Ai =ð i -ð1, i +ð 2 . {ð }ð [ð ]ð b. I =ð 0,1,2,3 , Ai =ð -ði,0,i . {ð }ð {ð }ð c. I =ð 0,1,2,3 , Ai =ð ¡ð \ i . {ð }ð {ð }ð 19. Wyznaczy Ai i Ai , gdy I =ð ¥ð+ð oraz gdy I =ð ¡ð+ð : Uð Ið iÎðI iÎðI a. Ai =ð xÎð¥ð : -ði £ð x £ð i {ð }ð b. Ai =ð xÎð¡ð : -ði £ð x £ð i {ð }ð 1 ìðx üð c. Ai =ð Îð¡ð :0 £ð x £ð íðýð i +ð1þð îð 1 i +ð1 ìðx üð d. Ai =ð Îð¡ð :1-ð £ð x £ð íðýð 1+ð i i +ð 2þð îð ¥ð ¥ð 20. Wyznaczy Ai i Ai , gdy I =ð ¥ð+ð : Ið Uð i=ð1 i=ð1 1 éð0, ùð. a. Ai =ð êð úð i ëð ûð 1 1 éð ùð. b. Ai =ð , êð-ð i i úð ëð ûð éð 1 ùð æð öð c. Ai =ð ¡ð \ çð ÷ð êð0,èð1+ð i øðúð. ëðûð d. Ai =ð ¡ð \ i,¥ð . [ð )ð a. 21. Wyznaczy Ai i Ai , gdy I =ð ¡ð : Ið Uð iÎðI iÎðI 1 éð0, ùð. a. Ai =ð êð i2 +ð1úð ëð ûð b. Ai =ð i,¥ð . (ð )ð 2 éð ùð c. Ai =ð ëð1,i ûð. Matematyka dyskretna. OpracowaBa L. Dobryakova 7 ¥ð 22. Wyznaczy Ai , gdy I =ð ¥ð+ð : Uð i=ð1 11 ìðx üð. a. Ai =ð Îð¡ð :-ð 2 +ð £ð x <ð 2 -ð íðýð ii îðþð b. Ai =ð xÎð¡ð :x2 +ð 2×ð x +ð i =ð 0 . {ð }ð ¥ð 23. Wyznaczy Ai , gdy I =ð ¥ð+ð : Ið i=ð1 1 ìðx üð. a. Ai =ð Îð¡ð :0 £ð x <ð 2 -ð íðýð i îðþð b. Ai =ð xÎð¡ð :x >ð i . {ð }ð 24. Udowodni, |e dla dowolnych rodzin A =ð Ai :i Îð I oraz B =ð Bi :i Îð I : {ð }ð {ð }ð a. Ið(A Èð Bi ) =ðIðA ÈðIðB . i i i iÎðI iÎðI iÎðI b. Uð(A Çð Bi ) ÍðUðA ÇðUðB . i i i iÎðI iÎðI iÎðI c. Uð(A Èð Bi ) =ðUðA ÈðUðB . i i i iÎðI iÎðI iÎðI 25. Wyznaczy iloczyn kartezjaDski A´ð B i B´ð A dla nastpujcych zbiorów A i B . a. A =ð 0,1 , B =ð{1,2,3} {ð }ð b. A =ð 0 ,1 , B =ð{1,2,3} {ð }ð {ð }ð c. A =ðÆð , B =ð a,b,c,d . {ð }ð d. A =ð{Æð, 4}, B =ð{1,2,3}. a. 26. Wyznaczy zbiór A2 i okre[li jego moc: a. A =ð 2,3,4,5 . {ð }ð b. A =ð a,b . {ð }ð 27. Sprawdzi, czy prawdziwa jest nastpujca równo[: A´ð(B ÈðC) =ð (A´ð B) Èð(A´ðC). 28. Sprawdzi, czy prawdziwa jest nastpujca równo[: a. A\ (B´ðC) =ð (A\ B)´ð(A\ C). b. AÇð(B´ðC) =ð (AÇð B)´ð(AÇðC). 29. Udowodni równo[: a. (AÇð B)´ðC =ð (A´ðC) Çð(B´ðC). b. A´ð(B \ C) =ð (A´ð B) \ (A´ðC) . c. B´ð =ð Ai ). IðA Ið(B´ð i iÎðI iÎðI d. B´ð =ð UðA Uð(B´ð Ai ) . i iÎðI iÎðI 30. Uzasadni, |e je[li A´ð B =ð B´ð A, to albo A =ðÆð , albo B =ðÆð , albo A =ð B. Matematyka dyskretna. OpracowaBa L. Dobryakova 8 RELACJE 1. Dane s zbiory A =ð -ð3,0,4 , B =ð -ð1,-ð2,5 , Wyznaczy relacje Âð Íð A´ð B, aÂðb: {ð }ð {ð }ð a. a +ð b >ð 0. b. a -ðb <ð 0 . c. a +ð b £ð 0. d. a -ðb ³ð 0 . e. a×ðb >ð 0 . 2. Wyznaczy dziedziny dla nastpujcych relacji: a. Âð=ð a,b , a,c , b,a . {ð }ð b. Âð=ð a,a , a,b , a,c , b,c . {ð }ð c. Âð=ð a,b,c,d , a,c,b,c , a,d,b,a . {ð }ð d. aÂðb Ûð (aÎð¥ð ÙðbÎð¥ð Ùð a <ð b). 3. Wyznaczy dziedziny relacji, oraz dla relacji binarnych pole relacji, dopeBnienie relacji oraz relacj odwrotn: a. A =ð -ð2,-ð1,0,2 , B =ð 1,2 ,C =ð 0,2,4 , Âð =ð a,b,c :aÎð AÙðbÎð B Ùð cÎðC Ùð a +ð 2×ðb =ð c . {ð }ð {ð }ð {ð }ð {ð }ð b. A =ð 2,3,7,14 , B=ð 3,5,6,9,10 , Âð =ð a,b :aÎð AÙðbÎð B Ùð a i bs wzgldniepierwsze . {ð }ð {ð }ð {ð (ð )ð }ð 4. Dla zadanych relacji dwuargumentowych Âð1 i Âð2 wyznaczy Âð1 oðÂð2 : a. Âð1 =ð 1,2 , 2,3 , 1,4 , Âð2 =ð 2,3 , 3,2 , 4,2 , 4,5 . {ð }ð {ð }ð b. Âð1 =ð x, y , x, z , Âð2 =ð x, y , y, x , y, z , z, z . {ð }ð {ð }ð 5. Dla zadanych relacji dwuargumentowych Âð wyznaczy D(Âð), D-ð1(Âð),Âð-ð1, ÂðoðÂð, ÂðoðÂð-ð1 oraz Âð-ð1 oðÂð : 2 a. Âð =ð x, y Îð ¥ð+ð :x | y . (ð )ð {ð }ð b. Âð =ð x, y Îð¡ð2 : x +ð y £ð 0 . {ð }ð c. Âð =ð x, y Îð¡ð2 : 2×ð x ³ð 3×ð y . {ð }ð 6. Udowodni, |e dla dowolnej relacji Âð : Âð Íð D Âð ´ð D-ð1 Âð . (ð )ð (ð )ð -ð1 7. Sprawdzi, czy prawdziwy jest wzór (Âð1 ÇðÂð2)-ð1 =ð Âð1 ÇðÂð-ð1. 2 -ð1 8. Udowodni, |e (Âð1 oðÂð2)-ð1 =ð Âð-ð1 oðÂð1 . 2 9. Udowodni, |e dla dowolnych relacji binarnych prawdziwa jest równo[ (Âð1 oðÂð2) oðÂð3 =ð Âð1 oð(Âð2 oðÂð3) . 10. Dla zbioru A =ð 1,2,3 poda przykBad relacji Âð : {ð }ð a. Zwrotnej. b. Symetrycznej. c. Przechodniej. 11. ZakBadajc, |e ró|ne litery oznaczaj ró|ne elementy, zbada, które wBasno[ci maj nastpujce relacje ÂðÍð A2 , gdzie A =ð a,b,c,d . {ð }ð a. Âð=ð a,a , b,b , a,b . A w zbiorze B =ð a,b ? {ð }ð {ð }ð b. Âð=ð a,a , b,b , c,c , d,d , a,b , b,a {ð }ð. c. Âð=ð a,b , a,c , b,c , c,c , a,a , b,b . A w zbiorze B =ð a,b,c ? {ð }ð {ð }ð Matematyka dyskretna. OpracowaBa L. Dobryakova 9 12. Udowodni, |e relacja ÂðÍð¡ð2 jest zwrotna, symetryczna i przechodnia: Âð =ð x, y :x2 =ð y2 . {ð }ð 13. Zbada, które wBasno[ci ma relacja Âð : a. Âð Íð ¥ð2 :Âð =ð x, y : 2 x +ð y . {ð }ð b. Âð Íð ¢ð2 :Âð =ð x, y :3 x -ð y {ð }ð. c. Âð Íð ¥ð2 :Âð =ð x, y : x ¹ð 0 Ùð x y {ð }ð. d. Âð Íð ¡ð2 :Âð =ð x, y : x2 ¹ð y2 . {ð }ð e. Âð Íð ¥ð2 :Âð =ð x, y : x×ð y =ð 4 {ð }ð. 14. Sprawdzi, czy nastpujce zdanie jest prawdziwe:  Cz[ wspólna dwu relacji przechodnich jest przechodnia . 15. Udowodni, |e na to by relacja Âð byBa symetryczna potrzeba i wystarcza, by Âð Íð Âð-ð1. 2 16. Dla danego zbioru X oraz relacji ÂðÍð X zbada, czy Âð jest zwrotna, symetryczna i przechodnia. Je[li relacja jest relacj równowa|no[ci, wskaza klasy abstrakcji: a. X =ð ¥ð, xÂðy Ûð 2 x +ð y . b. X =ð ¥ð, xÂðy Ûð 4 x +ð y c. X =ð ¥ð, xÂðy Ûð 5 x -ð y . d. X =ð ¡ð, xÂðy Ûð x -ð y =ð 3. e. X =ð ¡ð, xÂðy Ûð y =ð x2 . f. X =ð ¡ð, xÂðy Ûð x2 ¹ð y2 g. X =ð -ð2,-ð1,0,1 , xÂðy Ûð x -ð y ¹ð -ð3. {ð }ð h. X =ð ¡ð, xÂðy Ûð x2 +ð (y -ð 2)2 >ð 4. i. X =ð ¡ð, xÂðy Ûð 3 £ð x -ð y £ð 6 . j. X =ð ¡ð, xÂðy Ûð x×ð y ³ð 0. 17. Zbada, czy relacja Âð jest relacj równowa|no[ci. Je[li tak, wyznaczy klasy abstrakcji. X =ð ¥ð´ð¥ð, dla x =ð m1,n1 , y =ð m2,n2 relacja Âð jest okre[lona nastpujco: xÂðy Ûð m1,n1 Âð m2,n2 Ûð m1 +ð n2 =ð n1 +ð m2 . 18. W zbiorze X dana jest relacja Âð . Zbada, czy relacja ta jest relacj porzdku oraz relacj liniowego porzdku. a. X =ð ¢ð,Âð =ð x, y :x y {ð }ð. b. X jest zbiorem postaci 3n,nÎð¥ð,Âð =ð x, y :x y . {ð }ð c. X =ð ¡ð,Âð =ð x, y :x <ð y Úð y <ð x . {ð }ð d. X =ð ¡ð,Âð =ð x, y :x £ð 2×ð y . {ð }ð e. X =ð ¡ð,Âð =ð x, y :x <ð y Úð x =ð y . {ð }ð f. X =ð ¥ð,Âð =ð x, y :x y Úð x £ð y {ð }ð. g. X =ð ¡ð,Âð =ð x, y :x £ð y . {ð }ð Matematyka dyskretna. OpracowaBa L. Dobryakova 10 FUNKCJE 1. Zbada czy podane relacje s funkcjami? 2 a. Âð Íð ¡ð+ð ,Âð =ð x, y : x2 =ð y2 ; uwaga: ¡ð =ð ¡ð+ð Èð¡ð Èð 0 . (ð )ð {ð }ð {ð }ð -ð b. Âð Íð ¥ð´ð¢ð,Âð =ð x, y : x3 =ð y2 {ð }ð c.  x jest bratem lub siostr y  . d. Âð =ð x, x2 : xÎð¢ð . {ð }ð e. Âð Íð ¡ð2,Âð =ð x, y : x =ð y2 . {ð }ð f. Âð Íð £ð´ð£ð, x, y :Im x =ð Re y . {ð }ð 2. Przyjmujemy, |e dziedzin ka|dej z podanych poni|ej funkcji jest zbiór liczb rzeczywistych, dla których wzór okre[lajcy t funkcj ma sens. Wyznaczy t dziedzin: x +ð 3 a. f x =ð . (ð )ð x -ð 3 x +ð 3 b. f x =ð . (ð )ð x2 -ð 2 x +ð 3 c. f x =ð . (ð )ð 2 x -ð 2 (ð )ð 1 d. f x =ð . (ð )ð 1-ð 4×ð x2 4 -ð x2 e. f x =ð . (ð )ð x2 -ð x -ð 2 3. Dana jest funkcja f : ¡ð ®ð ¡ð . Wyznaczy przeciwdziedzin tej funkcji: a. f x =ð x2 +ð 3. (ð )ð b. f x =ð cos x . (ð )ð c. f x =ð cos x . (ð )ð d. f x =ð1-ð x . (ð )ð e. f x =ð 8. (ð )ð 1 ìð dla x ¹ð 0 ïð f. f x =ð . (ð )ð x4 íð ïð-ð6 dla x =ð 0 îð 1 ìð dla x ¹ð 0 ïð g. f x =ð . (ð )ð x3 íð ïð0 dla x =ð 0 îð 4. Dana jest funkcja f : ¡ð ®ð ¡ð i zbiór A Íð ¡ð . Wyznaczy obraz zbioru A w przeksztaBceniu f : a. f x =ð 4×ð x +ð12, A =ð 1,3,5 . (ð )ð {ð }ð f x =ð 5×ð x +ð1, A =ð -ð2,1 . (ð )ð (ð )ð b. f x =ð x -ð 2 , A =ð 1,6 . (ð )ð [ð )ð c. f x =ð 8, A =ð 1,6 . (ð )ð [ð )ð d. x -ð 3 dla x <ð1 ìð f x =ð , A =ð 0,5 . (ð )ð [ð ]ð íð e. îðx +ð 2 dla x ³ð1 Matematyka dyskretna. OpracowaBa L. Dobryakova 11 5. Wyznaczy obraz zbioru A =ð 5,7,8,9,11,12,13,15 w przeksztaBceniu f : ¥ð ®ð ¥ð {ð }ð okre[lonym poni|ej: a. f x jest najwiksz liczb parzyst mniejsz lub równ x . (ð )ð b. f x jest najwiksz liczb nieparzyst spo[ród dzielników liczby x . (ð )ð 6. Niech f : ¡ð ®ð ¡ð bdzie okre[lone wzorem f (x) =ð x2 -ð5×ð x +ð 6 . Znalez: a. f * 0,2 . [ð ]ð b. f * 0,4 . {ð }ð c. f * -ð2,6 . [ð ]ð -ð1 d. f * -ð¥ð,0 . (ð ]ð -ð1 e. f * -ð¥ð,-ð3 (ð ]ð -ð1 f. f * -ð0,25 . {ð }ð 7. Niech f : ¡ð ®ð ¡ð bdzie okre[lone wzorem f x =ð sin x +ð1. Znalez: (ð )ð a. f * 0,pð . {ð }ð pð pð pð üð b. f *ìð , , . íðýð 2 4 6 îðþð 3×ðpð ùð c. f *éð0, . êð úð 2 ëð ûð 1 -ð1 d. f *æð ,¥ðöð . çð ÷ð 2 èð øð -ð1 e. f * -ð¥ð,1 . (ð )ð -ð1 f. f * 0 . {ð }ð 8. Wyznaczy przeciwobraz zbioru B w przeksztaBceniu f : ¡ð ®ð ¡ð okre[lonym poni|ej: a. f x =ð 3×ð x +ð 2, B =ð 5,11,14 . (ð )ð {ð }ð b. f x =ð x , B =ð 0,2,8 . (ð )ð {ð }ð c. f x =ð1-ð x2, B =ð 0,-ð3 . (ð )ð [ð ]ð d. f x =ð 8, B =ð 4,9 . (ð )ð [ð )ð e. f x =ð 8, B =ð 4,7 . (ð )ð [ð )ð 1 ìð dla x ¹ð 0 ïð f. f x =ð , B =ð -ð1;1 . (ð )ð x2 (ð )ð íð ïð-ð4 dla x =ð 0 îð 9. Niech a ¹ð b , za[ X =ð a,b, a,b , Y =ð a,b , f : X ®ðY bdzie odwzorowaniem {ð {ð }ð {ð }ð }ð okre[lonym wzorami f a =ð f b =ð a , f a,b =ð b . Znalez f * a,b . (ð )ð (ð )ð (ð )ð {ð }ð {ð }ð 10. Udowodni, |e: a. f * AÇð B Ìð f * A Çð f *B . (ð )ð (ð )ð (ð )ð b. f * A \ f *B Ìð f * A \ B . (ð )ð (ð )ð (ð )ð -ð1 c. A Ìð f * f * A . (ð )ð Matematyka dyskretna. OpracowaBa L. Dobryakova 12 11. Okre[li superpozycj f oð g oraz wyznaczy obrazy f oð g * A, f oð g * B : (ð )ð (ð )ð a. f : ¡ð ®ð ¡ð okre[lone jest wzorem f x =ð x +ð 2 , g : ¡ð ®ð ¢ð okre[lone jest wzorem (ð )ð 2 êðx úð g(x) =ð -ð , A =ð 0,1 , B =ð ¡ð+ð , gdzie  caBo[ z liczby  najwiksza liczba caBkowita nie [ð )ð êðûð ëðaúð êð 3úð ëð ûð wiksza od danej liczby. b. f : ¥ð ®ð ¡ð okre[lone jest wzorem f n =ð n , g : ¡ð ®ð ¡ð okre[lone jest wzorem (ð )ð g x =ð x4 -ð x2 , A =ð 2,4,6,8,10 , B =ð 0,1 . (ð )ð {ð }ð {ð }ð c. f : ¡ð2 ®ð £ð okre[lone jest wzorem f ( x, y ) =ð x +ð i ×ð y , g : £ð ®ð ¡ð okre[lone jest wzorem g x =ð x +ð1, A =ð 0,1 ´ð 0,1 , B =ð x, y : x2 +ð y2 £ð 2 . (ð )ð (ð )ð [ð ]ð {ð }ð 12. Niech A =ð 1,2,5,7 i B =ð 3,4,6,8 . Które relacje Âð Íð A´ð B s funkcjami: {ð }ð {ð }ð a. Âð=ð 7,4 , 2,3 , 1,4 , 5,6 . {ð }ð b. Âð=ð 2,4 , 5,8 , 1,3 , 7,6 . {ð }ð c. Âð=ð 2,3 , 5,6 , 7,4 . {ð }ð d. Âð=ð 7,3 , 1,4 , 5,3 , 1,8 , 2,6 . {ð }ð Które z tych funkcji s injekcjami (odwzorowaniami ró|nowarto[ciowymi), a jakie surjekcjmi (odwzorowaniami "na")? 13. Dla danego przeksztaBcenia f : ¡ð ®ð ¡ð zbada, czy f jest injekcj (odwzorowaniem ró|nowarto[ciowym), czy f jest surjekcj (odwzorowaniem "na" ). Je[li f nie jest injekcj, wskaza x1 i x2 takie, |e x1 ¹ð x2 , ale f x1 =ð f x2 . Je[li nie jest surjekcj znalez Wf . (ð )ð (ð )ð a. f x =ð x2 (ð )ð b. f x =ð x3 -ð x2 (ð )ð c. f x =ð , gdzie  caBo[ z liczby  najwiksza liczba caBkowita nie wiksza od danej (ð )ð êðûð êðûð ëðxúð ëðxúð liczby. x ìð , x ¹ð-ð1 ïð d. f x =ð . (ð )ð x +ð1 íð ïð1, x =ð-ð1 îð e. f x =ð x4 -ð5×ð x2 +ð 4 (ð )ð 2×ð x +ð1 ìð , x ¹ð 1 ïð f. f x =ð . (ð )ð x -ð1 íð ïð0, x =ð1 îð 2×ð x g. f x =ð . (ð )ð x2 +ð1 14. Niech f :¥ð ®ð ¥ð bdzie okre[lone wzorem f (n) =ð n2 +ð1. Czy f jest przeksztaBceniem ró|nowarto[ciowym? Czy f jest przeksztaBceniem "na"? 15. Niech f : X ®ðY i g :Y ®ð Z bd przeksztaBceniami ró|nowarto[ciowymi. Udowodni, |e f oð g : X ®ð Z jest tak|e przeksztaBceniem ró|nowarto[ciowym. Matematyka dyskretna. OpracowaBa L. Dobryakova 13 16. Niech f :¥ð2 ®ð ¥ð bdzie odwzorowaniem, okre[lonym wzorem f n,k =ð n×ðk . (ð )ð a. Czy odwzorowanie f jest "na"? b. Wyznaczy f * ¥ð´ð 2 . {ð }ð (ð )ð -ð1 c. Wyznaczy f * 0 . {ð }ð -ð1 d. Wyznaczy f * 2n :nÎð¥ð . {ð }ð -ð1 17. Dana jest funkcja f . Wyznaczy funkcj odwrotn f : a. f : ¡ð ®ð ¡ð, f x =ð 4×ð x +ð1 (ð )ð b. f : ¡ð ®ð ¡ð, f x =ð 2 -ð3×ð x (ð )ð 1 c. f : ¡ð \ 2 ®ð ¡ð \ 0 , f x =ð {ð }ð {ð }ð (ð )ð 2×ð x -ð 4 18. Odpowiedzie na pytania: a. Ile nale|y wylosowa kart z talii liczcej 52 karty, aby na pewno trafiBy si co najmniej dwie w jednym kolorze? b. Ile nale|y wylosowa kart z talii liczcej 52 karty, aby na pewno trafiBy si co najmniej cztery w jednym kolorze? 19. W bloku 6 pitrowym na parterze do windy wsiadBo 8 osób. Czy mo|liwa jest sytuacja, |e ka|dy z pasa|erów wysidzie na innym pitrze? 20. Wykaza, |e w grupie 20 osób musz by co najmniej dwie, które urodziBy si w tym samym miesicu. 21. Na zajciach koBa matematycznego pojawiBo si 50 osób. Czy mo|na spo[ród nich wybra 5 osób urodzonych w tym samym miesicu; 22. Niech S =ð 0,1,2,3,...,19 . Jak najmniejsz liczb liczb nieparzystych nale|y wybra ze {ð }ð zbioru S , aby suma co najmniej dwóch z nich byBa równa 20? 23. Udowodni, |e w[ród wybranych dowolnych 7 ró|nych liczb caBkowitych musz by takie 2, których suma lub ró|nica dzieli si przez 10. Matematyka dyskretna. OpracowaBa L. Dobryakova 14 REKURENCJE 1. Dana jest rekurencja. Wypisa kilka pierwszych wyrazów cigu. Wyznaczy zbiór warto[ci cigu: a0 =ð1 ìð a. íða =ð 3×ðan-ð1 -ð 2 , dla nÎð¥ð . îð n ìð ïða0 =ð 5 b. , dla nÎð¥ð . íð n-ð1 (ð )ð ïða =ð -ð1 ×ð an-ð1 n îð ìða0 =ð1 ïð ïð c. , dla nÎð¥ð . íða =ð 2 1 ïð n-ð1 (ð )ð ïða =ð 2×ð an-ð1 +ð -ð1 ×ð an-ð2 n îð 2. Dany jest cig 1, 5, 25, 125, 625,.... Poda wzór ogólny na n  ty wyraz cigu. Okre[li ten cig rekurencyjnie. 3. Okre[li rekurencyjnie: a. 1, 1×ð3, 1×ð3×ð5, 1×ð3×ð5×ð7,... ; b. 0, 0 +ð 2, 0 +ð 2 +ð 4, 0 +ð 2 +ð 4 +ð 6,... ; c. 1, 1×ð22, 1×ð22 ×ð32,×ð1×ð22 ×ð32 ×ð42,... ; d. 1, 1+ð 2, 1+ð 2 +ð 4, 1+ð 2 +ð 4 +ð8, 1+ð 2 +ð 4 +ð8+ð16,... ; e. 1, 1-ð3, 1-ð3+ð5, 1-ð3+ð5-ð7, 1-ð3+ð5-ð7 +ð9...; f. 12, 12 -ð 22, 12 -ð 22 +ð32, 12 -ð 22 +ð32 -ð 42,...; 4. Poda wzór ogólny an cigu okre[lonego rekurencyjnie: a0 =ð 2 ìð íða =ð -ð3×ð an-ð1 . îð n 5. Dowie[, |e je|eli wyrazy cigu an speBniaj nastpujce warunki a0 =ð 0 ìð ïða =ð 5 íð 1 ïða =ð -ðan-ð1 +ð 6×ð an-ð2, îð n n to wzór ogólny ma posta an =ð 2n -ð -ð3 . (ð )ð 6. Dowie[, |e je|eli wyrazy cigu an speBniaj nastpujce warunki: a0 =ð 2 ìð ïða =ð 3 , íð 1 ïða =ð 3×ð an-ð1 -ð 2×ð an-ð2 îð n to wzór ogólny ma posta an =ð 2n +ð1. 7. W ka|dym z nastpujcych przypadków wyznaczy wzór ogólny cigu an : a0 =ð 2 a0 =ð1 a0 =ð1 ìð ìð ìð ïða ïða ïða a. =ð-ð1 b. =ð 8 c. =ð 3 íð íð íð 1 1 1 ïða =ð -ðan-ð1 +ð 6×ð an-ð2 ïða =ð 4×ð an-ð1 -ð 4×ð an-ð2 ïða =ð an-ð2 îð n îð n îð n =ð 4 ìð ìð a0 =ð 0 ïða0 d. íð ïð e. =ð1 ïðan =ð 2×ðan-ð1 +ð n2 íða 1 îð ïða =ð 6×ðan-ð1 -ð8×ðan-ð2 +ð 5n îð n Matematyka dyskretna. OpracowaBa L. Dobryakova 15 8. Wykorzystujc schemat Hornera obliczy warto[ wielomianu: a. w(x) =ð 2×ð x4 -ð5×ð x2 +ð 4×ð x +ð 1 w punkcie x0 =ð 3/ 2 . b. w(x) =ð 3×ð x4 +ð 5×ð x3 +ð 4×ð x2 +ð 5 w punkcie x0 =ð1. c. w(x) =ð 3×ð x4 +ð 5×ð x3 +ð 4×ð x2 +ð 5 w punkcie x0 =ð 3. ¥ð 1 n 9. Wiedzc, |e =ð gdy x <ð1, wyznaczy zwykB funkcj tworzca w postaci åðx 1-ð x n=ð0 szeregu, gdy dana jest jej posta zwarta: 1 a. 1-ð 2×ð x 1 b. . 1+ð 3×ð x 1 c. . (1-ð x)2 1 d. . 1-ð x2 ¥ð 1 n 10. Wiedzc, |e funkcja tworzca cigu 1,1,1,1,... ma posta G(x) =ð =ð , wyznaczy åðx 1-ð x n=ð0 posta zwart funkcji tworzcej G(x) dla danego cigu: a. 1,0,0,0,... . b. 0,0,...,0,1,0,0... . 1ð2ð4ð 4ð 3ð m zer c. 1,-ð1,1,-ð1,... . d. an =ð 3n . 11. Wyznaczy wzór ogólny dla cigu Fibbonacciego, wykorzystujc funkcj tworzc. 12. Wyznaczy wzór ogólny cigu okre[lonego rekurencyjnie, wykorzystujc funkcj tworzc: a0 =ð 0 ìð ïða a. =ð1 . íð 1 ïða =ð 5×ðan-ð1 -ð 4×ðan-ð2 îð n a0 =ð-ð4 ìð ïða =ð-ð3 ïð 1 b. . íða =ð-ð7 2 ïð ïðan =ð 2×ð an-ð1 +ð1×ðan-ð1 -ð 2×ð an-ð3 îð a0 =ð 0 ìð c. íða =ð 2×ðan-ð1 +ð 2×ð n -ð1. îð n a0 =ð1 ìð ïða d. =ð 2 . íð 1 ïða =ð 6×ðan-ð1 -ð8×ð an-ð2 +ð n îð n Matematyka dyskretna. OpracowaBa L. Dobryakova 16 TEORIA LICZB 1. Znalez NWD a,b wykorzystujc algorytm Euklidesa. (ð )ð a. a =ð 89,b =ð 55. b. a =ð 220,b =ð 28. c. a =ð 546,b =ð 231. d. a =ð1001,b =ð 6253. e. a =ð 2475,b =ð 700. 2. Znalez NWD a,b oraz NWW a,b wykorzystujc faktoryzacj: (ð )ð (ð )ð a. a =ð189, b =ð 720 . b. a =ð 224,b =ð 375 . 3. Okre[li funkcj Eulera dla danych liczb (wskazówka: aby czynniki byBy parami wzgldnie pierwsze wystarczy przedstawi caBy iloczyn wykorzystujc faktoryzacj): a. -ð1,1,4,7,10,13 . b. 3×ð7 , 3×ð7×ð11 , 13×ð17 , 16×ð27×ð49 , 24×ð28×ð45 . (ð )ð (ð )ð (ð )ð (ð )ð (ð )ð c. 36,58,113,173,192. d. 375,720,988,4320. 4. jð a =ð 840 oraz a =ð 3að ×ð7bð ×ð11gð . Wyznaczy a . (ð )ð 5. jð a =ð 60 oraz a =ð p×ðq , gdzie p i q s ró|nymi liczbami pierwszymi. Wyznaczy a , je|eli (ð )ð p -ð q =ð 4. 6. jð a =ð120 oraz a =ð p2 ×ðq2 , gdzie p i q s ró|nymi liczbami pierwszymi. Wyznaczy a . (ð )ð 7. Wyznaczy ile jest liczb naturalnych, mniejszych od liczby 1665, takich, |e najwikszy wspólny dzielnik tych liczb z liczb 1665 jest równy 37. 8. Wyznaczy ile jest liczb naturalnych, mniejszych od liczby 1476, takich, |e najwikszy wspólny dzielnik ka|dej z tych liczb z liczb 1476 jest równy 41. 9. Dane s liczby 100, 210, 346. Które z tych liczb przystaj do 23 modulo 7? 10. Dane s liczby 180, 531, 104. Które z tych liczb przystaj do 11 modulo 13? 11. Wykona obliczenia: a. 324548-ð345-ð34234 mod3. (ð )ð b. 12543×ð4321 mod5. (ð )ð c. 529 -ð121 mod7. (ð )ð d. 329×ð988 mod9 . (ð )ð e. 13×ð 18+ð 23 mod7 . (ð (ð )ð )ð f. 37 mod 2 . 12. Wyznaczy reszt z dzielenia liczby 133×ð548 przez 57 . 13. Pokaza, |e je[li n jest liczb nieparzyst, to n2 ºð1mod8 . 14. Z jak najmniejsz liczb (wedBug warto[ci bezwzgldnej) kongruentna jest liczba N =ð11×ð18×ð2322×ð13×ð19 modulo 7? 15. Sprawdzi, czy 518 ºð1mod 27. Matematyka dyskretna. OpracowaBa L. Dobryakova 17 16. Wykona obliczenia w zbiorze ¢ðn : a. ¢ð7 : 7 +ð 2, 4 -ð8, 2×ð4 . b. ¢ð13 : 5+ð11, 1-ð9, 7×ð6 . c. ¢ð12 : 5 +ð 4, 3-ð8, 5×ð8 . 17. Rozwiza równanie: a. 2×ð x ºð 3mod6. f. 4×ð x ºð 6mod7 . b. 3×ð x ºð 4mod7 . g. 3×ð x ºð 3mod6 . c. 3×ð x ºð 2mod5. h. 21×ð x ºð 5mod36. d. 3×ð x ºð 5mod6 . i. 5×ð x ºð 2mod10. e. 4×ð x ºð 8mod12 18. Rozwiza ukBad równaD: x ºð 3mod 7 ìð a. . íð îðx ºð 7 mod13 x ºð 2 mod3 ìð x ºð 3mod11 ìð ïðx ºð 3mod 5 b. íðx ºð 5mod 7 . ïð d. îð íðx ºð 4 mod11 ïð x ºð 23mod31 ìð ïðx ºð 5mod16 ïðx îð c. ºð 7 mod12 íð ïðx ºð12mod 35 îð 19. Rozwiza ukBad równaD: 2×ð x ºð 7 mod13 4×ð x ºð 3mod 7 ìð ìð ïð5×ð ïð5×ð x ºð 8mod17 a. x ºð 4mod11 . ïð íð b. íð3×ð x ºð 7 mod31 . ïð11×ð x ºð 8mod13 îð ïð ïð14×ð x ºð 35mod19 îð 20. Znalez najmniejsz liczb naturaln, która przy dzieleniu przez 3,5,11 daje odpowiednio reszty 2,2,10. 21. Reszta z dzielenia pewnej liczby caBkowitej x przez 3 jest równa 2, reszta z dzielenia x2 przez 32 jest równa 7, reszta z dzielenia x3 przez 33 jest równa 111. Wyznaczy liczb x . 22. Obliczy mo|liwe szybko: a. 584 mod3. b. 447 mod5. c. 3636 mod17 . d. 85143 mod11. 23. Wyznaczy reszt z dzielenia: a. 383175 przez 45 . b. 109345 przez 14. c. 380 +ð 780 przez 11. d. 3100 +ð 5100 przez 7 . 24. Wyznaczy ostatni cyfr liczby: a. 3564139 w zbiorze ¢ð7 . b. 2320119 w zbiorze ¢ð5 . 25. Wyznaczy ostatnie dwie cyfry liczby 743 . Matematyka dyskretna. OpracowaBa L. Dobryakova 18

Wyszukiwarka