Ayrık Matematik: hızlı tekrar paketi

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.

Niceleyiciler ve argümanlar: ¬∀x P(x) ≡ ∃x ¬P(x) ve ¬∃x P(x) ≡ ∀x ¬P(x). Değili içeri taşıyın, geçtiği her niceleyiciyi değiştirin ve iç formülün değilini ¬(a → b) ≡ a ∧ ¬b gibi önermeler mantığı kurallarıyla alın. Tüm öncüllerin 1 olduğu her satırda sonuç da 1 ise bir argüman geçerlidir. Öncüllerin doğru, sonucun yanlış olduğu tek bir satır bir karşı örnektir ve argümanın geçersiz olduğunu gösterir.

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|.

Bağıntılar: bir X kümesi üzerindeki bir R bağıntısı, sıralı (x, y) çiftlerinin kümesidir. X’teki her x için (x, x) ∈ R ise R yansıyandır; (x, y) ∈ R her zaman (y, x) ∈ R ile birlikte geliyorsa simetriktir; (x, y) ve (y, x) yalnızca x = y ise birlikte R’deyse ters simetriktir; R’deki (x, y) ve (y, z) (x, z) ∈ R’yi zorunlu kılıyorsa geçişlidir. Denklik bağıntısı yansıyan, simetrik ve geçişlidir ve X’i ayrık sınıflara böler.

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.