Matematika Diskrit: paket kilat

Ekuivalensi logis: dua rumus ekuivalen (≡) jika bernilai sama pada setiap baris tabel kebenaran. Tautologi bernilai 1 pada setiap baris, kontradiksi bernilai 0 pada setiap baris, dan kontingensi bukan keduanya. Hukum yang berguna: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b dan ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (kontrapositif); ¬(a → b) ≡ a ∧ ¬b; dan hukum distributif, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).

Kuantor dan argumen: ¬∀x P(x) ≡ ∃x ¬P(x) dan ¬∃x P(x) ≡ ∀x ¬P(x). Pindahkan negasi ke dalam, tukar setiap kuantor yang dilewatinya, dan negasikan rumus di dalamnya dengan hukum proposisional, seperti ¬(a → b) ≡ a ∧ ¬b. Sebuah argumen valid jika kesimpulannya bernilai 1 pada setiap baris yang semua premisnya bernilai 1. Satu baris dengan premis benar dan kesimpulan salah adalah contoh penyangkal dan menunjukkan bahwa argumen itu tidak valid.

Himpunan dan diagram Venn: A ∪ B memuat elemen di A atau B (atau keduanya), A ∩ B elemen di keduanya, A − B elemen A yang tidak ada di B, dan komplemen A′ semua yang ada di U tetapi tidak di A. Dalam diagram Venn setiap ekspresi himpunan adalah gabungan daerah-daerah, jadi hitunglah daerah demi daerah. Inklusi–eksklusi: |A ∪ B| = |A| + |B| − |A ∩ B|, dan |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Fungsi dan pencacahan: fungsi f: A → B memberi setiap elemen A tepat satu bayangan di B. f injektif (satu-satu) jika elemen berbeda punya bayangan berbeda, surjektif (pada) jika setiap elemen B adalah bayangan, dan bijektif jika keduanya berlaku. Dengan |A| = m dan |B| = n ada nᵐ fungsi, n!/(n − m)! fungsi injektif (m ≤ n), dan menurut inklusi–eksklusi Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ fungsi surjektif. |𝒫(A)| = 2ᵐ dan |A × B| = m·n.

Euler, Hamilton, dan pohon: graf terhubung memiliki sirkuit Euler (setiap sisi sekali, kembali ke awal) jika setiap simpul berderajat genap, dan lintasan Euler yang bukan sirkuit jika tepat dua simpul berderajat ganjil; lintasan itu berjalan dari satu simpul ganjil ke simpul ganjil lainnya. Sirkuit Hamilton mengunjungi setiap simpul sekali; K_n memiliki (n − 1)!/2 sirkuit seperti itu. Pohon dengan n simpul memiliki n − 1 sisi, dan graf terhubung dengan m sisi masih memiliki pohon rentang setelah m − n + 1 sisi dihapus.

Lintasan terpendek dan pohon rentang: algoritma Dijkstra menetapkan satu simpul per putaran: simpul belum tetap dengan jarak sementara terkecil. Jaraknya lalu final, dan setiap tetangga v mendapat d(v) = min(d(v), d(u) + w(u, v)). Algoritma Kruskal membangun pohon rentang minimum dengan mengambil sisi dari yang ringan ke berat dan melewati sisi yang akan membentuk siklus; algoritma Prim menumbuhkan satu pohon dari simpul awal dengan selalu menambahkan sisi teringan yang keluar dari pohon. Pohon rentang dengan n simpul memiliki n − 1 sisi.

Invers dan kongruensi: a memiliki invers modulo n tepat ketika FPB(a, n) = 1. Algoritma Euclid yang diperluas menuliskan 1 = s·n + t·a, dan kemudian a⁻¹ ≡ t (mod n). Kongruensi a·x ≡ b (mod n) dengan FPB(a, n) = 1 memiliki penyelesaian x ≡ a⁻¹·b. Dua kongruensi x ≡ r₁ (mod m₁) dan x ≡ r₂ (mod m₂) dengan modulus saling prima memiliki satu penyelesaian modulo m₁·m₂ (teorema sisa Cina). φ(n) Euler menghitung bilangan dari 1 sampai n yang saling prima dengan n: φ(n) = n·∏(1 − 1/p).

Pangkat modular dan RSA: hitung aᵏ mod n dengan pengkuadratan berulang: tulis k dalam biner, kuadratkan, reduksi setelah setiap langkah, dan kalikan pangkat yang bitnya 1. Fermat: aᵖ⁻¹ ≡ 1 (mod p) untuk bilangan prima p yang tidak membagi a, sehingga eksponen dapat direduksi modulo p − 1. RSA: pilih bilangan prima p dan q, n = p·q dan φ(n) = (p − 1)(q − 1); eksponen publik e saling prima dengan φ(n), dan eksponen privat adalah d = e⁻¹ mod φ(n). Enkripsi dengan c = mᵉ mod n dan dekripsi dengan m = cᵈ mod n.