Od czego zacząć zadanie z matematyki dyskretnej?
Największy problem w zadaniach z matematyki dyskretnej nie polega zwykle na samych rachunkach, ale na rozpoznaniu typu zadania. Inaczej zaczynasz zadanie z tablicą prawdy, inaczej z działaniami na zbiorach, inaczej z relacją, a jeszcze inaczej z grafem lub kongruencją modulo.
Ten poradnik prowadzi przez najczęstsze typy poleceń: „zrób tablicę prawdy”, „sprawdź prawa De Morgana”, „oblicz sumę i część wspólną zbiorów”, „sprawdź własności relacji”, „rozwiąż kongruencję liniową”, „zastosuj zasadę szufladkową” oraz „zbadaj graf”. Do szybkiego sprawdzenia wzorów użyj też tablicy matematyki dyskretnej.
Jeśli chcesz od razu liczyć, przejdź do kalkulatorów: tablica prawdy, działania na zbiorach, relacje, kongruencje liniowe oraz macierz sąsiedztwa grafu.
Najpierw rozpoznaj typ zadania
Zanim zaczniesz liczyć, przeczytaj czasowniki w poleceniu. One zwykle wskazują, jakiego narzędzia użyć.
| Polecenie w zadaniu | Co to oznacza? | Od czego zacząć? | Narzędzie |
|---|---|---|---|
| „Zbuduj tablicę prawdy” | Logika zdań | Wypisz wszystkie kombinacje p, q, r | kalkulator tablicy prawdy |
| „Zaneguj wyrażenie” | Prawa De Morgana | Zmień „i” na „lub” albo odwrotnie | prawa De Morgana |
| „Policz A∪B, A∩B” | Działania na zbiorach | Wypisz elementy A, B i U | działania na zbiorach |
| „Sprawdź własności relacji” | Relacje | Szukaj par (a,a), odbić i łańcuchów | relacje |
| „Oblicz resztę / rozwiąż modulo” | Arytmetyka modularna | Ustal moduł i resztę | modulo |
| „Rozwiąż ax≡b (mod m)” | Kongruencja liniowa | Policz NWD(a,m) | kongruencje liniowe |
| „Pokaż, że coś musi się powtórzyć” | Zasada szufladkowa | Nazwij obiekty i szuflady | zasada szufladkowa |
| „Zbadaj graf” | Teoria grafów | Wypisz wierzchołki i krawędzie | stopnie grafu |
Logika zdań: jak robić tablicę prawdy?
Tablicę prawdy zaczynasz od wypisania wszystkich kombinacji wartości zmiennych. Dla dwóch zmiennych są cztery wiersze, dla trzech osiem, dla czterech szesnaście. Następnie liczysz wyrażenie od środka: najpierw nawiasy i negacje, potem koniunkcje i alternatywy, a na końcu implikacje lub równoważności, jeśli występują.
Do sprawdzania dłuższych formuł użyj kalkulatora tablicy prawdy. Jeśli w formule pojawia się zaprzeczenie nawiasu, od razu porównaj je z kalkulatorem praw De Morgana.
Prawa De Morgana: jak nie pomylić zaprzeczenia?
Najprostsza zasada brzmi: gdy zaprzeczasz nawias, odwracasz składniki i zmieniasz operator. Dla logiki oznacza to zmianę i na lub albo lub na i. Dla zbiorów oznacza to zmianę części wspólnej na sumę albo sumy na część wspólną.
Logika
¬(p ∧ q) = ¬p ∨ ¬q
¬(p ∨ q) = ¬p ∧ ¬q
Zbiory
(A ∩ B)' = A' ∪ B'
(A ∪ B)' = A' ∩ B'
Jeśli wpisujesz w Google „jak zaprzeczyć p i q” albo „dopełnienie sumy zbiorów”, to właśnie ten przypadek. Przykłady policzysz w kalkulatorze praw De Morgana.
Zbiory: jak liczyć sumę, część wspólną i różnicę?
Przy zbiorach najpierw wypisz elementy bez powtórzeń. Potem zdecyduj, czy chcesz elementy „z jednego lub drugiego zbioru”, „w obu naraz” czy „tylko w pierwszym”. Jeżeli pojawia się dopełnienie, koniecznie ustal uniwersum U.
| Działanie | Jak myśleć? | Przykład |
|---|---|---|
| A∪B | wszystko, co jest w A lub B | {1,2,3}∪{3,4}={1,2,3,4} |
| A∩B | część wspólna obu zbiorów | {1,2,3}∩{3,4}={3} |
| A\B | elementy A bez elementów B | {1,2,3}\{3,4}={1,2} |
| A△B | elementy tylko w jednym zbiorze | {1,2,4} |
| A' | wszystko z U, czego nie ma w A | zależy od uniwersum |
Do szybkiego sprawdzania kilku zbiorów użyj kalkulatora działań na zbiorach. W zadaniach z relacjami przyda się także kalkulator własności relacji.
Relacje: jak sprawdzić zwrotność, symetrię i przechodniość?
Relacja to zbiór par, dlatego przy sprawdzaniu własności nie patrzysz na pojedyncze liczby, ale na pary. Najlepiej zacząć od macierzy relacji albo uporządkowanej listy par. Dopiero potem sprawdzasz warunki po kolei.
| Własność | Jak sprawdzać praktycznie? | Co często brakuje? |
|---|---|---|
| Zwrotność | dla każdego a musi być (a,a) | brakuje par diagonalnych |
| Symetria | jeśli jest (a,b), musi być (b,a) | brakuje pary odwrotnej |
| Antysymetria | nie może być dwóch kierunków dla różnych elementów | pojawia się (a,b) i (b,a) |
| Przechodniość | z (a,b) i (b,c) wynika (a,c) | brakuje domknięcia łańcucha |
Jeżeli relacja jest zwrotna, symetryczna i przechodnia, jest relacją równoważności. Jeżeli jest zwrotna, antysymetryczna i przechodnia, może być porządkiem częściowym. Obie klasy rozpoznaje kalkulator relacji i własności relacji.
Modulo i kongruencje: jak zacząć?
W zadaniach z modulo najpierw ustal moduł, czyli liczbę, względem której liczysz resztę. Zapis a ≡ b (mod m) oznacza, że liczby a i b dają tę samą resztę z dzielenia przez m, czyli m dzieli a-b.
Przy kongruencji liniowej a·x ≡ b (mod m) pierwszym krokiem jest zawsze NWD(a,m). Jeżeli NWD(a,m) nie dzieli b, równanie nie ma rozwiązań. Jeżeli dzieli, można przejść do redukcji i odwrotności modularnej.
Do zwykłych reszt użyj kalkulatora modulo. Do równań wybierz kalkulator kongruencji liniowych. Do NWD, Bézouta i odwrotności modularnej przyda się rozszerzony algorytm Euklidesa.
Zasada szufladkowa: jak znaleźć szuflady?
W zadaniach z zasadą szufladkową najtrudniejsze jest nazwanie szuflad. Szufladami mogą być miesiące urodzenia, kolory, reszty z dzielenia, foldery, klasy, pudełka albo inne grupy. Obiektami są rzeczy, które do tych szuflad trafiają.
Jeżeli pytanie brzmi „ile potrzeba, aby mieć pewność”, zwykle działa wzór s(k-1)+1. Jeżeli pytanie brzmi „ile na pewno jest w jednej grupie”, działa ceil(N/s). Oba tryby obsługuje kalkulator zasady szufladkowej Dirichleta.
Grafy: jak czytać zadanie z wierzchołkami i krawędziami?
W grafach zaczynasz od wypisania wierzchołków i krawędzi. Jeżeli zadanie dotyczy stopni, używasz wzoru suma stopni = 2m. Jeżeli dotyczy grafu pełnego, stosujesz wzór n(n-1)/2. Jeżeli dotyczy drzewa, sprawdzasz spójność i warunek m=n-1.
| Typ zadania | Najważniejszy warunek | Kalkulator |
|---|---|---|
| Stopnie wierzchołków | Σdeg(v)=2m | stopnie grafu |
| Graf pełny Kₙ | m=n(n-1)/2 | graf pełny |
| Drzewo | m=n-1 i spójność | drzewa w grafach |
| Ścieżka lub cykl | kolejne pary muszą mieć krawędź | ścieżki i cykle |
| Macierz sąsiedztwa | aᵢⱼ=1, gdy istnieje połączenie | macierz sąsiedztwa |
Macierz sąsiedztwa: jak ją zbudować?
Najpierw ustal kolejność wierzchołków. Ta kolejność będzie jednocześnie kolejnością wierszy i kolumn. Następnie dla każdej krawędzi wpisz 1 w odpowiedniej komórce. W grafie nieskierowanym wpisujesz też jedynkę symetrycznie, a w grafie skierowanym tylko w kierunku łuku.
Graf nieskierowany
Jeżeli jest krawędź A-B, wpisujesz 1 w komórce A,B i B,A.
Graf skierowany
Jeżeli jest łuk A→B, wpisujesz 1 tylko w komórce A,B.
Ręczne tworzenie macierzy łatwo pomylić, dlatego do kontroli użyj kalkulatora macierzy sąsiedztwa grafu.
Przykłady zadań z rozwiązaniami
Sprawdź, czy ¬(p∧q) jest tym samym co ¬p∨¬q.
Dla A={1,2,3}, B={3,4} policz A∪B i A∩B.
Czy 6x≡5 (mod 9) ma rozwiązanie?
Graf ma 12 wierzchołków, 11 krawędzi i jest spójny. Czy jest drzewem?
Najczęstsze błędy uczniów i studentów
| Błąd | Skutek | Jak tego uniknąć? |
|---|---|---|
| Mylenie alternatywy z XOR | Zły wynik w tablicy prawdy | Sprawdź, czy oba zdania mogą być jednocześnie prawdziwe |
| Zaprzeczenie nawiasu bez zmiany operatora | Błędne prawa De Morgana | Przy negacji zmień ∧ na ∨ albo ∨ na ∧ |
| Brak uniwersum przy dopełnieniu | Nie da się policzyć A' | Zawsze zapisz zbiór U |
| Brak par odwrotnych w relacji symetrycznej | Fałszywa ocena symetrii | Dla każdej pary (a,b) szukaj (b,a) |
| Dzielenie kongruencji jak zwykłego równania | Utrata rozwiązań | Najpierw policz NWD(a,m) |
| Mylenie ścieżki z cyklem | Zły typ przejścia w grafie | Sprawdź, czy pierwszy i ostatni wierzchołek są takie same |
| Zła kolejność macierzy sąsiedztwa | Poprawne liczby w złych komórkach | Najpierw ustal etykiety wierszy i kolumn |
Ciekawostka
Matematyka dyskretna jest bardzo praktyczna: logika działa w układach cyfrowych, relacje opisują porządki i zależności, grafy modelują sieci i trasy, a modulo jest podstawą wielu algorytmów kryptograficznych.
Co dalej policzyć?
Do logiki wybierz tablicę prawdy i prawa De Morgana. Do zbiorów i relacji przejdź przez działania na zbiorach oraz relacje i własności relacji.
Do części liczbowej użyj modulo, kongruencji liniowych, rozszerzonego algorytmu Euklidesa i zasady szufladkowej. Do grafów sprawdź stopnie, graf pełny, drzewa, ścieżki i cykle oraz macierz sąsiedztwa.
Wskazówka od KalkulatorXXL
Przed sprawdzianem lub kolokwium z matematyki dyskretnej nie zaczynaj od zapamiętywania definicji. Weź po jednym zadaniu z każdego typu: logika, zbiory, relacje, modulo i grafy. Wtedy szybciej zobaczysz, który warunek pasuje do którego polecenia.
Zobacz cały pakiet: Akademia matematyki dyskretnej – logika, zbiory i grafy porządkuje kalkulatory, tablicę wzorów i poradniki od logiki zdań oraz zbiorów po liczby pierwsze, kombinatorykę i grafy.