Pytania egzaminacyjne z „Matematyki dyskretnej 2008”
Co nazywamy k-elementową kombinacją bez powtórzeń zbioru n-elementowego A?	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);.
Co nazywamy k-elementową kombinacją z powtórzeniami zbioru n-elementowego A?	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.
Co nazywamy k-elementową wariacją bez powtórzeń zbioru n-elementowego A?	Każdy k-wyrazowy ciąg rożnych elementów n-elementowego zbioru A nazywamy k-elementową wariacją bez powtórzeń zbioru n-elementowego.
Co nazywamy k-elementową wariacją z powtórzeniami zbioru n-elementowego A?	Każdy k-wyrazowy ciąg elementów n-elementowego zbioru A nazywamy k-elementową wariacją z powtórzeniami zbioru n-elementowego.
Co nazywamy klasą abstrakcji elementu aA względem relacji A^2.	Zbiór postaci [a] = {b| bA  ab} nazywamy klasą abstrakcji elementu a względem relacji 
Co nazywamy obcięciem relacji A^2 do A1, gdzie A1A?	Jeżeli   A^2 i A1  A to relację   A1^2 nazywamy obcięciem relacji  do A1 i oznaczamy |A1
Co nazywamy tautologią rachunku zdań?	Tautologią nazywamy formułę, która przy dowolnym wartościowaniu przybiera wartość logiczną 1.
Co to jest dopełnienie zbioru A?	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 jest działanie zewnętrzne?	Działaniem zewnętrznym nazywamy odwzorowanie O: A×→A gdzie A≠K które każdej parze (a, k), gdzie aA i kK przyporządkowuje element zbioru A.
Co to jest forma zamknięta w logice predykatów? Podaj przykład.	Wyrażenie logiki predykatów nie zawierające żadnych zmiennych wolnych nazywamy formą zamkniętą (np. x y f(x,y))
Co to jest funktor zdaniowy?	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.
Co to jest grupa permutacji?	Grupa permutacji zbioru X - grupa wszystkich bijekcji zbioru X z działaniem składania jako mnożeniem i identycznością jako elementem neutralnym. Jest ona także nazywana grupą symetryczną.
Co to jest iloczyn kartezjański n-zbiorów?	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 izomorfizm algebr?	Izomorfizmem nazywamy wzajemnie jednoznaczne odwzorowanie f takie, że f i jego odwrotność f^−1 są homomorfizmami.
Co to jest kongruencja?	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.
Co to jest liczba kardynalna zbioru skończonego?	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 moc zbioru skończonego?	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 największa wspólna wielokrotność liczb całkowitych a i b?	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
Co to jest największy wspólny dzielnik liczb całkowitych a i b?	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 n-ta potęga kartezjańska zbioru A?	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 odwzorowanie?	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 permutacja zbioru n-elementowego X?	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.
Co to jest podzbiór?	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)
Co to jest pole relacji binarnej?	Zbiór D()  D^-1() nazywamy polem relacji 
Co to jest predykat? Podaj przykład predykatu dwuargumentowego.	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 relacja binarna?	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 relacja n-argumentowa?	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 rozmieszczenie uporządkowane?	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
Co to jest system algebraiczny?	Systemem algebraicznym (relacyjnym) nazywamy układ S postaci S = (A, O1, O2,…, Om, 1, 2,…, k), gdzie A jest niepustym zbiorem zwanym uniwersum systemu, Oi, dla i=1,2,…,m jest działaniem w A oraz zbiór A jest zamknięty ze względu na te działania i j dla j=1,2,…,k są relacjami w A.
Co to jest teoria mnogości?	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.
Co to jest wartościowanie?	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 to jest wartość logiczna zdania?	Wartością logiczną lub stałą logiczną zdania nazywamy „Prawdę” lub „fałsz” (oznaczamy: P,F; 1,0)
Co to jest zbiór potęgowy?	Zbiór wszystkich podzbiorów zbioru A nazywamy zbiorem potęgowym zbioru A i oznaczamy P(A): P(A) = {M| M  A}
Co to jest zdanie logiczne?	Zdanie logiczne - wypowiedź, w której orzeka się coś o czymś - zdanie oznajmujące.
Co to jest zmienna wolna w pewnym predykacie? Podaj przykład.	Zmienną x określamy jako wolną jeśli nie jest zmienną kwantyfikatora x lub x. np. x>5
Co to jest zmienna zdaniowa?	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 zmienna związana w pewnym predykacie? Podaj przykład.	Zmienną x określamy jako związaną jeśli jest zmienną kwantyfikatora x lub x. np. x f(x)
Co to jest zwykła funkcja tworząca?	Funkcję postaci F(x) = ^ k=0 ak * x^k nazywamy funkcją tworzącą ciągu (ak)
Co to są diagramy Venna?	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.
Czy istnieje największa liczba kardynalna? Odpowiedź uzasadnij.	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).
Czym zajmuje się kombinatoryka?	Kombinatoryka zajmuje się konstruowaniem spełniających pewne ograniczenia odwzorowań jednego zbioru skończonego w drugi i znajdowanie wzorów na liczbę tych odwzorowań.
Ile jest wszystkich funkcji f: X→Y jeżeli X ma n-elementów, a Y ma m-elementów?	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?	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?	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!
Ile wynosi liczba rozmieszczeń uporządkowanych n obiektów w m pudełkach?	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
Ile wynosi liczba wszystkich k-elementowych kombinacji bez powtórzeń zbioru n-elementowego?	Liczba k-elementowych kombinacji bez powtórzeń wynosi (n)(k) (n po k, symbol Newtona) = [n]k/k! = n!/(k!(n-k)!)
Ile wynosi liczba wszystkich k-elementowych kombinacji z powtórzeniami zbioru n-elementowego?	Liczba k-elementowych kombinacji bez powtórzeń wynosi [n]^k/k! = (n+k-1)(k)
Ile wynosi liczba wszystkich k-elementowych wariacji bez powtórzeń zbioru n-elementowego?	Liczba k-elementowych wariacji bez powtórzeń wynosi [n]k = n(n-1)(n-2)…(n-k+1)
Ile wynosi liczba wszystkich k-elementowych wariacji z powtórzeniami zbioru n-elementowego?	Liczba k-elementowych wariacji z powtórzeniami wynosi n^k
Ile wynosi liczba wszystkich permutacji zbioru n-elementowego X?	Liczba wszystkich permutacji zbioru n-elementowego X oznaczamy przezPn = n!
Jak określamy zbiór?	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}
Jaka jest moc zbioru potęgowego P(A) n-elementowego zbioru A?	Jeśli A ma n elementów to moc zbioru P(A) wynosi 2^n
Jaka liczba jest najmniejszą liczbą kardynalną?	Najmniejszą nieskończoną liczbą kardynalną jest liczba kardynalna zbioru liczb naturalnych N oznaczana card N = X0 (alef 0; to nie jest zwykłe X)
Jaką funkcję nazywamy odwzorowaniem?	Odwzorowaniem (przekształceniem) zbioru X w zbiór Y nazywamy taką funkcję f, że Df=X i WfY i oznaczamy f: X→Y
Jaką relację binarną nazywa się antysymetryczną?	Antysymetryczna w A: ( aA  bA) ab  ba  a = b
Jaką relację binarną nazywa się liniową?	Liniowa w A: (aA  bA) ab  ba
Jaką relację binarną nazywa się przechodnią?	Przechodnia w A: (aA  bA  cA) ab  bc  ac
Jaką relację binarną nazywa się przeciwsymetryczną?	Przeciwsymetryczna (asymetryczna) w A: (aA  bA) ab  ~(ba)
Jaką relację binarną nazywa się przeciwzwrotną?	Przeciwzwrotna w A: aA ~(aa)			1
Jaką relację binarną nazywa się spójną?	Spójna w A: (aA  bA) ab  ba  a = b
Jaką relację binarną nazywa się symetryczną?	Symetryczna w A: (aA  bA) ab  ba			1
Jaką relację binarną nazywa się zwrotną?	Zwrotna w A: aA aa			0
Jaką relację binarną nazywamy łańcuchem?	Łańcuchem (całkowitym porządkiem) nazywamy relację binarną w zbiorze A, która jest zwrotna, słaboantysymetryczna, przechodnia i liniowa.
Jaką relację binarną nazywamy relacją porządkującą?	Relacją porządkującą nazywamy relację binarną w zbiorze A, która jest zwrotna, słaboantysymetryczna i przechodnia
Jaką relację binarną nazywamy relacją równoważności?	Relację binarną   A^2 nazywamy relacją równoważności, jeżeli jest zwrotna, symetryczna i przechodnia
Jaką relację nazywamy funkcją?	Relację   XY nazywamy funkcją, jeżeli: (xX  yY  zY) (xy  xz  y = z)
Jaki podzbiór ZP(A) zbioru potęgowego P(A) nazywamy rozkładem zbioru A?	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
Jaki zbiór należy do każdego zbioru potęgowego?	Do każdego zbioru potęgowego należy zbiór pusty   P(A)
Jaki zbiór nazywamy zbiorem ilorazowym A/?	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 zbiór określamy jako uporządkowany przez relację ?	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).
Jakie algebry nazywamy izomorficznymi?	Algebry podobne Q1=(A,O1,O2,…,On) oraz Q2=(B,O1',O2',…,On'), dla których istnieje izomorfizm przekształcający A na B nazywamy izomorficznymi.
Jakie liczby nazywamy względnie pierwszymi?	Jeżeli gcd(a, b) = 1 (NWD(a,b))=1, to a i b są względnie pierwsze.
Jakie odwzorowanie f nazywamy różnowartościowym (injekcją, monomorfizmem)?	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ą)?	Odwzorowanie f nazywamy wzajemnie jednoznacznym (bijekcją) jeżeli jest „na” i różnowartościowa(surjekcją i injekcją).
Jakie odwzorowanie f nazywamy z X na Y (surjekcją, epimorfizmem)?	Odwzorowanie f nazywamy z X „na” Y (surjekcja, epimorfizm) jeżeli yY xX f(x) = y (inaczej: Wf=Y)
Jakie wyrażenie w logice predykatów nazywamy tautologią?	Wyrażenie predykatywne nazywa się tautologią (ogólnie obowiązujące) jeśli jest prawdziwe we wszystkich interpretacjach.
Jakie zbiory nazywamy przeliczalnymi?	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 nazywamy rozłącznymi?	Dwa zbiory nazywamy rozłącznymi, jeżeli nie mają żadnego wspólnego elementu: A  B = 
Jakie zbiory nazywamy równolicznymi?	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ą.
Jakie zbiory są nieprzeliczalne?	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
Kwadrat logiczny - określenie i zastosowanie.	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.
Na czym opiera się metoda dowodzenia „nie wprost”?	Metoda „nie wprost” opiera się na tautologii rachunku zdań zwanej prawem kontrapozycji: (p  q)  (~q  ~p)
Na czym polega metoda dowodu „przez zaprzeczenie”?	Metoda dowodu przez zaprzeczenie opiera się na równoważności (p  q)  ~(p  ~q)
Na czym polega rekurencja?	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 definicję elementu neutralnego.	Niech S, będzie zbiorem z określonym działaniem dwuargumentowym *. Element e, nazywa się elementem neutralnym, jeżeli spełnia następujące warunki: S e*e=a S e*a=a
Podaj definicję elementu odwrotnego.	Niech * oznacza działanie dwuargumentowe w zbiorze S. Element x nazywa się elementem odwrotnym do y jeżeli spełnione są dwa warunki: x*y=e y*x=e gdzie e oznacza element neutralny działania *.
Podaj definicję grupy cyklicznej.	Grupa (G, *), w której istnieje element a o tej właściwości, że każdy element grupy jest jego potęgą (wielokrotnością) nazywa się grupą cykliczną. Element a nazywa się generatorem grupy cyklicznej, co zapisujemy G=<a>.
Podaj definicję iloczynu zbiorów.	Iloczyn zbiorów „”: A  B = {x| xA  xB]
Podaj definicję logarytmu dyskretnego (indeksu)?	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
Podaj definicję przekształcenia zwanego złożeniem (superpozycją) odwzorowań.	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)]
Podaj definicję różnicy symetrycznej zbiorów.	Różnica symetryczne dwóch zbiorów: A  B = {x| (xA  xB)  (xB  xA)} = (A\B)  (B\A)
Podaj definicję różnicy zbiorów.	Różnica zbiorów: A\B = {x| xA  xB} = A\(A  B)
Podaj definicję sumy zbiorów.	Suma zbiorów „”: A  B = {x| xA  xB}
Podaj dwie własności klasy abstrakcji.	Własności klasy abstrakcji(2/3): [a]   ab  [a] = [b] ~(ab)  [a]  [b] = 
Podaj określenie dopełnienia relacji binarnej.	Dopełnieniem ' relacji binarnej  jest zbiór: ' = (A  B)\
Podaj określenie dopełnienia zbioru A.	Dopełnienie zbioru A: xA'  xU  xA
Podaj określenie działania (operacji)	Niech X będzie dowolnym zbiorem z określoną na nim strukturą algebraiczną. Działaniem n-argumentowym nazywa się funkcję f: X^n→X
Podaj określenie grupy.	Zbiór G wraz działaniem * nazywamy grupą i oznaczamy (G, *), jeśli 1. * jest działaniem łącznym, 2. istnieje element neutralny działania *, 3. "gÎG istnieje element odwrotny.
Podaj określenie odwzorowania odwrotnego do odwzorowania f.	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 relacji odwrotnej do relacji binarnej .	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.	Złożeniem (superpozycją) relacji 1 i 2 nazywamy zbiór: 1 ◦ 2 = {(a, c)| bB a1b  b2c}
Podaj podstawowe twierdzenie arytmetyki.	Podstawowe twierdzenie arytmetyki: Każda liczba całkowita n ≥ 2 może być przedstawiona jako iloczyn dodatnich całkowitych potęg liczb pierwszych
Podaj podzbiory niewłaściwe zbioru A.	Zbiory niewłaściwe zbioru A: zbiór A oraz zbiór pusty 
Podaj prawa de Morgana dla zbiorów.	Prawa de Morgana: (A  B)' = A'  B' (A  B)' = A'  B'
Podaj prawa idempotentności dla zbiorów	Prawa idempotentności: A  A = A A  A = A
Podaj przykład grupy.	Zbiór { − 1,1} z działaniem mnożenia, czyli grupa (Z2,∙)
Podaj przykład izomorficznych algebr.	115.
Podaj przykłady zbioru przeliczalnego i zbioru nieprzeliczalnego.	Zbiory liczb całkowitych (Z) i wymiernych (Q) są przeliczalne, natomiast zbiory liczb zespolonych (C) i rzeczywistych (R) są nieprzeliczalne
Podaj twierdzenie o rozkładzie (faktoryzacji).	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)
Podaj wzór wykładniczej funkcji tworzącej dla ciągu {an}={1,1,…}.	F(x) = ^ n=0 an * x^n = (1-x^n+1)/(1-x)
Podaj zasadę dystrybutywności dla zbiorów.	Zasada dystrybutywności: żaden zbiór nie jest identyczny z żadnym ze swoich elementów: ~(A x (xA  x = A))  {a} ≠ a
Podaj zasadę ekstensjonalności dla zbiorów.	Zasada ekstensjonalności: dwa zbiory A i B są równe  zawierają te same elementy: A = B  x (xA  xB)
Podaj zasadę indukcji matematycznej.	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
Podaj zasadę sprzeczności dla zdań logicznych..	Zasada sprzeczności - w logice dwuwartościowej zakłada się, że każde poprawnie zbudowane zdanie jest albo prawdziwe albo fałszywe
Podaj zasadę włączania - wyłączania dla trzech zbiorów A, B, C.	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
Podaj zastosowanie schematu Hornera.	Schemat Hornera można zastosować do wyliczenia wartości wielomianu W(x) w punkcie z.
Przez jaką relację jest częściowo uporządkowany zbiór potęgowy P(A)?	Przez standardową relację „jest mniejsze lub równe”
Sformułuj klasyczny problem kombinatoryczny.	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?
Wymień metody dowodzenia twierdzeń.	Metody dowodzenia twierdzeń: dowód bezpośredni „wprost” dowód „nie wprost” dowód „przez zaprzeczenie” zasada indukcji matematycznej dowód konstruktywny
Zapisz pole relacji binarnej ={(1,1);(b,2);(c,c)}.	Pole relacji wynosi ={(1,1),(b,2),(c,c)} wygląda tak: D()  D^-1() = {1, b, c, 2}
Zapisz w postaci macierzy relację binarną ={(1,2);(2,2);(2,3);(3,1);(3,2)}.			2	3

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

---