Bağıntı ve Fonksiyon
Ders 4
4-1
Konular
4-2
1
Bağıntı
4-3
Bağıntı Örneği
4-4
2
Bağıntı Bileşkesi
4-5
Bileşke Matris Örneği
4-6
3
Birleşme Özelliği
4-7
Bileşke Özelliği
4-8
4
Bileşke Özellikleri
4-9
Evrik Bağıntı – Ters Bağıntı
4-10
5
Evrik Bağıntı Özellikleri
4-11
Evrik Bağıntı Teoremleri
4-12
6
Evrik Bağıntı Teoremleri
4-13
Evrik Bağıntı Teoremleri
4-14
7
Bileşke Evriği
4-15
Bileşke Evriği Matrisi
4-16
8
Kümeiçi Bağıntı
Yansıyan, reflexive
Simetrik
4-17
Bağıntıların Özellikleri
Tanım: R, A kümesi üzerinde bir bağıntı olsun. O halde R;
Tüm aA için, sadece ve sadece aRa ise yansıyandır.
(reflexive).
ii. a,bA için aRb, sadece ve sadece bRa anlamına geliyorsa
simetriktir (bakışlıdır).
iii. a,bA için aRb ve bRa sadece ve sadece a=b anlamına
geliyorsa ters simetriktir (ters bakışlıdır).
iv. a,b,cA için aRb ve bRc sadece ve sadece aRc anlamına
geliyorsa geçişlidir (transitive).
i.
4-18
9
Örnek
• Örnek: A={a,b,c,d} ve
R={(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(b,d),(d,d)}
olsun.
• R bağıntısı yukarıdaki tanımdaki hiçbir özelliği sağlamaz.
• R yansıyan değildir çünkü cRc değildir; bu nedenle tüm xA için
xRx doğru değildir.
• R simetrik değildir zira örneğin aRc’dir fakat cRa değildir.
• R ters simetrik değildir zira aRb ve bRa ‘dır fakat a=b değildir.
• R geçişli değildir çünkü aRb ve bRd ‘dir fakat aRd değildir.
4-19
UYARI
• Verilen digraphlar veya ikili matrisler ile bağıntı özelliklerinin
anlaşılması mümkündür.
• Eğer bağıntı yansıyan bağıntı ise R’ nin digraphının her
noktasından kendisine bir yönlü ok vardır.
• İkili matrisinde ise diyagonal elemanların hepsi 1’ dir.
• Eğer R simetrik ise digraphtaki okların tamamı iki-yönlüdür.
• Ters simetrik ise okların hiçbiri iki yönlü değildir.
• Öte yandan geçişli bağıntıların digraphlarından veya ikili
matrislerinden özellik tanımlamak zordur.
4-20
10
Yansıma
4-21
Yansıma Örnekleri
4-22
11
Ters Yansıma
4-23
Bakışlılık - Simetrik
4-24
12
Bakışsızlık (simetrik değil)
4-25
Ters Bakışlılık (Ters Simetri)
4-26
13
Geçişlilik
4-27
Geçişsizlik
4-28
14
Ters Geçişlilik
4-29
Evrik Bağıntı
4-30
15
Özel Bağıntılar
4-32
Özel Bağıntılar
4-33
16
Özel Bağıntılar
4-34
Özel Bağıntılar
4-35
17
Eşdeğerlilik
4-42
Bölmeleme veya Eşdeğerlik Sınıfları
4-43
18
Fonksiyon
4-44
Birebir Fonksiyon
4-45
19
Örten Fonksiyon
4-46
Bijektif Fonksiyon
4-47
20
Altküme Görüntüsü
4-48
Fonksiyon Bileşkesi
4-49
21
Fonksiyon Bileşkesi Örnekleri
4-50
Fonksiyon Bileşkesi Teoremleri
4-51
22
Fonksiyon Bileşkesi Teoremleri
4-52
Birim Fonksiyon
4-53
23
Evrilebilir (Ters) Fonksiyon
4-54
Fonksiyon Evriği
4-55
24
Evrilebilir (Ters) Fonksiyon
4-56
Evrilebilir Fonksiyon
4-57
25
Permutasyonlar
4-58
Çevrimli Permutasyon
4-59
26
Permutasyon Bileşkesi
4-60
Çevrimli Permutasyon Bileşkesi
4-61
27
Transpozisyon Bileşkesi
4-62
Güvercin Deliği İlkesi
4-63
28
Güvercin Deliği İlkesi
4-64
Genelleştirilmiş Güvercin Deliği İlkesi
4-65
29
Güvercin Deliği İlkesi Örneği
4-66
Güvercin Deliği İlkesi Örneği
4-67
30
Güvercin Deliği İlkesi Örneği
4-68
Güvercin Deliği İlkesi Örneği
Her
xS
için
x  2r p, r  0 ve obeb(2, p)  1.
Buradan p nin tek olduğu ortaya çıkar.
y  T  1,3,5,...,199 ve T  100
S kümesinden 101 tane eleman seçildiğinden güvercin deliği ilkesinden
dolayı p  T
olmak üzere
a  2r p ve b  2s p
gibi iki farklı eleman vardır.
Burada, eğer
r < s ise a|b,
aksi halde r
> s ise b|a dır.
4-69
31
Rekürsif Fonksiyonlar
4-70
Tümevarımla Tanımlanan
Fonksiyon Örnekleri
4-71
32
Öklid Algoritması
4-72
Fibonacci Dizisi
4-73
33
Fibonacci Dizisi
4-74
Ackermann Fonksiyonu
4-75
34
Download

Ders04