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

Która formuła jest logicznie równoważna q ∨ (r ∧ p)? Kliknij ją.

q ∨ (r ∧ p)

1(q ∨ r) ∧ (q ∨ p)
2(q ∨ r) ∧ p
3(q ∧ r) ∨ (q ∧ p)
4q ∧ (r ∨ p)

2.Rachunek zdań i dowodyTrudny

Dane są przesłanki a ∨ b; a → c; b → c. Jaki wniosek z nich wynika? Kliknij go.

a ∨ ba → cb → c

1¬c
2a
3a ∧ b
4c

3.Zbiory, relacje i funkcjeŚredni

Ankieta wśród 47 osób: laptop (L) ma 22, tablet (T) 33, smartwatch (W) 26. L i T ma 15, L i W 7, T i W 15, a wszystkie trzy 1. Ile elementów należy do dokładnie dwóch z trzech zbiorów? Nazwij tę liczbę n.

|U| = 47

n =

4.Zbiory, relacje i funkcjeTrudny

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

|X| = 4

N =

5.Teoria grafówŚredni

Graf spójny: liczba wierzchołków 11, liczba krawędzi 13. Ile krawędzi k trzeba usunąć, aby zostało drzewo rozpinające?

|V| = 11|E| = 13

k =

6.Teoria grafówTrudny

Znajdź łączną wagę W minimalnego drzewa rozpinającego grafu ważonego.

|V| = 7|E| = 9

W =

7.Teoria liczb i arytmetyka modularnaŚredni

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

a = 87n = 98

87⁻¹ mod 98 =

8.Teoria liczb i arytmetyka modularnaTrudny

Rozwiąż 45x ≡ 57 (mod 66). Podaj najmniejsze dodatnie rozwiązanie x.

45x ≡ 57 (mod 66)

x =

3Roztwory

1.Rachunek zdań i dowody

Odpowiedź: (q ∨ r) ∧ (q ∨ p)

Równoważność logiczna: dwie formuły są równoważne (≡), gdy mają tę samą wartość w każdym wierszu tablicy prawdy. Tautologia jest równa 1 w każdym wierszu, kontradykcja 0 w każdym wierszu, a formuła kontyngentna nie jest ani jednym, ani drugim. Przydatne prawa: prawa de Morgana, ¬(a ∧ b) ≡ ¬a ∨ ¬b oraz ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (kontrapozycja); ¬(a → b) ≡ a ∧ ¬b; oraz prawa rozdzielności, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).

Prawo

∨ jest rozdzielne względem ∧: a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).

q ∨ (r ∧ p) ≡ (q ∨ r) ∧ (q ∨ p)

Sprawdź tablicą prawdy

p = 1, q = 1, r = 1: 1 | 1 1 1 1

p = 1, q = 1, r = 0: 1 | 1 1 1 1

p = 1, q = 0, r = 1: 1 | 1 1 0 0

p = 1, q = 0, r = 0: 0 | 0 0 0 0

p = 0, q = 1, r = 1: 1 | 1 0 1 1

p = 0, q = 1, r = 0: 1 | 1 0 0 0

p = 0, q = 0, r = 1: 0 | 0 0 0 0

p = 0, q = 0, r = 0: 0 | 0 0 0 0

Odpowiedź

(q ∨ r) ∧ (q ∨ p)

Kolumny po kresce to opcje w pokazanej kolejności.

2.Rachunek zdań i dowody

Odpowiedź: c

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.

Wiersze z wszystkimi prawdziwymi przesłankami

a = 1, b = 1, c = 1: ¬c = 0, a = 1, a ∧ b = 1, c = 1

a = 1, b = 0, c = 1: ¬c = 0, a = 1, a ∧ b = 0, c = 1

a = 0, b = 1, c = 1: ¬c = 0, a = 0, a ∧ b = 0, c = 1

Wniosek

c (dowód przez rozpatrzenie przypadków)

Odpowiedź

3.Zbiory, relacje i funkcje

Odpowiedź: n = 34

Zbiory i diagramy Venna: A ∪ B zawiera elementy należące do A lub B (lub obu), A ∩ B elementy należące do obu, A − B elementy A, które nie należą do B, a dopełnienie A′ wszystko w U, co nie należy do A. Na diagramie Venna każde wyrażenie na zbiorach jest sumą obszarów, więc zliczaj je obszar po obszarze. Włączenia i wyłączenia: |A ∪ B| = |A| + |B| − |A ∩ B| oraz |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Środek i pary

L ∩ T ∩ W: 1

L ∩ T tylko: 15 − 1 = 14

L ∩ W tylko: 7 − 1 = 6

T ∩ W tylko: 15 − 1 = 14

Pojedyncze zbiory

L tylko: 22 − 14 − 6 − 1 = 1

T tylko: 33 − 14 − 14 − 1 = 4

W tylko: 26 − 6 − 14 − 1 = 5

Odpowiedź

14 + 6 + 14 = 34

Odpowiedź

n = 34

4.Zbiory, relacje i funkcje

Odpowiedź: N = 1024

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.

Policz dowolne wybory

N = 2^{4 + 6} = 1024

Odpowiedź

N = 1024

5.Teoria grafów

Odpowiedź: k = 3

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.

Krawędzie drzewa rozpinającego

11 − 1 = 10

Krawędzie do usunięcia

k = 13 − 10 = 3

Odpowiedź

k = 3

6.Teoria grafów

Odpowiedź: W = 57

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 Kruskala

CE (1): weź

BC (3): weź

GD (5): weź

BD (9): weź

GB (13): pomiń, zamyka cykl

DE (17): pomiń, zamyka cykl

GC (18): pomiń, zamyka cykl

EF (19): weź

AB (20): weź

Łączna waga

W = 1 + 3 + 5 + 9 + 19 + 20 = 57

Odpowiedź

W = 57

7.Teoria liczb i arytmetyka modularna

Odpowiedź: 87⁻¹ mod 98 = 89

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·87 (mod 98).

r = 98, t = 0

r = 87, q = 1, t = 1

r = 11, q = 7, t = −1

r = 10, q = 1, t = 8

r = 1, q = 10, t = −9

Odwrotność

1 ≡ −9·87 (mod 98)

x = 89

sprawdzenie: 87·89 = 7743 = 79·98 + 1

Odpowiedź

87⁻¹ mod 98 = 89

8.Teoria liczb i arytmetyka modularna

Odpowiedź: x = 13

Podziel przez NWD

gcd(45, 66) = 3

15x ≡ 19 (mod 22)

Rozwiąż skróconą kongruencję

15⁻¹ ≡ 3 (mod 22) → x ≡ 13 (mod 22)

Rozwiązania modulo 66

x ∈ {13, 35, 57}

x = 13

Odpowiedź

x = 13

ExamProblems · examproblems.com/courses/discrete-mathematics