Genel Boole Cebri Sayısal Devreler (Lojik Devreleri) 2.1 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info Boole Cebri B={0,1} kümesi üzerinde tanımlı İkili işlemler: VEYA, VE { + , • } Birli işlem: Tümleme { ' } Aksiyomlar: a , b ¸ B olmak üzere 1.Kapalılık (Closure): a + b ¸ B a • b ¸ B 2.Değişme (Commutative): a + b = b + a a • b = b • a 3.Birleşme (Associative): a + (b + c) = (a + b) + c a • (b • c) = (a • b) • c 4.Etkisiz eleman (Identity) : a + 0 = a a • 1 = a 5.Dağılma (Distributive): a + (b • c) = (a + b) • (a + c) a • (b + c) = (a • b) + (a • c) 6.Tümleme (Inverse): a + a' = 1 a • a' = 0 a • b a + b 0 1 1 0 a' a Tümleme 1 0 b 1 0 1 0 0 0 a George Boole (1815-1864) İngiliz Matematikçi Ders Notlarının Creative Commons lisansı Feza BUZLUCA’ya aittir. Lisans: http://creativecommons.org/licenses/by-nc-nd/3.0/ 1 0 b 1 1 1 1 0 0 a Sayısal Devreler (Lojik Devreleri) 2.2 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info 1. Yutma: a + 1 = 1 a • 0 = 0 2. Dönüşme (Involution): (a')' = a 3. Sabit kuvvet (Idempotency): a+a+a+….+a = a a•a•a •… •a = a 4. Soğurma (Absorption): a + a b = a a (a+b) = a 5. De Morgan Teoremi: Augustus De Morgan (1806 – 1871) (a + b)' = a' • b’ (a • b)' = a' + b' 5. Genel De Morgan Teoremi: f '(X1,X2,...,Xn,0,1,+,•) = f(X1',X2',...,Xn',1,0,•,+) İkili işlemler (VE, VEYA) arasında ilişki sağlar: • ve + arasında Özellikler ve Teoremler: Burada gösterilen tüm özellikler ve teoremler Boole cebrinin tanımında yer alan işlemler ve aksiyomlar ile kanıtlanabilirler. (Kanıt 2.4’te)Sayısal Devreler (Lojik Devreleri) 2.3 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info 6. Düalite (Duality principle) Bir lojik ifadenin düali, • yerine +, + yerine •, 0 yerine 1, 1 yerine 0, koyarak ve değişkenler değiştirilmeden elde edilir. a + b + ... a • b • ... Kanıtlanan her teorem düali için de geçerlidir. Örnek: Soğurma (Absorption): a + a b = a kanıtlanırsa düali de doğrudur. a (a+b) = a Önceki yansılarda yer alan aksiyom ve teoremlerde düal ifadeler yan yana yazılmıştır. Genelleştirilmiş düalite: f (X1,X2,...,Xn,0,1,+,•) f(X1,X2,...,Xn,1,0,•,+) De Morgan Teoreminden farklıdır. Teoremlerin kanıtları arasında ilişki sağlar. Lojik ifadelerin dönüştürülmesini sağlayan bir yöntem değildir. Sayısal Devreler (Lojik Devreleri) 2.4 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info Teoremlerin Kanıtlanması: a) Aksiyomlar ile Örnek: Teorem: X • Y + X • Y' = X Kanıt: Dağılma X • Y + X • Y' = X • (Y + Y') Tümleme = X • (1) Etkisiz = X Örnek: Teorem: X + X • Y = X Soğurma (Absorption) Kanıt: Etkisiz X + X • Y = X • 1 + X • Y Dağılma = X • (1 + Y) Yutma = X • (1) Etkisiz = X İşlemler Arası Öncelik: Bir lojik ifade değerlendirilirken işlemler arasındaki öncelik yüksekten öncelikten başlayarak şöyledir: 1. Parantez, 2. Tümleme, 3. VE, 4. VEYASayısal Devreler (Lojik Devreleri) 2.5 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info (X + Y)' = X' • Y' (X • Y)' = X' + Y' X Y X' Y' (X + Y)' X' • Y' 0 0 1 1 0 1 1 0 1 0 0 1 1 1 0 0 X Y X' Y' (X • Y)' X' + Y' 0 0 1 1 0 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 Teoremlerin Kanıtlanması: b) Doğruluk Tablosu De Morgan: Doğruluk tablolarında çok sayıda satır olsa da bunları bir bilgisayar programı yardımıyla kısa sürede sınamak mümkün olabilir. Sayısal Devreler (Lojik Devreleri) 2.6 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info Teoremler lojik ifadelerin sadeleştirilmesinde de kullanılır. Örnek: Z = A' B C + A B' C + A B C' + A B C = A' B C + A B' C + A B C' + A B C + A B C = A' B C + A B C + A B' C + A B C' + A B C = (A' + A) B C + A B' C + A B C' + A B C = (1) B C + A B' C + A B C' + A B C = B C + A B' C + A B C' + A B C + A B C = B C + A B' C + A B C + A B C' + A B C = B C + A (B' + B) C + A B C' + A B C = B C + A (1) C + A B C' + A B C = B C + A C + A B (C' + C) = B C + A C + A B (1) = B C + A C + A B Sayısal Devreler (Lojik Devreleri) 2.7 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info Lojik İfadeler (Expressions) Lojik ifade, değişkenlerin, sabitlerin ve işlemlerin kurallara uygun şekilde yazılmış sonlu kombinezonudur. X= (x 1 , x 2 , .... x n ), Her x i ¸ {0,1} olmak üzere E(X) şeklinde gösterilir. E 1 ve E 2 lojik ifade ise, E 1 ', E 2 ', E 1 + E 2 , E 1 • E 2 gibi tüm kombinezonlar da birer lojik ifadedir. Lojik İfadelerin Yapıları: Monoform ifadelerde değişkenlerin sadece kendileri ya da sadece tümleyenleri bulunur. Biform ifadeler belli bir x değişkenine göre tanımlanırlar. x'e göre biform bir ifadede hem x hem de tümleyeni bulunur. Çarpım ifadeleri, değişkenlerin sadece lojik çarpımlarından oluşurlar. Örnek: ab'cd Çarpım (product) yerine monom sözcüğü de kullanılır. Toplam ifadeleri, değişkenlerin sadece lojik toplamlarından oluşurlar. Örnek: a'+b'+c+d Toplam (sum) yerine monal sözcüğü de kullanılır. Çarpım böleni, bir çarpımdan bir ya da daha fazla değişken kaldırıldığında elde edilen çarpım ifadesidir. Örnek: ab'cd nin bazı bölenleri: a, b', c, d, ab', b'c, acd, b'd Lisans: http://creativecommons.org/licenses/by-nc-nd/3.0/ Sayısal Devreler (Lojik Devreleri) 2.8 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info İfadelerin yazılma şekilleri: • SPSP SP SP : Lojik çarpımların lojik toplamı ya da “VE”lerin “VEYA”lanması Örnek: bc'+ad+a'b • PSPS PS PS : Lojik toplamların lojik çarpımı ya da “VEYA”ların “VE"lenmesi Örnek: (a+b+c')(a+d)(a'+b) Bir lojik ifadenin değeri: E(X) ifadesi X=(x 1 , .... x n ) giriş vektörünün her değeri için B={0,1} kümesinden bir çıkış değeri üretir. Bu değerler ifadenin doğruluk tablosunu oluşturur. Örnek: E(X) = x 1 x 2 + x 3 ifadesinin doğruluk tablosu Tüm giriş kombinezonları (X) uzayı 000 010 001 011 101 111 110 100 E(X)’nin ‘1’ değeri ürettiği (örttüğü) kombinezonlar x 1 x 2 x 3 E(X) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1Sayısal Devreler (Lojik Devreleri) 2.9 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info Lojik ifadelerin bazı özelliklerini ortaya koymak için aşağıda tanımlanan sıra bağıntısı da kullanılır. B={0,1} kümesinin elemanları arasında şu sıra bağıntısı tanımlanır: 0 < 1 0, 1'den "önce gelir" ya da "küçüktür" diye okunur. Buna göre X vektörleri arasında da bir sıra bağıntısı tanımlanabilir. Eğer X1 vektörünün tüm elemanları X2 vektörünün aynı sıradaki elemanlarından yukarıda tanımlandığı anlamda "küçük"se (önce geliyorsa) ya da eşitse X1 £ X2 sıralaması geçerlidir. Örnek: X1=1001 , X2 = 1101 ise X1 £ X2 dir. İki vektör arasında sıra bağıntısı olmayabilir. Örneğin, X1=0011 , X2 = 1001 ise X1 ile X2 arasında sıra bağıntısı yoktur. Sıra bağıntısı: Sayısal Devreler (Lojik Devreleri) 2.10 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info E 2 E 1 E 1 (X) £ E 2 (X) yazılışı, X'in tüm kombinezonları için E 1 'in alacağı değerlerin E 2 'nin alacağı değerlere eşit ya da küçük olduğunu belirtir. x 1 x 2 x 3 E 1 (X) E 2 (X) 0 0 0 0 = 0 0 0 1 1 = 1 0 1 0 0 < 1 0 1 1 1 = 1 1 0 0 0 = 0 1 0 1 1 = 1 1 1 0 0 < 1 1 1 1 1 = 1 E 1 (X) £ E 2 (X) ise E 1 (X), E 2 (X)‘yi gerektirir, E 1 (X)?E 2 (X), E 2 (X), E 1 (X)‘i örter. Örnek : E 1 (X)’in 1 değerini aldığı her giriş kombinezonu için E 2 (X) de 1 değerini alır. (Bu özel bir durumdur.) Tüm giriş kombinezonları (X) uzayı E 2 (X)’nin ‘1’ değeri ürettiği (örttüğü) kombinezonlar E 1 (X)’nin ‘1’ de- ğeri ürettiği (örttüğü) kombinezonlar İfadeler üzerinde sıra bağıntısı: 000 100 001 011 101 111 010 110 E 1 (X) £ E 2 (X) ise: 1. E 1 (X) + E 2 (X) = E 2 (X) 2. E 1 (X) • E 2 (X) = E 1 (X)Sayısal Devreler (Lojik Devreleri) 2.11 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info F E E ve F lojik ifadeler olmak üzere, aşağıdaki eşitsizlikleri her zaman geçerlidir: E F £ E £ E+F ve E F £ F £ E+F E+E F = E Yutma özellikleri: Kanıt: E(E+F) = EE+EF = E+EF = E(1+F) = E E(E+F) = E ve düali E+E' F = E+F Kanıt: E+E'F = (E+E')(E+F) = 1(E+F) = E+F E(E'+F) = E F ve düali İki ifade arasında her zaman sıra bağıntısı (£ ) geçerli olmaz. Bu özellikler lojik ifadelerin sadeleştirilmesinde kullanılır. Sayısal Devreler (Lojik Devreleri) 2.12 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info Konsensüs: •Çarpımların toplamı şeklinde yazılmış olan xE 1 + x'E 2 biform karesinde E 1 E 2 çarpımına konsensüs adı verilir. Örnek: abc + a'cd ifadesinin a ya göre konsensüsü: bccd = bcd •Toplamların çarpımı şeklinde yazılmış olan (x+E 1 )(x'+E 2 ) biform karesinde E 1 +E 2 toplamı konsensüstür. Örnek: (a+b+c) (a'+c+d) ifadesinin a ya göre konsensüsü: b+c+c+d = b+c+d Teorem: Biform kareler konsensüslerini yutarlar. xE 1 + x'E 2 + E 1 E 2 = xE 1 + x'E 2 (x+E 1 )(x'+E 2 )(E 1 +E 2 ) = (x+E 1 )(x'+E 2 ) E 1 ve E 2 içinde x 1 olmayan iki ifade olsun: E 1 (x 2 , .... x n ) ve E 2 (x 2 , .... x m ) E=x 1 E 1 +x 1 'E 2 ve düali E D = (x 1 +E 1 D )(x 1 '+E 2 D ) ifadeleri x 1 in biform kareleridir. Örnek: x 1 (x 2 +x 3 ')+x 1 '(x 3 +x 4 ) , x 1 x 2 x 3 +x 1 ’x 4 x 5 , (x 1 +x 2 +x 3 ')(x 1 '+x 3 +x 4 ) ve (x 1 +x 2 x 3 ')(x 1 '+x 3 x 4 ) x 1 'in biform karelerine dair örneklerdir. Biform kareler:Sayısal Devreler (Lojik Devreleri) 2.13 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info F(A, B, C) = A'B'C + A'BC + AB'C + ABC + ABC' C ye göre konsensüs eklendi = A'B'C + A'BC + AB'C + ABC + ABC' + AB = A'B'C + A'BC + AB'C + ABC + ABC' + AB Soğurma, yutma (Absorption) = A'B'C + A'BC + AB'C + AB B ye göre konsensüs eklendi = A'B'C + A'BC + A'C + AB'C + AB = A'B'C + A'BC + A'C + AB'C + AB Soğurma, yutma (Absorption) = A'C + AB'C + AB B ye göre konsensüs eklendi = A'C + AB'C + AB + AC Soğurma (Absorption) = A'C + AB + AC A ya göre konsensüs eklendi = A'C + AB + AC + C Soğurma (Absorption) = AB + C Örnek: Konsensüs teoremi ile lojik ifadelerin indirgenmesi Lisans: http://creativecommons.org/licenses/by-nc-nd/3.0/ Teorem: Biform kareler arasında dönüşme özelliği vardır. xE 1 + x'E 2 = (x+E 2 )(x'+E 1 ) Tüm lojik ifadeler her iki şekilde de yazılabilir. SPSP SP SP « « « « PS PS PS PS Sayısal Devreler (Lojik Devreleri) 2.14 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info Lojik fonksiyonlar B n kümesi (n elemanlı 2'li kodların kümesi) üzerinde tanımlanırlar ve üçe ayrılırlar: 1. Yalın fonksiyonlar: Çok girişli bir çıkışlı " X 0 ¸ B n ; $ ! y 0 ¸ B ; y=f(X) B n kümesinden değer alan X 0 kombinezonuna f fonksiyonu uygulandığında B kümesinden değer alan bir y 0 değeri elde edilir ve bu değer tektir. Lojik Fonksiyonlar f x 1 x 2 x 3 y x 1 x 2 x 3 y 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 Örnek:Sayısal Devreler (Lojik Devreleri) 2.15 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info n girişli 2 ( 2 n ) adet yalın lojik fonksiyon vardır. İki girişli 16 adet yalın lojik fonksiyon vardır: f x y z Yalın Lojik Fonksiyonlar (devam): 2 girişli 16 adet yalın lojik fonksiyon (F0–F15) X Y F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 X VE Y X Y X VEYA Y Y' X' 1 X YA DA Y X TVEYA Y (X VEYA Y)' X = Y X TVE Y (X VE Y)' Girişler Fonksiyonlar Sayısal Devreler (Lojik Devreleri) 2.16 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info 2. Genel fonksiyonlar: Çok girişli, çok çıkışlı f x 1 x 2 x 3 y 1 y 2 0 0 0 1 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 0 x 1 x 2 x 3 y 1 y 2 Örnek: Y = f(X): B n ? B m , X=(x 1 , .... x n ), Y=(y 1 , .... y m ), Sayısal Devreler (Lojik Devreleri) 2.17 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info Bu girişler için devrenin (fonksiyonun) çıkışlarının alacağı değer belirsizdir. Belirsiz değerleri göstermek için X yerine F sembolü de kullanılır. 3. Tümüyle tanımlanmamış fonksiyonlar: Bazı giriş kombinezonları için fonksiyonun alacağı değer belirsizdir. Bu giriş değeri ya fiziksel olarak oluşamaz ya da bu giriş geldiğinde devrenin çıkışının alacağı değer önemli değildir. I8 I4 I2 I1 O8 O4 O2 O1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 X X X X 1 0 1 1 X X X X 1 1 0 0 X X X X 1 1 0 1 X X X X 1 1 1 0 X X X X 1 1 1 1 X X X X O1 O2 O4 O8 I1 I2 I4 I8 Örnek: BCD sayıları 1 arttıran fonksiyon: Sayısal Devreler (Lojik Devreleri) 2.18 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info Aynı lojik fonksiyon farklı yöntemler ile gösterilebilir. Bu fonksiyona ilişkin devre tasarlanırken bu gösterilimlerden uygun olanı kullanılır. Doğruluk Tablosu İle Gösterilim Tüm giriş kombinezonları için çıkışın (veya çıkışların) alacağı değerler tablo halinde yazılır. Sayısal Gösterilim Giriş kombinezonları 2'li sayılarla kodlandığına göre her kombinezona 10 tabanında bir numara verilir. Fonksiyon hangi giriş kombinezonları için lojik "1" değeri (ya da lojik "0“, ”F ”) üretiyorsa o kombinezonların numaraları listelenir. Lojik Fonksiyonların Gösterilişi Lisans: http://creativecommons.org/licenses/by-nc-nd/3.0/ Sayısal Devreler (Lojik Devreleri) 2.19 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info Örnek: Tümüyle tanımlanmış, yalın bir fonksiyonun gösterilimi: Giriş Çıkış No x 1 x 2 y 0 0 0 1 1 0 1 0 2 1 0 1 3 1 1 0 y = f(x 1 ,x 2 )= ¨¨ ¨ ¨ 1 (0,2) Aynı fonksiyon lojik “0” üreten kombinezonlar ile de gösterilebilir. y = f(x 1 ,x 2 ) = ¨¨ ¨ ¨ 0 (1,3) Örnek: Tümüyle tanımlanmış, genel bir fonksiyonun gösterilimi: Her çıkış için yukarıdaki gösterilim uygulanır. No x 1 x 2 y 1 y 2 0 0 0 1 1 1 0 1 0 1 2 1 0 1 0 3 1 1 0 0 Aynı fonksiyon lojik 0 üreten kombinezonlar ile de gösterilebilir. y 1 =f(x 1 ,x 2 )= ¨¨ ¨ ¨ 1 (0,2) y 2 =f(x 1 ,x 2 )= ¨¨ ¨ ¨ 1 (0,1) y 2 =f(x 1 ,x 2 )= ¨¨ ¨ ¨ 0 (2,3) y 1 =f(x 1 ,x 2 )= ¨¨ ¨ ¨ 0 (1,3) y = f(x 2 ,x 1 )= ¨¨ ¨ ¨ 1 (0,1) Değişkenlerin sırası önemlidir. Doğruluk tablosundaki sıraya dikkat edilmelidir. Aksi durumda kombinezon numaraları değişecektir. ¨¨ ¨ ¨ : Birleşme (union) veya "kümesidir" Sayısal Devreler (Lojik Devreleri) 2.20 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info Örnek: Tümüyle tanımlanmamış, genel bir fonksiyonun gösterilimi: Bu durumda sadece lojik "1" veya lojik "0" üreten çıkışları göstermek yeterli değildir. No x 1 x 2 y 1 y 2 0 0 0 1 1 1 0 1 0 F 2 1 0 F 0 3 1 1 0 F y 1 = f(x 1 ,x 2 ) = ¨¨ ¨ ¨ 1 (0) + ¨¨ ¨ ¨ 0 (1,3) veya y 1 = f(x 1 ,x 2 ) = ¨¨ ¨ ¨ 1 (0) + ¨¨ ¨ ¨ F (2) veya y 1 = f(x 1 ,x 2 ) = ¨¨ ¨ ¨ 0 (1,3) + ¨¨ ¨ ¨ F (2) y 2 = f(x 1 ,x 2 ) = ¨¨ ¨ ¨ 1 (0) + ¨¨ ¨ ¨ 0 (2) veya y 2 = f(x 1 ,x 2 ) = ¨¨ ¨ ¨ 1 (0) + ¨¨ ¨ ¨ F (1,3) veya y 2 = f(x 1 ,x 2 ) = ¨¨ ¨ ¨ 0 (2) + ¨¨ ¨ ¨ F (1,3) Sayısal Devreler (Lojik Devreleri) 2.21 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info Girişi kombinezonları B n kümesinin elemanları olduklarına göre n boyutlu uzaydaki bir (çok boyutlu) hiperküpün köşelerini oluştururlar. Fonksiyonun doğru noktalarını (lojik 1) üreten kombinezonlar küp üzerinde işaretlenir. Fonksiyonun giriş sayısı küpün boyutunu belirler. n giriş ? n boyutlu küp Boole Küpleri: 1-boyutlu X 0 1 2-boyutlu X Y 11 00 01 10 3-boyutlu X Y Z 000 111 101 4-boyutlu W X Y Z 0000 1111 1000 0111 Grafik Gösterilim Sayısal Devreler (Lojik Devreleri) 2.22 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info A B F 0 0 1 0 1 0 1 0 1 1 1 0 A B 11 00 01 10 Örnek: Örnek: A B C F 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 A B C 000 111 101 Giriş sayısı arttıkça çizimin zorlaşması nedeniyle, Boole küpleri lojik fonksiyonların gösterilmesi için pratikte kullanılan bir yöntem değildir. Grafik gösterilim lojik fonksiyonların anlaşılması ve bundan sonraki konuların anlatılması açısından yararlıdır.Sayısal Devreler (Lojik Devreleri) 2.23 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info Karnaugh Diyagramları (Karnaugh Map) Maurice Karnaugh (1924-), ABD, fizikçi Boole küplerinin düzlem üzerindeki iz düşümleri olarak düşünülebilir. No A B F 0 0 0 1 1 0 1 0 2 1 0 1 3 1 1 0 A B 11 00 01 10 0 1 2 3 0 1 B A 0 1 1 1 0 0 F 0 2 1 3 0 1 A B 0 1 1 0 0 1 F veya Tabloların gözleri Gray koduna göre düzenlenir. Yan yana (ve alt alta) gözlere ait kombinezonların bitişik olması sağlanır. Üç girişli bir fonksiyon için Karanaugh diyagramının biçimi: B C 000 111 101 100 001 010 011 110 0 1 4 5 00 01 BC A 0 1 3 2 7 6 11 10 F 000 001 100 101 011 010 111 110 BC A F Gray Kodu Sayısal Devreler (Lojik Devreleri) 2.24 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info 0 1 4 5 00 01 BC A 0 1 3 2 7 6 11 10 0 0 1 0 0 1 1 1 F 0 1 4 5 3 2 7 6 12 13 8 9 15 14 11 10 CD AB 00 01 11 10 00 01 11 10 F A B C 000 111 101 011 Örnek: 3 girişli bir fonksiyonun Karnaugh diyagramı: No A B C F 0 0 0 0 0 1 0 0 1 0 2 0 1 0 0 3 0 1 1 1 4 1 0 0 0 5 1 0 1 1 6 1 1 0 1 7 1 1 1 1 4 girişli bir fonksiyona ilişkin Karnaugh diyagramının biçimi: Karnaugh diyagramları dersin ilerleyen bölümlerinde fonksiyonların indirgenmesinde kullanılacaktır. Lisans: http://creativecommons.org/licenses/by-nc-nd/3.0/ Gray Kodu Gray KoduSayısal Devreler (Lojik Devreleri) 2.25 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info Cebirse Gösterilim (İfadeler) ve Kanonik Açılımlar Gerçek dünyadaki bir problemin çözümü doğruluk tablosu ile ifade edilebilir. Örneğin; giriş değişkeni A bir aracın kapısının açık olduğunu, B anahtarın yuvaya takılı olduğunu ifade ederse, alarmın çalıp çalmadığı gösteren (Z=1 ise alarm çalıyor) doğruluk tablosu aşağıdaki gibi oluşturulabilir. Lojik fonksiyonların ifadeleri doğruluk tablolarından kanonik açılımlar ile elde edilir. İki tür kanonik açılım vardır: • 1. kanonik açılım : Çarpımların toplamı (SPSP SP SP ) "1" çıkışı üreten giriş kombinezonlarının çarpımlarının toplamından oluşur. • 2. kanonik açılım : Toplamların çarpımı (PP P PS S S S ) "0" çıkışı üreten giriş kombinezonlarının toplamlarının çarpımından oluşur. . Num. A B Z 0 0 0 0 1 0 1 0 2 1 0 0 3 1 1 1 Ancak gerçek dünyadaki problemler çok daha fazla girişe sahip olduklarından doğruluk tabloları da daha karmaşıktır. Bu problemlerin çözümlerini basitleştirmek ve ilgili devreleri lojik kaplılar ile gerçeklemek için fonksiyonların cebirsel ifadelerini bulmak gerekir. Sayısal Devreler (Lojik Devreleri) 2.26 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info • 1. kanonik açılım, fonksiyonun "doğru" (1 çıkışı üreten) noktalarına ilişkin çarpımların toplamından oluşur • n Değişkenli bir fonksiyonda n değişkenin hepsini sadece bir defa (ya kendisi ya da tümleyeni şeklinde) içeren çarpım ifadelerine minterim denir. • Örneğin 3 değişkenli (a, b, c) bir fonksiyonun 8 adet minterimi vardır: a'b'c', a'b'c, a'bc', a'bc, ab'c', ab'c, abc', abc • Her minterim doğruluk tablosunda sadece bir "doğru" satırı örter. • Fonksiyonun 1. kanonik açılımı minterimlerin toplamından oluşur. • Minterimlerin oluşturulması, • Doğruluk tablosunda çıkışın "1" olduğu satırlar seçilir. • Bu satırlarda girişlerin 1 olduğu yerlere değişkenlerin kendileri (örneğin A, B, C) ve sıfır olduğu yerlere tümleyenleri (A', B', or C') yazılarak çarpımlar oluşturulur. • Bir lojik fonksiyonun birden fazla cebirsel ifadesi vardır. • Ancak bir fonksiyonun 1nci kanonik açılımı tektir. 1. Kanonik Açılım: Çarpımların toplamıSayısal Devreler (Lojik Devreleri) 2.27 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info A B C F 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 Minterimlerin Toplamı: F = F' = A'B'C' + A'BC' + AB'C' "Doğru" değer üreten kombinezonlar: F = 001 011 101 110 111 + A'BC + AB'C + ABC' + ABC A'B'C Fonksiyonun tümleyeni de benzer şekilde "yanlış" noktalardan hareket edilerek yazılır: Örnek: F‘ 1 0 1 0 1 0 0 0 Sayısal Devreler (Lojik Devreleri) 2.28 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info A B C minterimler 0 0 0 A'B'C' m0 0 0 1 A'B'C m1 0 1 0 A'BC' m2 0 1 1 A'BC m3 1 0 0 AB'C' m4 1 0 1 AB'C m5 1 1 0 ABC' m6 1 1 1 ABC m7 Minterimlerin numaralanması: Minterimler giriş kombinezonlarının sıraları dikkate alınarak numaralandırılırlar. 3 değişkenli minterimlerin simgesel gösterilimi Kanonik açılımın basitleştirilmesi F(A, B, C) = A'B'C + A'BC + AB'C + ABC + ABC' = (A'B' + A'B + AB' + AB)C + ABC' = ((A' + A)(B' + B))C + ABC' = C + ABC' = ABC' + C = AB + C Kanonik açılım fonksiyonun en basit cebirsel ifadesi değildir. Çoğunlukla kanonik açılımlar yalınlaştırılabilir (basitleştirilebilir). Yansı 2.27’deki Örnek F nin Kanonik açılımı: F(A, B, C) = S m(1,3,5,6,7) = m1 + m3 + m5 + m6 + m7 = A'B'C + A'BC + AB'C + ABC' + ABC F = S A, B, C (1,3,5,6,7) şeklinde de yazılabilir.Sayısal Devreler (Lojik Devreleri) 2.29 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info 2. Kanonik Açılım: Toplamların Çarpımı • 2. kanonik açılım, fonksiyonun "yanlış" (0 çıkışı üreten) noktalarına ilişkin toplamların çarpımlarından oluşur • n Değişkenli bir fonksiyonda n değişkenin hepsini sadece bir defa (ya kendisi ya da tümleyeni şeklinde) içeren toplam ifadelerine maksterim denir. • Örneğin 3 değişkenli (a, b, c) bir fonksiyonun 8 adet maksterimi vardır: a+b+c, a+b+c', a+b'+c, a+b'+c', a'+b+c, a'+b+c', a'+b'+c, a'+b'+c' • Her maksterim doğruluk tablosundaki sade bir giriş kombinezonu için 0 değerini alır. • Fonksiyonun 2. kanonik açılımı maksterimlerin çarpımlarından oluşur. • Maksterimlerin oluşturulması, • Doğruluk tablosunda çıkışın "0" olduğu satırlar seçilir. • Bu satırlarda girişlerin "0" olduğu yerlere değişkenlerin kendileri (örneğin A, B, C) ve "1" yerlere tümleyenleri (A', B', or C') yazılarak toplamlar oluşturulur. • Bir lojik fonksiyonun 2nci kanonik açılımı tektir. Sayısal Devreler (Lojik Devreleri) 2.30 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info A B C F 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 "Yanlış" değer üreten kombinezonlar: F = 000 010 100 Maksterimlerin Çarpımı: F = F' = (A + B + C') (A + B' + C') (A' + B + C') (A' + B' + C) (A' + B' + C') (A + B + C) (A + B' + C) (A' + B + C) Fonksiyonun tümleyeninin 2.kanonik açılımı benzer şekilde “doğru" noktalardan hareket edilerek yazılır: Örnek:Sayısal Devreler (Lojik Devreleri) 2.31 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info Örnek: 2.30'daki F nin kanonik açılımı: F(A, B, C) = P M(0,2,4) = M0 • M2 • M4 = (A + B + C) (A + B' + C) (A' + B + C) F = P A,B,C (0,2,4) şeklinde de yazılabilir. İndirgeme: F(A, B, C) = (A+B+C) (A+B’+C) (A’+B+C) = (A+C)(B+B') (A'+B+C) = (A+C) (A'+B+C) = (A+C) (A'+B+C) (B+C) (konsensüs) = (A + C) (B + C) A B C maksterimler 0 0 0 A+B+C M0 0 0 1 A+B+C' M1 0 1 0 A+B'+C M2 0 1 1 A+B'+C' M3 1 0 0 A'+B+C M4 1 0 1 A'+B+C' M5 1 1 0 A'+B'+C M6 1 1 1 A'+B'+C' M7 3 değişkenli maksterimlerin simgesel gösterilimi Kanonik açılım fonksiyonun en basit cebirsel ifadesi değildir. Çoğunlukla kanonik açılımlar indirgenebilir (sadeleştirilebilir). Maksterimlerin numaralanması: Maksterimler giriş kombinezonlarının sıraları dikkate alınarak numaralandırılırlar. Sayısal Devreler (Lojik Devreleri) 2.32 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info Kanonik Açılımların Dönüştürülmesi 1. kanonik açılımdan 2. kanonik açılıma (minterimden maksterime) dönüşüm 1. kanonik açılımda yer almayan minterimlerin indisleri maksterim olarak seçilir. F(A,B,C) = S m(1,3,5,6,7) = P M(0,2,4) 2. kanonik açılımdan 1. kanonik açılıma ( maksterimden minterime) dönüşüm 2. kanonik açılımda yer almayan maksterimlerin indisleri minterim olarak seçilir. F(A,B,C) = P M(0,2,4) = S m(1,3,5,6,7) Minterimler ile tümleyen ifadenin bulunması Açılımda yer almayan minterimler seçilir F(A,B,C) = S m(1,3,5,6,7) F'(A,B,C) = S m(0,2,4) Maksterimler ile tümleyen ifadenin bulunması Açılımda yer almayan maksterimler seçilir F(A,B,C) = P M(0,2,4) F'(A,B,C) = P M(1,3,5,6,7)Sayısal Devreler (Lojik Devreleri) 2.33 ©2000-2011 Yrd.Doç.Dr. Feza BUZLUCA http://www.akademi.itu.edu.tr/buzluca http://www.buzluca.info Çarpımların Toplamı (Fonksiyonun tümleyeni) F' = A'B'C' + A'BC' + AB'C' De Morgan (F')' = (A'B'C' + A'BC' + AB'C')' F = (A + B + C) (A + B' + C) (A' + B + C) 2. kanonik açılım elde edildi. Toplamların Çarpımı (Fonksiyonun tümleyeni) F' = (A + B + C') (A + B' + C') (A' + B + C') (A' + B' + C) (A' + B' + C') De Morgan (F')' = ( (A + B + C')(A + B' + C')(A' + B + C')(A' + B' + C)(A' + B' + C') )' F = A'B'C + A'BC + AB'C + ABC' + ABC 1. kanonik açılım elde edildi. Kanonik Açılımlar ve De Morgan Teoremi