1. Karnaugh haritası nedir
Karnaugh haritası, bir doğruluk tablosunun ızgara olarak yeniden çizilmiş hâlidir. Maurice Karnaugh bunu 1953'te Bell Labs'te, anahtarlama devrelerini gözle sadeleştirmenin bir yolu olarak ortaya koydu; küçük bir Boole fonksiyonunu elde sadeleştirmenin hâlâ en hızlı yolu odur: cebir yok, ezberlenecek yasa yok, yalnızca dikdörtgenler.
Haritanın her hücresi doğruluk tablosunun bir satırını taşır. Haritayı bir yeniden dizmeden fazlası yapan şey, bu satırların yerleştirilme sırasıdır: yan yana duran hücreler tam olarak bir değişkende farklıdır.
Bütün işi bu tek özellik yapar. İki komşu hücre de doğruysa, aralarında değişen değişken ifadeyi doğru yapan şey olamaz; bu yüzden düşer ve tek bir terim iki hücreyi birden kaplar. Sadeleştirmek böylece çizilebilecek en büyük dikdörtgenleri çizmeye dönüşür.
2. Sütunlar neden sırasız görünüyor
Karnaugh haritasının sütunları 00, 01, 10, 11 diye saymaz. 00, 01, 11, 10 diye ilerler: yansımalı Gray kodu, yani her değerin bir sonrakinden tek bir bit farklı olduğu bir sıralama. İkilik sistemde saymak 01 ile 10'u yan yana getirirdi; bunlar iki bit farklıdır ve komşu hücreler artık hiçbir şey söylemezdi.
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 3 | 2 |
| 1 | 4 | 5 | 7 | 6 |
Kenarlar da komşudur. En soldaki ve en sağdaki sütun tek bir değişkende ayrılır; en üstteki ile en alttaki satır da öyle. Dolayısıyla bir grup bir kenardan çıkıp öbür kenardan devam edebilir - dört değişkenli bir haritanın dört köşesinin tek bir grup oluşturmasının nedeni budur. Karnaugh haritası aslında bir simit yüzeyine çizilidir; düz sayfa yalnızca kolaylıktır.
3. Birleri gruplamak
Haritadan en sade çarpımlar toplamını okumak için, 1 taşıyan her hücreyi dikdörtgen gruplarla kaplayın; dört kural var:
- Bir grup 1, 2, 4, 8 … hücrelik bir dikdörtgendir - her kenarı ikinin bir kuvveti.
- Bir grup haritanın kenarlarından dolanabilir: yatay, dikey ya da her iki yönde.
- Gruplar üst üste binebilir. Bir hücreyi iki kez kaplamanın bedeli yoktur; kapsız bırakmak ise fonksiyonu değiştirir.
- Her grubu olabildiğince büyütün, sonra bütün birleri kaplayacak en az sayıda grubu kullanın.
Her grup bir terime dönüşür. Terimi okumak için hangi değişkenlerin grup boyunca aynı kaldığına bakılır: onlar terimde yer alır - 1 oldukları yerde olduğu gibi, 0 oldukları yerde değillenmiş olarak - ve değişen her değişken düşer. İki hücrelik grup bir değişken kaybeder, dört hücrelik iki, sekiz hücrelik üç. En sade ifade, bu terimlerin tikel evetlemesidir.
4. Çözümlü bir örnek
(A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D) ifadesini ele alalım. Haritası dört değişkenlidir: satırlarda A ile B, sütunlarda C ile D.
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 0 | 1 | 1 |
| 01 | 0 | 0 | 1 | 1 |
| 11 | 1 | 1 | 1 | 1 |
| 10 | 0 | 0 | 0 | 0 |
İki grup bütün birleri kaplar. Biri, A = 0 olan iki satır ile C = 1 olan iki sütunun kesiştiği dört hücrelik bloktur: içinde hem B hem D değişir, bu yüzden düşerler ve terim ¬A ∧ C olur. Öteki, A ile B'nin ikisinin de 1 olduğu satırın tamamıdır, dört sütun boyunca: C ile D bu satır boyunca değişir, geriye A ∧ B kalır.
Yani en sade biçim (¬A ∧ C) ∨ (A ∧ B). Özgün ifadenin üçüncü terimi olan B ∧ C ∧ D yok oldu: kapladığı her hücre zaten iki gruptan biri tarafından kaplanıyordu. Yutma yasası, görülebilir hâle geldiğinde işte böyle görünür.
5. Asal ve zorunlu asal önermeler
Daha fazla büyütülemeyen gruba asal içerim (prime implicant) denir. Asal içerimleri listelemek işin kolay yarısıdır; hangilerinin tutulacağını seçmek ise ters giden yarısı.
Bir hücreyi yalnızca tek bir asal içerim kaplıyorsa, o içerim zorunludur: hiçbir sade biçim onu dışarıda bırakamaz, çünkü o hücreyi kaplayan başka bir şey yoktur. Önce zorunlu içerimleri alın, geriye kalanı da kalan gruplardan olabildiğince azıyla kaplayın.
Açgözlü davranmak - her seferinde elde kalan en büyük grubu almak - çekicidir ama her zaman işe yaramaz. Hiçbir içerimin zorunlu olmadığı ve her hücrenin iki kez kaplandığı döngüsel bir çizelgede, açgözlü seçim en iyi yanıttan bir terim fazlasıyla bitebilir. Bu sitedeki harita bunun yerine kalan seçenekleri baştan sona tarar; dört değişkende bunun maliyeti yok denecek kadar azdır.
6. Bunun yerine sıfırları gruplamak
Yukarıdaki her şey sıfırlar için de aynı şekilde geçerlidir. Onları aynı dikdörtgenlerle kaplayın, her grubu değilleri alınmış olarak okuyun - grup boyunca 1 olan değişken değillenmiş, 0 olan olduğu gibi görünür - ve grupları ∨ yerine ∧ ile bağlayın.
Sonuç bir toplamlar çarpımıdır: tam olarak ifadenin yanlış olduğu hücrelerde yanlış, dolayısıyla başka her yerde doğru olan bir tikel evetlemeler tümel evetlemesi. Hangi biçimin daha kısa olduğu fonksiyona bağlıdır - az sayıda 1 içeren bir formülün çarpımlar toplamı kısadır, az sayıda 0 içerenin ise toplamlar çarpımı - bu yüzden seçmeden önce ikisini de haritadan okumaya değer.
7. Daha büyük haritalar ve fark etmez durumlar
Beş ve altı değişken, dört değişkenli iki ya da dört harita üst üste konarak çizilebilir; komşu katmanlarda aynı konumdaki hücreler bitişik sayılır. İşe yarar, ama yöntemi görsel kılan bitişiklik artık görülen değil hatırlanan bir şeydir. Bunun ötesinde aynı işi tablo biçiminde Quine-McCluskey algoritması yapar: tam olarak bu gruplamanın mekanik hâlidir ve buradaki haritaların arkasında çalışan da odur.
Donanım tasarımı buna bir fikir daha ekler. Bazı giriş bileşimleri hiç oluşmaz - ikili kodlanmış bir onluk basamak asla 1010 değildir - bu yüzden tasarımcı devrenin onlarla ne yaptığını umursamaz. O hücreler X ile işaretlenir ve grupları hangisi büyütüyorsa o değerle okunabilir. Bu hesap makinesindeki haritalar bir formülden kurulur ve formül her atamaya bir değer verir; dolayısıyla hiçbir hücre fark etmez durumunda değildir.
8. Kendiniz deneyin
Hesap makinesine iki ile dört değişkenli bir ifade yazın; haritası doğruluk tablosunun altına çizilir, her grup kendi rengiyle çevrelenir ve en sade biçim altına yazılır. Sıfırların gruplandığını görmek için toplamlar çarpımına geçin.