Jak korzystać z tej tablicy?
Ta strona zbiera najważniejsze wzory i zasady z działu matematyka dyskretna, logika, zbiory i grafy. Jeżeli szukasz szybkiej odpowiedzi typu „jak zrobić tablicę prawdy”, „jak działa prawo De Morgana”, „kiedy relacja jest przechodnia”, „jak rozwiązać kongruencję liniową”, „ile krawędzi ma drzewo” albo „jak zrobić macierz sąsiedztwa grafu”, znajdziesz tu najważniejsze warunki i przykłady.
Do obliczeń przechodź bezpośrednio do kalkulatorów: tablica prawdy, działania na zbiorach, relacje, modulo, kongruencje liniowe oraz macierz sąsiedztwa grafu.
Szybka mapa działu
| Obszar | Co obejmuje? | Najważniejszy test/wzór | Kalkulator |
|---|---|---|---|
| Logika zdań | AND, OR, NOT, implikacja, równoważność, XOR | sprawdzenie wszystkich kombinacji p, q, r | tablica prawdy |
| Prawa De Morgana | Negacja koniunkcji, alternatywy i działań na zbiorach | ¬(p∧q)=¬p∨¬q; ¬(p∨q)=¬p∧¬q | prawa De Morgana |
| Zbiory | Suma, część wspólna, różnica, dopełnienie | A∪B, A∩B, A\B, A′ | działania na zbiorach |
| Relacje | Zwrotność, symetria, antysymetria, przechodniość | sprawdzenie par (a,b) | relacje i własności |
| Modulo | Reszty z dzielenia i arytmetyka modularna | a ≡ b (mod m), gdy m | (a-b) | modulo |
| Kongruencje | Równania a·x ≡ b (mod m) | NWD(a,m) dzieli b | kongruencje liniowe |
| Grafy | Stopnie, krawędzie, drzewa, cykle, macierze | suma stopni = 2m | stopnie grafu |
Logika zdań - operatory i tablice prawdy
W logice zdań zaczynasz od wartości prawda/fałsz dla pojedynczych zdań, a potem sprawdzasz wartość całego wyrażenia. Przy dwóch zmiennych są 4 wiersze, przy trzech 8 wierszy, przy czterech 16 wierszy. To dlatego ręczne liczenie szybko staje się uciążliwe.
| Operator | Zapis | Kiedy jest prawdą? | Typowy błąd |
|---|---|---|---|
| Negacja | ¬p | Gdy p jest fałszywe | Zapominanie o odwróceniu wartości |
| Koniunkcja | p ∧ q | Gdy oba zdania są prawdziwe | Mylenie z alternatywą |
| Alternatywa | p ∨ q | Gdy przynajmniej jedno zdanie jest prawdziwe | Traktowanie jak XOR |
| Implikacja | p → q | Fałszywa tylko dla p=1, q=0 | Uznawanie jej za zwykłe „i wtedy” |
| Równoważność | p ↔ q | Gdy p i q mają tę samą wartość | Mylenie z implikacją jednostronną |
| XOR | p ⊕ q | Gdy dokładnie jedno zdanie jest prawdziwe | Mylenie z alternatywą zwykłą |
Jeśli chcesz sprawdzić gotowe wyrażenie, użyj kalkulatora tablicy prawdy. Przy przekształceniach negacji przejdź do praw De Morgana.
Prawa De Morgana - logika i zbiory
Prawa De Morgana są mostem między logiką zdań a teorią zbiorów. W praktyce służą do poprawnego rozbijania zaprzeczeń. Jeżeli widzisz wyrażenie „nieprawda, że A i B”, to po zaprzeczeniu pojawia się „nie A lub nie B”.
W logice
¬(p ∧ q) = ¬p ∨ ¬q
¬(p ∨ q) = ¬p ∧ ¬q
W teorii zbiorów
(A ∩ B)′ = A′ ∪ B′
(A ∪ B)′ = A′ ∩ B′
Typowe wyszukiwania użytkowników to „jak zaprzeczyć p i q”, „dopełnienie sumy zbiorów” i „prawo De Morgana przykłady”. Do sprawdzenia obu wersji służy kalkulator praw De Morgana.
Działania na zbiorach - najważniejsze wzory
Teoria zbiorów w matematyce dyskretnej nie jest tym samym co statystyka zbioru danych. Tutaj zbiór oznacza grupę elementów, na której wykonujesz działania: sumę, część wspólną, różnicę, różnicę symetryczną i dopełnienie.
| Działanie | Zapis | Znaczenie | Przykład dla A={1,2,3}, B={3,4} |
|---|---|---|---|
| Suma | A ∪ B | Elementy z A lub B | {1,2,3,4} |
| Część wspólna | A ∩ B | Elementy jednocześnie w A i B | {3} |
| Różnica | A \ B | Elementy z A, których nie ma w B | {1,2} |
| Różnica symetryczna | A △ B | Elementy tylko w jednym ze zbiorów | {1,2,4} |
| Dopełnienie | A′ | Elementy z U, których nie ma w A | zależy od uniwersum U |
Do liczenia elementów i porównywania zbiorów użyj kalkulatora działań na zbiorach. Jeżeli zbiory są częścią relacji, przejdź dalej do kalkulatora relacji.
Relacje - własności, które najczęściej pojawiają się w zadaniach
Relacja to zbiór par uporządkowanych. W zadaniach najczęściej trzeba sprawdzić, czy relacja jest zwrotna, symetryczna, antysymetryczna i przechodnia. Z tych własności wynikają pojęcia relacji równoważności i porządku częściowego.
| Własność | Warunek | Co sprawdzać? |
|---|---|---|
| Zwrotność | dla każdego a: (a,a) ∈ R | Czy wszystkie pary diagonalne są w relacji? |
| Przeciwzwrotność | dla żadnego a: (a,a) ∈ R | Czy nie ma żadnej pary (a,a)? |
| Symetria | jeśli (a,b), to (b,a) | Czy każda para ma odbicie? |
| Antysymetria | jeśli (a,b) i (b,a), to a=b | Czy nie ma dwustronnych par dla różnych elementów? |
| Przechodniość | jeśli (a,b) i (b,c), to (a,c) | Czy domykają się wszystkie łańcuchy? |
| Równoważność | zwrotna + symetryczna + przechodnia | Czy dzieli zbiór na klasy? |
| Porządek częściowy | zwrotna + antysymetryczna + przechodnia | Czy można porządkować elementy? |
Najwygodniej sprawdzić pary w kalkulatorze relacji i własności relacji, bo pokazuje brakujące pary oraz macierz relacji.
Modulo, NWD i kongruencje
Arytmetyka modularna jest jednym z filarów matematyki dyskretnej. Pojawia się w zadaniach z resztami, podzielnością, zegarem, kryptografią, algorytmami i kongruencjami liniowymi.
| Temat | Wzór/warunek | Przykład | Narzędzie |
|---|---|---|---|
| Reszta modulo | a mod m | 17 mod 5 = 2 | modulo |
| Kongruencja | a ≡ b (mod m) ⇔ m | (a-b) | 17 ≡ 2 (mod 5) | modulo |
| Równanie modularne | a·x ≡ b (mod m) | 14x ≡ 30 (mod 100) | kongruencje liniowe |
| Istnienie rozwiązań | NWD(a,m) | b | NWD(14,100)=2, 2 | 30 | kongruencje |
| Bézout | ax + by = NWD(a,b) | dla odwrotności modularnej | Euklides rozszerzony |
Zasada szufladkowa Dirichleta
Zasada szufladkowa odpowiada na pytania o gwarantowane powtórzenia. Jeżeli rozdzielasz N obiektów do s szuflad, to w co najmniej jednej szufladzie znajdzie się przynajmniej ceil(N/s) obiektów.
Jeśli chcesz zagwarantować co najmniej k obiektów w jednej szufladzie, używasz wzoru Nmin = s(k-1)+1. Przykład: aby mieć pewność, że wśród uczniów dwie osoby urodziły się w tym samym miesiącu, trzeba 13 osób, bo miesięcy jest 12.
Do takich zadań użyj kalkulatora zasady szufladkowej Dirichleta. W zadaniach z resztami szufladami często są klasy reszt modulo, więc warto połączyć go z kalkulatorem modulo.
Grafy - najważniejsze wzory i warunki
W teorii grafów wierzchołki reprezentują obiekty, a krawędzie relacje lub połączenia. W zadaniach najczęściej trzeba policzyć stopnie, liczbę krawędzi, rozpoznać drzewo, sprawdzić ścieżkę lub utworzyć macierz sąsiedztwa.
| Pojęcie | Warunek/wzór | Co oznacza? | Kalkulator |
|---|---|---|---|
| Suma stopni | Σdeg(v)=2m | Każda krawędź dolicza się do dwóch końców | stopnie grafu |
| Graf pełny Kₙ | m=n(n-1)/2 | Każdy wierzchołek połączony z każdym | graf pełny |
| Drzewo | m=n-1 i graf spójny | Graf bez cykli | drzewa |
| Cykl | początek = koniec, brak powtórzeń wewnętrznych | Zamknięta ścieżka | ścieżki i cykle |
| Macierz sąsiedztwa | aᵢⱼ=1, gdy istnieje połączenie | Tabela połączeń grafu | macierz sąsiedztwa |
Macierz sąsiedztwa - szybkie zasady
Macierz sąsiedztwa ma tyle wierszy i kolumn, ile graf ma wierzchołków. Przy grafie nieskierowanym macierz jest symetryczna, a przy grafie skierowanym nie musi być symetryczna. Jedynka na przekątnej oznacza pętlę.
Graf nieskierowany
Jeśli jest krawędź A-B, wpisujesz 1 w komórkach A,B oraz B,A.
Liczba zwykłych krawędzi poza przekątną jest zapisana podwójnie.
Graf skierowany
Jeśli jest łuk A → B, wpisujesz 1 tylko w komórce A,B.
Suma wiersza daje stopień wyjściowy, a suma kolumny stopień wejściowy.
Gotową listę krawędzi przeliczysz w kalkulatorze macierzy sąsiedztwa grafu.
Przykłady zadań do szybkiej powtórki
Sprawdź, czy ¬(p∧q) jest równoważne ¬p∨¬q.
Dla A={1,2,3}, B={3,4} policz A∩B.
Czy 14x≡30 (mod 100) ma rozwiązania?
Ile krawędzi ma drzewo o 18 wierzchołkach?
Najczęstsze błędy w matematyce dyskretnej
| Błąd | Dlaczego szkodzi? | Jak poprawić? |
|---|---|---|
| Mylenie alternatywy z XOR | p∨q jest prawdziwe także wtedy, gdy oba zdania są prawdziwe | Sprawdź tabelę prawdy |
| Złe zaprzeczenie „i” oraz „lub” | Negacja zmienia operator | Użyj praw De Morgana |
| Brak uniwersum przy dopełnieniu zbioru | Nie wiadomo, względem czego liczysz A′ | Najpierw ustal U |
| Dzielenie kongruencji bez NWD | Można stracić albo dopisać rozwiązania | Sprawdź NWD(a,m) | b |
| Traktowanie m=n-1 jako jedynego warunku drzewa | Graf musi być jeszcze spójny | Sprawdź spójność albo brak cykli |
| Zła kolejność w macierzy sąsiedztwa | Wiersze i kolumny opisują inne wierzchołki | Najpierw zapisz kolejność etykiet |
Ciekawostka
Matematyka dyskretna jest podstawą informatyki. Tablice prawdy są blisko elektroniki cyfrowej, grafy opisują sieci i trasy, modulo pojawia się w kryptografii, a relacje pomagają modelować porządki, klasy równoważności i zależności między obiektami.
Sprawdź także powiązane kalkulatory
Do logiki użyj tablicy prawdy i praw De Morgana. Do zbiorów i relacji przejdź do działań na zbiorach oraz relacji i własności relacji.
Do zadań liczbowych sprawdź modulo, kongruencje liniowe, rozszerzony algorytm Euklidesa i zasadę szufladkową. Do grafów wybierz stopnie grafu, graf pełny, drzewa, ścieżki i cykle oraz macierz sąsiedztwa.
Wskazówka od KalkulatorXXL
Przy powtórce nie ucz się tej tablicy od góry do dołu. Zacznij od typu zadania: logika, zbiory, relacje, modulo albo grafy. Potem wybierz właściwy warunek i od razu sprawdź przykład w powiązanym kalkulatorze.
Pełna ścieżka nauki: Akademia matematyki dyskretnej – logika, zbiory i grafy prowadzi od tej tablicy do kalkulatorów logiki, zbiorów, relacji, modulo, kombinatoryki i grafów oraz do poradników krok po kroku.