Ayrık Matematik: hızlı tekrar paketi

Formül kâğıtları, her konunun temel yöntem adımları ve 8 alıştırma sorusu; tam çözümler en sonda.

Yeni sorular Derse dön

Yazdırma penceresinde, bir kopyayı cihazınızda saklamak için “PDF olarak kaydet” seçeneğini seçin.

1Formüller ve yöntemler

Önermeler mantığı ve ispatlar

Bir doğruluk tablosunun satırları: 2ⁿ
Gerektirme: p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
Gerektirmenin değili: ¬(p → q) ≡ p ∧ ¬q
Çift yönlü gerektirme: p ↔ q ≡ (p → q) ∧ (q → p)
De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
Dağılma kuralları: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Niceleyicilerin değili: ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
Modus ponens, modus tollens: p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

Yöntem

Farklı değişkenleri sayın: doğruluk tablosu 2ⁿ satırdan oluşur ve hepsinin 1 olduğu satırla başlar.
Her alt formüle kendi sütununu verin ve sütunları içten dışa doğru doldurun.
Her bağlacın kuralını uygulayın: → yalnızca 1 → 0 için 0’dır, ↔ iki taraf aynı olduğunda 1’dir.
Denkliklerde son sütunları satır satır karşılaştırın; bir argümanda ise yalnızca bütün öncüllerin 1 olduğu satırlara bakın.
Niceleyicili bir önermenin değilini almak için ¬’yi içeri taşıyın, ∀ ile ∃’yi değiştirin ve iç formülün değilini alın.

Kümeler, bağıntılar ve fonksiyonlar

İki küme: |A ∪ B| = |A| + |B| − |A ∩ B|
Üç küme: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
Fark ve tümleyen: A − B = A ∩ B′, |A′| = |U| − |A|
Kuvvet kümesi ve çarpım: |𝒫(A)| = 2^|A|, |A × B| = |A|·|B|
k elemanlı alt kümeler: C(n, k) = n!/(k!(n − k)!)
A → B fonksiyonları: nᵐ; injective n!/(n − m)!; surjective Σ (−1)ᵏ C(n, k)(n − k)ᵐ
n elemanlı küme üzerindeki bağıntılar: 2^n²; reflexive 2^{n² − n}; symmetric 2^n(n+1)/2
Bileşke: (g ∘ f)(x) = g(f(x))

Yöntem

Bir Venn şeması çizin ve küme ifadesine hangi bölgelerin ait olduğuna bölge bölge karar verin.
Sayma sorularında bölgeleri ortadan dışa doğru doldurun: önce tüm kümelerin kesişimi, sonra ikili kesişimler, sonra tek kümeler, en son dış bölge.
Kontrol için dahil etme–dışarıda bırakma ilkesini kullanın: |A ∪ B| = |A| + |B| − |A ∩ B|.
Bir bağıntı için her özelliği tüm çiftlerde sınayın; özellik sağlanmıyorsa bir karşı örnek verin.
Bir fonksiyon için B’nin her elemanına gelen okları sayın: en çok bir ok varsa birebirdir, en az bir ok varsa örtendir.

Graf kuramı

El sıkışma lemması: Σ deg(v) = 2|E|
Tam graflar: |E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
Düzgün (regüler) graf: |E| = n·k/2
Ağaç ve orman: |E| = n − 1, |E| = n − c
Ağacın yaprakları: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler: devre: tüm derecelerin çift olması; yol: tam olarak 2 tek derece
K_n içindeki Hamilton devreleri: (n − 1)!/2
Dijkstra güncellemesi: d(v) = min(d(v), d(u) + w(u, v))
L uzunluğundaki gezintiler: (Mᴸ)_ij

Yöntem

Her köşenin derecesini yazın; dereceler toplamı kenar sayısının iki katıdır.
Euler sorularında grafın bağlantılı olduğunu denetleyin ve derecesi tek olan köşeleri sayın.
Ağaçlarda n − 1 kenarı ve el sıkışma lemmasını kullanın.
Dijkstra için geçici uzaklıkların bir tablosunu tutun ve her turda henüz kesinleşmemiş köşelerden en küçük uzaklığa sahip olanı kesinleştirin.
En küçük kapsayan ağaç için kenarları ağırlığa göre sıralayın ve bir döngü kapatan her kenarı atlayın (Kruskal) ya da bir başlangıç köşesinden tek bir ağaç büyütün (Prim).

Sayılar kuramı ve modüler aritmetik

Kalanlı bölme: a = q·n + r, 0 ≤ r < n
Öklid: gcd(a, b) = gcd(b, a mod b)
En küçük ortak kat: lcm(a, b) = a·b/gcd(a, b)
Ters: a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Doğrusal denklik: a·x ≡ b → x ≡ a⁻¹·b (mod n)
Euler’in φ fonksiyonu: φ(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

Yöntem

Önce her sayıyı n modunda indirgeyin; kalanlar 0 ile n − 1 arasındadır.
EBOB için Öklid algoritmasıyla art arda bölün; sıfırdan farklı son kalan EBOB’dur.
Bir ters için genişletilmiş algoritmayı çalıştırın ve a’nın katsayısını alın; negatifse n ekleyin.
a·x ≡ b denkliğini a⁻¹ ile çarparak çözün; iki denkliği x = r₁ + m₁k yazarak birleştirin.
Kuvvetler için üssü ikilik tabanda yazın ve art arda kare alın; RSA’da d = e⁻¹ mod φ(n) ve φ(n) = (p − 1)(q − 1)’dir.

2Alıştırma soruları

1.Önermeler mantığı ve ispatlarOrta

Doğruluk tablosunun 8 satırının kaçında (c ∨ (b ∧ c)) ∧ ((a ∧ b) ∨ a) doğrudur? Bu sayıya N deyin.

(c ∨ (b ∧ c)) ∧ ((a ∧ b) ∨ a)

N =

2.Önermeler mantığı ve ispatlarZor

Doğruluk tablosunun 16 satırının kaçı ¬((c ∧ ¬(d ∧ ¬a)) ↔ (b ↔ (d ∨ b))) formülünü doğru yapar? Bu sayıya N deyin.

¬((c ∧ ¬(d ∧ ¬a)) ↔ (b ↔ (d ∨ b)))

N =

3.Kümeler, bağıntılar ve fonksiyonlarOrta

{1, 2, 3, 4} kümesi üzerindeki R bağıntısı yönlü bir graf olarak çizilmiştir (bir döngü (x, x) ∈ R demektir). Dört özellikten tam biri sağlanır. Ona tıklayın.

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

1yansıyan
2simetrik
3ters simetrik
4geçişli

4.Kümeler, bağıntılar ve fonksiyonlarZor

3 elemanlı bir küme üzerinde kaç simetrik bağıntı vardır? Sayıya N deyin.

|X| = 3

N =

5.Graf kuramıOrta

Bağlantılı bir grafın 15 köşesi ve 23 kenarı vardır. Bir kapsayan ağaç kalması için kaç kenar (k) kaldırılmalıdır?

|V| = 15|E| = 23

k =

6.Graf kuramıZor

Kruskal algoritması en küçük kapsayan ağacı kurar. 3. kenar olarak eklediği kenara tıklayın; atlanan kenarlar sayılmaz.

k = 3

1kenar AB
2kenar AC
3kenar BC
4kenar BD
5kenar CE
6kenar DE
7kenar DF
8kenar BE

7.Sayılar kuramı ve modüler aritmetikOrta

45x ≡ 35 (mod 73) denkliğini çözün. 0 < x < 73 olan x çözümünü verin.

45x ≡ 35 (mod 73)

x =

8.Sayılar kuramı ve modüler aritmetikZor

m = 913 mesajını (n, e) = (943, 19) RSA genel anahtarıyla şifreleyin. Şifreli metni, c, bulun.

n = 943e = 19m = 913

c =

3Çözeltiler

1.Önermeler mantığı ve ispatlar

Cevap: N = 2

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.

Doğruluk tablosu satır satır

a = 1, b = 1, c = 1: b ∧ c = 1, c ∨ (b ∧ c) = 1, a ∧ b = 1, (a ∧ b) ∨ a = 1, (c ∨ (b ∧ c)) ∧ ((a ∧ b) ∨ a) = 1

a = 1, b = 1, c = 0: b ∧ c = 0, c ∨ (b ∧ c) = 0, a ∧ b = 1, (a ∧ b) ∨ a = 1, (c ∨ (b ∧ c)) ∧ ((a ∧ b) ∨ a) = 0

a = 1, b = 0, c = 1: b ∧ c = 0, c ∨ (b ∧ c) = 1, a ∧ b = 0, (a ∧ b) ∨ a = 1, (c ∨ (b ∧ c)) ∧ ((a ∧ b) ∨ a) = 1

a = 1, b = 0, c = 0: b ∧ c = 0, c ∨ (b ∧ c) = 0, a ∧ b = 0, (a ∧ b) ∨ a = 1, (c ∨ (b ∧ c)) ∧ ((a ∧ b) ∨ a) = 0

a = 0, b = 1, c = 1: b ∧ c = 1, c ∨ (b ∧ c) = 1, a ∧ b = 0, (a ∧ b) ∨ a = 0, (c ∨ (b ∧ c)) ∧ ((a ∧ b) ∨ a) = 0

a = 0, b = 1, c = 0: b ∧ c = 0, c ∨ (b ∧ c) = 0, a ∧ b = 0, (a ∧ b) ∨ a = 0, (c ∨ (b ∧ c)) ∧ ((a ∧ b) ∨ a) = 0

a = 0, b = 0, c = 1: b ∧ c = 0, c ∨ (b ∧ c) = 1, a ∧ b = 0, (a ∧ b) ∨ a = 0, (c ∨ (b ∧ c)) ∧ ((a ∧ b) ∨ a) = 0

a = 0, b = 0, c = 0: b ∧ c = 0, c ∨ (b ∧ c) = 0, a ∧ b = 0, (a ∧ b) ∨ a = 0, (c ∨ (b ∧ c)) ∧ ((a ∧ b) ∨ a) = 0

Değeri 1 olan satırları sayın

(c ∨ (b ∧ c)) ∧ ((a ∧ b) ∨ a): 1, 0, 1, 0, 0, 0, 0, 0

N = 2

Cevap

N = 2

2.Önermeler mantığı ve ispatlar

Cevap: N = 8

Sütunlar

¬a; d ∧ ¬a; ¬(d ∧ ¬a); c ∧ ¬(d ∧ ¬a); d ∨ b; b ↔ (d ∨ b); (c ∧ ¬(d ∧ ¬a)) ↔ (b ↔ (d ∨ b)); ¬((c ∧ ¬(d ∧ ¬a)) ↔ (b ↔ (d ∨ b)))

a üzerinden bölün

a = 1: 4

a = 0: 4

N = 4 + 4 = 8

Cevap

N = 8

3.Kümeler, bağıntılar ve fonksiyonlar

Cevap: ters simetrik

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.

yansıyan

sağlanmaz: (1, 1) ∉ R

simetrik

sağlanmaz: (2, 1) ∈ R, (1, 2) ∉ R

ters simetrik

sağlanır

geçişli

sağlanmaz: (4, 2), (2, 1) ∈ R, (4, 1) ∉ R

Cevap

ters simetrik

4.Kümeler, bağıntılar ve fonksiyonlar

Cevap: N = 64

Serbest seçimleri sayın

N = 2^{3 + 3} = 64

Cevap

N = 64

5.Graf kuramı

Cevap: k = 9

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.

Kapsayan ağacın kenarları

15 − 1 = 14

Kaldırılacak kenarlar

k = 23 − 14 = 9

Cevap

k = 9

6.Graf kuramı

Cevap: kenar DF

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.

Kruskal algoritması

1. BD (1)

2. BE (3)

3. DF (8)

4. AB (11)

5. BC (16)

kenar numarası 3

Cevap

kenar DF

7.Sayılar kuramı ve modüler aritmetik

Cevap: x = 17

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

45 sayısının tersi

r = 73, t = 0

r = 45, q = 1, t = 1

r = 28, q = 1, t = −1

r = 17, q = 1, t = 2

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

r = 6, q = 1, t = 5

r = 5, q = 1, t = −8

r = 1, q = 5, t = 13

45⁻¹ ≡ 13 (mod 73)

Çözün

x ≡ 13·35 = 455 ≡ 17 (mod 73)

kontrol: 45·17 = 765 ≡ 35 (mod 73)

Cevap

x = 17

8.Sayılar kuramı ve modüler aritmetik

Cevap: c = 518

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.

Tekrarlı kare alma

19 = 16 + 2 + 1

913¹ ≡ 913 (mod 943)

913² ≡ 900 (mod 943)

913⁴ ≡ 906 (mod 943)

913⁸ ≡ 426 (mod 943)

913¹⁶ ≡ 420 (mod 943)

913¹⁹ ≡ 913·900·420 ≡ 518 (mod 943)

Şifreli metin

c = 518

Cevap

c = 518

ExamProblems · examproblems.com/courses/discrete-mathematics