# Ayrık Matematik: Kümeler, Mantık, Bağıntılar ve Graflar

> Kümeler, sayma ilkeleri, önermeler mantığı, bağıntılar, fonksiyonlar, graf teorisi ve temel algoritmaları kapsayan ayrık matematik ders notları.

- Author: Muhammet Ali Köker
- Language: tr
- Canonical: https://alikoker.com.tr/ayrik-matematik-kumeler-mantik-bagintilar-graflar
- Translation: https://alikoker.com.tr/en/discrete-mathematics-sets-logic-relations-graphs
- Published: 2013-10-13T17:45:00+03:00
- Modified: 2026-08-09T00:12:00+03:00
- Verified: 2026-08-09T00:12:00+03:00
- Type: article

Ayrık matematik notlarını 2013-2014 dönemindeki Bilgisayar Mühendisliği lisans dersleri sırasında hazırladım. Güncel sürüm, kümelerden mantık ve bağıntılara, graflardan temel algoritmik düşünmeye uzanan özgün konu sırasını korurken terminolojiyi ve kaynakçayı yeniden gözden geçirmektedir.

## Ünite 1: Kümeler Teorisine Giriş

### Küme kavramı

Bir bütün olarak ele alınan nesne topluluğuna **küme** denir. Topluluğu oluşturan nesnelere **eleman** denir.

Kümeler büyük harfle, elemanlar küçük harfle gösterilir. Aitlik ilişkisi iki simgeyle yazılır:

```text
a ∈ A     a, A kümesinin elemanıdır
b ∉ B     b, B kümesinin elemanı değildir
```

Bir kümenin verilmesi için elemanlarının kesin biçimde belirlenmesi gerekir. İki gösterim kullanılır.

**Liste yöntemi**: elemanlar tek tek yazılır.

```text
A = {1, 2, 3}
```

**Ortak özellik yöntemi**: elemanları ayırt eden karakteristik özellik verilir.

```text
B = { x : x tam sayı ve x > 0 }
```

Tanımın belirleyici koşulu şudur. Bir nesnenin kümeye ait olup olmadığı kesin olarak karara bağlanabilmelidir.

Kümede sıra ve tekrar önemsizdir. {1, 2, 2, 3} ile {3, 1, 2} aynı kümedir.

Bu ders kümeler kuramını aksiyomatik olarak ele almaz. Kümeler cebri düzeyinde kalır.

### Venn diyagramları

Kümeler düzlemde kapalı bölgelerle gösterilir. Evrensel küme dikdörtgenle çizilir.

Diyagram ispat aracı değildir. Bağıntıları görselleştirir ve karşı örnek aramayı kolaylaştırır.

### Sonlu ve sonsuz kümeler

Eleman sayısı bir doğal sayıyla ifade edilebilen kümeye **sonlu küme** denir. Eleman sayısına **kardinalite** denir ve s(A) ya da |A| ile gösterilir.

Sonlu olmayan kümeye **sonsuz küme** denir.

Sonsuz kümeler ikiye ayrılır. Doğal sayılarla birebir eşlenebilenlere **sayılabilir sonsuz** denir. Tam sayılar ve rasyonel sayılar bu sınıftadır. Eşlenemeyenlere **sayılamaz** denir. Reel sayılar bu sınıftadır.

### Boş küme

Hiç elemanı olmayan kümeye **boş küme** denir. ∅ ya da { } ile gösterilir.

Boş küme tektir. Her kümenin alt kümesidir.

{∅} kümesi boş küme değildir. Tek elemanlı bir kümedir ve elemanı boş kümedir.

### Alt küme ve özalt küme

A kümesinin her elemanı B kümesinde de bulunuyorsa A, B'nin **alt kümesidir**:

```text
A ⊆ B  ⟺  ∀x (x ∈ A ⟹ x ∈ B)
```

A ⊆ B ve A ≠ B ise A, B'nin **özalt kümesidir**. A ⊂ B yazılır.

Her küme kendisinin alt kümesidir. Özalt kümesi değildir.

n elemanlı bir kümenin alt küme sayısı 2ⁿ'dir. Özalt küme sayısı 2ⁿ − 1'dir.

Bir kümenin bütün alt kümelerinden oluşan kümeye **kuvvet kümesi** denir. P(A) ile gösterilir ve |P(A)| = 2ⁿ olur.

### Kümelerin eşitliği

İki küme aynı elemanlardan oluşuyorsa eşittir:

```text
A = B  ⟺  A ⊆ B  ve  B ⊆ A
```

Bu ölçüt küme eşitliği ispatlarının standart yöntemidir. İki kapsama ayrı ayrı gösterilir.

### Evrensel küme

Belirli bir incelemede söz konusu olan bütün elemanları içeren kümeye **evrensel küme** denir. E ya da U ile gösterilir.

Evrensel küme mutlak değildir. Probleme göre seçilir.

### Birleşim

En az birine ait olan elemanlardan oluşan kümedir:

```text
A ∪ B = { x : x ∈ A veya x ∈ B }
```

Özellikleri:

```text
A ∪ B = B ∪ A                    değişme
(A ∪ B) ∪ C = A ∪ (B ∪ C)        birleşme
A ∪ ∅ = A                        birim eleman
A ∪ A = A                        eş güçlülük
A ∪ E = E                        yutan eleman
A ⊆ B  ⟺  A ∪ B = B
```

Sonlu kümelerde eleman sayısı **içerme dışlama** ilkesiyle bulunur:

```text
|A ∪ B| = |A| + |B| − |A ∩ B|
|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|
```

### Kesişim

Her ikisine birden ait olan elemanlardan oluşan kümedir:

```text
A ∩ B = { x : x ∈ A ve x ∈ B }
```

Özellikleri birleşimle simetriktir:

```text
A ∩ B = B ∩ A
(A ∩ B) ∩ C = A ∩ (B ∩ C)
A ∩ E = A
A ∩ A = A
A ∩ ∅ = ∅
A ⊆ B  ⟺  A ∩ B = A
```

Kesişimi boş küme olan kümelere **ayrık kümeler** denir.

Dağılma özellikleri iki işlemi birbirine bağlar:

```text
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
```

İki yönde de dağılma geçerlidir. Sayılarda toplama ve çarpma arasında bu simetri yoktur.

### Tümleyen ve fark

Evrensel kümede olup A kümesinde olmayan elemanlar A kümesinin **tümleyenidir**:

```text
A' = { x ∈ E : x ∉ A }
```

Fark işlemi:

```text
A \ B = { x : x ∈ A ve x ∉ B } = A ∩ B'
```

Temel özellikler:

```text
(A')' = A
A ∪ A' = E
A ∩ A' = ∅
E' = ∅,   ∅' = E
```

**De Morgan kuralları** tümleyeni işlemin içine taşır:

```text
(A ∪ B)' = A' ∩ B'
(A ∩ B)' = A' ∪ B'
```

Kurallar sonlu sayıda kümeye genişler. Tümleyen alındığında birleşim ve kesişim yer değiştirir.

### Simetrik fark

Yalnız birine ait olan elemanlardan oluşan kümedir:

```text
A Δ B = (A \ B) ∪ (B \ A) = (A ∪ B) \ (A ∩ B)
```

Değişme ve birleşme özellikleri vardır. A Δ A = ∅ ve A Δ ∅ = A olur.

Mantıktaki "dışlayan veya" işleminin küme karşılığıdır.

### Sıralı ikili ve kartezyen çarpım

Sırası önemli olan iki elemanlı yapıya **sıralı ikili** denir. (a, b) ile gösterilir.

Eşitlik ölçütü şudur:

```text
(a, b) = (c, d)  ⟺  a = c ve b = d
```

Kümede sıra önemsizdi. Sıralı ikilide belirleyicidir.

**Kartezyen çarpım** bütün sıralı ikililerin kümesidir:

```text
A × B = { (a, b) : a ∈ A, b ∈ B }
```

Eleman sayısı çarpılır:

```text
|A × B| = |A| · |B|
```

Kartezyen çarpım değişmeli değildir. A × B ile B × A genelde farklıdır.

İşlem, birleşim ve kesişim üzerine dağılır.

### Kümelerde Boole cebri

Küme işlemleri belirli aksiyomları sağlar. Kuvvet kümesi, birleşim, kesişim ve tümleyen işlemleriyle birlikte bir **Boole cebri** oluşturur.

Sağlanan aksiyomlar şunlardır: değişme, birleşme, dağılma, birim eleman ve tümleyen.

**İkilik ilkesi** bu yapının en kullanışlı sonucudur. Doğru bir eşitlikte ∪ ile ∩ ve E ile ∅ karşılıklı değiştirilirse yine doğru bir eşitlik elde edilir.

Aynı cebirsel yapı önermeler mantığında ve anahtarlama devrelerinde ortaya çıkar. Üç alan aynı kurallarla işler. Ünite 3'te bu bağ kurulur.

### Sayı kümeleri

Kapsama zinciri şöyledir:

```text
ℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ
```

**Doğal sayılar** ℕ = {0, 1, 2, ...} sayma sayılarıdır.

**Tam sayılar** ℤ negatifleri de içerir. Çıkarma işlemine göre kapalıdır.

**Rasyonel sayılar** ℚ, a/b biçiminde yazılabilen sayılardır. b ≠ 0 olmalıdır. Ondalık açılımları sonlu ya da devirlidir.

**İrrasyonel sayılar** kesir biçiminde yazılamaz. Ondalık açılımları sonsuz ve devirsizdir. √2, π ve e bu sınıftadır.

**Reel sayılar** ℝ, rasyonel ve irrasyonel sayıların birleşimidir.

### Aralıklar

```text
[a, b] = { x : a ≤ x ≤ b }      kapalı
(a, b) = { x : a < x < b }      açık
[a, b) ve (a, b]                yarı açık
```

Sonsuz uçlar her zaman açık yazılır.

### Mutlak değer

```text
|x| = x,   x ≥ 0
|x| = −x,  x < 0
```

Geometrik anlamı, sayının sıfıra uzaklığıdır. |x − a| ifadesi x ile a arasındaki uzaklıktır.

Temel özellikler:

```text
|x| ≥ 0
|x·y| = |x|·|y|
|x/y| = |x|/|y|
|x + y| ≤ |x| + |y|          üçgen eşitsizliği
||x| − |y|| ≤ |x − y|
```

Eşitsizlik çözümlerinde iki dönüşüm kullanılır:

```text
|x| < a  ⟺  −a < x < a
|x| > a  ⟺  x < −a  veya  x > a
```

### Tam kısım

x sayısını aşmayan en büyük tam sayıya **tam kısım** denir. ⌊x⌋ ile gösterilir.

```text
⌊3,7⌋ = 3
⌊−3,7⌋ = −4
```

Negatif sayılarda aşağı yuvarlama yapılır. En sık yapılan hata, kesir kısmının atılacağı varsayımıdır.

Temel bağıntı:

```text
⌊x⌋ ≤ x < ⌊x⌋ + 1
```

x − ⌊x⌋ farkına **kesir kısmı** denir ve her zaman [0, 1) aralığındadır.

Tavan fonksiyonu ⌈x⌉, x'ten küçük olmayan en küçük tam sayıdır. Algoritma analizinde blok sayısı hesaplarında kullanılır.

## Ünite 2: Permütasyon ve Kombinasyon

### Faktöriyel

Ardışık pozitif tam sayıların çarpımına **faktöriyel** denir:

```text
n! = n · (n−1) · (n−2) · ... · 2 · 1
```

Tanım gereği 0! = 1 alınır. Bu, boş dizilimin tek biçimde yapılabilmesinin karşılığıdır.

Yineleme bağıntısı:

```text
n! = n · (n−1)!
```

Faktöriyel çok hızlı büyür. 20! değeri 64 bitlik tam sayıya sığar, 21! sığmaz. Kombinatorik hesaplarda taşma bu yüzden erken oluşur.

### Sayma ilkeleri

**Toplama ilkesi**: bir iş ayrık yollardan biriyle yapılabiliyorsa toplam yol sayısı, yol sayılarının toplamıdır.

**Çarpma ilkesi**: bir iş ardışık aşamalardan oluşuyorsa toplam yol sayısı, aşama sayılarının çarpımıdır.

```text
n₁ · n₂ · ... · nₖ
```

Ayrım şu sorudadır. Seçimler arasında "veya" varsa toplanır, "ve" varsa çarpılır.

**Güvercin yuvası ilkesi**: n kutuya n+1 nesne yerleştirilirse en az bir kutuda birden çok nesne bulunur.

İlke basittir, sonuçları güçlüdür. Genelleştirilmiş biçiminde n nesne k kutuya konursa en az bir kutuda ⌈n/k⌉ nesne bulunur.

### Permütasyon

Bir kümenin elemanlarının sıralı dizilişine **permütasyon** denir.

n elemanın tümünün permütasyon sayısı:

```text
P(n, n) = n!
```

n elemandan r tanesinin sıralı seçimi:

```text
P(n, r) = n! / (n − r)! = n · (n−1) · ... · (n−r+1)
```

Belirleyici özellik sıradır. Aynı elemanlar farklı sırada farklı permütasyon sayılır.

### Tekrarlı permütasyon

Bazı elemanlar özdeş ise sıralamalar tekrar eder. n elemanın içinde k tür varsa ve tekrar sayıları n₁, n₂, ..., nₖ ise:

```text
n! / (n₁! · n₂! · ... · nₖ!)
```

Her elemanın her seferinde seçilebildiği durumda, r uzunluklu diziliş sayısı nʳ olur. Şifre ve karakter dizisi sayımlarında bu biçim kullanılır.

**Dairesel permütasyon** sabit bir başlangıç noktası olmadığından farklıdır. n elemanın dairesel diziliş sayısı (n−1)! olur.

### Permütasyonlar grubu

Sonlu bir kümenin kendi üzerine bire bir ve örten fonksiyonlarına da permütasyon denir. Bu bakış, sayma yerine yapı üzerinedir.

n elemanlı kümenin bütün permütasyonlarının kümesi Sₙ ile gösterilir. Eleman sayısı n! olur.

Bileşke işlemi altında Sₙ bir **grup** oluşturur. Grup koşulları şunlardır:

1. Bileşke işlemi kapalıdır. İki permütasyonun bileşkesi yine bir permütasyondur.
2. İşlem birleşmelidir.
3. Her elemanı kendisine eşleyen **birim permütasyon** vardır.
4. Her permütasyonun bir **tersi** vardır. Ters permütasyon, eşlemenin yönünü çevirir.

Bileşke işlemi değişmeli değildir. n ≥ 3 için Sₙ değişmeli bir grup değildir.

### Kombinasyon

Sıranın önemsiz olduğu seçime **kombinasyon** denir:

```text
C(n, r) = n! / [ r! · (n − r)! ]
```

Gösterimler: C(n, r), ⁿCᵣ ve binom katsayısı biçimi.

Permütasyonla ilişkisi şudur:

```text
C(n, r) = P(n, r) / r!
```

r! bölümü, aynı seçimin farklı sıralarını tek sayıma indirger.

Ayrımı belirleyen tek soru şudur: sıra sonucu değiştiriyor mu? Değiştiriyorsa permütasyon, değiştirmiyorsa kombinasyondur.

### Kombinasyonun özellikleri

```text
C(n, 0) = C(n, n) = 1
C(n, 1) = n
C(n, r) = C(n, n−r)                     simetri
C(n, r) = C(n−1, r−1) + C(n−1, r)       Pascal kuralı
Σ C(n, r) = 2ⁿ,   r = 0..n
```

Simetri özelliğinin anlamı şudur. r eleman seçmek, seçilmeyecek n−r elemanı seçmekle aynıdır.

Pascal kuralı, Pascal üçgeninin kuruluş kuralıdır. Belirli bir elemanın seçilip seçilmemesine göre ayrıştırma yapılır.

Alt küme sayısının 2ⁿ olması, bütün kombinasyonların toplamından da çıkar.

**Binom teoremi** kombinasyonu cebire bağlar:

```text
(x + y)ⁿ = Σ C(n, r) · xⁿ⁻ʳ · yʳ
```

### Tekrarlı kombinasyon

n türden r nesnenin sırasız ve tekrarlı seçimi:

```text
C(n + r − 1, r)
```

Bu formül, r özdeş nesnenin n kutuya dağıtılması problemine denktir. Çubuk ve yıldız yöntemiyle türetilir.

## Ünite 3: Önermeler Mantığı

### Önerme

Doğru ya da yanlış olduğu kesin biçimde söylenebilen ifadeye **önerme** denir.

Doğru ya da yanlışlığına 1 ve 0 ile değer verilir. Buna **doğruluk değeri** denir.

Soru, emir ve ünlem cümleleri önerme değildir. Doğruluk değeri taşımayan ifadeler dışarıda kalır.

İçinde belirsiz değişken bulunan ve değişkene değer verildiğinde önermeye dönüşen ifadeye **önermesel** denir. "x > 3" ifadesi önermesel, "5 > 3" ifadesi önermedir.

Önermeler p, q, r gibi harflerle gösterilir.

### Bileşik önerme ve doğruluk tablosu

Birden çok önermenin bağlaçlarla birleştirilmesiyle **bileşik önerme** elde edilir.

Bileşik önermenin doğruluk değeri, bileşenlerin değerlerine bağlıdır. Bu bağımlılık **doğruluk tablosuyla** gösterilir.

n önerme içeren bir bileşik önermenin doğruluk tablosunda 2ⁿ satır bulunur.

### Değilleme

Bir önermenin doğruluk değerini tersine çeviren işlemdir. p' ya da ¬p ile gösterilir.

```text
p    p'
1    0
0    1
```

Çift değilleme özgün önermeye döner:

```text
(p')' = p
```

### Evetleme

"VE" bağlacıyla kurulur. p ∧ q ile gösterilir.

Yalnız her iki önerme de doğruyken doğrudur.

```text
p  q   p∧q
1  1    1
1  0    0
0  1    0
0  0    0
```

### Ayrıklık

"VEYA" bağlacıyla kurulur. p ∨ q ile gösterilir.

En az biri doğruyken doğrudur. Yalnız her ikisi yanlışken yanlıştır.

```text
p  q   p∨q
1  1    1
1  0    1
0  1    1
0  0    0
```

Bu işlem **kapsayan veya** anlamındadır. Günlük dildeki "ya o ya bu" anlamı farklıdır ve **dışlayan veya** ile karşılanır. p ⊕ q yalnız tam olarak biri doğruyken doğrudur.

### Koşullu önerme

"eğer p ise q" biçimindeki önermedir. p ⟹ q ile gösterilir. p **hipotez**, q **hüküm** adını alır.

Yalnız hipotez doğru ve hüküm yanlışken yanlıştır.

```text
p  q   p⟹q
1  1    1
1  0    0
0  1    1
0  0    1
```

Hipotez yanlışken önermenin doğru sayılması sezgiye aykırı görünür. Tanım şu ilkeye dayanır: yanlış bir varsayımdan çıkarılan hiçbir sonuç yanlış sayılamaz. Buna boş doğruluk denir.

Koşullu önerme diğer işlemlerle yazılabilir:

```text
p ⟹ q  ≡  p' ∨ q
(p ⟹ q)'  ≡  p ∧ q'
```

### Karşıt, ters ve karşıt tersi

p ⟹ q önermesinden üç türev önerme elde edilir:

```text
q ⟹ p       karşıt (converse)
p' ⟹ q'     ters (inverse)
q' ⟹ p'     karşıt tersi (contrapositive)
```

Denklik ilişkisi kesindir. Bir önerme yalnız karşıt tersine denktir:

```text
(p ⟹ q) ≡ (q' ⟹ p')
```

Karşıt ile ters birbirine denktir. Özgün önermeye denk değildirler.

Bu ayrım ispat yöntemlerinin temelidir. Doğrudan ispat zorsa karşıt tersi ispatlanır. Sonuç aynıdır.

### Karşılıklı koşullu önerme

"p ancak ve ancak q" biçimindedir. p ⟺ q ile gösterilir.

İki önermenin doğruluk değerleri aynıyken doğrudur.

```text
p ⟺ q  ≡  (p ⟹ q) ∧ (q ⟹ p)
```

Matematiksel tanımlar bu biçimdedir. İki yönlü ispat gerektirir.

### Denk önermeler ve standart biçim

Doğruluk tabloları aynı olan önermelere **denk önermeler** denir. p ≡ q yazılır.

Denklik bağıntısı yansıyan, simetrik ve geçişkendir.

Önermeler cebirsel işlemlerle sadeleştirilir. Standart biçime indirgeme, karmaşık ifadeyi az sayıda bağlaçla yazmaktır.

### Totoloji ve çelişme

Bileşenlerin bütün değerlerinde doğru olan önermeye **totoloji** ya da özdoğruluk denir.

Bütün değerlerde yanlış olan önermeye **çelişme** denir.

Örnekler:

```text
p ∨ p'          totoloji
p ∧ p'          çelişme
(p ∧ q) ⟹ p     totoloji
```

Bir totolojinin değili çelişmedir.

p ≡ q ile p ⟺ q totolojidir ifadeleri aynı anlama gelir. Denklik, karşılıklı koşullunun totoloji olmasıdır.

### Mantık kanunları

```text
p ∨ p ≡ p,   p ∧ p ≡ p                      eş güçlülük
p ∨ q ≡ q ∨ p,   p ∧ q ≡ q ∧ p              değişme
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)                   birleşme
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)             dağılma
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)             dağılma
(p ∨ q)' ≡ p' ∧ q'                          De Morgan
(p ∧ q)' ≡ p' ∨ q'                          De Morgan
p ∨ 0 ≡ p,   p ∧ 1 ≡ p                      birim eleman
p ∨ 1 ≡ 1,   p ∧ 0 ≡ 0                      yutan eleman
p ∨ (p ∧ q) ≡ p                             yutulma
```

Bu kanunlar küme işlemlerindeki kanunlarla birebir örtüşür. ∨ birleşime, ∧ kesişime, değilleme tümleyene karşılık gelir.

İki alan da Boole cebridir. Aynı sadeleştirme aynı adımlarla yapılır.

### Quine yöntemi

Bir önermenin totoloji olup olmadığını doğruluk tablosu kurmadan sınayan yöntemdir.

Değişkenlerden birine bir değer atanır. İfade bu değere göre sadeleştirilir. İşlem, bütün değişkenler tükenene kadar sürer.

Yöntemin dayanağı yutan elemanlardır. Bir alt ifade 1 değerini aldığında, onun dahil olduğu bütün ayrıklıklar 1 olur ve incelenmez.

Değişken sayısı arttıkça kazanç büyür. Doğruluk tablosu 2ⁿ satır ister. Quine yöntemi çoğu durumda dalların erken kapanmasıyla bunun altında kalır. En kötü durumda üstel kalır.

### Mantıksal devreler

Önermeler cebri anahtarlama devrelerine doğrudan uygulanır. Anahtarın kapalı olması 1, açık olması 0 değerine karşılık gelir.

**Seri bağlama** VE işlemini gerçekleştirir. Akım geçmesi için iki anahtar da kapalı olmalıdır.

**Paralel bağlama** VEYA işlemini gerçekleştirir. Akım geçmesi için en az bir anahtarın kapalı olması yeterlidir.

Bağlantılar genelleştirilir. n anahtarın seri bağlanması n değişkenli VE, paralel bağlanması n değişkenli VEYA işlemidir.

**Köprü devreleri** salt seri ve paralel bileşimlere ayrılamayan yapılardır. Devre işlevi, akımın geçtiği bütün yolların ayrıklığı olarak yazılır.

**Devrelerin indirgenmesi**, devre fonksiyonunun mantık kanunlarıyla sadeleştirilmesidir. Doğruluk tablosu aynı kalan iki devreye **denk devre** denir. Sadeleştirme, daha az anahtarla aynı işlevi verir.

Bugünkü karşılığı **mantık kapılarıdır**. Anahtar yerine AND, OR ve NOT kapıları kullanılır. NAND ve NOR kapıları tek başına bütün Boole işlevlerini üretir; bu nedenle işlevsel olarak tamdır. Devre sadeleştirme, tümdevre tasarımında kapı sayısını ve gecikmeyi azaltmak için aynı cebirle yapılır.

Karar problemleri de bu yolla çözülür. Oylama sisteminde her üyenin oyu bir değişkendir. Kararın çıkması bir Boole fonksiyonu olarak yazılır ve devreye dönüştürülür.

## Ünite 4: Bağıntı

### Bağıntı kavramı

A × B kartezyen çarpımının her alt kümesine A'dan B'ye bir **bağıntı** denir.

β bir bağıntı ve (a, b) ∈ β ise a, b ile bağıntılıdır denir ve a β b yazılır.

A × A alt kümelerine A üzerinde bağıntı denir. Bu ders esas olarak bu durumu inceler.

n elemanlı bir küme üzerinde tanımlanabilecek bağıntı sayısı 2^(n²) olur. A × A kümesinin n² elemanı vardır ve her alt kümesi bir bağıntıdır.

Bağıntının tanım kümesi, birinci bileşenlerin kümesidir. Görüntü kümesi, ikinci bileşenlerin kümesidir.

### Gösterim biçimleri

**Liste**: sıralı ikililer yazılır.

**Ok diyagramı**: elemanlar noktalarla, ilişkiler oklarla gösterilir.

**Koordinat diyagramı**: sıralı ikililer düzlemde nokta olarak işaretlenir.

**Matris**: satır ve sütunlar elemanlara karşılık gelir. İlişki varsa 1, yoksa 0 yazılır.

**Yönlü graf**: elemanlar düğüm, ilişkiler yönlü kenardır.

Son iki gösterim bilgisayarda kullanılan biçimlerdir.

### Ters bağıntı

Sıralı ikililerin bileşenleri yer değiştirilerek elde edilir:

```text
β⁻¹ = { (b, a) : (a, b) ∈ β }
```

Ters bağıntının tersi kendisidir. Matris gösteriminde ters bağıntı, matrisin devriğidir.

### Yansıyan bağıntı

Her elemanın kendisiyle bağıntılı olması koşuludur:

```text
∀a ∈ A :  (a, a) ∈ β
```

Matriste köşegenin tümü 1 olur. Yönlü grafta her düğümde bir ilmek bulunur.

Hiçbir elemanın kendisiyle bağıntılı olmadığı durumda bağıntı **yansımazdır**. Yansıyan olmamak ile yansımaz olmak farklı kavramlardır.

### Simetrik bağıntı

```text
(a, b) ∈ β  ⟹  (b, a) ∈ β
```

Matris simetriktir. Grafta her ok çift yönlüdür.

### Ters simetrik bağıntı

```text
(a, b) ∈ β  ve  (b, a) ∈ β  ⟹  a = b
```

Farklı iki eleman arasında karşılıklı ilişki bulunmaz.

Simetrik ile ters simetrik birbirinin karşıtı değildir. Bir bağıntı ikisi birden olabilir. Köşegen bağıntı bu türdendir. Hiçbiri de olmayabilir.

### Geçişken bağıntı

```text
(a, b) ∈ β  ve  (b, c) ∈ β  ⟹  (a, c) ∈ β
```

Grafta iki adımda ulaşılan her düğüme doğrudan ok bulunmalıdır.

Geçişkenlik en sık atlanan koşuldur. Sınamada bütün ikili zincirler taranmalıdır.

### Denklik bağıntısı

Yansıyan, simetrik ve geçişken bağıntıya **denklik bağıntısı** denir.

Üç koşul birlikte aranır. Biri sağlanmazsa bağıntı denklik bağıntısı değildir.

Tipik örnekler: eşitlik, doğruların paralelliği, tam sayılarda mod n denkliği.

### Denklik sınıfları ve parçalanma

a elemanına denk olan bütün elemanların kümesine **denklik sınıfı** denir:

```text
[a] = { x ∈ A : x β a }
```

Temel özellikler:

1. Her eleman kendi sınıfındadır. Hiçbir sınıf boş değildir.
2. İki denklik sınıfı ya özdeştir ya da ayrıktır. Kısmen örtüşme olamaz.
3. Sınıfların birleşimi kümenin tamamını verir.

Bu üç özellik şu anlama gelir: her denklik bağıntısı kümeyi bir **parçalanmaya** ayırır. Karşıtı da doğrudur. Her parçalanma bir denklik bağıntısı tanımlar.

Denklik sınıflarının kümesine **bölüm kümesi** denir. A/β ile gösterilir.

Mod n denkliğinde tam sayılar n adet sınıfa ayrılır. Kalan sınıfları bu parçalanmanın elemanlarıdır.

### Sıralama bağıntıları

Yansıyan, ters simetrik ve geçişken bağıntıya **kısmi sıralama bağıntısı** denir.

Denklik bağıntısından tek farkı simetri koşulunun yerine ters simetrinin gelmesidir. Bu tek değişiklik yapıyı bütünüyle değiştirir. Denklik ayırır, sıralama düzenler.

Örnekler: sayılarda ≤ bağıntısı, kümelerde ⊆ bağıntısı, tam sayılarda bölünebilme.

Kısmi sıralamada her eleman çifti karşılaştırılabilir olmak zorunda değildir. Alt küme bağıntısında ayrık iki küme karşılaştırılamaz.

Her eleman çifti karşılaştırılabiliyorsa bağıntı **tam sıralamadır**:

```text
∀a, b :  a β b  veya  b β a
```

Sayılarda ≤ tam sıralamadır. Kümelerde ⊆ genelde değildir.

### Bağıntı matrisi

Bağıntı, 0 ve 1 değerlerinden oluşan kare matrisle temsil edilir.

Özellikler matris üzerinden okunur:

- Yansıyan: köşegen tümüyle 1.
- Simetrik: matris devriğine eşit.
- Ters simetrik: köşegen dışında karşılıklı iki konum birlikte 1 değil.
- Geçişken: M² matrisinde 1 olan her konum M matrisinde de 1.

Bileşke bağıntının matrisi, Boole matris çarpımıyla bulunur. Çarpma ∧, toplama ∨ işlemine karşılık gelir.

### Kapanışlar

Bir bağıntıya, istenen özelliği sağlaması için eklenmesi gereken en az sayıda ikili eklenerek **kapanış** elde edilir.

**Yansıyan kapanış**: eksik olan köşegen ikilileri eklenir.

```text
r(β) = β ∪ Δ
```

**Simetrik kapanış**: her ikilinin tersi eklenir.

```text
s(β) = β ∪ β⁻¹
```

**Geçişken kapanış**: zincirle ulaşılabilen bütün ikililer eklenir.

```text
t(β) = β ∪ β² ∪ β³ ∪ ... ∪ βⁿ
```

n, küme eleman sayısıdır. Daha uzun zincir yeni ikili üretmez, çünkü her yol en çok n düğüm içerir.

Kapanış, özgün bağıntıyı içeren ve istenen özelliği sağlayan en küçük bağıntıdır. Fazla ekleme yapılırsa kapanış olmaz.

### Warshall algoritması

Geçişken kapanışı matris üzerinde hesaplayan yöntemdir. Ardışık matris çarpımından belirgin biçimde hızlıdır.

Fikir şudur. Ara düğümler sırayla devreye alınır. k. adımda, yalnız ilk k düğümü ara nokta olarak kullanan yollar hesaba katılır.

```text
FOR k = 1 TO n
  FOR i = 1 TO n
    FOR j = 1 TO n
      M[i][j] = M[i][j] OR (M[i][k] AND M[k][j])
```

Üç iç içe döngü çalışır. Karmaşıklık Θ(n³) düzeyindedir.

Döngü sırası önemlidir. Ara düğüm döngüsü en dışta olmalıdır. Sıra değiştirilirse algoritma yanlış sonuç üretir.

Aynı yapı, ağırlıklı graflarda en kısa yol matrisini hesaplar. Boole işlemleri toplama ve enküçük alma işlemleriyle değiştirilir.

## Ünite 5: Fonksiyonlar ve İşlemler

### Fonksiyon

A kümesinin her elemanını B kümesinin bir ve yalnız bir elemanına eşleyen bağıntıya **fonksiyon** denir.

Fonksiyon, özel bir bağıntıdır. İki ek koşul taşır:

1. A kümesinin her elemanı eşlenmiş olmalıdır.
2. Hiçbir eleman birden çok elemanla eşlenmemelidir.

Üçüncü koşul yoktur. B kümesinin bir elemanına A kümesinin birden çok elemanı eşlenebilir.

A tanım kümesi, B değer kümesidir. Görüntülerin kümesine görüntü kümesi denir.

### Fonksiyon türleri

**İçine fonksiyon**: görüntü kümesi, değer kümesinin gerçek alt kümesidir.

**Örten fonksiyon**: görüntü kümesi değer kümesine eşittir. B kümesinde açıkta eleman kalmaz.

**Bire bir fonksiyon**: farklı elemanların görüntüleri farklıdır.

```text
f(x₁) = f(x₂)  ⟹  x₁ = x₂
```

**Bire bir örten fonksiyon**: iki koşulu birlikte sağlar. Yalnız bu fonksiyonların tersi vardır.

**Birim fonksiyon**: her elemanı kendisine eşler.

**Sabit fonksiyon**: bütün elemanları tek bir elemana eşler.

Sonlu kümelerde eleman sayıları belirleyicidir. |A| > |B| ise bire bir fonksiyon yoktur. Bu, güvercin yuvası ilkesinin fonksiyon diliyle ifadesidir. |A| < |B| ise örten fonksiyon yoktur. |A| = |B| ise bire birlik ile örtenlik birbirine denktir.

### Ters fonksiyon

f bire bir ve örten ise ters fonksiyon tanımlıdır:

```text
f⁻¹(y) = x  ⟺  f(x) = y
```

Ters fonksiyonun tanım kümesi f'nin değer kümesidir.

Bağıntı olarak her fonksiyonun tersi vardır. Bu ters bir fonksiyon olmayabilir.

### Bileşke fonksiyon

```text
(g ∘ f)(x) = g(f(x))
```

Tanımlı olması için f'nin görüntü kümesi g'nin tanım kümesinde bulunmalıdır.

Özellikler:

- Değişme özelliği yoktur. g ∘ f ile f ∘ g genelde farklıdır.
- Birleşme özelliği vardır: (h ∘ g) ∘ f = h ∘ (g ∘ f).
- Birim fonksiyon etkisizdir: f ∘ I = I ∘ f = f.
- Ters fonksiyonla bileşke birim fonksiyon verir: f ∘ f⁻¹ = I.

Bileşkenin tersi, terslerin ters sıradaki bileşkesidir:

```text
(g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹
```

Sıranın tersine dönmesi tanımın doğrudan sonucudur. En sık yapılan hata sırayı korumaktır.

İki bire bir fonksiyonun bileşkesi bire birdir. İki örten fonksiyonun bileşkesi örtendir.

### İkili işlem

A × A kümesinden A kümesine tanımlı fonksiyona **ikili işlem** denir.

Tanım gereği işlem sonucu yine A kümesindedir. Bu, kapalılığın tanıma gömülü olması demektir.

Tek bir elemana uygulanan işleme **birli işlem** denir. Tümleyen ve değilleme bu türdendir.

Sonlu kümelerde işlem, **işlem tablosuyla** verilir.

### İşlemin özellikleri

**Kapalılık**: her a, b ∈ A için a * b ∈ A olmalıdır. İşlem tablosunda kümeye ait olmayan eleman görünmemelidir.

**Değişme**: a * b = b * a. İşlem tablosu köşegene göre simetriktir.

**Birleşme**: (a * b) * c = a * (b * c).

**Birim eleman**: her a için a * e = e * a = a sağlayan e elemanıdır. Varsa tektir. İşlem tablosunda satırı ve sütunu başlık sırasını yineler.

**Ters eleman**: a * a⁻¹ = e sağlayan elemandır. Birim eleman yoksa terslikten söz edilemez. İşlem birleşmeli ise ters tektir.

**Dağılma**: iki işlem arasında tanımlıdır.

```text
a * (b ∘ c) = (a * b) ∘ (a * c)
```

Sol ve sağ dağılma ayrı ayrı incelenir. İşlem değişmeli değilse ikisi farklı olabilir.

Bu özellikler cebirsel yapıları tanımlar. Kapalı, birleşmeli, birim elemanlı ve her elemanı tersinir olan yapıya **grup** denir. Grup ayrıca değişmeli ise **değişmeli grup** adını alır.

## Ünite 6: Graf Teorisi

### Königsberg köprüleri problemi

Graf teorisi somut bir problemle doğdu. Königsberg şehrinde yedi köprü, nehrin ayırdığı dört kara parçasını birleştiriyordu. Soru şuydu: her köprüden yalnız bir kez geçerek bütün köprüler dolaşılabilir mi?

Euler problemi soyutladı. Kara parçaları düğüm, köprüler kenar olarak alındı. Şehrin geometrisi silindi; yalnız bağlantı yapısı kaldı.

Sonuç şudur. Her kenardan bir kez geçen kapalı bir yol için bütün düğümlerin derecesi çift olmalıdır. Yol kapalı olmayacaksa tam iki düğümün derecesi tek olabilir; başlangıç ve bitiş bu düğümlerdir. Tek dereceli düğüm sayısı ikiden fazlaysa çizim yapılamaz.

Königsberg'de dört düğümün de derecesi tektir. Problem çözümsüzdür.

### Temel terimler

**Graf**, düğümler kümesi ile kenarlar kümesinden oluşan yapıdır. G = (V, E) ile gösterilir.

**Düğüm** (köşe, vertex) grafın noktalarıdır.

**Kenar** iki düğümü birleştiren bağdır. Uç noktaları aynı olan kenara **ilmek** denir. Aynı iki düğümü birleştiren birden çok kenar varsa bunlara **paralel kenar** denir.

İlmek ve paralel kenar içermeyen grafa **basit graf** denir.

**Derece**, bir düğüme bağlı kenar sayısıdır. İlmek dereceyi iki artırır.

**El sıkışma teoremi**: derecelerin toplamı, kenar sayısının iki katıdır.

```text
Σ deg(v) = 2·|E|
```

Doğrudan sonucu şudur: tek dereceli düğüm sayısı her zaman çifttir.

Her düğümü diğer bütün düğümlere bağlı olan grafa **tam graf** denir. Kₙ ile gösterilir ve kenar sayısı C(n, 2) olur.

### Yörünge, zincir ve devre

**Yürüyüş**, ardışık kenarlardan oluşan dizidir.

**Zincir** kenarların tekrar etmediği yürüyüştür.

**Yol** düğümlerin de tekrar etmediği zincirdir.

Başlangıç ve bitiş düğümü aynı olan kapalı yürüyüşe **devre** denir.

**Euler devresi** her kenardan tam bir kez geçen kapalı devredir. Varlık koşulu bağlantılılık ve bütün derecelerin çift olmasıdır.

**Hamilton devresi** her düğümden tam bir kez geçen kapalı devredir. Euler koşulu gibi basit ve genel bir varlık ölçütü yoktur. Hamilton devresi bulma problemi NP-tam sınıfındadır.

İki kavram karıştırılmamalıdır. Euler kenar üzerinden, Hamilton düğüm üzerinden tanımlıdır.

### Bağlantılılık ve alt graflar

Her düğüm çifti arasında bir yol varsa graf **bağlantılıdır**.

Bağlantılı olmayan graf, **bağlantılı bileşenlere** ayrılır. Her bileşen kendi içinde bağlantılıdır ve bileşenler arasında kenar yoktur.

Düğüm ve kenar kümeleri, özgün grafın alt kümesi olan grafa **alt graf** denir.

Silindiğinde bileşen sayısını artıran kenara **köprü**, düğüme **kesim noktası** denir. Ağ güvenilirliği analizinde bu iki kavram tek arıza noktalarını gösterir.

### Ağaçlar

Devre içermeyen bağlantılı grafa **ağaç** denir.

Denk tanımlar şunlardır:

1. Devresiz ve bağlantılıdır.
2. Her düğüm çifti arasında tam bir yol vardır.
3. Bağlantılıdır ve kenar sayısı n − 1'dir.
4. Devresizdir ve kenar sayısı n − 1'dir.
5. Herhangi bir kenar eklenirse devre oluşur; herhangi bir kenar silinirse bağlantı kopar.

n düğümlü ağacın kenar sayısı her zaman n − 1'dir. Ağaç, bağlantılı kalabilen en seyrek yapıdır.

Bağlantılı grafın, bütün düğümleri içeren ağaç alt grafına **kapsayan ağaç** denir. Her bağlantılı grafın en az bir kapsayan ağacı vardır.

Derecesi 1 olan düğümlere **yaprak** denir. Her ağaçta en az iki yaprak bulunur.

### Yönlendirilmiş graflar

Kenarların yön taşıdığı grafa **yönlü graf** denir.

Derece ikiye ayrılır. Düğüme gelen kenar sayısı **iç derece**, çıkan kenar sayısı **dış derecedir**. İki toplam birbirine ve kenar sayısına eşittir.

Bağlantılılık iki düzeyde tanımlanır. Her düğümden her düğüme yönlere uyularak gidilebiliyorsa graf **güçlü bağlantılıdır**. Yönler yok sayıldığında bağlantılı ise **zayıf bağlantılıdır**.

Yönlü ve devresiz graflar iş sıralama problemlerinde kullanılır. Topolojik sıralama bu yapıda tanımlıdır.

Bağıntılar yönlü graflarla temsil edilir. Yansıyanlık ilmek, simetri çift yönlü kenar, geçişkenlik kısayol kenarı olarak görünür.

### Ağırlıklı graflar ve minimum kapsayan ağaç

Kenarlara sayısal değer atanmışsa graf **ağırlıklıdır**. Ağırlık uzaklık, maliyet ya da süre olabilir.

**Minimum kapsayan ağaç problemi**: bütün düğümleri bağlayan ve toplam ağırlığı en küçük olan ağacı bulmaktır.

**Kruskal algoritması** kenar tabanlıdır:

1. Kenarlar ağırlığa göre artan sırada sıralanır.
2. En küçük ağırlıklı kenar seçilir.
3. Seçilen kenar devre oluşturmuyorsa ağaca eklenir, oluşturuyorsa atlanır.
4. n − 1 kenar seçilene kadar üçüncü adım yinelenir.

Algoritma açgözlüdür. Her adımda yerel en iyi seçim yapılır ve sonuç küresel en iyidir. Bu, açgözlü yaklaşımın doğru sonuç verdiği az sayıdaki problemden biridir.

Devre denetimi ayrık kümeler yapısıyla yapılır. Sıralama baskın maliyettir; karmaşıklık O(E log E) düzeyindedir.

**Prim algoritması** düğüm tabanlı alternatiftir. Tek bir düğümden başlar ve ağacı her adımda en ucuz kenarla büyütür.

### Matrisler ve graflar

**Komşuluk matrisi**, düğüm sayısı kadar satır ve sütundan oluşur. i ile j arasında kenar varsa 1, yoksa 0 yazılır. Yönsüz grafta matris simetriktir. Ağırlıklı grafta 1 yerine ağırlık yazılır.

Matrisin kuvvetleri yol sayısını verir. Aᵏ matrisinin (i, j) elemanı, i düğümünden j düğümüne giden k uzunluklu yürüyüş sayısıdır.

**En kısa uzaklık matrisi**, her düğüm çifti arasındaki en kısa yol uzunluğunu tutar. Floyd-Warshall algoritmasıyla Θ(n³) sürede hesaplanır. Yapı, geçişken kapanış algoritmasıyla aynıdır; Boole işlemleri toplama ve enküçük alma ile değiştirilir.

**Komşuluk listesi** ikinci gösterim biçimidir. Her düğüm için komşularının listesi tutulur.

Seçim graf yoğunluğuna bağlıdır. Komşuluk matrisi Θ(n²) yer kaplar ve kenar sorgusunu sabit sürede yanıtlar. Komşuluk listesi Θ(n + m) yer kaplar ve seyrek graflarda belirgin biçimde ekonomiktir. Gerçek uygulamalardaki grafların çoğu seyrektir.

### Gantt diyagramları ve faaliyet ağları

Proje planlaması graf teorisinin doğrudan uygulama alanıdır.

**Gantt diyagramı**, faaliyetleri zaman ekseni üzerinde yatay çubuklarla gösterir. Sürelerin ve örtüşmelerin okunması kolaydır.

**Faaliyet ağı** öncelik ilişkilerini yönlü grafla gösterir. Bir faaliyetin başlaması için tamamlanması gereken faaliyetler kenarlarla bağlanır.

İki gösterim kullanılır. Faaliyet kenarda gösterilirse ok üzerinde faaliyet diyagramı, düğümde gösterilirse bağda faaliyet diyagramı elde edilir.

**Kukla faaliyet**, süresi sıfır olan yapay kenardır. İki amaçla kullanılır. Öncelik ilişkisini doğru kurmak ve iki faaliyetin aynı düğüm çiftini paylaşmasını önlemek.

En uzun süreli yola **kritik yol** denir. Bu yol üzerindeki faaliyetlerde gecikme projeyi doğrudan geciktirir. Diğer faaliyetlerin **bolluk süresi** vardır.

Kritik yol, devresiz yönlü grafta en uzun yol problemidir. Topolojik sırada tek geçişle hesaplanır.

## Ünite 7: Algoritmalar

### Algoritma kavramı

Bir problemi çözmek için izlenen sonlu ve kesin adımlar dizisine **algoritma** denir.

Taşıması gereken nitelikler şunlardır:

- **Kesinlik**: her adım tek anlamlı olmalıdır.
- **Sonluluk**: sonlu sayıda adımda bitmelidir.
- **Girdi ve çıktı**: tanımlı girdiler alır, en az bir çıktı üretir.
- **Etkinlik**: her adım sonlu sürede yapılabilir olmalıdır.
- **Genellik**: aynı türden bütün problemleri çözmelidir.

Algoritma, programlama dilinden bağımsızdır. Aynı algoritma farklı dillerde gerçeklenebilir.

### Sözde kod

Algoritmayı belirli bir dile bağlanmadan yazma biçimine **sözde kod** (pseudocode) denir.

Doğal dil ile programlama dili arasında durur. Söz dizimi katı değildir; anlam kesindir.

Standart bir yazımı yoktur. Ders boyunca kullanılan yapılar aşağıdadır.

### Karar yapısı

```text
IF <koşul> THEN
    <işlemler>
ELSE
    <işlemler>
END IF
```

Koşul bir önermedir. Doğruluk değerine göre iki daldan biri işletilir. ELSE bloğu isteğe bağlıdır.

İç içe karar yapıları kurulabilir. Çok dallı seçimlerde bu yapı zincirlenir.

### Döngü yapıları

**WHILE**, koşul doğru olduğu sürece yineler:

```text
WHILE <koşul>
    <işlemler>
END WHILE
```

Koşul her yinelemenin başında sınanır. Koşul başta yanlışsa gövde hiç işletilmez.

Sonsuz döngüden kaçınmak için gövdenin koşulu etkilemesi gerekir. Döngü değişkeni her adımda ilerlemelidir.

**FOR**, yineleme sayısı bilindiğinde kullanılır:

```text
FOR i = 1 TO n
    <işlemler>
END FOR
```

Sayaç otomatik olarak artar. Yineleme sayısı baştan bellidir.

İki yapı birbirine dönüştürülebilir. FOR döngüsü, sayaç yönetimi açıkça yazılarak WHILE ile ifade edilir.

### Alt program ve fonksiyon

Bir işlem dizisi birden çok yerde kullanılıyorsa ayrı bir birim olarak yazılır.

**Alt program** (subroutine), çağrıldığı yerde işini yapar ve döner. Değer döndürmesi gerekmez.

```text
SUBROUTINE <ad>
    <işlemler>
END SUBROUTINE
```

Çağrı CALL komutuyla yapılır.

**Fonksiyon** bir değer üretir ve RETURN ile döndürür:

```text
FUNCTION <ad>(<parametreler>)
    <işlemler>
    RETURN <değer>
END FUNCTION
```

Alt program kullanmanın üç yararı vardır. Kod tekrarı azalır, okunabilirlik artar, değişiklik tek noktadan yapılır.

**Dallanma** (branch), akışın sıradan sonraki adım yerine başka bir noktaya aktarılmasıdır. Koşullu ve koşulsuz dallanma vardır. Koşulsuz dallanmanın yaygın kullanımı akış izlemeyi zorlaştırır; yapısal programlamada karar ve döngü yapıları tercih edilir.

### En büyük değerin bulunması

Temel bir tarama algoritmasıdır. Yapısı, birçok dizi algoritmasının kalıbıdır.

```text
ALGORITHM ENBUYUK
    MAX = A[1]
    FOR i = 2 TO n
        IF A[i] > MAX THEN
            MAX = A[i]
        END IF
    END FOR
    RETURN MAX
END ALGORITHM
```

Dört aşama ayırt edilir: ilk değer ataması, tarama, karşılaştırma ve güncelleme, sonuç döndürme.

Dizi n − 1 kez karşılaştırılır. Karmaşıklık Θ(n) düzeyindedir. Daha azı mümkün değildir; her eleman en az bir kez okunmak zorundadır.

Boş dizi durumu ayrıca ele alınmalıdır. İlk değer ataması bu durumda tanımsızdır.

### Kümelerin bilgisayarda temsili

Evrensel küme sıralanır. Her eleman için bir bit ayrılır. Eleman kümede varsa bit 1, yoksa 0 olur. Bu gösterime **bit vektörü** denir.

Küme işlemleri bit işlemlerine dönüşür:

```text
birleşim   →  OR
kesişim    →  AND
tümleyen   →  NOT
fark       →  AND NOT
simetrik fark → XOR
```

Kazanç büyüktür. İşlemci bir komutta 64 biti işler. Eleman eleman dolaşan bir gerçeklemeye göre çok daha hızlıdır.

Yöntemin koşulu, evrensel kümenin sonlu ve baştan bilinen bir sıralamaya sahip olmasıdır. Eleman sayısı çok büyük ve küme seyrek ise bit vektörü yer bakımından verimsiz kalır; bu durumda karma tablo ya da sıralı liste kullanılır.

### Bağıntı ve grafların bilgisayarda gösterimi

**Bağıntı matrisi**, n × n boyutlu bit matrisidir. Bellek kullanımı Θ(n²) olur.

**Bağlı liste**, her düğüm için komşularının zincirini tutar. Bellek kullanımı Θ(n + m) olur.

Seçim ölçütü graf yoğunluğudur. m değeri n² mertebesindeyse matris uygundur. m değeri n mertebesindeyse liste uygundur.

İşlem maliyetleri de değişir. Matriste "i ile j komşu mu" sorusu sabit sürede yanıtlanır. Listede komşu taranır. Buna karşılık bir düğümün bütün komşularını dolaşmak listede derece kadar, matriste n kadar sürer.

### Geçişme algoritması

Warshall algoritması sözde kodla şöyle yazılır:

```text
ALGORITHM WARSHALL
    M = bağıntı matrisi
    FOR k = 1 TO n
        FOR i = 1 TO n
            FOR j = 1 TO n
                M[i][j] = M[i][j] OR (M[i][k] AND M[k][j])
            END FOR
        END FOR
    END FOR
    RETURN M
END ALGORITHM
```

Üç döngü n kez çalışır. Karmaşıklık Θ(n³) düzeyindedir. Bellek kullanımı Θ(n²) olur; matris yerinde güncellenir.

Algoritmanın doğruluğu tümevarımla gösterilir. k. adımdan sonra M matrisi, yalnız ilk k düğümü ara nokta olarak kullanan bütün yolları içerir.

## Genel Kavramsal Çerçeve

Dersin yedi ünitesi ayrı görünür. Tek bir fikir hepsini bağlar.

O fikir **sonlu yapıların ilişki olarak modellenmesidir**.

Zincir şöyle kurulur:

```text
küme
   ↓
kartezyen çarpım
   ↓
bağıntı
   ↓
fonksiyon
   ↓
graf
   ↓
matris ve algoritma
```

Küme temel nesnedir. Kartezyen çarpım eleman çiftlerini üretir. Bağıntı, bu çiftlerin bir alt kümesidir. Fonksiyon, ek koşul taşıyan bir bağıntıdır. Graf, bağıntının görsel karşılığıdır. Matris, grafın makine karşılığıdır. Algoritma, matris üzerinde işleyen yordamdır.

Her halka bir öncekinin özelleşmesi ya da başka bir dildeki karşılığıdır.

İkinci bağ **aynı cebrin üç yüzüdür**. Küme işlemleri, önerme bağlaçları ve anahtarlama devreleri aynı Boole cebrini kullanır.

```text
∪    ∨    paralel bağlama    OR
∩    ∧    seri bağlama       AND
'    ¬    açık anahtar       NOT
```

De Morgan kuralı üç alanda da aynıdır. Bir alanda yapılan sadeleştirme diğerinde geçerlidir. Bu nedenle küme cebri öğrenmek, devre sadeleştirme öğrenmektir.

Üçüncü bağ **sayma ile yapının birbirini beslemesidir**. Alt küme sayısının 2ⁿ olması kombinasyon toplamından çıkar. Bağıntı sayısının 2^(n²) olması aynı hesabın kartezyen çarpım üzerine uygulanmasıdır. Permütasyon hem bir sayma sonucudur hem bir grup yapısıdır.

Dördüncü bağ **temsil seçiminin maliyeti belirlemesidir**. Aynı bağıntı listeyle, matrisle ya da bit vektörüyle temsil edilir. Üçü de doğrudur. Hangi işlemin sık yapılacağı hangisinin seçileceğini belirler. Bu, ayrık matematiği doğrudan yazılım mühendisliğine bağlayan noktadır.

Beşinci bağ **denklik ile sıralamanın karşıtlığıdır**. İki bağıntı türü tek bir koşulla ayrılır. Simetri denklik verir ve kümeyi parçalara ayırır. Ters simetri sıralama verir ve kümeye düzen koyar. Ayırmak ve düzenlemek, ayrık yapılarla yapılan iki temel iştir.

## Kavramsal Ayrımlar

Akılda tutulması gereken ayrımlar şunlardır:

**∈ ≠ ⊆.** Aitlik eleman ile küme arasındadır. Kapsama iki küme arasındadır.

**∅ ≠ {∅}.** Boş kümenin elemanı yoktur. İkincisi tek elemanlıdır.

**Alt küme ≠ özalt küme.** Her küme kendisinin alt kümesidir, özalt kümesi değildir.

**Küme ≠ sıralı ikili.** Kümede sıra önemsizdir. Sıralı ikilide belirleyicidir.

**A × B ≠ B × A.** Kartezyen çarpım değişmeli değildir.

**Permütasyon ≠ kombinasyon.** Sıra sonucu değiştiriyorsa permütasyondur.

**Toplama ilkesi ≠ çarpma ilkesi.** Seçimler arasında "veya" varsa toplanır, "ve" varsa çarpılır.

**Önerme ≠ önermesel.** Önermenin doğruluk değeri vardır. Önermeselde değişken bulunur.

**Kapsayan veya ≠ dışlayan veya.** ∨ her ikisi doğruyken de doğrudur. ⊕ değildir.

**p ⟹ q ≠ q ⟹ p.** Karşıt önerme özgün önermeye denk değildir.

**p ⟹ q ≡ q' ⟹ p'.** Bir koşullu önerme yalnız karşıt tersine denktir.

**Totoloji ≠ çelişme.** İlki her durumda doğru, ikincisi her durumda yanlıştır.

**Denklik bağıntısı ≠ sıralama bağıntısı.** Biri simetrik, diğeri ters simetriktir.

**Simetrik ≠ ters simetrik.** İkisi birden olan bağıntı vardır. Hiçbiri olmayan da vardır.

**Yansıyan olmamak ≠ yansımaz olmak.** İlkinde bazı elemanlar eksiktir, ikincisinde hiçbiri yoktur.

**Denklik sınıfları örtüşmez.** İki sınıf ya özdeştir ya ayrıktır.

**Kısmi sıralama ≠ tam sıralama.** Tam sıralamada her çift karşılaştırılabilir.

**Bağıntı ≠ fonksiyon.** Fonksiyon iki ek koşul taşıyan bağıntıdır.

**Bire bir ≠ örten.** Sonsuz kümelerde biri diğerini gerektirmez.

**(g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹.** Bileşkenin tersinde sıra ters döner.

**Euler devresi ≠ Hamilton devresi.** İlki kenardan, ikincisi düğümden geçer.

**Euler koşulu basittir, Hamilton koşulu değildir.** Hamilton devresi problemi NP-tamdır.

**Ağaç ≠ bağlantılı graf.** Ağaç devresizdir ve kenar sayısı tam n − 1'dir.

**Kruskal ≠ Prim.** İlki kenar tabanlı, ikincisi düğüm tabanlıdır. İkisi de minimum kapsayan ağaç bulur.

**Komşuluk matrisi ≠ komşuluk listesi.** Matris yoğun, liste seyrek graflarda verimlidir.

**Geçişken kapanış ≠ geçişkenlik denetimi.** Kapanış eksik ikilileri ekler, denetim yalnız sınar.

**Warshall döngü sırası değiştirilemez.** Ara düğüm döngüsü en dışta olmalıdır.

**Algoritma ≠ program.** Algoritma dilden bağımsızdır.

**WHILE ≠ FOR.** İlki koşula, ikincisi sayaca dayanır.

Bu ayrımlar kavrandığında dersin konuları tek bir ilişki modelleme çerçevesinde yerine oturur.

## Kaynakça

- Ahmet Yesevi Üniversitesi Bilgisayar Mühendisliği Bölümü. *Ayrık Matematik* (TBIL108) ders materyalleri.
- Kenneth H. Rosen. *Discrete Mathematics and Its Applications*, 8th Edition. McGraw-Hill, 2019.
- Susanna S. Epp. *Discrete Mathematics with Applications*, 5th Edition. Cengage, 2019.
- Ralph P. Grimaldi. *Discrete and Combinatorial Mathematics: An Applied Introduction*, 5th Edition. Pearson, 2003.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. *Introduction to Algorithms*, 4th Edition. MIT Press, 2022.
- Reinhard Diestel. *Graph Theory*, 5th Edition. Springer, 2017.

## Bu Çalışmaya Atıf

Köker, M. A. (2013). Ayrık Matematik: Kümeler, Mantık, Bağıntılar ve Graflar. alikoker.com.tr. https://alikoker.com.tr/ayrik-matematik-kumeler-mantik-bagintilar-graflar

- BibTeX: https://alikoker.com.tr/ayrik-matematik-kumeler-mantik-bagintilar-graflar.bib
- RIS: https://alikoker.com.tr/ayrik-matematik-kumeler-mantik-bagintilar-graflar.ris
- CSL-JSON: https://alikoker.com.tr/ayrik-matematik-kumeler-mantik-bagintilar-graflar.csl.json