TRANSCRIPT
View Logic and Proof.pdf from CENG 172 at İzmir University. Discrete Mathematics (Ayrk Matematik) Do.Dr.Banu DR e-mail.
- 1. Ayrk Matematik Cebirsel YaplarH. Turgut Uyar Ayegl Genata Yayml s ucEmre Harmanc 2001-2012
2. Lisans c 2001-2012 T. Uyar, A. Yayml, E. Harmanc You are free: to Share to copy, distribute and transmit the work to Remix to adapt the work Under the following conditions: Attribution You must attribute the work in the manner specied by the author or licensor (but not in any way that suggests that they endorse you or your use of the work). Noncommercial You may not use this work for commercial purposes. Share Alike If you alter, transform, or build upon this work, you may distribute the resulting work only under the same or similar license to this one. Legal code (the full license): http://creativecommons.org/licenses/by-nc-sa/3.0/ 3. Konular 1 Cebirsel Yaplar Giri s Gruplar Halkalar 2 Kafesler Ksmi Sral Kmeler u Kafesler Boole Cebirleri 4. Konular 1 Cebirsel Yaplar Giri s Gruplar Halkalar 2 Kafesler Ksmi Sral Kmeler u Kafesler Boole Cebirleri 5. Cebirsel Yap cebirsel yap: u s tayc kmesu ilemler: ikili, teklis sabitler: etkisiz, yutucu 6. slemIher ilem bir fonksiyon sikili ilem: s:S S Ttekli ilem: s:S Tkapal: T S 7. slemIher ilem bir fonksiyon sikili ilem: s:S S Ttekli ilem: s:S Tkapal: T S 8. Kapal slem Ornekleri I Ornek c karma ilemi Z kmesinde kapalsu karma ilemi Z+ kmesinde kapal deil cs u g 9. Kapal slem Ornekleri I Ornek c karma ilemi Z kmesinde kapalsu karma ilemi Z+ kmesinde kapal deil cs u g 10. slem OzellikleriIkili I Tanm deime: gs a, b S a b = b a Tanm birleme:s a, b, c S (a b) c = a (b c) 11. slem OrneiIkili I gOrnek:ZZZa b = a + b 3abdeime:gsa b = a + b 3ab = b + a 3ba = b abirleme: s (a b) c =(a + b 3ab) + c 3(a + b 3ab)c =a + b 3ab + c 3ac 3bc + 9abc =a + b + c 3ab 3ac 3bc + 9abc =a + (b + c 3bc) 3a(b + c 3bc) =a (b c) 12. slem OrneiIkili I gOrnek:ZZZa b = a + b 3abdeime:gsa b = a + b 3ab = b + a 3ba = b abirleme: s (a b) c =(a + b 3ab) + c 3(a + b 3ab)c =a + b 3ab + c 3ac 3bc + 9abc =a + b + c 3ab 3ac 3bc + 9abc =a + (b + c 3bc) 3a(b + c 3bc) =a (b c) 13. slem OrneiIkili I gOrnek:ZZZa b = a + b 3abdeime:gsa b = a + b 3ab = b + a 3ba = b abirleme: s (a b) c =(a + b 3ab) + c 3(a + b 3ab)c =a + b 3ab + c 3ac 3bc + 9abc =a + b + c 3ab 3ac 3bc + 9abc =a + (b + c 3bc) 3a(b + c 3bc) =a (b c) 14. slem OrneiIkili I gOrnek:ZZZa b = a + b 3abdeime:gsa b = a + b 3ab = b + a 3ba = b abirleme: s (a b) c =(a + b 3ab) + c 3(a + b 3ab)c =a + b 3ab + c 3ac 3bc + 9abc =a + b + c 3ab 3ac 3bc + 9abc =a + (b + c 3bc) 3a(b + c 3bc) =a (b c) 15. slem OrneiIkili I gOrnek:ZZZa b = a + b 3abdeime:gsa b = a + b 3ab = b + a 3ba = b abirleme: s (a b) c =(a + b 3ab) + c 3(a + b 3ab)c =a + b 3ab + c 3ac 3bc + 9abc =a + b + c 3ab 3ac 3bc + 9abc =a + (b + c 3bc) 3a(b + c 3bc) =a (b c) 16. slem OrneiIkili I gOrnek:ZZZa b = a + b 3abdeime:gsa b = a + b 3ab = b + a 3ba = b abirleme: s (a b) c =(a + b 3ab) + c 3(a + b 3ab)c =a + b 3ab + c 3ac 3bc + 9abc =a + b + c 3ab 3ac 3bc + 9abc =a + (b + c 3bc) 3a(b + c 3bc) =a (b c) 17. slem OrneiIkili I gOrnek:ZZZa b = a + b 3abdeime:gsa b = a + b 3ab = b + a 3ba = b abirleme: s (a b) c =(a + b 3ab) + c 3(a + b 3ab)c =a + b 3ab + c 3ac 3bc + 9abc =a + b + c 3ab 3ac 3bc + 9abc =a + (b + c 3bc) 3a(b + c 3bc) =a (b c) 18. slem OrneiIkili I gOrnek:ZZZa b = a + b 3abdeime:gsa b = a + b 3ab = b + a 3ba = b abirleme: s (a b) c =(a + b 3ab) + c 3(a + b 3ab)c =a + b 3ab + c 3ac 3bc + 9abc =a + b + c 3ab 3ac 3bc + 9abc =a + (b + c 3bc) 3a(b + c 3bc) =a (b c) 19. slem OrneiIkili I gOrnek:ZZZa b = a + b 3abdeime:gsa b = a + b 3ab = b + a 3ba = b abirleme: s (a b) c =(a + b 3ab) + c 3(a + b 3ab)c =a + b 3ab + c 3ac 3bc + 9abc =a + b + c 3ab 3ac 3bc + 9abc =a + (b + c 3bc) 3a(b + c 3bc) =a (b c) 20. Sabitler TanmTanm etkisiz eleman:yutucu eleman: x 1=1x =xx 0=0x =0 soldan etkisiz: 1l x = xsoldan yutucu: 0l x = 0 sadan etkisiz: x 1r = x g sadan yutucu: x 0r = 0 g 21. Sabitler TanmTanm etkisiz eleman:yutucu eleman: x 1=1x =xx 0=0x =0 soldan etkisiz: 1l x = xsoldan yutucu: 0l x = 0 sadan etkisiz: x 1r = x g sadan yutucu: x 0r = 0 g 22. Sabit Ornekleri Ornek < N, max > iin etkisiz eleman 0 c < N, min > iin yutucu eleman 0 c < Z+ , min > iin yutucu eleman 1 c Ornek a b c a a b bb soldan etkisizb ab ca ve b sadan yutucu g c a b a 23. Sabit Ornekleri Ornek < N, max > iin etkisiz eleman 0 c < N, min > iin yutucu eleman 0 c < Z+ , min > iin yutucu eleman 1 c Ornek a b c a a b bb soldan etkisizb ab ca ve b sadan yutucu g c a b a 24. Sabitler TeoremTeorem 1l 1r 1l = 1r 0l 0r 0l = 0r Tant.Tant. 1l 1r = 1l = 1r 0l 0r = 0l = 0r 25. Sabitler TeoremTeorem 1l 1r 1l = 1r 0l 0r 0l = 0r Tant.Tant. 1l 1r = 1l = 1r 0l 0r = 0l = 0r 26. Sabitler TeoremTeorem 1l 1r 1l = 1r 0l 0r 0l = 0r Tant.Tant. 1l 1r = 1l = 1r 0l 0r = 0l = 0r 27. Sabitler TeoremTeorem 1l 1r 1l = 1r 0l 0r 0l = 0r Tant.Tant. 1l 1r = 1l = 1r 0l 0r = 0l = 0r 28. Sabitler TeoremTeorem 1l 1r 1l = 1r 0l 0r 0l = 0r Tant.Tant. 1l 1r = 1l = 1r 0l 0r = 0l = 0r 29. Sabitler TeoremTeorem 1l 1r 1l = 1r 0l 0r 0l = 0r Tant.Tant. 1l 1r = 1l = 1r 0l 0r = 0l = 0r 30. Sabitler TeoremTeorem 1l 1r 1l = 1r 0l 0r 0l = 0r Tant.Tant. 1l 1r = 1l = 1r 0l 0r = 0l = 0r 31. Sabitler TeoremTeorem 1l 1r 1l = 1r 0l 0r 0l = 0r Tant.Tant. 1l 1r = 1l = 1r 0l 0r = 0l = 0r 32. Evrikx y = 1 ise: x eleman y elemannn sol evriig y eleman x elemannn sa evriig gx y = y x = 1 ise x ile y evrik 33. Evrik Teorem ilemi birleme zellii tayorsa:ss o g s w x =x y =1w =y Tant.w =w 1=w (x y )=(w x) y=1y=y 34. Evrik Teorem ilemi birleme zellii tayorsa:ss o g s w x =x y =1w =y Tant.w =w 1=w (x y )=(w x) y=1y=y 35. Evrik Teorem ilemi birleme zellii tayorsa:ss o g s w x =x y =1w =y Tant.w =w 1=w (x y )=(w x) y=1y=y 36. Evrik Teorem ilemi birleme zellii tayorsa:ss o g s w x =x y =1w =y Tant.w =w 1=w (x y )=(w x) y=1y=y 37. Evrik Teorem ilemi birleme zellii tayorsa:ss o g s w x =x y =1w =y Tant.w =w 1=w (x y )=(w x) y=1y=y 38. Evrik Teorem ilemi birleme zellii tayorsa:ss o g s w x =x y =1w =y Tant.w =w 1=w (x y )=(w x) y=1y=y 39. Cebir Ailesi cebir ailesi: cebirsel yap, aksiyomlardeime, birlemegssevrik elemanlar 40. Cebir Ailesi Ornekleri Ornek aksiyomlar: x y =y x (x y ) z = x (y z) x 1=x bu aksiyomlar salayan yaplar:g < Z, +, 0 > < Z, , 1 > < P(S), , > 41. Cebir Ailesi Ornekleri Ornek aksiyomlar: x y =y x (x y ) z = x (y z) x 1=x bu aksiyomlar salayan yaplar:g < Z, +, 0 > < Z, , 1 > < P(S), , > 42. Altcebir Tanm altcebir: A =< S, , , k > A =< S , , , k > olsun A cebrinin A cebrinin bir altcebri olmas iin:c S S a, b S a b = a b S a S a = a S k =k 43. Altcebir Tanm altcebir: A =< S, , , k > A =< S , , , k > olsun A cebrinin A cebrinin bir altcebri olmas iin:c S S a, b S a b = a b S a S a = a S k =k 44. Altcebir Ornekleri Ornek < Z+ , +, 0 > cebri, < Z, +, 0 > cebrinin bir altcebridir. < N, , 0 > cebri, < Z, , 0 > cebrinin bir altcebri deildir.g 45. Altcebir Ornekleri Ornek < Z+ , +, 0 > cebri, < Z, +, 0 > cebrinin bir altcebridir. < N, , 0 > cebri, < Z, , 0 > cebrinin bir altcebri deildir.g 46. Konular 1 Cebirsel Yaplar Giri s Gruplar Halkalar 2 Kafesler Ksmi Sral Kmeler u Kafesler Boole Cebirleri 47. Yargruplar Tanm yargrup: < S, > a, b, c S (a b) c = a (b c) 48. Yargrup Ornekleri Ornek < + , & > : alfabe, + : en az 1 uzunluklu katarlar &: katar bititirme ilemis s 49. Monoidler Tanm monoid: < S, , 1 > a, b, c S (a b) c = a (b c) a S a 1 = 1 a = a 50. Monoid Ornekleri Ornek < , &, > : alfabe, : herhangi uzunluklu katarlar &: katar bititirme ilemis s: bo katars 51. GrupTanmgrup: < S, , 1 > a, b, c S (a b) c = a (b c) a S a 1 = 1 a = a a S a1 S a a1 = a1 a = 1 Abel grubu: a, b S a b = b a 52. GrupTanmgrup: < S, , 1 > a, b, c S (a b) c = a (b c) a S a 1 = 1 a = a a S a1 S a a1 = a1 a = 1 Abel grubu: a, b S a b = b a 53. Grup Ornekleri Ornek< Z, +, 0 > bir gruptur.< Q, , 1 > bir grup deildir. g< Q {0}, , 1 > bir gruptur. 54. Grup Ornekleri Ornek< Z, +, 0 > bir gruptur.< Q, , 1 > bir grup deildir. g< Q {0}, , 1 > bir gruptur. 55. gGrup Ornei: Permutasyon Bilekesi spermutasyon: kme ii bijektif bir fonksiyonucgsterilim: o a1 a2...anp(a1 ) p(a2 ) . . . p(an ) 56. Permutasyon Ornekleri Ornek A = {1, 2, 3}1 2 31 2 3p1 =p2 =1 2 31 3 21 2 31 2 3p3 =p4 =2 1 32 3 11 2 31 2 3p5 =p6 =3 1 23 2 1 57. gGrup Ornei: Permutasyon Bilekesi spermutasyon bilekesi birleme zellii gsterirss o g obirim permutasyon: 1A a1 a2 . . .an a1 a2 . . .anbir kme uzerindeki permutasyonlarn kmesi, u upermutasyon bilekesi ilemissve birim permutasyon bir grup oluturur s 58. gGrup Ornei: Permutasyon Bilekesi spermutasyon bilekesi birleme zellii gsterirss o g obirim permutasyon: 1A a1 a2 . . .an a1 a2 . . .anbir kme uzerindeki permutasyonlarn kmesi, u upermutasyon bilekesi ilemissve birim permutasyon bir grup oluturur s 59. gGrup Ornei: Permutasyon Bilekesi s Ornek ({1, 2, 3, 4} kmesindekiupermutasyonlar)A 1A p1 p2 p3 p4 p5 p6 p7 p8 p9 p10 p111 1 111 1 1 22 2 2 2 22 2 233 4 4 11 3 3 4 43 3 424 2 3 34 1 4 1 34 4 342 3 2 43 4 1 3 1p12 p13 p14 p15 p16 p17 p18 p19 p20 p21 p22 p2313 3 3 3 3 3 4 4 4 4 4 421 1 2 2 4 4 1 1 2 2 3 332 4 1 4 1 2 2 3 1 3 1 244 2 4 1 2 1 3 2 3 1 2 1 60. gGrup Ornei: Permutasyon Bilekesi s Ornekp8 p12 = p12 p8 = 1A : 11p12 = p8 , p8 = p12p14 p14 = 1A : 1p14 = p14G1 =< {1A , p1 , . . . , p23 }, , 1A > bir gruptur 61. gGrup Ornei: Permutasyon Bilekesi s Ornekp8 p12 = p12 p8 = 1A : 11p12 = p8 , p8 = p12p14 p14 = 1A : 1p14 = p14G1 =< {1A , p1 , . . . , p23 }, , 1A > bir gruptur 62. gGrup Ornei: Permutasyon Bilekesi s Ornek 1A p2 p6 p8 p12 p141A 1A p2 p6 p8 p12 p14p2 p2 1A p8 p6 p14 p12p6 p6 p12 1A p14 p2 p8p8 p8 p14 p2 p12 1A p6p12p12 p6 p14 1A p8 p2p14p14 p8 p12 p2 p6 1A< {1A , p2 , p6 , p8 , p12 , p14 }, , 1A > G1 in bir altgrubudur 63. Sadan ve Soldan Kaldrmag Teorem ac =bc a=b c a=c b a=b Tant. ac= bc (a c) c 1= (b c) c 1 a (c c 1 ) = b (c c 1 )a1= b1a= b 64. Sadan ve Soldan Kaldrmag Teorem ac =bc a=b c a=c b a=b Tant. ac= bc (a c) c 1= (b c) c 1 a (c c 1 ) = b (c c 1 )a1= b1a= b 65. Sadan ve Soldan Kaldrmag Teorem ac =bc a=b c a=c b a=b Tant. ac= bc (a c) c 1= (b c) c 1 a (c c 1 ) = b (c c 1 )a1= b1a= b 66. Sadan ve Soldan Kaldrmag Teorem ac =bc a=b c a=c b a=b Tant. ac= bc (a c) c 1= (b c) c 1 a (c c 1 ) = b (c c 1 )a1= b1a= b 67. Sadan ve Soldan Kaldrmag Teorem ac =bc a=b c a=c b a=b Tant. ac= bc (a c) c 1= (b c) c 1 a (c c 1 ) = b (c c 1 )a1= b1a= b 68. Sadan ve Soldan Kaldrmag Teorem ac =bc a=b c a=c b a=b Tant. ac= bc (a c) c 1= (b c) c 1 a (c c 1 ) = b (c c 1 )a1= b1a= b 69. Gruplarn Temel Teoremi Teorem a x = b denkleminin tek ozm: x = a1 b. c u u Tant.ac = b a1 (a c) = a1 b 1c = a1 b c = a1 b 70. Gruplarn Temel Teoremi Teorem a x = b denkleminin tek ozm: x = a1 b. c u u Tant.ac = b a1 (a c) = a1 b 1c = a1 b c = a1 b 71. Gruplarn Temel Teoremi Teorem a x = b denkleminin tek ozm: x = a1 b. c u u Tant.ac = b a1 (a c) = a1 b 1c = a1 b c = a1 b 72. Gruplarn Temel Teoremi Teorem a x = b denkleminin tek ozm: x = a1 b. c u u Tant.ac = b a1 (a c) = a1 b 1c = a1 b c = a1 b 73. Gruplarn Temel Teoremi Teorem a x = b denkleminin tek ozm: x = a1 b. c u u Tant.ac = b a1 (a c) = a1 b 1c = a1 b c = a1 b 74. Konular 1 Cebirsel Yaplar Giri s Gruplar Halkalar 2 Kafesler Ksmi Sral Kmeler u Kafesler Boole Cebirleri 75. Halka Tanm halka: < S, +, , 0 >a, b, c S (a + b) + c = a + (b + c)a S a + 0 = 0 + a = aa S (a) S a + (a) = (a) + a = 0a, b S a + b = b + aa, b, c S (a b) c = a (b c)a, b, c S a (b + c) = a b + a c (b + c) a = b a + c a 76. Halka Tanm halka: < S, +, , 0 >a, b, c S (a + b) + c = a + (b + c)a S a + 0 = 0 + a = aa S (a) S a + (a) = (a) + a = 0a, b S a + b = b + aa, b, c S (a b) c = a (b c)a, b, c S a (b + c) = a b + a c (b + c) a = b a + c a 77. Halka Tanm halka: < S, +, , 0 >a, b, c S (a + b) + c = a + (b + c)a S a + 0 = 0 + a = aa S (a) S a + (a) = (a) + a = 0a, b S a + b = b + aa, b, c S (a b) c = a (b c)a, b, c S a (b + c) = a b + a c (b + c) a = b a + c a 78. AlanTanmalan: < S, +, , 0, 1 > btn halka zellikleriuuo a, b S a b = b a a S a 1 = 1 a = a a S a1 S a a1 = a1 a = 1 79. AlanTanmalan: < S, +, , 0, 1 > btn halka zellikleriuuo a, b S a b = b a a S a 1 = 1 a = a a S a1 S a a1 = a1 a = 1 80. Kaynaklar Grimaldi Chapter 5: Relations and Functions5.4. Special Functions Chapter 16: Groups, Coding Theory, and Polyas Method of Enumeration16.1. Denitions, Examples, and Elementary Properties Chapter 14: Rings and Modular Arithmetic14.1. The Ring Structure: Denition and Examples 81. Konular 1 Cebirsel Yaplar Giri s Gruplar Halkalar 2 Kafesler Ksmi Sral Kmeler u Kafesler Boole Cebirleri 82. Ksmi Sral Kmeu Tanm ksmi sra bants:gyansmalters bakl sgeilicsksmi sral kme (poset):uelemanlar uzerinde ksmi sra bants tanmlanm kmeg s u 83. Ksmi Sral Kmeu Tanm ksmi sra bants:gyansmalters bakl sgeilicsksmi sral kme (poset):uelemanlar uzerinde ksmi sra bants tanmlanm kmeg s u 84. Ksmi Sra Ornekleri Ornek (kmeler kmesi, ) u u AA AB B AA=B AB B C AC 85. Ksmi Sra Ornekleri Ornek (Z, ) x x x y y x x =y x y y z x z 86. Ksmi Sra Ornekleri Ornek (Z+ , |) x|x x|y y |x x = y x|y y |z x|z 87. Karlatrlabilirlik s sa b: a bnin nndedir o ua bb a: a ile b karlatrlabilirs scizgisel sra:her eleman ifti karlatrlabiliyorc s s 88. Karlatrlabilirlik s sa b: a bnin nndedir o ua bb a: a ile b karlatrlabilirs scizgisel sra:her eleman ifti karlatrlabiliyorc s s 89. Karlatrlabilirlik Ornekleri s s OrnekZ+ , |: 3 ile 5 karlatrlamaz s sZ, : izgisel srac 90. Karlatrlabilirlik Ornekleri s s OrnekZ+ , |: 3 ile 5 karlatrlamaz s sZ, : izgisel srac 91. Hasse Cizenekleri a b: a bnin hemen nndediro u x a x b Hasse izenei: c g a b ise a ile b arasna izgi c o nde olan eleman aaya s g 92. Hasse Cizenekleri a b: a bnin hemen nndediro u x a x b Hasse izenei: c g a b ise a ile b arasna izgi c o nde olan eleman aaya s g 93. g Hasse Cizenei Ornekleri Ornek {1, 2, 3, 4, 6, 8, 9, 12, 18, 24} | bants g 94. Tutarl Saylama tutarl saylama: f :S N a b f (a) f (b) birden fazla tutarl saylama olabilir 95. Tutarl Saylama Ornekleri Ornek {a 5, b 3, c 4, d 1, e 2} {a 5, b 4, c 3, d 2, e 1} 96. Tutarl Saylama Ornekleri Ornek {a 5, b 3, c 4, d 1, e 2} {a 5, b 4, c 3, d 2, e 1} 97. En Byk - En Kuk Elemanu uucTanmen byk eleman: maxu ux S max x x = maxTanmen kuk eleman: minucx S x min x = min 98. En Byk - En Kuk Elemanu uucTanmen byk...