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

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:

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.

A = {1, 2, 3}

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

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:

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:

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:

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

Özellikleri:

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:

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

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

Özellikleri birleşimle simetriktir:

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:

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:

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

Fark işlemi:

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

Temel özellikler:

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

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

(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:

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:

(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:

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

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

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

ℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ

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

[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

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

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

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

⌊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ı:

⌊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:

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ı:

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.

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ı:

P(n, n) = n!

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

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:

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:

Bileşke işlemi kapalıdır. İki permütasyonun bileşkesi yine bir permütasyondur.
İşlem birleşmelidir.
Her elemanı kendisine eşleyen birim permütasyon vardır.
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:

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

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

Permütasyonla ilişkisi şudur:

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

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:

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

Tekrarlı kombinasyon

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

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.

p    p'
1    0
0    1

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

(p')' = p

Evetleme

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

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

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.

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.

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:

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

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

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

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:

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

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:

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ı

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:

β⁻¹ = { (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:

∀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ı

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

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

Ters simetrik bağıntı

(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ı

(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:

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

Temel özellikler:

Her eleman kendi sınıfındadır. Hiçbir sınıf boş değildir.
İki denklik sınıfı ya özdeştir ya da ayrıktır. Kısmen örtüşme olamaz.
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:

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

r(β) = β ∪ Δ

Simetrik kapanış: her ikilinin tersi eklenir.

s(β) = β ∪ β⁻¹

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

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.

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:

A kümesinin her elemanı eşlenmiş olmalıdır.
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.

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:

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

(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:

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

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.

Σ 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:

Devresiz ve bağlantılıdır.
Her düğüm çifti arasında tam bir yol vardır.
Bağlantılıdır ve kenar sayısı n − 1'dir.
Devresizdir ve kenar sayısı n − 1'dir.
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:

Kenarlar ağırlığa göre artan sırada sıralanır.
En küçük ağırlıklı kenar seçilir.
Seçilen kenar devre oluşturmuyorsa ağaca eklenir, oluşturuyorsa atlanır.
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ı

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:

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:

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.

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:

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.

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:

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:

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:

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.

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