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.

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}

3. Zasada ekstensjonalności: dwa zbiory A i B są równe zawierają te same elementy:

A = B ∀x (x∈A ∧ x∈B)

4. Zasada dystrybutywności: żaden zbiór nie jest identyczny z żadnym ze swoich elementów:

~(∃A ∃x (x∈A ∧ x = A)) {a} ≠ a

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)

6. Zbiory niewłaściwe zbioru A: zbiór A oraz zbiór pusty ∅

7. Zbiór wszystkich podzbiorów zbioru A nazywamy zbiorem potęgowym zbioru A i oznaczamy P(A):

P(A) = {M| M ⊂ A}

8. Do każdego zbioru potęgowego należy zbiór pusty ∅ ∈ P(A)

9. Jeśli A ma n elementów to moc zbioru P(A) wynosi 2ⁿ

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}

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.

12. Suma zbiorów „∪”: A ∪ B = {x| x∈A ∨ x∈B}

13. Iloczyn zbiorów „∩”: A ∩ B = {x| x∈A ∧ x∈B]

14. Dwa zbiory nazywamy rozłącznymi, jeżeli nie mają żadnego wspólnego elementu: A ∩ B = ∅

15. Różnica zbiorów: A\B = {x| x∈A ∧ x∉B} = A\(A ∩ B)

16. Dopełnienie zbioru A: x∈A' x∈U ∧ x∉A

17. Różnica symetryczne dwóch zbiorów: A ÷ B = {x| (x∈A ∧ x∉B) ∨ (x∈B ∧ x∉A)} = (A\B) ∩ (B\A)

18. Prawa de Morgana: (A ∩ B)' = A' ∪ B' (A ∪ B)' = A' ∩ B'

19. Prawa idempotentności: A ∩ A = A A ∪ A = A

20. Iloczynem kartezjańskim zbiorów A₁ A₂ A₃ … A_n nazywamy zbiór:

A₁ ⊗ A₂ ⊗ A₃ ⊗ … ⊗ A_n = { (a₁, a₂, a₃ … a_n)| a₁∈A₁ ∧ a₂∈A₂ ∧ … ∧ a_n∈A_n}

21. N-tą potęgą kartezjańską zbioru A nazywamy zbiór A₁ ⊗ A₂ ⊗ A₃ ⊗ … ⊗ A_n = Aⁿ jeżeli A₁ = A₂ = A₃ = … = A_n

22. Relacją ℜ n-argumentową na zbiorach A₁ A₂ A₃ … A_n nazywamy podzbiór iloczynu kartezjańskiego tych zbiorów. ℜ ⊂ A₁ ⊗ A₂ ⊗ A₃ ⊗ … ⊗ A_n

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² nazywamy relacją binarną określoną na A

24. Dziedziną relacji binarnej nazywamy zbiór: D(ℜ) = {a∈A| ∃b∈B ∧ aℜb}

25. Przeciwdziedziną relacji binarnej nazywamy zbiór: D^-1(ℜ) = {b∈B| ∃a∈A ∧ aℜb}

26. Zbiór D(ℜ) ∪ D^-1(ℜ) nazywamy polem relacji ℜ

27. Pole relacji wynosi ℜ={(a,1),(b,2),(c,3)} wygląda tak: D(ℜ) ∪ D^-1(ℜ) = {a, b, c, 1, 2, 3}

28. Dopełnieniem ℜ' relacji binarnej ℜ jest zbiór: ℜ' = (A ⊗ B)\ℜ

29. Relacją odwrotną ℜ^-1 do relacji binarnej ℜ jest zbiór: ℜ^-1 = {(a, b)| bℜa}

30. Złożeniem (superpozycją) relacji ℜ₁ i ℜ₂ nazywamy zbiór: ℜ₁ ◦ ℜ₂ = {(a, c)| ∃b∈B aℜ₁b ∧ bℜ₂c}

31.

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

32. Zwrotna w A: ∀a∈A aℜa

33. Przeciwzwrotna w A: ∀a∈A ~(aℜa)

34. Symetryczna w A: ∀(a∈A ∧ b∈A) aℜb bℜa

35. Przeciwsymetryczna (asymetryczna) w A: ∀(a∈A ∧ b∈A) aℜb ~(bℜa)

36. Antysymetryczna w A: ∀( a∈A ∧ b∈A) aℜb ∧ bℜa a = b

37. Przechodnia w A: ∀(a∈A ∧ b∈A ∧ c∈A) aℜb ∧ bℜc aℜc

38. Liniowa w A: ∀(a∈A ∧ b∈A) aℜb ∨ bℜa

39. Spójna w A: ∀(a∈A ∧ b∈A) aℜb ∨ bℜa ∨ a = b

40. Jeżeli ℜ ⊂ A² i A₁ ⊂ A to relację ℜ ∩ A₁² nazywamy obcięciem relacji ℜ do A₁ i oznaczamy ℜ|A₁

41. Relację binarną ℜ ⊂ A² nazywamy relacją równoważności, jeżeli jest zwrotna, symetryczna i przechodnia

42. Zbiór postaci [a]_ℜ = {b| b∈A ∧ aℜb} nazywamy klasą abstrakcji elementu a względem relacji ℜ

43. Własności klasy abstrakcji(2/3):

• [a]_ℜ ≠ ∅

• aℜb [a]_ℜ = [b]_ℜ

~(aℜb) [a]ℜ ∩ [b]ℜ = ∅

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}

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

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)

47. Relacją porządkującą nazywamy relację binarną w zbiorze A, która jest zwrotna, słaboantysymetryczna i przechodnia

48. Łańcuchem (całkowitym porządkiem) nazywamy relację binarną w zbiorze A, która jest zwrotna, słaboantysymetryczna, przechodnia i liniowa.

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).

50. Przez standardową relację „jest mniejsze lub równe”

51. Funkcją nazywamy relację ℜ ⊂ X⊗Y, jeżeli: ∀(x∈X ∧ y∈Y ∧ z∈Y) (xℜy ∧ xℜz y = z)

52. Relację ℜ ⊂ X⊗Y nazywamy funkcją, jeżeli: ∀(x∈X ∧ y∈Y ∧ z∈Y) (xℜy ∧ xℜz y = z)

53. Dziedziną funkcji f nazywamy zbiór D_f = {x∈X| ∃y∈Y ( f(x)=y) }

54. Przeciwdziedziną funkcji f nazywamy zbiór W_f = {y∈Y| ∃x∈X ( f(x)=y )}

55/56. Odwzorowaniem (przekształceniem) zbioru X w zbiór Y nazywamy taką funkcję f, że D_f=X i W_f⊂Y i oznaczamy f: X→Y

57. Odwzorowanie f nazywamy z X „na” Y (surjekcja, epimorfizm) jeżeli ∀y∈Y ∃x∈X f(x) = y (inaczej: W_f=Y)

58. Odwzorowanie f nazywamy różnowartościowym (iniekcją, monomorfizmem) jeżeli

∀x₁∈X ∧ ∀x₂∈X ∧ ∀y∈Y ((x₁,y)∈f ∧ (x₂,y)∈f x₁=x₂)

59. Odwzorowanie f nazywamy wzajemnie jednoznacznym (bijekcją) jeżeli jest „na” i różnowartościowa(surjekcją i injekcją).

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)

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)]

63. Złożenie odwzorowań nie jest przemienne g ◦ f ≠ f ◦ g, ale jest łączne h ◦ (g ◦ f) = (h ◦ g) ◦ f

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ą)

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ą.

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).

68. Najmniejszą nieskończoną liczbą kardynalną jest liczba kardynalna zbioru liczb naturalnych N oznaczana card N = X₀ (alef 0; to nie jest zwykłe X)

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 a₁ a₂ a₃ … ponumerowany kolejnymi liczbami naturalnymi.

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.

71. Zbiory liczb całkowitych (Z) i wymiernych (Q) są przeliczalne, natomiast zbiory liczb zespolonych (C) i rzeczywistych (R) są nieprzeliczalne.

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ń.

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?

74. Jeżeli X = n iY = m, to liczba wszystkich funkcji f: X → Y jest równa mⁿ

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]₀ = 1

76. Jeżeli X = n iY = m, 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!

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]ⁿ

78. Liczba rozmieszczeń uporządkowanych n elementów w m pudełkach wynosi:

[m]ⁿ = m * (m+1) * (m+2) * … * (m+n-1), przyjmując, że [m]⁰ = 1

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.

80. Liczba wszystkich permutacji zbioru n-elementowego X oznaczamy przezP_n = n!

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);.

82. Liczba k-elementowych kombinacji bez powtórzeń wynosi (n)(k) (n po k, symbol Newtona) = [n]_k/k! = n!/(k!(n-k)!)

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.

84. Liczba k-elementowych kombinacji bez powtórzeń wynosi [n]^k/k! = (n+k-1)(k)

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.

86. Liczba k-elementowych wariacji bez powtórzeń wynosi [n]_k = n(n-1)(n-2)…(n-k+1)

87. Każdy k-wyrazowy ciąg elementów n-elementowego zbioru A nazywamy k-elementową wariacją z powtórzeniami zbioru n-elementowego.

88. Liczba k-elementowych wariacji z powtórzeniami wynosi n^k

89/90 Zasada włączania - wyłączania pozwala wyznaczyć liczbę elementów zbioru A₁ ∪ A₂ ∪ … ∪ A_n, gdzie A_i są zbiorami skończonymi. Sumę zbiorów A₁ ∪ A₂ ∪ … ∪ A_n nazywamy sumą uogólnionych zbiorów A_i i oznaczamy przez ⁿU_i=1 A_i

• (89) Dla n=2: A₁∪A₂ = A₁ +A₂ -A₁∩A₂

• (90) Dla n=3: A₁∪A₂∪A₃ =A₁ +A₂ +A₃ -  A₁∩A₂ -A₁∩A₃ -A₂∩A₃ +A₁∩A₂∩A₃

91. Zdanie logiczne - wypowiedź, w której orzeka się coś o czymś - zdanie oznajmujące.

92. Zasada sprzeczności - w logice dwuwartościowej zakłada się, że każde poprawnie zbudowane zdanie jest albo prawdziwe albo fałszywe

93. Wartością logiczną lub stałą logiczną zdania nazywamy „Prawdę” lub „fałsz” (oznaczamy: P,F; 1,0)

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.

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ń.

96. Tautologią nazywamy formułę, która przy dowolnym wartościowaniu przybiera wartość logiczną 1.

97. Funktorem zdaniowym n-argumentowym nazywamy funkcję, która każdemu układowi zdań (p₁ p₂ p₃ … p_n) gdzie p_i jest P lub F, przyporządkowuje wartość logiczną 0 lub 1. Istnieje 2^2ⁿ funktorów zdaniowych n-argumentowych.

98. Metody dowodzenia twierdzeń:

• dowód bezpośredni „wprost”

• dowód „nie wprost”

• dowód „przez zaprzeczenie”

• zasada indukcji matematycznej

• dowód konstruktywny

99. Metoda „nie wprost” opiera się na tautologii rachunku zdań zwanej prawem kontrapozycji:

(p q) (~q ~p)

100. Metoda dowodu przez zaprzeczenie opiera się na równoważności

(p q) ~(p ∧ ~q)

101. Zasada 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 ≥ n₀, wystarczy pokazać, że:

• zdanie p(n₀) jest prawdziwe

• dla każdego k ≥ n_0, p(k) p(k+1), tzn. zdanie p(k+1) jest prawdziwe jeżeli tylko zdanie p(k) jest prawdziwe

102/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ą”

• „x dzieli y”,.

104. Zmienną x określamy jako związaną jeśli jest zmienną kwantyfikatora ∃x lub ∀x. np. ∀x f(x)

105. Zmienną x określamy jako wolną jeśli nie jest zmienną kwantyfikatora ∃x lub ∀x. np. x>5

106. Wyrażenie logiki predykatów nie zawierające żadnych zmiennych wolnych nazywamy formą zamkniętą (np. ∃x ∀y f(x,y))

107. Wyrażenie predykatywne nazywa się tautologią (ogólnie obowiązujące) jeśli jest prawdziwe we wszystkich interpretacjach.

108. 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.

109. Rozwiązanie równania rekurencyjnego: a_n = Aa_n-1 + Ba_n-2:

Z równania charakterystycznego: x^r - c₁x^r-1 - c₂x^r-2 = 0 wynika, że a_n = x^r ∧ a_n-1 = x^r-1 ∧ a_n-2 = x^r-2 .

Dla r = 2 zachodzi LEMAT: jeżeli α∈R i β∈R są różnymi pierwiastkami równania charakterystycznego:

x² = Ax + B (x² - Ax - B = 0), zatem równanie rekurencyjne a_n = Aa_n-1 + Ba_n-2 ma rozwiązanie postaci:

a_n = c₁αⁿ + c₂βⁿ . W przypadku gdy α = β to rozwiązanie ma postać: a_n = (nc₁ + c₂) αⁿ

110. Schemat Hornera można zastosować do wyliczenia wartości wielomianu W(x) w punkcie z.

111. Funkcję postaci F(x) = ^∝∑ _k=0 a_k * x^k nazywamy funkcją tworzącą ciągu (a_k)

112. F(x) = ^∝∑ _n=0 a_n * xⁿ = (1-xⁿ⁺¹)/(1-x)

113. 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

114. 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

115. Jeżeli gcd(a, b) = 1, to a i b są względnie pierwsze.

116. Podstawowe twierdzenie arytmetyki: Każda liczba całkowita n ≥ 2 może być przedstawiona jako iloczyn dodatnich całkowitych potęg liczb pierwszych

117. 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.

118.Wniosek z chińskiego twierdzenia o resztach dla par kongruencji:

Jeśli gcd(n₁, n₂) =1 to para kongruencji x=a₁ (mod n₁) ∧ x=a₂ (mod n₂) ma jednoznaczne rozwiązanie dane wzorem: x = a (mod n₁n₂)

119. 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

---