Karnaugh Haritaları, Doğruluk Çizelgeleri ve Boole İfadeleri

Karnaugh Haritaları, Doğruluk Çizelgeleri ve Boole İfadeleri
Bir haberleşme mühendisi olan Maurice Karnaugh, Karnaugh haritasını 1953 yılında Bell
Labaratuarında sayısal mantık tabanlı telefon anahtarlama devreleri dizayn ederken geliştirdi.
Venn diyagramları yardımıyla Karnaugh haritasını geliştirdiğimize göre kullanalım. Karnaugh
haritaları mantık fonksiyonlarını Boole cebrine göre daha hızlı ve kolayca indirger. İndirgemek ile
basitleştirmek ve kapı ve girdi sayısını azaltmak kastedilmektedir. Mantığı, bileşenleri kaldırarak
maliyetleri düşürmek için en düşük maliyete indirgemek isteriz. En düşük maliyeti en az sayıdaki
kapı ve kapı başına en az sayıdaki girdi olarak tanımlarız.
Öğrendikten sonra, seçenek verildiğinde çoğu öğrenci mantık basitleştirmeyi Boole cebri yerine
Karnaugh haritaları ile yapar.
Yukarıda beş farklı madde gösteriyoruz, bunlar sıradan 2-girdili sayısal mantık fonksiyonunu
göstermenin farklı yollarıdır. İlki röle merdiven mantığı, sonra mantık kapıları, bir gerçeklik tablosu,
bir Karnaugh haritası ve bir Boole denklemi. Bunların hepsi de aynıdır. İki A ve B girdisi duruma
göre 0 veya 1, yüksek veya alçak, açık veya kapalı, Doğru veya Yanlış değerleri alabilir. Bir çıktı
üreten 22 = 4 girdi kombinasyonu vardır. Bu bütün beş örnektekilere uygulanabilir.
Bu dört adet çıktı bir röle merdiven mantığındaki bir lambada, kapı diyagramında bir mantık
sondasında gözlenebilir. Bu çıktılar bir doğruluk tablosuna veya bir Karnaugh haritasına kayıt
edilebilir. Karnaugh haritasını tekrar düzenlenmiş bir doğruluk tablosu olarak görebiliriz. Boole
denkleminin çıktısı Boole cebrinin kuralları ile hesaplanabilir ve doğruluk tablosuna veya Karnaugh
haritasına transfer edilebilir. Birbirine denk beş mantık tanımlamalarından hangisini kullanacağız?
Verilen göreve en uygun olanını kullanmalıyız.
Bir doğruluk tablosunun çıktıları bir Karnaugh haritası girdilerine bire-bir mantığına göre eşleşir.
Doğruluk tablosunun tepesinden başlarsak, A=0, B=0 girdileri ? çıktısını üretir. Aynı ? çıktısının
Karnaugh haritasında A=0, B=0 hücre adresinde, K-haritasında A=0 satırı ve B=0 sütununun
kesiştiği üstte solda elde edildiğine dikkat edin. AB=01, 10, 11 girdilerinin ürettiği ß, ?, ? doğruluk
tablosu çıktıları ilgili K-haritası yerlerinde bulunur.
Aşağıda, önceki dikdörtgen şeklindeki Venn diyagramlarına benzer Boole bölgeleri yardımıyla, 2değişkenli K-haritasında komşu 2-hücreli bölgeleri gösteriyoruz.
Aşağıda en soldaki K-haritasında ? ve ? hücreleri elips şeklinde komşulardır. Önceki doğruluk
tablosuna göre durum böyle değil. Aralarında başka bir doğruluk tablosu girdisi (ß) var. Bu bizi Kharitasını bir kare dizi şeklinde organize etme noktasına getiriyor, herhangi bir ortak Boole
değişkeni olan hücreler bir desen oluşturacak ve dikkatimizi çekecek şekilde ve birbirine yakın
olmalı. ? ve ? hücreleri için B' Boole terimi ortaktır. Bunu biliyoruz çünkü ? ve ? hücrelerinin
üstündeki sütun için B=0 ( aynı şekilde B' için). Bunu K-haritasının üstündeki kare Venn diyagramı
ile kıyaslayın.
Benzer bir akıl yürütme gösteriyor ki ß ve ? için B (B=1) Boole terimi ortaktır. Sonra, ? ve ß için A'
(A=0) Boole terimi ortaktır. Son olarak, ? ve ? için A (A=1) boole terimi ortaktır. Son iki haritayı
ortadaki kare Venn diyagramı ile kıyaslayın.
Özetle, biz hücreler arasında ortak Boole değişkenlerine bakıyoruz. Karnaugh haritası, bu ortak
noktaları görebileceğimiz şekilde düzenlenmiştir. Şimdi bazı örneklere bakalım.
Örnek:
Yukarıdaki doğruluk tablosunun içeriğini Karnaugh haritasına taşıyın.
Çözüm:
Doğruluk tablosu iki tane 1 içerir. K- haritası her ikisini içermelidir. İlk 1 yukarıdaki doğruluk
tablosunun 2.satırına yerleştirilir.
•
doğruluk tablosunun AB adresine dikkat edin
•
K-haritasında aynı adrese sahip hücreyi bulun
•
o hücreye 1 yerleştirin
Bu süreci doğruluk tablosunun son sırasındaki 1 için tekrarlayın.
Örnek:
Yukarıdaki problemdeki Karnaugh haritası için Boole ifadesini yazınız. Çözüm aşağıdadır.
Çözüm:
Bir hücrenin üstünde veya yanındaki komşu hücrelere bakın. köşegen hücreler komşu hücre
değildir. Komşu hücreler bir veya fazla ortak Boole değişkenine sahip olmalıdır.
•
Sütundaki iki 1 i gruplandırın(daire içine alın)
•
Bir grup için aynı olan değişken(ler)i yukarıda ve/veya yan tarafta bulun, bunu Boole sonucu
olarak yazın. Bizim örneğimizde B.
•
Bir hücre grubu için aynı olmayan değişken(ler)i ihmal edin. Bizim örneğimizde A değişir, hem
1 hem de 0 olur, A Boole terimini ihmal edin..
•
1 leri içereb hücrelerle ilişkili olmayan değişkenleri ihmal edin. B' altında hiç 1 yok. B' ihmal
edilir.
•
Sonuç Out = B
Bunu görmek sağdaki Venn diyagramlarını özellikle B sütununu karşılaştırarak daha kolaydır.
Örnek:
Aşağıdaki Karnaugh haritası için Boole ifadesini yazın.
Çözüm: (yukarıda)
•
Satırdaki iki 1'leri gruplandırın (daire içine alın)
•
Grup için aynı olan değişken(ler)i bulun, Out = A'
Örnek:
Aşağıdaki doğruluk tablosu için çıktıları Karnaugh haritasına taşıyın sonra sonuç için Boole ifadesini
yazın.
Çözüm:
Doğruluk tablolarındaki 1leri K-haritasındaki ilgili yerlere taşıyın.
•
B=1 altındaki sütunda bulunan iki 1leri gruplandırın
•
A=1 sağındaki satırda bulunan iki 1leri gruplandırın
•
ilk grup için çarpım ifadesini = B yazın
•
ikinci grup için çarpımı = A yazın
•
Yukarıdaki iki ifadenin çarpımlarının toplamını Output = A+B şeklinde yazın.
Ortadaki K-haritasının çözümü en basit veya en düşük maliyetli çözümdür. Daha az tercih edilen bir
çözüm en sağdadır. İki adet 1leri gruplandırdıktan sonra, 1-hücreli bir grup oluşturma hatasını
yaparız. Bunun tercih edilmemesinin sebebi:
•
Tek hücre AB' çarpım ifadesine sahiptir
•
Karşılık gelen çözüm Output = AB' + B dir
•
Bu en basit çözüm değildir
Bu tek 1 terimini dikkate almanın yolu bu 1 (B) sütun grubunda daha önceden dahil edilmiş olsa
bile ortadaki K-haritasının alt satırında gösterildiği gibi sağındaki 1 ile ikili bir grup oluşturmaktır.
daha büyük gruplar oluşturmak için hücreleri tekrar kullanabiliriz. Aslında, bu tercih edilir çünkü bizi
daha basit çözüme ulaştırır.
Şunu belirtmeliyiz ki, yukarıdaki her iki Output veya Yanlış Output çözümü de mantık olarak
doğrudur. İki devre de aynı çıktıyı verir. Önceki devrenin en düşük maliyetli olması burada
önemlidir.
Örnek:
Aşağıdaki Boole ifadesi için Karnaugh haritasını doldurun, sonra sonuç için Boole ifadesini yazın.
Çözüm: (yukarıda)
Boole ifadesi üç çarpım teriminden oluşur. Her çarpım terimi için bir 1 girilir. Fakat genelde çarpım
terimi başına düşen 1 sayısı, K-haritasının büyüklüğü ile kıyaslandığında çarpımdaki değişken sayısı
ile değişir. Çarpım terimi 1 girilen hücrenin adresidir. İlk çarpım terimi A'B haritada 01 hücresine
karşılık gelir. Bu hücreye 1 girilir. Diğer iki çarpım terimleri toplam üç adet 1 olacak şekilde girilir.
Sonra basitleştirilmiş sonucu, önceki doğruluk tablosu probleminde olduğu gibi gruplandırma ve
çıkartma işlemi ile devam ediniz.
Örnek:
Aşağıdaki mantık diyagramını sadeleştirin.
Çözüm: (aşağıdaki şekil)
•
Aşağıda gösterildiği gibi orijinal mantık diyagramı için Boole ifadesini yazın
•
Çarpım terimlerini Karnaugh haritasına aktarın
•
Önceki problemlerdeki gibi hücreleri gruplandırın
•
Önceki problemlerdeki gibi gruplar için Boole ifadelerini yazın
•
Sadeleştirilmiş mantık diyagramlarını çizin
Örnek:
Aşağıdaki mantık diyagramını sadeleştirin.
Çözüm:
•
Yukarıda gösterildiği gibi orijinal mantık diyagramı için Boole ifadesini yazın
•
Çarpım terimlerini Karnaugh haritasına aktarın
•
Grup oluşturmak mümkün değildir
•
Sadeleştirme imkansızdır, olduğu gibi bırakın.
Yukarıdaki diyagram için mantık sadeleştirme mümkün değildir. Bu bazen olur. Ne Karnaugh
haritaları metodları ne de Boole cebri bu mantığı daha fazla sadeleştiremez. Yukarıda bir DışlayıcıOR çizim sembolü gösteriyoruz; fakat bu bir mantıksal sadeleştirme değildir. Sadece bir çizim
diyagramını daha iyi gösterir. Dışlayıcı-OR mantığını sadeleştirmek imkansız olduğu ve çokca
kullanıldığı için, üreticiler tarafından temel entegre devresi (7486) olarak sunulur.