Ayrık Matematik: hızlı tekrar paketi

Mantıksal denklik: doğruluk tablosunun her satırında aynı değere sahip iki formül denktir (≡). Totoloji her satırda 1, çelişki her satırda 0’dır; olumsallık ikisi de değildir. Yararlı kurallar: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b ve ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (karşıt değil); ¬(a → b) ≡ a ∧ ¬b; ve dağılma kuralları, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).

Doğruluk tabloları: n farklı değişkenli bir formülün 2ⁿ satırı vardır; her satır doğruluk değerlerinin bir birleşimidir (1 = doğru, 0 = yanlış). İçten dışa doğru çalışın ve her alt formüle kendi sütununu verin. ¬a değeri tersine çevirir; a ∧ b yalnızca ikisi de 1 olduğunda 1’dir; a ∨ b yalnızca ikisi de 0 olduğunda 0’dır; a → b yalnızca a = 1 ve b = 0 olduğunda 0’dır; a ↔ b iki taraf eşit olduğunda 1’dir.

Kümeler ve Venn şemaları: A ∪ B, A’da ya da B’de (veya her ikisinde) olan elemanları, A ∩ B her ikisinde de olanları, A − B A’nın B’de olmayan elemanlarını ve tümleyen A′ U’da A’da olmayan her şeyi içerir. Bir Venn şemasında her küme ifadesi bölgelerin bir birleşimidir; bu yüzden onu bölge bölge sayın. Dahil etme–dışarıda bırakma: |A ∪ B| = |A| + |B| − |A ∩ B| ve |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Fonksiyonlar ve sayma: bir f: A → B fonksiyonu A’nın her elemanına B’de tam olarak bir görüntü verir. Farklı elemanların görüntüleri farklıysa f birebirdir, B’nin her elemanı bir görüntüyse örtendir, ikisi de sağlanıyorsa eşlemedir (birebir ve örten). |A| = m ve |B| = n iken nᵐ fonksiyon, n!/(n − m)! birebir fonksiyon (m ≤ n) ve dahil etme–dışarıda bırakma ile Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ örten fonksiyon vardır. |𝒫(A)| = 2ᵐ ve |A × B| = m·n.

Euler, Hamilton ve ağaçlar: bağlantılı bir grafın tüm köşelerinin derecesi çiftse bir Euler devresi (her kenar bir kez, başlangıca dönüş), tam olarak iki köşenin derecesi tekse devre olmayan bir Euler yolu vardır; yol bir tek dereceli köşeden ötekine gider. Bir Hamilton devresi her köşeyi bir kez ziyaret eder; K_n grafında bunlardan (n − 1)!/2 tane vardır. n köşeli bir ağacın n − 1 kenarı vardır ve m kenarlı bağlantılı bir graf m − n + 1 kenar kaldırıldıktan sonra bir kapsayan ağaç bırakır.

En kısa yollar ve kapsayan ağaçlar: Dijkstra algoritması her turda bir köşeyi kesinleştirir: geçici uzaklığı en küçük olan, henüz kesinleşmemiş köşeyi. Uzaklığı artık kesindir ve her komşu v için d(v) = min(d(v), d(u) + w(u, v)) alınır. Kruskal algoritması en küçük kapsayan ağacı, kenarları hafiften ağıra alıp bir döngü kapatacak kenarları atlayarak kurar; Prim algoritması bir başlangıç köşesinden tek bir ağaç büyütür ve her seferinde ağaçtan çıkan en hafif kenarı ekler. n köşeli bir kapsayan ağacın n − 1 kenarı vardır.

Tersler ve denklikler: a’nın n modunda tersi, tam olarak ebob(a, n) = 1 olduğunda vardır. Genişletilmiş Öklid algoritması 1 = s·n + t·a yazar ve sonra a⁻¹ ≡ t (mod n) olur. ebob(a, n) = 1 olan a·x ≡ b (mod n) denkliğinin çözümü x ≡ a⁻¹·b’dir. Modülleri aralarında asal olan x ≡ r₁ (mod m₁) ve x ≡ r₂ (mod m₂) denkliklerinin m₁·m₂ modunda bir çözümü vardır (Çin kalan teoremi). Euler’in φ(n) fonksiyonu 1’den n’ye kadar n ile aralarında asal olan sayıları sayar: φ(n) = n·∏(1 − 1/p).

Modüler kuvvetler ve RSA: aᵏ mod n değerini tekrarlı kare almayla hesaplayın: k’yi ikilik tabanda yazın, kare alın, her adımdan sonra indirgeyin ve biti 1 olan kuvvetleri çarpın. Fermat: a’yı bölmeyen bir p asalı için aᵖ⁻¹ ≡ 1 (mod p); dolayısıyla üs p − 1 modunda indirgenebilir. RSA: p ve q asallarını seçin, n = p·q ve φ(n) = (p − 1)(q − 1); genel üs e, φ(n) ile aralarında asaldır ve özel üs d = e⁻¹ mod φ(n)’dir. c = mᵉ mod n ile şifreleyin ve m = cᵈ mod n ile çözün.