Matematyka dyskretna: zestaw na powtórkę

Wzory, najważniejsze kroki metod dla każdego tematu i 8 zadań do ćwiczenia, z pełnymi rozwiązaniami na końcu.

Nowe zadania Wróć do przedmiotu

W oknie drukowania wybierz „Zapisz jako PDF”, aby zachować kopię na swoim urządzeniu.

1Wzory i metody

Rachunek zdań i dowody

Wiersze tablicy prawdy: 2ⁿ
Implikacja: p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
Zaprzeczenie implikacji: ¬(p → q) ≡ p ∧ ¬q
Równoważność: p ↔ q ≡ (p → q) ∧ (q → p)
Prawa de Morgana: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
Prawa rozdzielności: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Zaprzeczanie kwantyfikatorów: ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
Modus ponens, modus tollens: p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

Metoda

Policz różne zmienne: tablica prawdy ma 2ⁿ wierszy, a zaczyna się od samych jedynek.
Każdej podformule daj osobną kolumnę i wypełniaj kolumny od wewnątrz na zewnątrz.
Stosuj regułę każdego spójnika: → jest 0 tylko dla 1 → 0, ↔ jest 1, gdy obie strony się zgadzają.
Przy równoważnościach porównaj końcowe kolumny wiersz po wierszu; przy wnioskowaniu patrz tylko na wiersze, w których każda przesłanka jest równa 1.
Aby zaprzeczyć zdaniu z kwantyfikatorem, przesuń ¬ do środka, zamień ∀ i ∃ oraz zaprzecz formule wewnętrznej.

Zbiory, relacje i funkcje

Dwa zbiory: |A ∪ B| = |A| + |B| − |A ∩ B|
Trzy zbiory: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
Różnica i dopełnienie: A − B = A ∩ B′, |A′| = |U| − |A|
Zbiór potęgowy i iloczyn kartezjański: |𝒫(A)| = 2^|A|, |A × B| = |A|·|B|
Podzbiory k-elementowe: C(n, k) = n!/(k!(n − k)!)
Funkcje A → B: nᵐ; injective n!/(n − m)!; surjective Σ (−1)ᵏ C(n, k)(n − k)ᵐ
Relacje na n elementach: 2^n²; reflexive 2^{n² − n}; symmetric 2^n(n+1)/2
Złożenie: (g ∘ f)(x) = g(f(x))

Metoda

Narysuj diagram Venna i rozstrzygnij obszar po obszarze, co należy do wyrażenia na zbiorach.
W zadaniach na zliczanie wypełniaj obszary od środka na zewnątrz: najpierw wszystkie zbiory, potem pary, potem pojedyncze zbiory, na końcu zewnętrze.
Użyj zasady włączeń i wyłączeń do sprawdzenia: |A ∪ B| = |A| + |B| − |A ∩ B|.
Dla relacji sprawdź każdą własność na każdej parze i podaj jeden kontrprzykład, gdy zawodzi.
Dla funkcji policz strzałki wchodzące do każdego elementu B: co najwyżej jedna oznacza różnowartościowość, co najmniej jedna – surjekcję.

Teoria grafów

Lemat o uściskach dłoni: Σ deg(v) = 2|E|
Grafy pełne: |E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
Graf regularny: |E| = n·k/2
Drzewo i las: |E| = n − 1, |E| = n − c
Liście drzewa: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler: cykl: wszystkie stopnie parzyste; ścieżka: dokładnie 2 stopnie nieparzyste
Cykle Hamiltona w K_n: (n − 1)!/2
Aktualizacja w algorytmie Dijkstry: d(v) = min(d(v), d(u) + w(u, v))
Marsze o długości L: (Mᴸ)_ij

Metoda

Zapisz stopień każdego wierzchołka; suma stopni jest równa dwukrotności liczby krawędzi.
W zadaniach o grafach eulerowskich sprawdź, czy graf jest spójny, i policz wierzchołki o nieparzystym stopniu.
Dla drzew użyj n − 1 krawędzi i lematu o uściskach dłoni.
W algorytmie Dijkstry prowadź tabelę tymczasowych odległości i w każdej rundzie zatwierdzaj niezatwierdzony wierzchołek o najmniejszej odległości.
Dla minimalnego drzewa rozpinającego posortuj krawędzie według wagi i pomijaj każdą krawędź zamykającą cykl (Kruskal) albo rozbudowuj jedno drzewo od wierzchołka startowego (Prim).

Teoria liczb i arytmetyka modularna

Dzielenie z resztą: a = q·n + r, 0 ≤ r < n
Euklides: gcd(a, b) = gcd(b, a mod b)
Najmniejsza wspólna wielokrotność: lcm(a, b) = a·b/gcd(a, b)
Odwrotność: a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Kongruencja liniowa: a·x ≡ b → x ≡ a⁻¹·b (mod n)
Funkcja φ Eulera: φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat: aᵖ⁻¹ ≡ 1 (mod p)
RSA: n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

Metoda

Najpierw zredukuj każdą liczbę modulo n; reszty leżą między 0 a n − 1.
Aby znaleźć NWD, dziel wielokrotnie algorytmem Euklidesa; ostatnia niezerowa reszta jest NWD.
Aby znaleźć element odwrotny, uruchom rozszerzony algorytm i zachowaj współczynnik przy a; dodaj n, jeśli jest ujemny.
Rozwiąż a·x ≡ b, mnożąc przez a⁻¹; dwie kongruencje połącz, zapisując x = r₁ + m₁k.
Przy potęgach zapisz wykładnik binarnie i wielokrotnie podnoś do kwadratu; w RSA d = e⁻¹ mod φ(n), gdzie φ(n) = (p − 1)(q − 1).

2Zadania do ćwiczenia

1.Rachunek zdań i dowodyŚredni

W ilu z 8 wierszy tablicy prawdy ¬((p ∨ q) ∨ ((r ∨ q) → p)) jest prawdziwe? Nazwij tę liczbę N.

¬((p ∨ q) ∨ ((r ∨ q) → p))

N =

2.Rachunek zdań i dowodyTrudny

Które zdanie jest równoważne ¬∀x (A(x) → ∃y R(x, y)), gdy negację przesunięto całkiem do środka? Kliknij je.

¬∀x (A(x) → ∃y R(x, y))

1∃x (A(x) → ∀y ¬R(x, y))
2∃x (A(x) ∧ ∀y ¬R(x, y))
3∃x (¬A(x) ∧ ∃y R(x, y))
4∀x (A(x) ∧ ∀y ¬R(x, y))

3.Zbiory, relacje i funkcjeŚredni

R = {(1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2)} jest relacją na {1, 2, 3}. Jaka jest najmniejsza liczba k par uporządkowanych, które trzeba dodać do R, aby stała się przechodnia (liczność domknięcia przechodniego minus |R|)?

R = {(1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2)}

k =

4.Zbiory, relacje i funkcjeTrudny

Ile jest relacji symetrycznych na zbiorze 3-elementowym? Nazwij tę liczbę N.

|X| = 3

N =

5.Teoria grafówŚredni

Drzewo ma 4× wierzchołek stopnia 3, 2× wierzchołek stopnia 4, 2× wierzchołek stopnia 5, 3× wierzchołek stopnia 2, a wszystkie jego pozostałe wierzchołki są liśćmi (stopień 1). Ile liści L ma to drzewo?

4 × deg 32 × deg 42 × deg 53 × deg 2

L =

6.Teoria grafówTrudny

Użyj algorytmu Dijkstry, aby znaleźć długość d(F) najkrótszej ścieżki z A do F w grafie ważonym.

start: Akoniec: F

d(F) =

7.Teoria liczb i arytmetyka modularnaŚredni

Znajdź element odwrotny do 34 modulo 67: liczbę x, dla której 0 < x < 67 oraz 34·x ≡ 1 (mod 67).

a = 34n = 67

34⁻¹ mod 67 =

8.Teoria liczb i arytmetyka modularnaTrudny

Rozwiąż 10x ≡ 58 (mod 86). Podaj najmniejsze dodatnie rozwiązanie x.

10x ≡ 58 (mod 86)

x =

3Roztwory

1.Rachunek zdań i dowody

Odpowiedź: N = 1

Tablice prawdy: formuła z n różnymi zmiennymi ma 2ⁿ wierszy, po jednym dla każdej kombinacji wartości logicznych (1 = prawda, 0 = fałsz). Pracuj od wewnątrz na zewnątrz i każdej podformule daj osobną kolumnę. ¬a odwraca wartość; a ∧ b jest równe 1 tylko wtedy, gdy oba są równe 1; a ∨ b jest równe 0 tylko wtedy, gdy oba są równe 0; a → b jest równe 0 tylko wtedy, gdy a = 1 i b = 0; a ↔ b jest równe 1, gdy obie strony są równe.

Tablica prawdy wiersz po wierszu

p = 1, q = 1, r = 1: p ∨ q = 1, r ∨ q = 1, (r ∨ q) → p = 1, (p ∨ q) ∨ ((r ∨ q) → p) = 1, ¬((p ∨ q) ∨ ((r ∨ q) → p)) = 0

p = 1, q = 1, r = 0: p ∨ q = 1, r ∨ q = 1, (r ∨ q) → p = 1, (p ∨ q) ∨ ((r ∨ q) → p) = 1, ¬((p ∨ q) ∨ ((r ∨ q) → p)) = 0

p = 1, q = 0, r = 1: p ∨ q = 1, r ∨ q = 1, (r ∨ q) → p = 1, (p ∨ q) ∨ ((r ∨ q) → p) = 1, ¬((p ∨ q) ∨ ((r ∨ q) → p)) = 0

p = 1, q = 0, r = 0: p ∨ q = 1, r ∨ q = 0, (r ∨ q) → p = 1, (p ∨ q) ∨ ((r ∨ q) → p) = 1, ¬((p ∨ q) ∨ ((r ∨ q) → p)) = 0

p = 0, q = 1, r = 1: p ∨ q = 1, r ∨ q = 1, (r ∨ q) → p = 0, (p ∨ q) ∨ ((r ∨ q) → p) = 1, ¬((p ∨ q) ∨ ((r ∨ q) → p)) = 0

p = 0, q = 1, r = 0: p ∨ q = 1, r ∨ q = 1, (r ∨ q) → p = 0, (p ∨ q) ∨ ((r ∨ q) → p) = 1, ¬((p ∨ q) ∨ ((r ∨ q) → p)) = 0

p = 0, q = 0, r = 1: p ∨ q = 0, r ∨ q = 1, (r ∨ q) → p = 0, (p ∨ q) ∨ ((r ∨ q) → p) = 0, ¬((p ∨ q) ∨ ((r ∨ q) → p)) = 1

p = 0, q = 0, r = 0: p ∨ q = 0, r ∨ q = 0, (r ∨ q) → p = 1, (p ∨ q) ∨ ((r ∨ q) → p) = 1, ¬((p ∨ q) ∨ ((r ∨ q) → p)) = 0

Policz wiersze z wartością 1

¬((p ∨ q) ∨ ((r ∨ q) → p)): 0, 0, 0, 0, 0, 0, 1, 0

N = 1

Odpowiedź

N = 1

2.Rachunek zdań i dowody

Odpowiedź: ∃x (A(x) ∧ ∀y ¬R(x, y))

Kwantyfikatory i wnioskowania: ¬∀x P(x) ≡ ∃x ¬P(x) oraz ¬∃x P(x) ≡ ∀x ¬P(x). Przesuń negację do środka, zamień każdy kwantyfikator, który mija, i zaneguj formułę wewnętrzną prawami rachunku zdań, takimi jak ¬(a → b) ≡ a ∧ ¬b. Wnioskowanie jest poprawne, gdy wniosek jest równy 1 w każdym wierszu, w którym wszystkie przesłanki są równe 1. Pojedynczy wiersz z prawdziwymi przesłankami i fałszywym wnioskiem jest kontrprzykładem i pokazuje, że wnioskowanie jest niepoprawne.

Przesuń negację do środka

¬∀x (A(x) → ∃y R(x, y)) ≡ ∃x (A(x) ∧ ∀y ¬R(x, y))

Odpowiedź

∃x (A(x) ∧ ∀y ¬R(x, y))

Pozostałe opcje albo zostawiają kwantyfikator bez zmian, albo zmieniają kolejność kwantyfikatorów, albo błędnie negują formułę wewnętrzną.

3.Zbiory, relacje i funkcje

Odpowiedź: k = 2

Relacje: relacja R na zbiorze X to zbiór par uporządkowanych (x, y). R jest zwrotna, gdy (x, x) ∈ R dla każdego x z X; symetryczna, gdy (x, y) ∈ R zawsze występuje razem z (y, x) ∈ R; antysymetryczna, gdy (x, y) i (y, x) należą do R tylko wtedy, gdy x = y; oraz przechodnia, gdy (x, y) i (y, z) w R wymuszają (x, z) ∈ R. Relacja równoważności jest zwrotna, symetryczna i przechodnia i dzieli X na rozłączne klasy.

Pary do dodania

{(1, 1), (3, 3)}

Policz

k = 2

Odpowiedź

k = 2

4.Zbiory, relacje i funkcje

Odpowiedź: N = 64

Policz dowolne wybory

N = 2^{3 + 3} = 64

Odpowiedź

N = 64

5.Teoria grafów

Odpowiedź: L = 16

Euler, Hamilton i drzewa: graf spójny ma cykl Eulera (każda krawędź raz, powrót do startu), gdy każdy wierzchołek ma stopień parzysty, oraz ścieżkę Eulera, która nie jest cyklem, gdy dokładnie dwa wierzchołki mają stopień nieparzysty; ścieżka biegnie wtedy od jednego wierzchołka nieparzystego do drugiego. Cykl Hamiltona odwiedza każdy wierzchołek raz; K_n ma ich (n − 1)!/2. Drzewo o n wierzchołkach ma n − 1 krawędzi, a graf spójny o m krawędziach zachowuje drzewo rozpinające po usunięciu m − n + 1 krawędzi.

Lemat o uściskach dłoni dla drzewa

L + 36 = 2(L + 11) − 2

L = 16

Odpowiedź

L = 16

Skrót: L = 2 + Σ (d − 2) po wierzchołkach o stopniu d ≥ 3.

6.Teoria grafów

Odpowiedź: d(F) = 20

Najkrótsze ścieżki i drzewa rozpinające: algorytm Dijkstry zatwierdza jeden wierzchołek na rundę: niezatwierdzony wierzchołek o najmniejszej tymczasowej odległości. Jego odległość jest wtedy ostateczna, a każdy sąsiad v dostaje d(v) = min(d(v), d(u) + w(u, v)). Algorytm Kruskala buduje minimalne drzewo rozpinające, biorąc krawędzie od lekkich do ciężkich i pomijając każdą, która zamknęłaby cykl; algorytm Prima rozbudowuje jedno drzewo od wierzchołka startowego, zawsze dodając najlżejszą krawędź wychodzącą z niego. Drzewo rozpinające o n wierzchołkach ma n − 1 krawędzi.

Algorytm Dijkstry runda po rundzie

Każdy wiersz: zatwierdzony wierzchołek, jego ostateczna odległość oraz sąsiedzi, których odległość się poprawia.

A (0): B: 9, C: 2

C (2)

B (9): D: 11, E: 22

D (11): E: 21, F: 20

F (20)

E (21)

Najkrótsza ścieżka

A → B → D → F

d(F) = 20

Odpowiedź

d(F) = 20

7.Teoria liczb i arytmetyka modularna

Odpowiedź: 34⁻¹ mod 67 = 2

Elementy odwrotne i kongruencje: a ma element odwrotny modulo n dokładnie wtedy, gdy NWD(a, n) = 1. Rozszerzony algorytm Euklidesa zapisuje 1 = s·n + t·a, a wtedy a⁻¹ ≡ t (mod n). Kongruencja a·x ≡ b (mod n) przy NWD(a, n) = 1 ma rozwiązanie x ≡ a⁻¹·b. Dwie kongruencje x ≡ r₁ (mod m₁) i x ≡ r₂ (mod m₂) o względnie pierwszych modułach mają jedno rozwiązanie modulo m₁·m₂ (chińskie twierdzenie o resztach). Funkcja φ(n) Eulera zlicza liczby od 1 do n względnie pierwsze z n: φ(n) = n·∏(1 − 1/p).

Rozszerzony algorytm Euklidesa

Każdą resztę r zapisujemy jako r ≡ t·34 (mod 67).

r = 67, t = 0

r = 34, q = 1, t = 1

r = 33, q = 1, t = −1

r = 1, q = 33, t = 2

Odwrotność

1 ≡ 2·34 (mod 67)

x = 2

sprawdzenie: 34·2 = 68 = 1·67 + 1

Odpowiedź

34⁻¹ mod 67 = 2

8.Teoria liczb i arytmetyka modularna

Odpowiedź: x = 23

Podziel przez NWD

gcd(10, 86) = 2

5x ≡ 29 (mod 43)

Rozwiąż skróconą kongruencję

5⁻¹ ≡ 26 (mod 43) → x ≡ 23 (mod 43)

Rozwiązania modulo 86

x ∈ {23, 66}

x = 23

Odpowiedź

x = 23

ExamProblems · examproblems.com/courses/discrete-mathematics