Pytania egzaminacyjne z „Matematyki dyskretnej”
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 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

---