Lista notatek
Kombinatoryka, zbiory, logika
Podtematy
Zbiory: pojęcia i oznaczenia
Zbiór to zestaw elementów. W zbiorze nie ma znaczenia kolejność elementów ani to, czy się powtarzają. Poniższe zbiory są zatem takie same:
- \{\square, \bigcirc, \triangle\}
- \{\bigcirc, \triangle, \square\}
- \{\square, \square, \square, \bigcirc, \bigcirc, \triangle\}
| Symbol | Znaczenie | Komentarz |
|---|---|---|
| \emptyset | zbiór pusty | |
| \overline{A} | dopełnienie | elementy, które nie należą do zbioru A |
| x \in A | należy do zbioru | elementy x należą do zbioru A |
| A \cap B | część wspólna | elementy, które należą do obu zbiorów A, B |
| A \cup B | suma zbiorów | elementy, które należą do któregokolwiek ze zbiorów A, B |
| A \setminus B | różnica | elementy, które należą do zbioru A, ale nie należą do zbioru B |
| A = B | równość | równość zbiorów A, B |
| A \subseteq B | podzbiór | wszystkie elementy zbioru A należą również do zbioru B |
| A \subset B | podzbiór właściwy | A jest podzbiorem B i jednocześnie A \neq B |
| |A| | moc zbioru | liczba elementów zbioru |
| A \cap B = \emptyset | zbiory rozłączne | zbiory A, B nie mają żadnego elementu wspólnego |
Notacja zbiorów, zbiory liczbowe
Zbiory zapisujemy wielkimi literami. Najważniejsze zbiory liczbowe mają w matematyce swoje oznaczenia:
| \mathbb{N} | zbiór liczb naturalnych |
| \mathbb{Z} | zbiór liczb całkowitych |
| \mathbb{Q} | zbiór liczb wymiernych |
| \mathbb{R} | zbiór liczb rzeczywistych |
Pozostałe zbiory zapisujemy na dwa sposoby:
Zapis z wyliczeniem – zapisujemy elementy zbioru w nawiasach klamrowych. Na przykład A = \{3, 7, 9\} jest to zbiór trójelementowy zawierający liczby 3, 7 i 9.
Zapis za pomocą warunku – określamy, jaki warunek muszą spełniać elementy zbioru. Na przykład A = \{x \in \mathbb{N} \mid x \lt 10\} to zbiór liczb naturalnych mniejszych niż 10.
Do góryWłasności zbiorów i działań na zbiorach
- Każdy zbiór jest swoim własnym podzbiorem: A\subseteq A
Przykłady A\subseteq B
Przykłady zbiorów A, B spełniających warunek A \subseteq B:
- A = \{11, 50, 415\}, B = \{11, 50, 333, 415\}
- A = \{1,4,8\}, B = \{1,4,8\}
- A = zbiór wszystkich liczb naturalnych, B = zbiór wszystkich liczb całkowitych
- Zbiór nie może być swoim podzbiorem właściwym: A\not\subset A
Przykłady A\subset B i A \not\subset B
Przykłady zbiorów A, B spełniających warunek A \subset B:
- A = \{11, 50, 415\}, B = \{11, 50, 333, 415\} (ponieważ liczba 333 znajduje się w zbiorze B)
- A = zbiór wszystkich liczb naturalnych, B = zbiór wszystkich liczb całkowitych (liczby ujemne znajdują się w zbiorze wszystkich liczb całkowitych, ale nie znajdują się w zbiorze wszystkich liczb naturalnych).
Przykłady zbiorów, dla których A \not\subset B:
- A = \{1, 4, 8\}, B = \{1,4,8\} ponieważ w B nie ma żadnego elementu, którego nie byłoby w A)
- Zbiór pusty jest podzbiorem dowolnego zbioru: \emptyset \subseteq A
- Zbiór pusty nie ma żadnego podzbioru.
- A \subseteq A \cup B
- A \cap B \subseteq A
- A \subseteq B \wedge B \subseteq A \Leftrightarrow A=B
Diagramy Venna
Diagram Venna przedstawia wszystkie możliwe relacje między kilkoma zbiorami. Elementy zbiorów są przedstawiane jako punkty na płaszczyźnie, a zbiory jako obszary ograniczone krzywymi. Najczęściej stosuje się diagramy Venna dla dwóch i trzech zbiorów, w których zbiory przedstawione są za pomocą okręgów. Można również tworzyć diagramy Venna dla większej liczby zbiorów, jednak w tym przypadku okręgi nie wystarczą (takie diagramy są mało czytelne i dlatego nie są zbyt często stosowane).
Typowy diagram Venna dla trzech zbiorów:
Przykład z konkretnymi elementami (zbiór A zawiera czerwone figury, zbiór B zawiera kółka, a zbiór C zawiera figury wypełnione):
Diagramy Venna wykorzystujemy na przykład do graficznego przedstawiania operacji na zbiorach. Poniższy rysunek ilustruje B∩(A∪C):
Logika: pojęcia i oznaczenia
Zdania logiczne
Zdanie logiczne to zdanie, w przypadku którego ma sens pytanie, czy jest ono prawdziwe, czy fałszywe, przy czym może zachodzić tylko jedna z tych możliwości.
Przykłady zdań logicznych:
Miasto Kraków leży w Polsce. (zdanie prawdziwe)
Kraków jest stolicą Polski. (zdanie fałszywe)
Na Marsie jest zakopany skarb. (zdanie, którego wartości logicznej nie znamy)
Przykłady zdań, które nie są zdaniami logicznymi: Jesteś głodny? Idź do sklepu po jajka.
Spójniki logiczne
| Zapis | Nazwa | Znaczenie |
|---|---|---|
| \neg A | negacja | nieprawda, że A |
| A \wedge B | koniunkcja, i | A i B są jednocześnie prawdziwe |
| A \vee B | alternatywa, lub | co najmniej jedno z A, B jest prawdziwe |
| A \Rightarrow B | implikacja, jeżeli-to | jeżeli A jest prawdziwe, to B również jest prawdziwe |
| A \Leftrightarrow B | równoważność, wtedy i tylko wtedy, gdy | A jest prawdziwe wtedy i w tylko wtedy, gdy B jest prawdziwe |
Tautologie i sprzeczności
Tautologia to formuła zdaniowa, która jest zawsze prawdziwa. Przykłady:
- A \vee \neg A (prawo wyłączonego środka)
- (A \Rightarrow B) \Leftrightarrow (\neg B \Rightarrow \neg A)
Sprzeczność to formuła zdaniowa, która jest zawsze fałszywa. Przykładem jest formuła A \wedge \neg A (prawo sprzeczności).
Formuła jest spełnialna, jeśli nie jest sprzecznością.
Do góryOcena wyrażeń logicznych
Tabela prawdy operacji logicznych
| A | B | A \vee B | A \wedge B | A \Rightarrow B | A \Leftrightarrow B |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
Symbol Newtona
Symbol Newtona określa liczbę kombinacji, czyli sposobów, na które możemy wybrać k elementów ze zbioru n-elementowego. Z symbolem Newtona spotykamy się w kombinatoryce. Oznaczamy go jako \binom{n}{k} (odczytujemy „n nad k“).
Dla n \geq k \geq 0 symbol Newtona przyjmuje postać: \binom{n}{k} = \frac{n!}{k!(n-k)!}
Dla symbolu Newtona zachodzą również inne zależności, na przykład:
- \binom{n}{k} = \binom{n}{n-k}
- \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}
- \sum_{k=0}^n \binom{n}{k} = 2^n
Przykłady:
| \binom{3}{1} | = 2 |
| \binom{4}{2} | = 6 |
| \binom{5}{3} | = 10 |
| \binom{6}{2} | = 15 |
| \binom{15}{15} | = 1 |
Rachunek prawdopodobieństwa: pojęcia i oznaczenie
Zdarzenie losowe to wynik doświadczenia losowego, o którym po jego przeprowadzeniu można stwierdzić, czy zaszło, czy nie zaszło. Jego charakterystyczną cechą jest to, że może, ale nie musi zajść. Prawdopodobieństwo zdarzenia to miara szansy, że dane zdarzenie wystąpi. Prawdopodobieństwo jest zawsze liczbą z przedziału od 0 do 1. W języku potocznym często wyrażamy prawdopodobieństwo w procentach, co stanowi stukrotność prawdopodobieństwa stosowanego w matematyce.
Pojęcia i oznaczanie
| zdarzenie elementarne | 0 \leq P(A) \leq 1 | podstawowy, niepodzielny wynik doświadczenia |
| zdarzenie pewne | P(A) = 1 | zachodzi zawsze |
| zdarzenie niemożliwe | P(A) = 0 | nie może zaistnieć |
| B jest zdarzeniem przeciwnym do A | P(B) = 1-P(A) | B zachodzi wtedy, kiedy nie zachodzi A |
| zdarzenia A i B są rozłączne | A\cap B=\emptyset | A i B nie mogą zajść jednocześnie (wykluczają się) |
Przykłady
- W woreczku mam pięć kulek, z czego dwie są czerwone, dwie niebieskie i jedna żółta. Kulki różnią się tylko kolorem. Eksperyment polega na tym, że losowo (bez patrzenia) wyciągam jedną kulkę z woreczka.
- „Wyciągnę czerwoną kulkę.“ to zdarzenie losowe. Jest to zdarzenie elementarne. Jego prawdopodobieństwo wynosi 0,4 (w języku potocznym powiedzielibyśmy 40 %).
- „Wyciągnę czerwoną lub żółtą kulkę.“ to zdarzenie złożone. Jego prawdopodobieństwo wynosi 0,6.
- „Wyciągnę kulkę.“ to zdarzenie pewne.
- „Wyciągnę zieloną kulkę.“ to zdarzenie niemożliwe.
Doświadczenia losowe i zdarzenia złożone
W rozwiązywaniu bardziej złożonych zadań nie wystarczy znajomość podstawowego wzoru na prawdopodobieństwo. Na przykład wtedy, gdy zdarzenie, którego prawdopodobieństwo chcemy obliczyć, składa się z kilku zdarzeń.
Prawdopodobieństwo sumy dwóch zdarzeń losowych
- Prawdopodobieństwo sumy dwóch rozłącznych zdarzeń jest równe sumie ich prawdopodobieństw. Czyli: P(A\cup B)=P(A)+P(B).
- Jeśli zdarzenia nie wykluczają się wzajemnie, od ich sumy musimy dodatkowo odjąć prawdopodobieństwo ich części wspólnej. Czyli: P(A\cup B)=P(A)+P(B)-P(A\cap B).
Obie te zależności możemy również przedstawić graficznie.
Prawdopodobieństwo sumy zdarzeń wykorzystujemy zazwyczaj w sytuacjach, gdy chcemy obliczyć prawdopodobieństwo, że zajdzie zdarzenie A lub zdarzenie B.
Przykład: rzut kostką
Jakie jest prawdopodobieństwo, że podczas rzutu kostką wypadnie liczba nieparzysta lub liczba podzielna przez 4?
- Mamy zbiór zdarzeń elementarnych \{1,2,3,4,5,6\}.
- Oznaczmy zdarzenie A – wypadnie liczba nieparzysta – A=\{1, 3, 5\}) oraz zdarzenie B – wypadnie liczba podzielna przez 4 –B=\{4\}.
- P(A)=\frac36=\frac12, P(B)=\frac16
- Zdarzenia A, B są rozłączne – liczba nieparzysta nie jest podzielna przez 4.
- P(A\cup B)=P(A)+P(B)=\frac12+\frac16=\frac46=\frac23
Prawdopodobieństwo wzajemnie niezależnych zdarzeń
Niezależne zdarzenia to takie zdarzenia, w przypadku których wystąpienie jednego zdarzenia nie ma wpływu na to, czy wystąpi drugie zdarzenie. Na przykład podczas wielokrotnego rzucania kostką wynik jednego rzutu nie ma wpływu na wyniki kolejnych rzutów.
Dla dwóch niezależnych zdarzeń A, B zachodzi: P(A\cap B)=P(A)\cdot P(B)
Prawdopodobieństwo iloczynu niezależnych zdarzeń stosujemy zazwyczaj w sytuacjach, gdy chcemy obliczyć prawdopodobieństwo, że wystąpiło zdarzenie A i jednocześnie wystąpiło zdarzenie B.
Przykład: wielokrotny rzut kostką
Jakie jest prawdopodobieństwo, że gdy dwukrotnie rzucimy kostką, w pierwszym rzucie wypadnie liczba nieparzysta, a w drugim liczba parzysta?
- Oznaczamy zdarzenie A – w pierwszym rzucie wypadła liczba nieparzysta. Oznaczamy zdarzenie B – w drugim rzucie wypadła liczba parzysta.
- Liczb nieparzystych i parzystych jest zawsze po trzy, dlatego: P(A)=P(B)=\frac36=\frac12
- Zdarzenia A, B są niezależne.
- P(A\cap B)=P(A)\cdot P(B)=\frac12\cdot\frac12=\frac14
Współczynnik korelacji
Korelacja jest miarą zależności między dwiema zmiennymi. Współczynnik korelacji jest liczbą określającą siłę tej zależności.
Istnieje kilka sposobów pomiaru korelacji. Najczęściej stosowanym jest współczynnik korelacji Pearsona, oznaczany symbolem r. Ma on następujące właściwości:
- Przyjmuje wartości z przedziału [-1, 1].
- Mierzy wyłącznie liniową zależność między zmiennymi.
- Wartość dodatnia oznacza, że wzrost jednej zmiennej wiąże się ze wzrostem drugiej.
- Wartość ujemna oznacza, że wzrost jednej zmiennej wiąże się ze spadkiem drugiej.
- Wartość równa 0 oznacza brak liniowej zależności.
- Wartość równa dokładnie 1 lub -1 oznacza idealną liniową zależność między zmiennymi.
