DeMorgan Teoremleri

DeMorgan Teoremleri
DeMorgan isimli matematikçi, Boole cebrinde grup tümlemesi hakkında bir çift önemli kural
geliştirdi. Grup tümleme ile birden fazla değişkenin uzun bir bar aracılığıyla gösterildiği terimlerin
bir grubunun tümleyenini ima ediyorum.
Geçidin tüm girişlerini evirerek geçidin temel fonksiyonunu AND den OR a yada vs. ye dönüştüren
ve aynı zamanda çıkışı eviren mantık geçitleri hakkındaki bölümü hatırlamalısınız. Dolayısıyla tüm
girişleri evirilmiş bir OR geçidi (Negatif-OR geçidi) NAND geçidi gibi davranır ve tüm girişleri
evirilmiş bir AND geçidi (Negatif-AND geçidi) NOR geçidi gibi davranır. DeMorgan teoremleri "geri"
formda aynı eşitliği ifade eder: evirilmiş girişli geçidin (AND e karşı OR) ters türü gibi, herhangi bir
geçidin çıkışını evirmek aynı fonksiyonla sonuçlanır:
AB terimini kapsayan uzun bar sembol grubu gibi davranır ve bu bağımsız olarak evirilmiş A ve B
nin çarpımından tamamen farklıdır. Başka bir ifadeyle, (AB)' A'B' ne eşit değildir. "Üssü" sembolü
(') bar gibi iki değişkenin üzerini kaplatılamadığından bir önceki cümlede AB terimine parantez
uygulamak zorunda bırakıldık. Bununla birlikte bar, birden fazla değişkenin üzerine kaplatıldığında
kendi gruplama sembolü gibi davranır. Görüleceği gibi bu, Boole ifadelerinin nasıl değerlendirildiği
ve indirgendiği üzerine derin tesire sahiptir.
DeMorgan teoremi uzun bar sembolünün terimlere bölünmesi (kesilmesi) olarak düşünülebilir. Uzun
bar bölündüğünde, bölünme esnasında işlem direkt olarak toplamadan çarpmaya veya tersine
dönüşür ve bölünen bar parçaları kendi değişkenleri üzerinde kalır. Örneklersek:
Bir ifadede barın çoklu "katmanları" var olduğunda bir kerede sadece bir barı bölebilirsiniz ve
genellikle ilk önce en uzun (en üstteki) barı bölerek sadeleştirmeye başlamak daha kolaydır.
Örneklemek için, (A + (BC)')' ifadesini alalım ve DeMorgan Teoremlerini kullanarak onu
indirgeyelim:
Öncelikle en uzun (en üstteki) barı bölme önerisini takip edin, ben ilk aşamada tüm ifadeyi
kaplayan barı bölerek başlayacağım:
Sonuç olarak orijinal devre, evirilmiş A girişi ile birlikte üç-girişli AND geçidine indirgenir:
Tek basamakta asla birden fazla basamak bölmemelisiniz, burada gösterildiği gibi:
Bir kerede birden fazla barı bölmek ve muhafaza etmek cazip olduğu kadar genellikle yanlış sonuca
götürür, bu nedenle bunu yapmayın!
Bu ifadeyi uygun bir şekilde indirgemek için öncelikle uzun barı bölmekten ziyade kısa barı bölmek
mümkündür:
Son sonuç aynıdır fakat öncelikle en uzun barın bölündüğü ilk metodu kullanarak daha fazla
basamağın karşılaştırılması gereklidir. Üçüncü basamaktaki uzun barı iki parçaya nasıl
böldüğümüze dikkat edin. Bu yasal bir matematiksel işlemdir ve bir adımdaki iki barın bölünmesiyle
aynı değildir! Birden fazla barın bölünmesine karşı yasak, birden fazla yerdeki barın bölünmesine
karşı yasak değildir. Tek bir adımda birden fazla yerin bölünmesi uygundur; tek bir adımda birden
fazla barın bölünmesi uygun değildir.
Alt-ifade B' + C' etrafına neden parantezler yerleştirildiğini merak ediyor olabilirsiniz, bu gerçeği
göz önünde bulundurarak sonraki adımda onları kaldırdım. DeMorgan teoreminin önemli ama
kolaylıkla ihmal edilebilir görüşünü vurgulamak için bunu yaptım. Uzun bar gruplama sembolü gibi
işlediğinden, bölünmüş bar aracılığıyla vaktiyle gruplanmış değişkenler uygun öncelik (işlem sırası)
kaybolmasın diye gruplanmış kalmalıdır. Bu örnekte eğer kısa bara bölünmeden sonra parantezleri
koymayı unutursam önemli olmayacaktır fakat diğer durumlarda önemli olabilir. Farklı ifade ile
başlayan bu örneği göz önüne alın:
Gördüğünüz gibi, bu ifade için tümleme barları ile örtülen gruplamanın korunması doğru cevabı elde
etmek için önemlidir.
Geçit devresinin basitleştirilmesi için DeMorgan teoremlerinin ilkelerini uygulayalım:
Her zaman olduğu gibi bu devreyi sadeleştirmedeki ilk basamağımız Boole ifadesi eşdeğerini
üretmek olmalıdır. Girişlerin bilindiği gibi, her bir geçidin çıkışında alt-ifade etiketi yerleştirerek
bunu yapabiliriz. Bu işlemdeki ilk adım şudur:
Daha sonra, ilk NOR geçidi ve NAND geçidinin çıkışlarını etiketleyebiliriz. Evirilmiş-çıkış geçitleri ele
alındığında, evirme balonundan az önce sivri ok ile son evirme olmadan geçidin çıkışı için bir ifade
yazarak onu kolaylaştırırım. Ardından geçidin yönündeki kabloda (balondan sonra), tam tümlenmiş
ifadeyi yazarım. Bu, ifade-yazma görevini iki adıma ayırmaya kendimi zorlayarak alt-ifade için
tümleme barını unutmamamı garanti etmeye yardımcı olur:
Son olarak, son NOR geçidi için bir ifade (yada ifade çifti) yazarız:
Şimdi, özdeşlikleri, seçenekleri, kuralları ve Boole cebrinin teoremlerini (DeMorgan ın) kullanarak
bu ifadeyi indirgeriz:
Bu çok-sadeleştirilmiş ifade için eşdeğer geçit devresi aşağıdaki gibidir:
•
ÖZET:
•
DeMorgan Teoremleri, evirilmiş girişli geçitler ile evirilmiş çıkışlı geçitler arasındaki eşitliği
tanımlar. Basitçe NAND geçidinin Negatif-OR geçidi eşdeğerini ve NOR geçidinin Negatif-AND
geçidi eşdeğerini koyar.
•
Boole ifadesinde tümleme barı "bölündüğünde", işlem bölünme altında (toplama yada çarpma)
tersine döner ve bölünmüş bar parçaları kendi terimleri üzerinde kalır.
•
Onun altındaki herhangi bir barı bölmeden önce en uzun (en üstteki) barı bölerek bir probleme
yaklaşmak genellikle daha basittir. Bir adımda iki barı bölmeye asla kalkışmamalısınız!
•
Tümleme barları gruplama sembolleri gibi çalışır. Bu yüzden bir bar bölündüğünde, altındaki
terimler gruplanmış kalmalıdır. Bu gruplanmış terimlerin etrafına önceliği değiştirmeyi
önlemeye yardımcı olarak parantezler yerleştirilebilir.