Matematyka dyskretna
Matematyka dyskretna to matematyka rzeczy osobnych i policzalnych: prawda albo fałsz, w zbiorze albo poza nim, ta ścieżka albo tamta. To matematyka, na której działają komputery, a zaczyna się od logiki, którą można włączać i wyłączać.
Ostatnia aktualizacja
Matematyka dyskretna to matematyka rzeczy osobnych i policzalnych. Zdanie jest prawdziwe albo fałszywe, element należy do zbioru albo nie, sieć ma połączenie między dwoma punktami albo go nie ma. Nie ma nic pomiędzy, i to właśnie znaczy "dyskretny", a dokładnie tak świat widzi komputer.
Pierwszy kurs obejmuje sześć tematów: logikę, zbiory, kombinatorykę, grafy, teorię liczb i dowody. Logika jest pierwsza, bo w niej zapisuje się wszystkie pozostałe tematy. Wybierz spójnik poniżej i przełączaj p i q.
Tabela prawdy dla p ∧ q
| p | q | p ∧ q |
|---|---|---|
| P | P | P |
| P | F | F |
| F | P | F |
| F | F | F |
Przełączaj p i q albo kliknij wiersz. Podświetlony wiersz to ten, który wybierają.
Czytaj p jako "x należy do A", a q jako "x należy do B". Zacieniowane obszary to miejsca, gdzie zdanie jest prawdziwe; kropka to bieżący wiersz.
p ∧ q
Czytaj jako p i q
Przy tych wartościach p ∧ q jest prawdziwe.
Prawdziwe tylko wtedy, gdy p i q są oba prawdziwe.
Jako zbiory AND to część wspólna: x należy do A ∩ B dokładnie wtedy, gdy x należy do A i x należy do B.
Logika: zdania i spójniki
Zdanie w logice to wypowiedź, która jest albo prawdziwa, albo fałszywa, np. "7 jest liczbą pierwszą" albo "pada deszcz". Logika buduje większe zdania z mniejszych za pomocą kilku spójników, a tabela prawdy wypisuje wynik dla każdej kombinacji wejść.
| symbol | nazwa | czytamy | prawdziwe, gdy |
|---|---|---|---|
| ∧ | AND, koniunkcja | "p i q" | oba są prawdziwe |
| ∨ | OR, alternatywa | "p lub q" | co najmniej jedno jest prawdziwe |
| ¬ | NOT, negacja | "nie p" | p jest fałszywe |
| ⊕ | XOR, alternatywa wykluczająca | "p lub q, ale nie oba" | dokładnie jedno jest prawdziwe |
| → | IMPLIKUJE, implikacja | "jeśli p, to q" | w każdym przypadku poza p prawdziwym i q fałszywym |
| ↔ | WTW, równoważność | "p wtedy i tylko wtedy, gdy q" | p i q mają tę samą wartość |
Dwa z nich zaskakują. Logiczne OR jest włączne: "p lub q" jest prawdziwe, gdy oba są prawdziwe, w przeciwieństwie do codziennego "herbata czy kawa?". Wersja wykluczająca ma własną nazwę, XOR.
Drugi to implikacja. p → q jest fałszywa tylko w jednym wierszu, gdy p jest prawdziwe, a q fałszywe. Potraktuj ją jak obietnicę: "jeśli będzie padać, wezmę parasol". Obietnica jest złamana tylko wtedy, gdy pada, a parasola nie ma. W suchy dzień obietnica nie została złamana, niezależnie od tego, co masz przy sobie, więc zdanie liczy się jako prawdziwe.
Zdania równoważne
Dwa zdania są równoważne, gdy ich tabele prawdy zgadzają się w każdym wierszu. W widżecie wybierz OR i zaneguj p: kolumna dla ¬p ∨ q jest identyczna z kolumną dla p → q, więc oba zdania mówią to samo.
Najbardziej przydatne równoważności to prawa De Morgana, które mówią, jak NOT przechodzi przez AND i OR:
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
Słowami: "nie oba" to to samo co "jedno albo drugie jest fałszywe", a "żadne" to to samo co "oba są fałszywe". Programiści codziennie używają ich do przepisywania warunków takich jak "nie (zalogowany i zweryfikowany)".
Logika i zbiory to jedna idea
Czytaj p jako "x należy do A", a q jako "x należy do B". Wtedy AND to część wspólna, OR to suma, a NOT to dopełnienie, a każda tabela prawdy to zacieniowany diagram Venna, i dlatego widżet rysuje go obok tabeli. Prawa De Morgana stają się regułami o zbiorach:
(A ∩ B)′ = A′ ∪ B′
Strona o zapisie zbiorów cieniuje każde z nich na diagramie, który możesz klikać.
Kombinatoryka
Liczenie w matematyce dyskretnej oznacza liczenie bez wypisywania. Większość pracy wykonują dwie reguły.
Reguła mnożenia. Jeśli jeden wybór można zrobić na m sposobów, a drugi na n sposobów, to parę wyborów można zrobić na m × n sposobów. 4-cyfrowy PIN ma 10 możliwości dla każdej cyfry, więc możliwych PIN-ów jest 10^4 = 10000.
Kombinacje. Liczbę sposobów wyboru k rzeczy spośród n, gdy kolejność nie ma znaczenia, zapisuje się jako C(n, k). Wybór 3 dodatków do pizzy spośród 8:
C(8, 3) = (8 × 7 × 6) / (3 × 2 × 1) = 56
Licznik liczy wybory uporządkowane, a dzielenie przez 3 × 2 × 1 usuwa 6 kolejności, w jakich można było wybrać te same trzy dodatki.
Wynik to 6 × 5 podzielone przez 2, czyli 15. Jeśli wyszło ci 30, każda para została policzona dwa razy, raz w każdej kolejności.
Grafy
Graf to zbiór punktów, zwanych wierzchołkami, połączonych liniami, zwanymi krawędziami. Modeluje wszystko, co składa się z połączeń: drogi między miastami, znajomych w sieci społecznościowej, linki między stronami internetowymi.
Pierwszy wynik: jeśli 5 osób wymienia uścisk dłoni każda z każdą raz, uścisków jest C(5, 2) = 10. Każda osoba ściska 4 dłonie, co daje 5 × 4 = 20 końców uścisków, a każdy uścisk ma dwa końce, więc 20 / 2 = 10. To rozumowanie to lemat o uściskach dłoni: stopnie wszystkich wierzchołków sumują się do podwojonej liczby krawędzi.
Teoria liczb i dowody
Arytmetyka modularna to arytmetyka na tarczy zegara. 17 mod 5 to 2, czyli reszta z dzielenia 17 przez 5. Dziewięć godzin po 8 jest godzina 5, bo 17 mod 12 to 5. Ta sama idea, na bardzo dużych liczbach, stoi za szyfrowaniem RSA, które chroni bezpieczne strony internetowe.
Dowód indukcyjny pokazuje w dwóch krokach, że zdanie jest prawdziwe dla każdej liczby naturalnej n: sprawdź je dla n = 1, a potem pokaż, że jeśli jest prawdziwe dla pewnego n, to jest też prawdziwe dla n + 1. Tak dowodzi się na przykład, że
1 + 2 + ... + n = n(n + 1) / 2
dla każdego n, a nie tylko dla sprawdzonych wartości.
Do czego służy matematyka dyskretna
- Programowanie: każda instrukcja if to logika, a prawa De Morgana przepisują warunki.
- Bazy danych: zapytanie, które łączy albo filtruje tabele, to działania na zbiorach.
- Algorytmy: kombinatoryka mówi, ile kroków wykonuje program, gdy rosną dane wejściowe.
- Sieci i mapy: najkrótsze trasy i sieci społecznościowe to problemy grafowe.
- Bezpieczeństwo: szyfrowanie opiera się na teorii liczb i arytmetyce modularnej.
- Sprzęt: procesor jest zbudowany z bramek logicznych, czyli tabel prawdy w krzemie.
Czy matematyka dyskretna jest trudna?
Jest trudna inaczej niż algebra i analiza. Jest niewiele wzorów do zapamiętania, a rachunki są małe, ale wiele pytań każe coś udowodnić, a nie obliczyć, a pisanie przekonującego rozumowania to dla większości uczniów nowa umiejętność.
Najbardziej pomaga rozwiązywanie małych przypadków ręcznie, zanim zacznie się szukać wzoru: narysuj diagram Venna, wypisz tabelę prawdy, wymień każdy przypadek. Zapis wydaje się na początku ciężki, ale większość to symbole z tej strony i ze strony o zapisie zbiorów.
Częste pytania
- Co to jest matematyka dyskretna?
- Dział matematyki, który bada obiekty osobne i policzalne, a nie wielkości zmieniające się płynnie. Jej główne tematy to logika, zbiory, kombinatoryka, grafy, teoria liczb i dowody. Analiza matematyczna pyta, jak rzeczy zmieniają się w sposób ciągły; matematyka dyskretna pyta ile, które i czy zdanie jest prawdziwe.
- Czy matematyka dyskretna jest trudna?
- Jest trudna inaczej niż analiza. Jest mniej wzorów do stosowania, a więcej rozumowań do zbudowania, i dla wielu studentów to pierwszy przedmiot oparty na pisaniu dowodów. Algebry jest zwykle niewiele. Ci, którym idzie ciężko, najczęściej przyzwyczajają się do dowodów, a to szybko się poprawia dzięki ćwiczeniu na małych przykładach.
- Do czego służy matematyka dyskretna?
- Do prawie wszystkiego w informatyce. Logika to sposób działania układów elektronicznych i instrukcji if, zbiory leżą u podstaw zapytań do baz danych, kombinatoryka mówi, jak długo działa algorytm, grafy modelują sieci i mapy, a teoria liczb jest podstawą szyfrowania, które chroni płatności w internecie.
- Jakie tematy obejmuje matematyka dyskretna?
- Typowy pierwszy kurs obejmuje rachunek zdań i tabele prawdy, zbiory i diagramy Venna, funkcje i relacje, metody dowodzenia, w tym indukcję, kombinatorykę z permutacjami i kombinacjami, podstawy rachunku prawdopodobieństwa, grafy i drzewa oraz arytmetykę modularną. Niektóre kursy dodają rekurencje i algebrę Boole'a.
- Czy do informatyki potrzebna jest matematyka dyskretna?
- Tak. Prawie każdy kierunek informatyczny ją wymaga, zwykle na pierwszym albo drugim roku, bo algorytmy, struktury danych i teoria obliczeń zakładają jej znajomość. Samo programowanie można zacząć bez niej, ale logika, zbiory i kombinatoryka pojawiają się w codziennym kodzie szybciej, niż większość osób się spodziewa.
- Czym różni się matematyka dyskretna od ciągłej?
- Matematyka dyskretna zajmuje się wartościami, które można wypisać jedna po drugiej, np. liczbami całkowitymi, prawdą i fałszem albo węzłami sieci. Matematyka ciągła, np. analiza, zajmuje się wielkościami, które mogą przyjąć dowolną wartość z przedziału, np. czasem, odległością albo temperaturą.
- Co to jest tabela prawdy?
- Tabela, która wypisuje każdą kombinację prawdy i fałszu dla wejść zdania logicznego oraz wartość zdania dla każdej z nich. Przy dwóch wejściach p i q są cztery wiersze. Tabela prawdy to sposób na udowodnienie, że dwa zdania są równoważne: jeśli ich kolumny zgadzają się w każdym wierszu, zdania zawsze mają tę samą wartość.
