Pytania egzaminacyjne z „Matematyki dyskretnej”
Co to jest teoria mnogości?	1. Teoria mnogości (teoria zbiorów) - dział matematyki, badający własności zbiorów. Na gruncie teorii mnogości można zdefiniować wszystkie podstawowe pojęcia matematyczne.
Jak określamy zbiór?	2. Zbiór określany jest jednoznacznie przez swoje elementy. Sposoby określenia zbiorów: wyliczenie wszystkich elementów: A = {x,y,z} podanie własności elementów zbioru: A = {x| x jest nieparzysty}
Podaj zasadę ekstensjonalności dla zbiorów.	3. Zasada ekstensjonalności: dwa zbiory A i B są równe  zawierają te same elementy: A = B  x (xA  xB)
Podaj zasadę dystrybutywności.	4. Zasada dystrybutywności: żaden zbiór nie jest identyczny z żadnym ze swoich elementów: ~(A x (xA  x = A))  {a} ≠ a
Co to jest podzbiór?	5. Jeżeli A i B są zbiorami oraz każdy element zbioru A jest elementem zbioru B to A nazywamy podzbiorem B A  B: A  B  x (xA  xB)
Podaj podzbiory niewłaściwe zbioru A.	6. Zbiory niewłaściwe zbioru A: zbiór A oraz zbiór pusty 
Co to jest zbiór potęgowy?	7. Zbiór wszystkich podzbiorów zbioru A nazywamy zbiorem potęgowym zbioru A i oznaczamy P(A): P(A) = {M| M  A}
Jaki zbiór należy do każdego zbioru potęgowego?	8. Do każdego zbioru potęgowego należy zbiór pusty   P(A)
Jaka jest moc zbioru potęgowego P(A) n-elementowego zbioru A?	9. Jeśli A ma n elementów to moc zbioru P(A) wynosi 2^n
Co to jest dopełnienie zbioru A?	10. Dopełnieniem zbioru A jest zbiór A' do którego należą elementy, które nie należą do zbioru A (należą do U - uniwersum): A' = {x| xU  xA}
Co to są diagramy Venna?	11. Diagramy Venna stosuje się do zobrazowania zbiorów i operacji na nich wykorzystując figury płaskie. Zbiory A, B - koła, owale; U - prostokąt.
Podaj definicję sumy zbiorów.	12. Suma zbiorów „”: A  B = {x| xA  xB}
Podaj definicję iloczynu zbiorów.	13. Iloczyn zbiorów „”: A  B = {x| xA  xB]
Jakie zbiory nazywamy rozłącznymi?	14. Dwa zbiory nazywamy rozłącznymi, jeżeli nie mają żadnego wspólnego elementu: A  B = 
Podaj definicję różnicy zbiorów.	15. Różnica zbiorów: A\B = {x| xA  xB} = A\(A  B)
Podaj określenie dopełnienia zbioru A.	16. Dopełnienie zbioru A: xA'  xU  xA
Podaj definicję różnicy symetrycznej zbiorów.	17. Różnica symetryczne dwóch zbiorów: A  B = {x| (xA  xB)  (xB  xA)} = (A\B)  (B\A)
Podaj prawa de Morgana dla zbiorów.	18. Prawa de Morgana: (A  B)' = A'  B' (A  B)' = A'  B'
Podaj prawa idempotentności dla zbiorów	19. Prawa idempotentności: A  A = A A  A = A
Co to jest iloczyn kartezjański n-zbiorów?	20. Iloczynem kartezjańskim zbiorów A1 A2 A3 … An nazywamy zbiór: A1  A2  A3  …  An = { (a1, a2, a3 … an)| a1A1  a2A2  …  anAn}
Co to jest n-ta potęga kartezjańska zbioru A?	21. N-tą potęgą kartezjańską zbioru A nazywamy zbiór A1  A2  A3  …  An = A^n jeżeli A1 = A2 = A3 = … = An
Co to jest relacja n-argumentowa?	22. Relacją  n-argumentową na zbiorach A1 A2 A3 … An nazywamy podzbiór iloczynu kartezjańskiego tych zbiorów.   A1  A2  A3  …  An
Co to jest relacja binarna?	23. Relacją binarną między elementami zbiorów A i B nazywamy dowolny podzbiór  zbioru A  B. Jeżeli A = B to relację   A^2 nazywamy relacją binarną określoną na A
Co to jest dziedzina relacji binarnej?	24. Dziedziną relacji binarnej nazywamy zbiór: D() = {aA| bB  ab}
Co to jest przeciwdziedzina relacji binarnej?	25. Przeciwdziedziną relacji binarnej nazywamy zbiór: D^-1() = {bB| aA  ab}
Co to jest pole relacji binarnej?	26. Zbiór D()  D^-1() nazywamy polem relacji 
Zapisz pole relacji binarnej ={(1,1);(b,2);(c,c)}.	27. Pole relacji wynosi ={(1,1),(b,2),(c,c)} wygląda tak: D()  D^-1() = {1, b, c, 2}
Podaj określenie dopełnienia relacji binarnej.	28. Dopełnieniem ' relacji binarnej  jest zbiór: ' = (A  B)\
Podaj określenie relacji odwrotnej do relacji binarnej .	29. Relacją odwrotną ^-1 do relacji binarnej  jest zbiór: ^-1 = {(a, b)| ba}
Podaj określenie złożenia relacji binarnych 1 oraz 2.	30. Złożeniem (superpozycją) relacji 1 i 2 nazywamy zbiór: 1 ◦ 2 = {(a, c)| bB a1b  b2c}
Zapisz w postaci macierzy relację binarną ={(1,2);(2,2);(2,3);(3,1);(3,2)}.		1		2	3
Jaką relację binarną nazywa się zwrotną?	32. Zwrotna w A: aA aa	1		0	0
Jaką relację binarną nazywa się przeciwzwrotną?	33. Przeciwzwrotna w A: aA ~(aa)	0		1	1
Jaką relację binarną nazywa się symetryczną?	34. Symetryczna w A: (aA  bA) ab  ba	1		0	1
Jaką relację binarną nazywa się przeciwsymetryczną?	35. Przeciwsymetryczna (asymetryczna) w A: (aA  bA) ab  ~(ba)
Jaką relację binarną nazywa się antysymetryczną?	36. Antysymetryczna w A: ( aA  bA) ab  ba  a = b
Jaką relację binarną nazywa się przechodnią?	37. Przechodnia w A: (aA  bA  cA) ab  bc  ac
Jaką relację binarną nazywa się liniową?	38. Liniowa w A: (aA  bA) ab  ba
Jaką relację binarną nazywa się spójną?	39. Spójna w A: (aA  bA) ab  ba  a = b
Co nazywamy obcięciem relacji A^2 do A1, gdzie A1A?	40. Jeżeli   A^2 i A1  A to relację   A1^2 nazywamy obcięciem relacji  do A1 i oznaczamy |A1
Jaką relację binarną nazywamy relacją równoważności?	41. Relację binarną   A^2 nazywamy relacją równoważności, jeżeli jest zwrotna, symetryczna i przechodnia
Co nazywamy klasą abstrakcji elementu aA względem relacji A^2.	42. Zbiór postaci [a] = {b| bA  ab} nazywamy klasą abstrakcji elementu a względem relacji 
Podaj dwie własności klasy abstrakcji.	43. Własności klasy abstrakcji(2/3): [a]   ab  [a] = [b] ~(ab)  [a]  [b] = 
Jaki zbiór nazywamy zbiorem ilorazowym A/?	44. Zbiór ilorazowy A/R jest to zbiór wszystkich klas abstrakcji zbioru A wzglądem relacji równoważności R. A/={[a] | aA}
Jaki podzbiór ZP(A) zbioru potęgowego P(A) nazywamy rozkładem zbioru A?	45. Podzbiór Z  P(A) zbioru potęgowego P(A) nazywamy rozkładem zbioru A, jeżeli: Z  (X, Y  Z  X ≠ Y  X  Y = )  (XZ) X = A; (XZ) -> suma wszystkich zbiorów XZ
Podaj twierdzenie o rozkładzie (faktoryzacji).	46. Twierdzenie o rozkładzie (faktoryzacji): Każda relacja równoważności  w zbiorze A indukuje pewien rozkład Z zbioru A, a mianowicie Z=A\R i na odwrót, każdemu rozkładowi Z zbioru A odpowiada pewna relacja równoważności  w A: ab  XZ (aX  bX)
Jaką relację binarną nazywamy relacją porządkującą?	47. Relacją porządkującą nazywamy relację binarną w zbiorze A, która jest zwrotna, słaboantysymetryczna i przechodnia
Jaką relację binarną nazywamy łańcuchem?	48. Łańcuchem (całkowitym porządkiem) nazywamy relację binarną w zbiorze A, która jest zwrotna, słaboantysymetryczna, przechodnia i liniowa.
Jaki zbiór określamy jako uporządkowany przez relację ?	49. Zbiór A określony jest wówczas jako uporządkowany (liniowo uporządkowany) przez relację , gdy jest ona relacją porządkującą (łańcuchem).
Przez jaką relację jest częściowo uporządkowany zbiór potęgowy P(A)?	50. Przez standardową relację „jest mniejsze lub równe”
Co to jest funkcja?	51. Funkcją nazywamy relację   XY, jeżeli: (xX  yY  zY) (xy  xz  y = z)
Jaką relację nazywamy funkcją?	52. Relację   XY nazywamy funkcją, jeżeli: (xX  yY  zY) (xy  xz  y = z)
Jaki zbiór nazywamy dziedziną funkcji?	53. Dziedziną funkcji f nazywamy zbiór Df = {xX| yY ( f(x)=y) }
Jaki zbiór nazywamy przeciwdziedziną funkcji?	54. Przeciwdziedziną funkcji f nazywamy zbiór Wf = {yY| xX ( f(x)=y )}
Jaką funkcję nazywamy odwzorowaniem?	55/56. Odwzorowaniem (przekształceniem) zbioru X w zbiór Y nazywamy taką funkcję f, że Df=X i WfY i oznaczamy f: X→Y
Co to jest odwzorowanie?	55/56. Odwzorowaniem (przekształceniem) zbioru X w zbiór Y nazywamy taką funkcję f, że Df=X i WfY i oznaczamy f: X→Y
Jakie odwzorowanie f nazywamy z X na Y (surjekcją, epimorfizmem)?	57. Odwzorowanie f nazywamy z X „na” Y (surjekcja, epimorfizm) jeżeli yY xX f(x) = y (inaczej: Wf=Y)
Jakie odwzorowanie f nazywamy różnowartościowym (injekcją, monomorfizmem)?	58. Odwzorowanie f nazywamy różnowartościowym (iniekcją, monomorfizmem) jeżeli x1X  x2X  yY ((x1,y)f  (x2,y)f  x1=x2)
Jakie odwzorowanie f nazywamy wzajemnie jednoznacznym (bijekcją)?	59. Odwzorowanie f nazywamy wzajemnie jednoznacznym (bijekcją) jeżeli jest „na” i różnowartościowa(surjekcją i injekcją).
Dla jakiego odwzorowania określamy odwzorowanie odwrotne?	60/61. Dla odwzorowania wzajemnie jednoznacznego f: X → Y określa się odwzorowanie odwrotne f^--1: X → Y, takie że xX yY (f(x) = y  f^--1(y) = x)
Podaj określenie odwzorowania odwrotnego do odwzorowania f.	60/61. Dla odwzorowania wzajemnie jednoznacznego f: X → Y określa się odwzorowanie odwrotne f^--1: X → Y, takie że xX yY (f(x) = y  f^--1(y) = x)
Podaj definicję przekształcenia zwanego złożeniem (superpozycją) odwzorowań.	62. Dla danych odwzorowań f: X → Y i g: Y → Z definiuje się przekształcenie g ◦ f : X → Z zwane złożeniem (superpozycją) według wzoru: (x,y)  g ◦ f  (yY) f(x) = y  g(y)=z. Zapisujemy też: g ◦ f = g[f(x)]
Czy złożenie przekształceń jest łączne i czy jest przemienne?	63. Złożenie odwzorowań nie jest przemienne g ◦ f  f ◦ g, ale jest łączne h ◦ (g ◦ f) = (h ◦ g) ◦ f
Co to jest moc zbioru skończonego?	64/65. Liczbę elementów zbioru skończonego A nazywamy mocą zbioru A lub liczbą kardynalną zbioru A i oznaczamy: card A, |A| lub A (powinny być dwie kreseczki nad A, dopiszcie sobie drugą)
Co to jest liczba kardynalna zbioru skończonego?	64/65. Liczbę elementów zbioru skończonego A nazywamy mocą zbioru A lub liczbą kardynalną zbioru A i oznaczamy: card A, |A| lub A (powinny być dwie kreseczki nad A, dopiszcie sobie drugą)
Jakie zbiory nazywamy równolicznymi?	66. Dwa zbiory A i B nazywamy równolicznymi (A~B), jeżeli istnieje jakiekolwiek odwzorowanie wzajemnie jednoznaczne (bijekcja) między tymi zbiorami. Zbiory równoliczne mają taką samą liczbę kardynalną.
Czy istnieje największa liczba kardynalna? Odpowiedź uzasadnij.	67. Nie istnieje największa liczba kardynalna, ponieważ żaden zbiór nie jest równoliczny ze swoim zbiorem potęgowym (A ≠ P(A)) (pamiętać o dwóch kreskach nad literkami).
Jaka liczba jest najmniejszą liczbą kardynalną?	68. Najmniejszą nieskończoną liczbą kardynalną jest liczba kardynalna zbioru liczb naturalnych N oznaczana card N = X0 (alef 0; to nie jest zwykłe X)
Jakie zbiory nazywamy przeliczalnymi?	69. Zbiór nieskończony nazywamy przeliczalnym, jeżeli jest równoliczny ze zbiorem liczb naturalnych. Oznacza to, że jego elementy można ustawić w ciąg a1 a2 a3 … ponumerowany kolejnymi liczbami naturalnymi.
Jakie zbiory są nieprzeliczalne?	70. Zbiór nieskończony nazywamy nieprzeliczalnym, jeżeli nie jest równoliczny ze zbiorem liczb naturalnych. Wynika z tego, że zbiór, który nie jest przeliczalny jest nieprzeliczalny
Podaj przykłady zbioru przeliczalnego i zbioru nieprzeliczalnego.	71. Zbiory liczb całkowitych (Z) i wymiernych (Q) są przeliczalne, natomiast zbiory liczb zespolonych (C) i rzeczywistych (R) są nieprzeliczalne
Czym zajmuje się kombinatoryka?	72. Kombinatoryka zajmuje się konstruowaniem spełniających pewne ograniczenia odwzorowań jednego zbioru skończonego w drugi i znajdowanie wzorów na liczbę tych odwzorowań.
Sformułuj klasyczny problem kombinatoryczny.	73. Klasyczny problem kombinatoryczny to zadanie postaci: Dane są dwa zbiory skończone X, Y przy czym X = n iY = m. Ile jest funkcji f: X → Y spełniających dane ograniczenia?
Ile jest wszystkich funkcji f: X→Y jeżeli X ma n-elementów, a Y ma m-elementów?	74. Jeżeli X = n iY = m, to liczba wszystkich funkcji f: X → Y jest równa m^n
Ile jest wszystkich funkcji różnowartościowych f: X→Y jeżeli X ma n-elementów, a Y ma m-elementów?	75. Jeżeli X = n iY = m i n ≤ m, to liczba wszystkich funkcji różnowartościowych f: X → Y wynosi: [m]n = m * (m-1) * (m-2) * … * (m-n+1), przyjmując, że [m]0 = 1
Ile jest wszystkich wzajemnie jednoznacznych odwzorowań f: X→Y jeżeli X ma n-elementów, a Y ma n-elementów?	76. Jeżeli X = n iY = n, to liczba wszystkich bijekcji f: X ^1-1 → na Y jest równa: [n]n = n * (n-1) * (n-2) * … * 1, co oznaczamy przez n!
Co to jest rozmieszczenie uporządkowane?	77. Dwa rozmieszczenia n obiektów w m pudełkach (każde pudełko zawiera ciąg) uważamy za równe, jeśli każde pudełko zawiera taki sam ciąg obiektów. Rozmieszczenia tego typu nazywa się rozmieszczeniami uporządkowanymi n obiektów w m pudełkach i ich liczbę oznaczmy przez [m]^n
Ile wynosi liczba rozmieszczeń uporządkowanych n obiektów w m pudełkach?	78. Liczba rozmieszczeń uporządkowanych n elementów w m pudełkach wynosi: [m]^n = m * (m+1) * (m+2) * … * (m+n-1), przyjmując, że [m]^0 = 1
Co to jest permutacja zbioru n-elementowego X?	79. Permutacją zbioru n-elementowego X nazywamy dowolną wzajemnie jednoznaczną funkcję f: X → X. Inaczej permutacją nazywamy dowolny, różnowartościowy ciąg długości n o elementach ze zbioru X.
Ile wynosi liczba wszystkich permutacji zbioru n-elementowego X?	80. Liczba wszystkich permutacji zbioru n-elementowego X oznaczamy przezPn = n!
Co nazywamy k-elementową kombinacją bez powtórzeń zbioru n-elementowego A?	81. Jeżeli jest dany n-elementowy zbiór A to każdy k-elementowy podzbiór zbioru A nazywamy k-elementową kombinacją bez powtórzeń n-elementowego zbioru (k ≤ n);.
Ile wynosi liczba wszystkich k-elementowych kombinacji bez powtórzeń zbioru n-elementowego?	82. Liczba k-elementowych kombinacji bez powtórzeń wynosi (n)(k) (n po k, symbol Newtona) = [n]k/k! = n!/(k!(n-k)!)
Co nazywamy k-elementową kombinacją z powtórzeniami zbioru n-elementowego A?	83. Dla skończonego n-elementowego zbioru A można określić k-elementowy podzbiór z powtórzeniami zbioru A, który nazywamy k-elementową kombinacja z powtórzeniami zbioru n-elementowego.
Ile wynosi liczba wszystkich k-elementowych kombinacji z powtórzeniami zbioru n-elementowego?	84. Liczba k-elementowych kombinacji bez powtórzeń wynosi [n]^k/k! = (n+k-1)(k)
Co nazywamy k-elementową wariacją bez powtórzeń zbioru n-elementowego A?	85. Każdy k-wyrazowy ciąg rożnych elementów n-elementowego zbioru A nazywamy k-elementową wariacją bez powtórzeń zbioru n-elementowego.
Ile wynosi liczba wszystkich k-elementowych wariacji bez powtórzeń zbioru n-elementowego?	86. Liczba k-elementowych wariacji bez powtórzeń wynosi [n]k = n(n-1)(n-2)…(n-k+1)
Co nazywamy k-elementową wariacją z powtórzeniami zbioru n-elementowego A?	87. Każdy k-wyrazowy ciąg elementów n-elementowego zbioru A nazywamy k-elementową wariacją z powtórzeniami zbioru n-elementowego.
Ile wynosi liczba wszystkich k-elementowych wariacji z powtórzeniami zbioru n-elementowego?	88. Liczba k-elementowych wariacji z powtórzeniami wynosi n^k
Podaj zasadę włączania - wyłączania dla dwóch zbiorów A, B.	89/90 Zasada włączania - wyłączania pozwala wyznaczyć liczbę elementów zbioru A1  A2  …  An, gdzie Ai są zbiorami skończonymi. Sumę zbiorów A1  A2  …  An nazywamy sumą uogólnionych zbiorów Ai i oznaczamy przez ^nUi=1 Ai Dla n=2: A1A2 = A1 +A2 -A1A2
Podaj zasadę włączania - wyłączania dla trzech zbiorów A, B, C.	89/90 Zasada włączania - wyłączania pozwala wyznaczyć liczbę elementów zbioru A1  A2  …  An, gdzie Ai są zbiorami skończonymi. Sumę zbiorów A1  A2  …  An nazywamy sumą uogólnionych zbiorów Ai i oznaczamy przez ^nUi=1 Ai Dla n=3: A1A2A3 =A1 +A2 +A3 -  A1A2 -A1A3 -A2A3 +A1A2A3
Co to jest zdanie logiczne?	91. Zdanie logiczne - wypowiedź, w której orzeka się coś o czymś - zdanie oznajmujące.
Podaj zasadę sprzeczności dla zdań logicznych..	92. Zasada sprzeczności - w logice dwuwartościowej zakłada się, że każde poprawnie zbudowane zdanie jest albo prawdziwe albo fałszywe
Co to jest wartość logiczna zdania?	93. Wartością logiczną lub stałą logiczną zdania nazywamy „Prawdę” lub „fałsz” (oznaczamy: P,F; 1,0)
Co to jest zmienna zdaniowa?	94. Zmienna zdaniowa (p, q, r…) jest literą reprezentującą dowolne zdanie, wskazuje wolne miejsce, które może zostać wypełnione przez dowolne wyrażenie z kategorii zdań logicznych.
Co to jest wartościowanie?	95. Wartościowaniem nazywamy funkcję, która każdej zmiennej zdaniowej przyporządkowuje wartość logiczną 0 lub 1. Funkcje taką można uogólnić na zbiór wszystkich formuł rachunku zdań.
Co nazywamy tautologią rachunku zdań?	96. Tautologią nazywamy formułę, która przy dowolnym wartościowaniu przybiera wartość logiczną 1.
Co to jest funktor zdaniowy?	97. Funktorem zdaniowym n-argumentowym nazywamy funkcję, która każdemu układowi zdań (p1 p2 p3 … pn) gdzie pi jest P lub F, przyporządkowuje wartość logiczną 0 lub 1. Istnieje 2^2^n funktorów zdaniowych n-argumentowych.
Wymień metody dowodzenia twierdzeń.	98. Metody dowodzenia twierdzeń: dowód bezpośredni „wprost” dowód „nie wprost” dowód „przez zaprzeczenie” zasada indukcji matematycznej dowód konstruktywny
Na czym opiera się metoda dowodzenia „nie wprost”?	99. Metoda „nie wprost” opiera się na tautologii rachunku zdań zwanej prawem kontrapozycji: (p  q)  (~q  ~p)
Na czym polega metoda dowodu „przez zaprzeczenie”?	100. Metoda dowodu przez zaprzeczenie opiera się na równoważności (p  q)  ~(p  ~q)
Podaj zasadę indukcji matematycznej.	101. Niech p(n) będzie zdaniem, które dla każdego naturalnego n może być zdaniem P lub F. Aby udowodnić, że zdanie p(n) jest prawdziwe dla wszystkich liczb naturalnych n, gdzie n ≥ n0, wystarczy pokazać, że: zdanie p(n0) jest prawdziwe dla każdego k ≥ n0, p(k)  p(k+1), tzn. zdanie p(k+1) jest prawdziwe jeżeli tylko zdanie p(k) jest prawdziwe
Kwadrat logiczny - określenie i zastosowanie.	102. Kwadrat logiczny pokazuje, że na podstawie prawa kontrapozycji implikacje prosta i przeciwstawna są równoważne oraz implikacje odwrotna i przeciwna są równoważne. Przy tej samej przekątnej są umieszczone implikacje równoważne, natomiast do udowodnienia wszystkich spośród tych implikacji, wystarczy udowodnić dowolną parę tych implikacji umieszczonych na jednym boku kwadratu.
Co to jest predykat? Podaj przykład predykatu jednoargumentowego.	103 Zakładamy, że wszystkie rozpatrywane elementy x należą do pewnej klasy indywiduów X (np. do N). Właściwości tych obiektów określane są jako predykaty (odpowiednik orzeczenia w gramatyce). „x jest liczbą pierwszą”
Co to jest predykat? Podaj przykład predykatu dwuargumentowego.	104. Zakładamy, że wszystkie rozpatrywane elementy x należą do pewnej klasy indywiduów X (np. do N). Właściwości tych obiektów określane są jako predykaty (odpowiednik orzeczenia w gramatyce). „x dzieli y”
Co to jest zmienna związana w pewnym predykacie? Podaj przykład.	105. Zmienną x określamy jako związaną jeśli jest zmienną kwantyfikatora x lub x. np. x f(x)
Co to jest zmienna wolna w pewnym predykacie? Podaj przykład.	106. Zmienną x określamy jako wolną jeśli nie jest zmienną kwantyfikatora x lub x. np. x>5
Co to jest forma zamknięta w logice predykatów? Podaj przykład.	107. Wyrażenie logiki predykatów nie zawierające żadnych zmiennych wolnych nazywamy formą zamkniętą (np. x y f(x,y))
Jakie wyrażenie w logice predykatów nazywamy tautologią?	108. Wyrażenie predykatywne nazywa się tautologią (ogólnie obowiązujące) jeśli jest prawdziwe we wszystkich interpretacjach.
Na czym polega rekurencja?	109. Rekurencja składa się z podania wartości brzegowej (początkowej) i równania wyrażającego ogólną wartość za pomocą wartości wyrazów wcześniejszych.
Podaj rozwiązanie zadania rekurencyjnego an=Aan-1+Ban-2.	110. Z równania charakterystycznego: x^r - c1x^r-1 - c2x^r-2 = 0 wynika, że an = x^r  an-1 = x^r-1  an-2 = x^r-2 . Dla r = 2 zachodzi LEMAT: jeżeli R i R są różnymi pierwiastkami równania charakterystycznego: x^2 = Ax + B (x^2 - Ax - B = 0), zatem równanie rekurencyjne an = Aan-1 + Ban-2 ma rozwiązanie postaci: an = c1^n + c2^n . W przypadku gdy  =  to rozwiązanie ma postać: an = (nc1 + c2) ^n
Podaj zastosowanie schematu Hornera.	111. Schemat Hornera można zastosować do wyliczenia wartości wielomianu W(x) w punkcie z.
Co to jest zwykła funkcja tworząca?	112. Funkcję postaci F(x) = ^ k=0 ak * x^k nazywamy funkcją tworzącą ciągu (ak)
Podaj wzór wykładniczej funkcji tworzącej dla ciągu {an}={1,1,…}.	113. F(x) = ^ n=0 an * x^n = (1-x^n+1)/(1-x)
Co to jest największy wspólny dzielnik liczb całkowitych a i b?	114. Największym wspólnym dzielnikiem liczb a i b (gcd(a,b), NWD(a,b)) jest nieujemna liczba całkowita d = gcd(a, b) = NWD(a, b), taka, że d jest wspólnym dzielnikiem a i b c|a  c|b  c|d
Co to jest największa wspólna wielokrotność liczb całkowitych a i b?	115. Najmniejsza wspólna wielokrotność liczb a i b (lcm(a,b), NWW(a,b)) jest nieujemna liczba całkowita D = lcm(a, b) = NWW(a, b), taka, że a|d  b|d a|c  b|c  d|c
Jakie liczby nazywamy względnie pierwszymi?	116. Jeżeli gcd(a, b) = 1, to a i b są względnie pierwsze.
Podaj podstawowe twierdzenie arytmetyki.	117. Podstawowe twierdzenie arytmetyki: Każda liczba całkowita n ≥ 2 może być przedstawiona jako iloczyn dodatnich całkowitych potęg liczb pierwszych
Co to jest kongruencja?	118. Niech a, b, nZ będą liczbami całkowitymi oraz n > 0. Notacja: a = b (mod n) oznacza, że a i b przystają do siebie według modułu n (są kongruentne modulo n), i równoważna jest temu, że n | (a - b). Relacja = nosi nazwę kongruencji.
Podaj wniosek z chińskiego twierdzenia o resztach dla pary kongruencji.	119.Wniosek z chińskiego twierdzenia o resztach dla par kongruencji: Jeśli gcd(n1, n2) =1 to para kongruencji x=a1 (mod n1)  x=a2 (mod n2) ma jednoznaczne rozwiązanie dane wzorem: x = a (mod n1n2)
Co to jest grupa multiplikatywna? Podaj elementy grupy multiplikatywnej dla n=4.	120. Grupą multiplikatywną Zn jest zbiór: Z^*n = { a  Zn : gcd(a,n) = 1 }
Podaj definicję logarytmu dyskretnego (indeksu)?	121. Logarytm dyskretny (indeksem) z b przy podstawie a jest jednoznacznie określona liczba 0 ≤ x ≤ n - 1 (n jest rzędem skończonej grupy cyklicznej), taka, że a^x=b

M	1	2	3
1	0	1	0
2	0	1	1
3	1	1	0

---