- Doğruluk tabloları kurmak, mantıksal denklikleri kullanmak ve niceleyicili önermelerin olumsuzunu almak
- Doğrudan ispat, olmayana ergi ve tümevarımla ispat yazmak
- Kümelerle işlem yapmak ve bir fonksiyonun birebir, örten ya da birebir ve örten olup olmadığına karar vermek
- Derecelerle graflar hakkında akıl yürütmek ve bir Euler yolunun olup olmadığına karar vermek
Bir programdaki her “eğer … ise …”, bir veritabanı sorgusundaki her WHERE koşulu ve telefonundaki her yonga doğru ile yanlışın mantığına dayanır. 1730'larda Leonhard Euler, Königsberg'in yedi köprüsünün her birinden tam bir kez geçerek şehri dolaşmanın mümkün olup olmadığını sordu ve bunun imkânsız olduğunu kanıtlarken graf kuramının temellerini attı. Ayrık matematik, yani mantık, kümeler, fonksiyonlar ve graflar, ispatların ve bilgisayar biliminin dilidir.
Önermeler, doğruluk tabloları ve niceleyiciler
Ya doğru (1) ya da yanlış (0) olan bir cümle; örneğin “7 asal sayıdır”. Bileşik önermeler ¬ (değil), ∧ (ve), ∨ (veya), → (ise, koşullu önerme) ve ↔ (ancak ve ancak, iki yönlü koşullu önerme) bağlaçlarıyla kurulur.
| p | q | ¬p | p ∧ q | p ∨ q | p → q | p ↔ q |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
p → q koşullu önermesi yalnızca p doğru ve q yanlış olduğunda yanlıştır. “Yağmur yağarsa şemsiye alırım” sözü yalnızca şemsiyesiz yağmurlu bir günde bozulur; kuru bir günde ne yaparsam yapayım söz tutulmuş olur. Bu yüzden öncülü yanlış olan bir koşullu önerme doğru sayılır.
- ≡mantıksal denklik: her satırda aynı doğruluk değeri
De Morgan kuralları.
- ¬q → ¬pkarşıt ters, p → q ile denktir
- q → pkarşıt önerme, denk değildir
Çok sayıda nesne hakkındaki önermelerde niceleyiciler kullanılır: ∀ (“her”) ve ∃ (“en az bir … vardır”). Örneğin ∀x ∈ ℝ: x² ≥ 0 doğrudur, ∃n ∈ ℕ: n² = 2 ise yanlıştır. Niceleyicili bir önermenin olumsuzunu almak için ∀ ile ∃ yer değiştirir ve arkasından gelen kısım olumsuzlanır:
- P(x)x'in bir özelliği (yüklem)
- ∀evrensel niceleyici
- ∃varlıksal niceleyici
Olumsuzunu yazın: a) “Gruptaki her öğrenci en az bir sınavı geçti”; b) “Bir sayı 4'e bölünüyorsa çifttir”.
Çözümü gösterÇözümü gizle
b) p → q; burada p = “4'e bölünür”, q = “çifttir”. Olumsuzu p ∧ ¬q'dur: “4'e bölünen ama çift olmayan bir sayı vardır”. Bu yanlıştır; yani ilk önerme doğrudur.
İspat yöntemleri
- Doğrudan ispat: varsayımlardan başlayıp geçerli adımlarla sonuca ulaşılır.
- Karşıt ters: p → q yerine ¬q → ¬p ispatlanır.
- Olmayana ergi: önermenin yanlış olduğu varsayılır ve bir çelişkiye ulaşılır.
- Tümevarım: P(1) ispatlanır, sonra P(n) ⇒ P(n + 1) gösterilir; o zaman P(n) her doğal sayı n için doğrudur, tıpkı sonsuz bir sıra hâlinde devrilen domino taşları gibi.
İspatlayın: a) iki tek sayının toplamı çifttir; b) √2 irrasyoneldir.
Çözümü gösterÇözümü gizle
b) √2 = p/q sadeleşmeyen bir kesir olsun. O zaman p² = 2q², p² çifttir, dolayısıyla p de çifttir (p tek olsaydı p² de tek olurdu): p = 2k.
Bu durumda 4k² = 2q², q² = 2k²; yani q de çifttir.
Hem p hem q çift; bu, kesrin sadeleşmemesiyle çelişir. Demek ki √2 irrasyoneldir ∎.
- P(1)temel adım
- P(n) → P(n + 1)tümevarım adımı; P(n) tümevarım hipotezidir
Her doğal sayı n için 1 + 3 + 5 + … + (2n − 1) = n² olduğunu ispatlayın.
Çözümü gösterÇözümü gizle
Tümevarım adımı: 1 + 3 + … + (2n − 1) = n² olsun. Sonraki tek sayıyı, 2n + 1'i ekleyelim:
1 + 3 + … + (2n − 1) + (2n + 1) = n² + 2n + 1 = (n + 1)².
Bu, n + 1 için önermedir; tümevarımla eşitlik her n için doğrudur ∎. Örneğin 1 + 3 + 5 + 7 = 16 = 4².
Kümeler ve Venn şemaları
- A ∪ Bbirleşim: A'da veya B'de (ya da ikisinde) olan elemanlar
- A ∩ Bkesişim: ikisinde de olan elemanlar
- A \ Bfark: A'da olup B'de olmayanlar
- Aᶜtümleyen: U evrensel kümesinin A'da olmayan elemanları
Küme işlemleri mantığı yansıtır: ∪, ∨'ye; ∩, ∧'ye; tümleyen de ¬'ye karşılık gelir; bu yüzden De Morgan kuralları yine geçerlidir: (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ ve (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ. A ⊆ B, A'nın her elemanının B'de olduğu anlamına gelir. n elemanlı bir kümenin 2ⁿ alt kümesi vardır; A × B kartezyen çarpımı ise tüm (a, b) sıralı ikililerinden oluşur.
- |A|A kümesinin eleman sayısı
İçerme-dışlama ilkesi: iki kümede de olan elemanlar iki kez sayıldığından bir kez çıkarılır. Üç küme için: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
40 öğrencilik bir grupta 25 kişi İngilizce, 18 kişi Rusça, 7 kişi de her ikisini öğreniyor. Kaç kişi en az bir dil öğreniyor, kaç kişi hiçbirini öğrenmiyor ve kaç kişi yalnızca İngilizce öğreniyor?
Çözümü gösterÇözümü gizle
Hiçbiri: 40 − 36 = 4.
Yalnızca İngilizce: 25 − 7 = 18; yalnızca Rusça: 18 − 7 = 11.
Venn şemasının bölgeleriyle kontrol: 18 + 7 + 11 + 4 = 40 ✓.
Bağıntılar ve fonksiyonlar
A'dan B'ye bir bağıntı, herhangi bir R ⊆ A × B alt kümesidir. Tek bir küme üzerindeki bağıntı yansıyan (a R a), simetrik (a R b ⇒ b R a) ve geçişken (a R b ve b R c ⇒ a R c) olabilir. Üçü birlikte bir denklik bağıntısı verir ve kümeyi sınıflara ayırır: örneğin “3'e bölümünden aynı kalanı verir” bağıntısı ℤ'yi üç sınıfa ayırır.
Her a ∈ A elemanına tam olarak bir f(a) ∈ B görüntüsü karşılık gelen f: A → B bağıntısı. A tanım kümesi, B değer kümesidir.
| Tür | Anlamı | Örnek |
|---|---|---|
| Birebir | Farklı elemanların görüntüleri farklıdır: f(a₁) = f(a₂) ⇒ a₁ = a₂ | f(x) = 2x, ℤ → ℤ (örten değil: tek sayılar elde edilmez) |
| Örten | Her b ∈ B, bir a'nın görüntüsüdür | f(x) = x³ − x, ℝ → ℝ (birebir değil: f(0) = f(1) = 0) |
| Birebir ve örten | Hem birebir hem örten; ters fonksiyonu f⁻¹ vardır | f(x) = x³, ℝ → ℝ; f(x) = x², [0, ∞) → [0, ∞) |
| Hiçbiri | Ne birebir ne örten | f(x) = x², ℝ → ℝ: f(−2) = f(2) ve negatif sayılar hiç değer olarak çıkmaz |
Graflar
Bir düğümler (köşeler) kümesi V ile her biri iki düğümü birleştiren bir kenarlar kümesi E: G = (V, E). v'nin derecesi deg(v), v'ye bağlı kenar sayısıdır. Yol, kenarlarla birleşen düğümler dizisidir; döngü kapalı bir yoldur; her iki düğüm bir yolla birleşiyorsa graf bağlantılıdır.
- deg(v)v düğümünün derecesi
- |E|kenar sayısı
El sıkışma lemması: her kenarın iki ucu vardır. Sonuç: tek dereceli düğümlerin sayısı her zaman çifttir.
- |V|ağacın düğüm sayısı
Ağaç, döngüsü olmayan bağlantılı bir graftır (soy ağacı, bilgisayardaki klasörler, mümkün olan en az bağlantıyla kurulmuş bir ağ). Her ağaçta kenar sayısı düğüm sayısından tam bir eksiktir: herhangi bir kenar eklemek döngü oluşturur, herhangi bir kenarı silmek bağlantıyı koparır.
Bir Euler yolu her kenardan tam bir kez geçer; Euler devresi ayrıca başladığı yere döner. Euler teoremi: bağlantılı bir grafta Euler devresi ancak ve ancak tüm dereceler çiftse, (kapalı olmayan) bir Euler yolu ise ancak ve ancak tam iki düğümün derecesi tekse vardır; yol bunlardan birinde başlayıp diğerinde bitmelidir. Königsberg'de dört kara parçasının dereceleri 5, 3, 3 ve 3'tü: dört tek düğüm olduğundan yürüyüş imkânsızdır. Hamilton yolu ise her düğümden tam bir kez geçer; bunun için basit bir ölçüt bilinmez ve böyle en kısa turu bulmak (gezgin satıcı problemi) bilgisayar biliminin ünlü zor problemlerinden biridir.
Bir “ev”: ABCD karesi (A sol alt, B sağ alt, C sağ üst, D sol üst), AC ve BD köşegenleri ve D–E–C çatısı. Hiçbir çizgiyi iki kez çizmeden tek hamlede çizilebilir mi?
Çözümü gösterÇözümü gizle
Dereceler: A = 3, B = 3, C = 4, D = 4, E = 2; toplam 16 = 2 · 8 ✓ (el sıkışma lemması).
Tam iki tek düğüm var (A ve B); yani bir Euler yolu vardır ve A'da ya da B'de başlamalıdır.
Bir çözüm: A → B → D → E → C → D → A → C → B.
Euler devresi ise imkânsızdır, çünkü A ve B'nin dereceleri tektir.
a) 10 kişi buluşuyor ve her biri tam 3 kişiyle tokalaşıyor. Toplam kaç tokalaşma olur? b) 7 kişinin her biri tam 3 kişiyle tokalaşabilir mi?
Çözümü gösterÇözümü gizle
b) Toplam 7 · 3 = 21, yani tek bir sayı olurdu; oysa 2|E|'ye eşit olmalıdır. İmkânsız.
Önemli noktalar
- p → q yalnızca p = 1, q = 0 iken yanlıştır; p → q ≡ ¬q → ¬p, ama q → p'ye denk değildir.
- Olumsuzlama: ∀ ile ∃, ∧ ile ∨ yer değiştirir (De Morgan) ve ¬(p → q) ≡ p ∧ ¬q.
- Tümevarım: temel adım P(1) ve tümevarım adımı P(n) ⇒ P(n + 1); ikisi de zorunludur.
- |A ∪ B| = |A| + |B| − |A ∩ B|; (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ.
- Birebir ve örten = birebir + örten; yalnızca böyle bir fonksiyonun tersi vardır.
- ∑ deg(v) = 2|E|; ağaçta |E| = |V| − 1; Euler yolu için 0 veya 2 tek düğüm gerekir.
Kendini test et
10 soru. Her doğru cevap XP kazandırır.