Öğrenci şunları yapmalıdır:

Bilmek:

· Minimizasyon yöntemleri mantık fonksiyonları.

Yapabilmek:

· Doğrudan dönüşümler yöntemiyle fonksiyonların minimizasyonunu gerçekleştirin; Doğrudan dönüşümler yöntemiyle fonksiyonların minimizasyonunu gerçekleştirin;

· Karnaugh haritalarını kullanarak fonksiyon minimizasyonu gerçekleştirin.

Doğrudan dönüşümler yöntemi

Devre oluşturma ilkesini belirten mantıksal bir işlev dijital aygıt, yukarıda gösterildiği gibi doğruluk tablosu veya SDNF veya SKNF şeklinde sunulabilir ve cihazın mantıksal devresini elde etmek için kullanılabilir. Bununla birlikte, ortaya çıkan mantık devresi genellikle optimal olmayacaktır. Bu yüzden dönüm noktası sentez mantık devreleri mantıksal fonksiyonların minimizasyonudur.

minimizasyon(gösterim formunun basitleştirilmesi) bir mantıksal devrenin sentezinde önemli bir işlemdir, çünkü ön minimizasyon nedeniyle devre en az sayıda elemanla uygulanır.

Minimize etmek için birçok yöntem geliştirilmiştir. Biri basit yöntemler minimizasyon, mantık cebirinin temel teoremleri kullanılarak gerçekleştirilen bir doğrudan dönüşüm yöntemidir.

Örneğin, mantıksal işlev

SDNF şeklinde, minimize edilebilir Aşağıdaki şekilde:

1. x + x = x kuralını kullanarak, bu fonksiyonda zaten bulunan terimini bu fonksiyona ekleyin.

2. Aynı altı çizili temel bağlaçları yapıştırma yöntemini uygulayın

3. Son iki temel bağlaç için yapıştırma yöntemini uygulayın

Minimizasyon sonucunda elde edilen mantıksal fonksiyona çıkmaz fonksiyon denir. Bir boole işlevinin birden çok çıkmaz ucu olabilir.

Mantık cebirinin aksiyomlarını, yasalarını, kimliklerini ve teoremlerini kullanarak bir fonksiyonun gösterimindeki fazlalıkların tanımlanması ve ortadan kaldırılması, hantal hesaplamalar gerektirir ve büyük bir zaman harcaması ile ilişkilendirilir.

Karnot haritaları

Doğrudan dönüşüm yöntemi en uygun olanıdır. basit formüller dönüşüm dizisi sanatçı için açık olduğunda. Çoğu zaman, bu yöntem, diğer yöntemlerle minimizasyonundan sonra elde edilen ifadelerin son minimizasyonu için kullanılır.

Komşu temel ürünler için aramayı algoritmalaştırma arzusu, geliştirilmesine yol açtı. tablo yöntemleri mantıksal fonksiyonların minimizasyonu. Bunlardan biri Karnot haritalarının kullanımına dayalı bir yöntemdir.

Karnot haritaları 1952'de Edward W. Veitch tarafından icat edildi ve 1953'te bir fizikçi olan Maurice Karnot tarafından geliştirildi. Bell Laboratuvarları" ve dijital elektronik devreleri basitleştirmeye yardımcı olması amaçlandı.

Carnot'un haritası Grafik sunum mantıksal fonksiyonların doğruluk tabloları. 2 n dikdörtgen hücre içeren bir tablodur, burada n mantıksal değişkenlerin sayısıdır.

Örneğin, dört değişkenli bir fonksiyon için bir Karnaugh haritası 2 4 = 16 hücreye sahiptir.

İki değişkenli fonksiyonlar için Karnaugh haritasının yapısı Şekil 2.2'de gösterilmiştir. 2

Şekil 2.2

Şekil 2.3, Karnaugh haritasının yapısını göstermektedir. üçün işlevleri değişkenler.

a) doğruluk tablosu; b) Karnot haritasının yapısı

Şekil 2.3

Harita, giriş değişkenlerinin değerlerine karşılık gelen bir koordinat sistemi ile işaretlenir. Örneğin, üst çizgiüç değişkenli bir fonksiyon için harita (şekil 2.3), x1 değişkeninin sıfır değerine, alttaki ise birim değerine karşılık gelir.

Bu haritanın her sütunu, iki değişkenin değerleri ile karakterize edilir: x2 ve x3. Her sütunu işaretleyen sayıların kombinasyonu, bu sütunun hücrelerine yerleştirilen fonksiyonun x2 ve x3 değişkenlerinin hangi değerleri için hesaplandığını gösterir.

Belirtilen sette ise değişken fonksiyon bire eşitse, SDNF'si mutlaka bu kümedeki birim değeri alan bir temel ürün içerir. Böylece, bir fonksiyonu temsil eden Carnot haritasının hücreleri, SDNF'sinde temel ürünler olduğu kadar çok birim içerir ve her birim, temel ürünlerden birine karşılık gelir.

Karnot haritasındaki satır ve sütunların koordinatlarının ikili kodların doğal artan sırasına göre değil, 00, 01, 11, 10 sırasına göre takip ettiğine dikkat edelim. kümeler, komşu kümeler komşu olacak şekilde yapılır, yani . sadece bir değişkenin değerinde farklılık gösterir.

Fonksiyonun bire eşit değerler aldığı hücreler birlerle doldurulur. Hücrelerin geri kalanı sıfırlarla doldurulur.

Şekil 2.4'te gösterilen örneği kullanarak minimizasyon sürecini düşünün.

a) doğruluk tablosu; b) Carnot haritası

Şekil 2.4

İlk olarak, her biri 2k hücre içeren dikdörtgenler oluşturuyoruz, burada k bir tam sayıdır.

Dikdörtgenler halinde birleştirilir komşu hücreler, komşu temel ürünlere karşılık gelir.

Örneğin Şekil 2.4b'de koordinatları 001 ve 101 olan hücreler birleştirilir.Bu hücreler birleştirildiğinde x1 değişkeninin değerini değiştirdiği bir dikdörtgen oluşur. Sonuç olarak, karşılık gelen temel ürünler birbirine yapıştırıldığında kaybolacak ve sadece x2 ve x3 kalacak ve x2 değişkenini ters biçimde alıyoruz, çünkü 0'a eşittir.

İlk sırada yer alan hücreler (Şekil 2.4 b) birimleri içerir ve bitişiktir. Bu nedenle, hepsi 2 2 = 4 hücre içeren bir dikdörtgende birleştirilir.

Dikdörtgen içindeki x2 ve x3 değişkenleri değerlerini değiştirir; bu nedenle, ortaya çıkan temel üründen kaybolacaklar. x1 değişkeni değişmeden kalır ve sıfıra eşittir. Böylece, Şekil 2.4 b'nin ilk satırındaki hücrelerin birleştirilmesi sonucunda elde edilen temel ürün, ters biçimde aldığımız sadece bir x1 içerir, çünkü 0'a eşittir.

Bu, özellikle, ilk satırın dört hücresinin, dört temel ürünün toplamına karşılık gelmesi gerçeğinden kaynaklanmaktadır:

Üçüncü sütunun iki hücresi, iki ürünün toplamına karşılık gelir.

Şekil 2.4'e karşılık gelen fonksiyon:

Tüm birimleri kapsayan dikdörtgenler kümesine örtü denir. Aynı hücrenin (örneğin, 001 koordinatlarındaki hücre) iki veya daha fazla kez kapsanabileceğini unutmayın.

Dolayısıyla, aşağıdaki sonuçları çıkarabiliriz:

1. Mantıksal bir fonksiyonun Karnaugh haritaları kullanılarak minimizasyonundan elde edilen formül, kapsamadaki dikdörtgenler kadar çok sayıda temel ürünün toplamını içerir.

2. Bir dikdörtgende ne kadar çok hücre varsa, karşılık gelen temel üründe o kadar az değişken bulunur.

Örneğin, Şekil 2.5a'da gösterilen Karnaugh haritası için, dört hücre içeren bir dikdörtgen, iki değişkenli bir temel ürüne karşılık gelir ve yalnızca bir hücreden oluşan bir kare, bir temel ürüne karşılık gelir. dört değişkeni de içerir.

bir B C)

Şekil 2.5

Şekil 2.5a'da gösterilen kapsama karşılık gelen fonksiyon şu şekildedir:

Karnaugh haritalarının bir düzlem üzerinde çizilmesine rağmen, karelerin komşuluğu bir simit yüzeyinde kurulur. Karnaugh haritasının üst ve alt sınırları adeta "birbirine yapıştırılmıştır" ve bir silindirin yüzeyini oluşturur. Yan sınırları yapıştırırken toroidal bir yüzey elde edilir. Yukarıdaki akıl yürütmeyi takiben, Şekil 2.5 b'de gösterilen 1011 ve 0011 koordinatlarına sahip hücrelerin bitişik olduğunu ve bir dikdörtgen halinde birleştirildiğini tespit ediyoruz. Gerçekten de, belirtilen hücreler, temel ürünlerin toplamına karşılık gelir.

Diğer dört birim hücre benzer şekilde birleştirilir. Kombinasyonlarının bir sonucu olarak, temel ürünü elde ederiz.

Son olarak, Şekil 2.5b'de gösterilen kapsama karşılık gelen fonksiyon şu şekildedir:

Şekil 2.5c'de gösterilen Karnaugh haritası, köşelerde yer alan tek hücreler içermektedir. Dört hücrenin tümü bitişiktir ve birleştirildikten sonra temel bir ürün verirler.

Yukarıda ele alınan örnekler, Karnaugh haritalarını kullanarak mantıksal işlevleri en aza indirme sırasını formüle etmemize izin verir:

1. n değişken için bir tablo görüntülenir ve kenarları işaretlenir.

2. Tablonun fonksiyonu bire çeviren değişken kümelerine karşılık gelen hücreleri bir, kalan hücreler sıfırlarla doldurulur.

3. Seçin en iyi kapsama konturlarla daire içine aldığımız düzenli dikdörtgenlere sahip tablolar. Her dikdörtgen 2n hücre içermelidir.

4. Birimleri olan aynı hücreler farklı konturlara dahil edilebilir.

5. Dikdörtgenlerin sayısı minimum, dikdörtgenlerin alanı maksimum olmalıdır.

6. Her dikdörtgen için sadece değerini değiştirmeyen değişkenlerin çarpımını yazarız. Bu değişken sıfıra eşitse, ters biçimde yazılır.

7. Ortaya çıkan ürünleri mantıksal bir ekleme işaretiyle bağlarız.

sınav soruları:

1. Mintermler ve mintermler nedir?

2.Kayıt fonksiyonları, tablolar tarafından verilen SDNF ve SKNF'de 2.9 ve 2.10.

Tablo 2.9

3. Özdeşlik aksiyomlarını ve mantık cebir yasalarını kullanarak mantık işlevlerini basitleştirin:

a)

c)

mantık öğeleri

öğrenci gerekir

Bilmek:

· Ana işlevsel mantıksal devreler için mantıksal durum tabloları;

· Mantıksal devrelerin inşası için temel temeller.

Yapabilmek:

Çıkışlardaki mantıksal durumları belirleyin dijital devreler girişlerde bilinen durumlara göre;

· Mikro devreler temelinde mantıksal tasarım gerçekleştirin;

Referans kitaptan bir mikro devre seçin. parametreleri ayarla ve kullanım koşulları.

Mantık cihazı ilkesi, iş yerindeki IC'ye dayanır bipolar transistörler anahtar modunda (kapalı veya açık).

Mantıksal eylem, bir (tek girişli) ile olduğu gibi gerçekleştirilir. mantıksal öğe) ve bir dizi (çok girişli mantık öğesi) giriş değişkenleriyle.

İşte mantıksal aygıtlar Boole cebirine göre üç temel eylem kullanılır - "VE", "VEYA", "DEĞİL".

Mantıksal bir işlev, cebirsel biçimde, zamanlama diyagramları kullanılarak anahtarlama tablosu adı verilen bir doğruluk tablosuyla sözlü olarak ifade edilebilir. Mantıksal işlevleri temsil etmek için tüm seçenekleri göz önünde bulundurun.

Yöntem, herhangi bir sayıda değişkenli fonksiyonlar için geçerlidir, ancak biz onu 3 değişkenli fonksiyonlar için ele alacağız.

Belirsiz katsayıları k olan bir DNF biçiminde temsil ediyoruz:

(**)

Bu DNF, fonksiyona dahil edilebilecek tüm olası temel bağlaçları içerir ve k katsayıları 0 veya 1 değerlerini alabilir. Bu DNF'nin minimum olması için katsayıların değerleri seçilmelidir.

Bize verilen fonksiyonu tüm kümelerde ele alacağız ve her kümedeki (**) ifadesini (sıfır bağlaçları atarak) fonksiyonun karşılık gelen değeri ile eşitleyeceğiz. Formun bir denklem sistemi elde ederiz:

Bu denklemlerden herhangi birinde sağ taraf 0'a eşitse, sol tarafın tüm terimleri de 0'a eşittir. Bu katsayılar, sağ tarafları 1'e eşit olan tüm denklemlerden çıkarılabilir. Bu denklemlerde, 1 değeri, en küçük sıranın birleşimine karşılık gelen katsayıya atanmalıdır. Bu katsayılar MDNF'yi belirleyecektir.

Örnek

(**) ifadesini kullanarak bir sistem oluşturuyoruz.

Sıfır terimlerini çıkardıktan sonra,

Geri kalan katsayıların sıfır olduğunu varsayıyoruz. MDNF alıyoruz:

2.2. Quine-McCluskey Yöntemi

düşünülen yöntem belirsiz katsayılar fonksiyon argümanlarının sayısı 5 - 6'dan fazla değilse etkilidir. Bunun nedeni denklem sayısının 2 n olmasıdır. Bir işlev için tüm olası bağlaçları değil, yalnızca bu işlevin DNF'sinde bulunabilecek bağlaçları yazmak daha verimlidir. Quine'ın yöntemi buna dayanmaktadır. Fonksiyonun SDNF şeklinde verildiği varsayılmaktadır. Bu yöntemde, DNF'ye dahil edilen rank n'nin elemanter bağlaçlarına rank n'nin minitermleri denir. Quine'in yöntemi, aşağıdaki adımların sıralı yürütülmesinden oluşur.

1. Asal imaları bulma

Fonksiyonun her bir mini terimine sırayla bakarız ve bunu mümkün olan tüm mini terimlerle yapıştırırız. n'inci sıradaki minitermlerin yapıştırılmasının bir sonucu olarak, (n-1)-inci sıradaki minitermleri elde ederiz. Yapıştırma işlemine katılan n. sıradaki minitermler işaretlenir. Daha sonra (n-1)-inci sıradaki mini terimleri ele alır ve bunlara yapıştırma işlemini uygularız. (n-1)'inci sıranın birbirine yapıştırılmış mini terimlerini işaretliyoruz ve (n-2)'nci sıranın yapıştırma vb. sonucu oluşan mini terimlerini yazıyoruz. Yeni elde edilen minitermler ise aşama sona erer. ben-th rank artık birbirine yapıştırılmış değil. Tüm işaretlenmemiş mini terimlere birincil imalar denir. Onların ayrılığı Abbr. DNF işlevleri.

4. sıradaki minitermleri yapıştırıyoruz ve yapıştırma minitermlerini yıldızlarla işaretliyoruz

2. sıradaki mini terimleri oluşturuyoruz:

Birincil (basit) imalar şunlardır:

2. etiketleme

Bu işlev için, Abbr. DNF şuna benzer:

Çıkmaz DNF'ler ve Abbr oluşturmak için. DNF'nin fazladan aralıkları atması gerekiyor. Satırları birincil çıkarımlara karşılık gelen bir tablo oluşturuyoruz ve sütunlar SDNF mini terimlerine karşılık geliyor. Bazı mini terimler bazı imaları içeriyorsa, ilgili satır ve sütunun kesişimine bir etiket yerleştirilir, örneğin, 1.

Örneğin devamı

3. Temel çıkarımları bulma

Herhangi bir sütun yalnızca bir birim içeriyorsa, bu satırı tanımlayan birincil ima esas olarak adlandırılır. Örneğin, önemli bir implikant . Önemli bir ima, Kısaltma'dan çıkarılamaz. DNF, yalnızca bazı SDNF mini terimlerini kapsayabildiğinden. Bu nedenle, bu çıkarımlara karşılık gelen satırları ve bu satırlarda bulunan sütunları tablodan çıkarıyoruz.

Bu örnekte, satır ve sütunları hariç tutuyoruz.

Sonuç olarak, bir tablo elde ederiz.

4. Fazladan sütunları ve satırları geçme

Ortaya çıkan tablo aynı sütunlara sahipse, biri hariç tümünün üzerini çizeriz. Bundan sonra tablo gösterecekse boş satırlar, ardından bunları silin.

5. Maksimum Aralıklarla Minimum Kapsamı Seçme

Ortaya çıkan tabloda, tüm sütunlarda bulunanları içeren böyle bir satır kümesi seçiyoruz. Böyle bir seçim için birkaç olası seçenekle, kapsamı oluşturan satırlarda minimum harf sayısı olan seçenek tercih edilir.

Örneğin devamı

Tablonun minimum kapsamı, ilgililere karşılık gelen satırlardan oluşur. Sonra MDNF şu forma sahiptir:

Quine'in yönteminde, Kısaltma oluşturma aşamasında mini terimlerin tam bir ikili karşılaştırma ihtiyacı ile ilişkili önemli bir rahatsızlık vardır. DNF. 1956'da McCluskey, Quine yönteminin ilk aşamasının miniterm karşılaştırmalarının sayısını önemli ölçüde azaltacak bir modernizasyonunu önerdi.

McCluskey yönteminin fikri aşağıdaki gibidir. Tüm mini terimler ikili sayılar olarak yazılır, örneğin 1010 gibi. Bu sayılar sayıdaki birim sayısına göre gruplara ayrılır yani i-inci grup kaydında i birimi olan sayıları içerir. Yapıştırmaya uygun mini terimler yalnızca bir kategoride birbirinden farklı olduğundan, yalnızca sayıca bitişik gruplar arasında ikili karşılaştırma yapılır. Sıfırdan daha yüksek bir ranktan mini terimler oluşturulduğunda, hariç tutulan değişkenlere karşılık gelen rakamlara bir tire yerleştirilir.

Örnek

İşlev için MDNF'yi bulalım:

Gruplara göre 4. sıradaki mini terimler

Tier 3 minitermler

2. sıradaki minitermler

Etiketlenmemiş mini terimler veya basit imalar

Bir etiket tablosu oluşturma

Her iki birincil etki esastır ve minimum kapsamı belirler, yani MDNF forma sahiptir.

ilki için - X 3 X 4;

ikincisi için - X 1 X 3;

üçüncü için - X 2 X 3;

dördüncü için - X 1 X 2 X 4;

beşinci için - X 1 X 2 X 4;

Minimum DNF şöyle görünür:

Karnot harita yöntemini diğer fonksiyon minimizasyon yöntemleriyle karşılaştırarak, ilkinin manuel yürütme için en uygun olduğu sonucuna varabiliriz. Zaman kendi emeğiyleönemli ölçüde azalır (yapışkanların görsel temsili nedeniyle). Bu yöntemin yazılım uygulamasının kendi zorlukları vardır. evet uygulaması çok zor optimal seçim düzenli dikdörtgenler, özellikle Büyük bir sayı argümanlar.

1.3.5 Belirsiz katsayıların yöntemi

Bu yöntem herhangi bir sayıda argüman için kullanılabilir. Ancak bu yöntem oldukça hantal olduğundan, yalnızca argüman sayısının 5-6'dan fazla olmadığı durumlarda kullanılır.

Belirsiz katsayılar yöntemi, evrensel ve sıfır kümeleri yasalarını ve tekrar yasalarını kullanır. Başlangıçta, tüm katsayılar belirsizdir (dolayısıyla yöntemin adı).

Dört argüman için belirsiz katsayılardan oluşan bir matris oluşturalım. Bu durumda, 16 denklemlik bir sistemimiz olacak.

Sistem bir sonraki sayfada gösterilmektedir.

Sütun vektöründe 0'a karşılık gelen bu satırlardaki tüm 0 katsayılarını eşitleyin. Sonra diğer satırlardaki karşılık gelen katsayıları 0'a eşitleriz. Bu dönüşümlerden sonra sistem aşağıdaki formu alacaktır:

V = 1 VVVVV = 1 VVV V VV = 1 V = 1 VVV = 1 VVVVVV = 1 VVV = 1 VVVVV = 1 VVV = 1

Şimdi, her satırda, minimum rütbenin katsayısını seçip bire ve kalan katsayıları 0'a eşitlemeniz gerekir. Bundan sonra, aynı satırlardan birini bırakarak (tüm katsayılı satırlar) aynı satırları geçiyoruz. 0'a eşit olanlar da üstü çizilir).

= 1 = 1 = 1 = 1 = 1

Şimdi katsayılara karşılık gelen bağlaçları yazalım birimlere eşit. Minimum DNF'yi alacağız.

F(X 1 X 2 X 3 X 4) = X 1 X 3 V X 2 X 3 V X 3 X 4 V X 1 X 2 X 4 V X 1 X 2 X 4 .

Böylece, minimum DNF'yi birkaç şekilde elde ettik.Her durumda, aynı olduğu ortaya çıktı, yani, işlevi en aza indirmek için açıklanan yöntemlerden herhangi biri kullanılabilir. Ancak bu yöntemler hem MDNF bulma prensibi açısından hem de uygulama süresi açısından birbirinden önemli ölçüde farklılık göstermektedir. Manuel hesaplamalar için Carnot harita yöntemi çok uygundur. Görseldir, gerektirmez rutin işlemler ve düzenli dikdörtgenlerin en uygun düzenini seçmek zor değildir. Bu yöntemin makine uygulaması, dikdörtgenlerin en uygun konumunu bulma ihtiyacı nedeniyle karmaşıktır. Doğal olarak, diğer yöntemlerin (Quine yöntemi, Quine-McCluskey yöntemi, belirsiz katsayılar yöntemi) kullanılması manuel hesaplamalar için uygun değildir. Çok sayıda tekrarlayan basit işlem içerdiklerinden makine uygulaması için daha uygundurlar.

Görev 2.

2.1 Quine yöntemi için algoritma şeması

1. Başlat.

2. DSNF matrisini girin orijinal işlev.

3. i-th (i=1,m-1: m, DSNF'deki satır sayısıdır) ve j-th (j=i+1, m) satırlarını yapıştırmak için kontrol edin. Çizgiler yapıştırılmışsa 6. adıma, aksi halde 5. adıma gidin.

4. Daha önce bu dizelerin birbirine yapıştırıldığı değişkeni '*' sembolüyle işaretlemiş olan bir dizi basit implikant oluşturun.

5. 2. adıma gidin.

6. Son diziye başka bir diziyle birbirine yapışmayan diziyi yazın.

7. Adım 2'ye gidin.

8. Ortaya çıkan matrisin çıktısı.

Lyapunov'un notasyonundaki algoritmanın mantıksal şeması

V H V 1 Z 1 ­ V 2 ¯ V 3 V 4 VK

V H başlangıçtır.

V 1 – orijinal işlevin DSNF matrisini girin.

V 2 - daha önce bu dizelerin birbirine yapıştırıldığı değişkeni '*' sembolü ile işaretlemiş olan bir dizi basit implikant oluşturun.

V 3 - son diziye yazmak için başka bir dizeyle yapıştırılmamış bir dize.

V 4 - ortaya çıkan matrisin çıktısı.

Z 1 - çizgiler yapıştırılmışsa 3. adıma gidin, aksi takdirde 5. adıma gidin.

VK sondur.

Algoritmanın grafik şeması.

Tanım makine prosedürler

Sıkışmış Prosedür(S1, S2: Diz; IndexS1, IndexS2: bayt);

Bu prosedür kendisine iletilen iki maddeyi yapıştırır. Cümleler S1, S2 parametrelerinde belirtilmiştir. IndexS1, IndexS2 endeksleri, ana çalışma dizisindeki bu tümcelerin endekslerini belirler. İşlemin algoritması şu şekildedir: ilk olarak yapıştırılan karakter sayısı aranır. Bunlardan 0 varsa, bunlar aynıdır ve bunlardan yalnızca biri son diziye yazılır. 1 ise, bu iki ayrımın yapıştırıldığı karakterin yerini belirleyin ve bu karakteri '*' ile değiştirin. Elde edilen tüm sonuçlar REZ dizisine girilir.

Programın diğer tüm işlevleri ve prosedürleri dizilerdeki işlemlerle ilgilidir, yani doğrudan dizilerle ilgili değildir. Bu method MDNF'yi bulmak. Bu nedenle, onları tanımlamanın bir anlamı yoktur.

2.2 Petrik yöntemi için algoritma şeması

1. Başlat.

2. Orijinal fonksiyonun DSNF matrisini ve Quine yöntemiyle elde edilen basit implikantları girin.

3. Bir etiket tablosu oluşturun.

4. Etiketler tablosuna göre, her biri içinde bulunan bu imaların bir koleksiyonu olan bir ayrımlar birleşimi oluşturun. bu sütun etiketleri var.

Mantık fonksiyonlarının minimizasyonu, devre öğrenme sürecindeki tipik görevlerden biridir. Bu nedenle böyle bir yazının olması gereken bir yer olduğunu düşünüyorum, umarım beğenirsiniz.

Bu neden gerekli?

Mantıksal bir fonksiyonun karmaşıklığı ve dolayısıyla onu uygulayan devrenin (devrenin) karmaşıklığı ve maliyeti, sayı ile orantılıdır. mantıksal işlemler ve değişkenlerin oluşum sayısı veya olumsuzlamaları. Prensip olarak, herhangi bir mantıksal işlev, mantık aksiyomları ve teoremleri yardımıyla doğrudan basitleştirilebilir, ancak kural olarak, bu tür dönüşümler hantal hesaplamalar gerektirir.

Ayrıca, Boolean ifadelerini basitleştirme işlemi algoritmik değildir. Bu nedenle, işlevi daha basit, hızlı ve doğru bir şekilde basitleştirmeyi mümkün kılan özel algoritmik minimizasyon yöntemlerini kullanmak daha uygundur. Bu tür yöntemler arasında örneğin Quine yöntemi, Carnot eşlem yöntemi, dolaylı test yöntemi, örtük matris yöntemi, Quine-McCluskey yöntemi vb. bulunur. Bu yöntemler, özellikle mantıksal bir fonksiyonun minimizasyonu olmak üzere yaygın uygulama için en uygundur. Karnaugh haritalarını kullanarak. Carnot eşleme yöntemi, değişken sayısı altıyı geçmediğinde görünürlüğü korur. Argüman sayısının altıdan fazla olduğu durumlarda, genellikle Quine-McCluskey yöntemi kullanılır.

Belirli bir mantıksal işlevi en aza indirme sürecinde, genellikle elektronik devreler kullanarak minimal formunu uygulamanın hangi temelde daha verimli olacağı dikkate alınır.

Karnaugh Haritaları ile Boole İşlevlerini En Aza İndirme

Carnot Haritası - grafik yolu büyük ifadelerle çalışmanın göreceli kolaylığını ve potansiyel yarışların ortadan kaldırılmasını sağlayan anahtarlama (boolean) işlevlerinin en aza indirilmesi. İkili eksik yapıştırma ve temel absorpsiyon işlemlerini temsil eder. Karnaugh haritaları, buna göre yeniden düzenlenmiş bir fonksiyon doğruluk tablosu olarak kabul edilir. Karnaugh haritaları, n boyutlu bir boole küpünün belirli bir düz açılımı olarak düşünülebilir.

Karnot haritaları 1952'de Edward W. Veitch tarafından icat edildi ve 1953'te Bell Laboratuarlarında fizikçi olan Maurice Karnot tarafından dijital elektronik devrelerin basitleştirilmesine yardımcı olmak için geliştirildi.

Boolean değişkenleri doğruluk tablosundan Karnaugh haritasına aktarılır ve sonraki her sayının bir öncekinden yalnızca bir basamak farklı olduğu Gray kodu kullanılarak sıralanır.

SDNF veya SKNF olarak temsil edilen mantıksal işlevleri en aza indirmenin ana yöntemi, ikili eksik yapıştırma ve temel absorpsiyon işlemidir. İkili yapıştırma işlemi, biri hariç tüm değişkenler için oluşumları (doğrudan ve ters) aynı olan aynı değişkenleri içeren iki terim (üye) arasında gerçekleştirilir. Bu durumda, biri hariç tüm değişkenler parantez dışına alınabilir ve parantez içinde kalan bir değişkenin doğrudan ve ters oluşumları birbirine yapıştırılabilir. Örneğin:

Absorpsiyon olasılığı bariz eşitliklerden kaynaklanmaktadır.

Bu nedenle, SDNF ve SKNF'yi en aza indirmedeki ana görev, yapıştırma ve ardından absorpsiyon için uygun terimlerin aranmasıdır. büyük formlar oldukça zor bir görev olabilir. Karnaugh haritaları, bu tür terimleri bulmak için görsel bir yol sağlar.

Bilindiği gibi, boole fonksiyonları SDNF veya SKNF olarak temsil edilen N değişken, 2N farklı terim içerebilir. Tüm bu elemanlar topolojik olarak N-boyutlu bir kübe eşdeğer bir yapı oluşturur ve bir kenarla birbirine bağlanan herhangi iki terim yapıştırma ve soğurma için uygundur.

resim gösterir basit masa iki değişkenli bir fonksiyon için doğruluk, bu tabloya karşılık gelen 2 boyutlu bir küp (kare) ve ayrıca SDNF üyeleri ile 2 boyutlu bir küp ve terimleri gruplamak için eşdeğer bir tablo:

Üç değişkenli bir fonksiyon söz konusu olduğunda, üç boyutlu bir küple uğraşmak gerekir. Bu daha karmaşık ve daha az görsel ama teknik olarak mümkün. Örnek olarak, şekil, üç değişkenli bir Boole fonksiyonu ve karşılık gelen küp için doğruluk tablosunu göstermektedir.

Şekilden görülebileceği gibi, üç boyutlu durum için terimlerin daha karmaşık konfigürasyonları mümkündür. Örneğin, bir küpün aynı yüzüne ait dört terim, iki değişkenin absorpsiyonu ile bir terimde birleştirilir:

AT Genel dava Hiperküpün bir K boyutlu yüzüne ait 2K terimin bir terime yapıştırıldığını, K değişkenlerin emildiğini söyleyebiliriz.

Çok sayıda değişkenin Boole fonksiyonlarıyla çalışmayı basitleştirmek için aşağıdaki uygun numara önerildi. Bir terimler yapısı olan küp, şekilde görüldüğü gibi bir düzlem üzerine açılmaktadır. Böylece Boolean fonksiyonların ikiden fazla değişkenli düz bir tablo şeklinde temsil edilmesi mümkün hale gelir. Aynı zamanda tablodaki terim kodlarının sırasının (00 01 11 10) terimlerin sırasına karşılık gelmediği unutulmamalıdır. ikili sayılar, ve tablonun en uç sütunlarında bulunan hücreler birbirine bitişiktir.

Benzer şekilde, dört, beş veya daha fazla değişkenli fonksiyonlarla çalışabilirsiniz. N=4 ve N=5 için tablo örnekleri şekilde gösterilmiştir. Bu tablolar için, bitişik hücrelerin, uç sütunların karşılık gelen hücrelerinde ve üst ve üst sütunların karşılık gelen hücrelerinde bulunanlar olduğu unutulmamalıdır. Sonuç olarak. 5 veya daha fazla değişkenli tablolar için, 4x4 karelerin üçüncü boyutta neredeyse birbirinin üzerinde olduğu, bu nedenle iki bitişik 4x4 karenin karşılık gelen hücrelerinin bitişik olduğu ve karşılık gelen terimlerin birbirine yapıştırılabileceği de dikkate alınmalıdır.

Herhangi bir sayıda değişken için bir Karnot haritası çizilebilir, ancak en fazla beş değişkenle çalışmak uygundur. Aslında Karnaugh haritası 2 boyutlu biçimde derlenmiş bir doğruluk tablosudur. İçinde Gray kodunun kullanılması nedeniyle, üst sıra alta, sağ sütun sola bitişiktir, yani. Karnot haritasının tamamı bir şekil simidine (çörek) katlanır. Bir satır ve bir sütunun kesiştiği noktada doğruluk tablosundan karşılık gelen değer yazılır. Harita doldurulduktan sonra simge durumuna küçültmeye başlayabilirsiniz.

Minimum DNF'yi elde etmek gerekirse, o zaman Haritada yalnızca bir içeren hücreleri, CNF gerekiyorsa, sıfır içeren hücreleri dikkate alırız. Minimizasyonun kendisi aşağıdaki kurallara göre gerçekleştirilir (örneğin, DNF):

Daha sonra ilk alanı alıyoruz ve bu alan içerisinde hangi değişkenlerin değişmediğini görüyoruz, bu değişkenlerin birleşimini yazıyoruz, eğer değişmeyen değişken sıfır ise bunun üzerine bir inversiyon koyuyoruz. Bir sonraki alanı alıyoruz, ilkiyle aynı şeyi yapıyoruz ve tüm alanlar için böyle devam ediyoruz. Bölgelerin bağlaçları bir ayrılma ile birleştirilir.
Örneğin (2 değişkenli Haritalar için):

CNF için her şey aynıdır, sadece sıfırlı hücreleri dikkate alırız, aynı bölgedeki değişmeyen değişkenleri ayrıklarda birleştiririz (birim değişkenlerin üzerine ters çevirmeler koyarız) ve bölgelerin ayrılmalarını bir birleşimde birleştiririz. Bu minimizasyonu tamamlar. Dolayısıyla Şekil 1'deki Karnaugh haritası için DNF formatındaki ifade şöyle görünecektir:

CNF formatında:

1.6. Pascal'da Kümeleri Kullanma

2. Genel cebir unsurları

2.1. Setlerdeki işlemler

2.2. Galois permütasyon grubu

2.3. Kümelerin cebiri (Cantor cebiri)

2.4. Cebirsel sistemler. kafesler

2.5. Bileşenlere göre kümeleri belirtme

2.6. Küme Cebirinde Denklem Çözme.

3. Kombinatorik Elemanları

3.1. kombinatoryal hesaplamalar

3.2. Kombinatoriğin temel kavramları

3.3. Konaklama

3.4. permütasyonlar

3.5. kombinasyonlar

3.6. Pascal üçgeni.

3.7. Binom teoremi

3.8. Birleşimsel denklemleri çözme

4. Grafik teorisinin temel kavramları

4.1. Grafikleri ayarlamanın yolları

4.2. Grafik Özellikleri

4.3. Grafiklerde görev kavramı

4.4. Hanoi kulesi sorunu

5. Anahtarlama işlevleri ve bunları ayarlamak için yöntemler

5.1. Anahtarlama fonksiyonları kavramı

5.2. İkili anahtarlama işlevleri ve bunların nasıl ayarlanacağı

5.3. Temel ikili mantıksal işlemler

5.4. Anahtarlama devreleri kavramı ve anahtarlama fonksiyonlarının teknik uygulaması

5.5. Grafik Teorisinde Boole İşlemlerini Kullanma

6. Temel ikili anahtarlama işlevleri ve anahtarlama işlevleri sistemlerinin işlevsel bütünlüğü

6.1. Tek değişkenli temel anahtarlama fonksiyonları

6.2. İki değişkenli temel anahtarlama (mantıksal) fonksiyonları

6.3. Anahtarlamalı işlev sistemlerinin işlevsel bütünlüğü

6.4. Anahtarlama fonksiyonlarının temsili için temeller

6.5. Ondalık bir sayı ile verilen bir pf'nin özelliklerini analiz etme ve belirleme örneği

7. Boole cebrinin temel yasaları ve anahtarlama fonksiyonlarının dönüşümü

7.1. Anahtarlama Fonksiyonlarının Boole Cebirinin Temel Kanunları

7.2. Eşdeğer dönüşümler. Anahtarlama fonksiyonları cebir formüllerinin basitleştirilmesi

7.3. Anahtarlama fonksiyonlarının temsil biçimlerinin dönüştürülmesi

8. Anahtarlama fonksiyonlarının minimizasyonu

8.1. Anahtarlama işlevlerini en aza indirme hedefi

8.2. Minimizasyonda kullanılan temel kavramlar ve tanımlar

8.3. Anahtarlama Fonksiyonlarını En Aza İndirmek İçin Analitik Yöntemler

8.4. Karnot haritaları ile anahtarlama fonksiyonlarının minimizasyonu

8.5. Çalışma ve Yasak Kümelerin Bitsel Karşılaştırma Yöntemi

Çalışan ve yasaklanmış sekizli kümelerin bit düzeyinde karşılaştırmasına dayalı anahtarlama işlevlerinin minimizasyonu.

8.6. Temelde verilen anahtarlama fonksiyonlarının minimizasyonu (, ve, değil)

8.7. Anahtarlama fonksiyonları sistemlerinin minimizasyonu

8.8. Belirsiz katsayılar yöntemi ile anahtarlama fonksiyonlarının minimizasyonu

9. Otomat kavramı ve matematiksel açıklaması

9.1. Sonlu otomata teorisinin temel tanımları

9.2. Sonlu deterministik otomatların açıklaması

9.3. Sonlu otomatların teknik yorumu kavramı

9.4. Belirli bir temelde kombinasyonel otomatların sentezi

9.5. boole türevi

9.6. Birleşimsel otomat ve gecikmeye dayalı temel bellek otomatları

9.7. Otomatın sentezi - dizi tanıyıcı

10. Kodlama teorisinin unsurları

10.1. kodlama kavramı

10.2. Çeşitli kodların temeli olarak sayı sistemleri

10.3. Hata düzeltici kodlama kavramı

10.4. Hamming kodlama

10.5. Döngüsel kodlar ve polinomların çarpımı ve bölünmesinin matematiksel aparatını kullanarak kodlama. imza analizi

10.6. Kriptografik bilgi koruma kavramı

10.7. Bilgi sıkıştırma kavramı

8.3. Anahtarlama Fonksiyonlarını En Aza İndirmek İçin Analitik Yöntemler

Quine yöntemi.

Yöntem, mümkünse tüm bileşenlerin (SDNF üyeleri) ikili olarak karşılaştırılmasına ve yapıştırılmasına dayanmaktadır. Bunu yapmak için, her bir bileşen sonrakilerle karşılaştırılır, bu da ima edenin alınmasına yol açar. Ortaya çıkan sonuçlar tekrar karşılaştırılır ve mümkünse birbirine yapıştırılır, vb. kalan imalar artık kendilerini yapıştırmaya ödünç vermeyene kadar. Bunlar basit çıkarımlardır, bunların ayrımı kısaltılmış bir DNF'dir.

Sıralama için bileşenleri, ters çevrilmemiş değişkenlerin sayısına göre gruplara ayırmanız önerilir. Bu durumda, üstten başlayarak sonraki her bir bileşen, yalnızca alta bitişik grubun bileşenleri ile, tersine çevrilmemiş değişkenlerin sayısı bir fazla olacak şekilde karşılaştırılır.

SDNF tarafından verilen bir anahtarlama işlevi olsun:

Bileşenleri, ters çevrilmemiş değişkenlerin sayısına göre gruplara ayıralım.

Grup numarasının Romen rakamı, ters olmayan değişkenlerin sayısına karşılık gelir. Yapıştırılacak bileşenleri gösteren çizgiler çizin. Yapıştırmanın sonucu her zaman orijinal bağlaçların (özellikle bir bileşen) ortak bir parçası olan temel bir bağlaçtır.

Ortaya çıkan imalar aynı zamanda yapıştırmaya da izin verir ve sonuç aynı ima eder
.

Daha fazla yapıştırma imkansızdır, bu nedenle ortaya çıkan sonuçlar basittir ve kısaltılmış DNF şu şekildedir:

İlk etap tamamlandı. İkinci aşamada, gereksiz asal implikantları ortadan kaldırmak gerekir. Bu, özel bir Quine örtük tablosu (kapak tablosu) kullanılarak yapılır. Tablo satırları, anahtarlama fonksiyonunun basit anlamları ile işaretlenmiştir, yani. kısaltılmış DNF'nin üyeleri ve sütunlar birimin bileşenleridir, yani. SDNF anahtarlama fonksiyonunun üyeleri.

Daha önce belirtildiği gibi, basit bir dolaylı, eğer kendi parçasıysa, birimin bazı bileşenlerini emer. Belirli bir basit implikantın bir satırının ve birim bileşenleri olan sütunların kesişimindeki ilgili tablonun ilgili hücresi, örneğin bir "+" işaretiyle işaretlenir. Minimum DNF'ler, olası tablodan aşağıdaki gibi oluşturulur:

1) yalnızca bir çarpıya sahip olan dolaylı tablonun sütunları aranır; bu çarpılara karşılık gelen basit implikantlara temel implikantlar denir ve anahtarlama fonksiyonunun sözde çekirdeğini oluşturur. Çekirdek zorunlu olarak minimum DNF'ye dahil edilir;

2) dahil edilen matrisin kalan sütunlarını haçlarla kaplayacak bir dizi basit implikant seçmek için çeşitli seçenekler göz önünde bulundurulur ve minimum toplam harf sayısına sahip seçenekler seçilir.

Fonksiyonumuzun çekirdeği (Tablo 35) implikants'tır.
ve x 1 x 2 x 3, yani. işlevin tek bir çıkmaz ucu ve minimum DNF'si vardır:

Tablo 35

Quine dolaylı tablo

		Bileşenler 1 (SDNF üyeleri)
	imalar

İma edenlerin zaten kapsadığı bileşenleri kapsadığı için, x 2 x 3 x 4'ün gereksiz olduğu görülebilir.
, x 1 x 2 x 3 .

Bir çizgideki çarpı sayısı 2'nin katıdır; ayrıca, bunun N=2 n - k'ye eşit olduğundan emin olunabilir, burada k, asal implikanttaki harf sayısıdır, n, fonksiyonun bağlı olduğu değişkenlerin sayısıdır.

SDNF başlangıçta belirtilmemişse, örneğin zaten bildiğimiz yöntemler kullanılarak elde edilmelidir.

Açıktır ki, geniş kapsamlı tablolar için, minimum sayıda harfle varyantları görsel olarak tanımlamanın zor olduğu açıktır. Bu nedenle, tüm çıkmaz DNF'leri, sözde birleştirici temsilini kurarak, dolaylı bir tablodan elde etmeyi mümkün kılan Petrik yöntemi kullanılır. Bunu yapmak için, tüm asal imalar farklı harflerle gösterilir (Tablo 35'te A, B, C) ve daha sonra her sütun için tablonun satırlarını gösteren tüm harflerden bir ayrım yapılır ve bu sütunla kesişimi aşağıdaki gibidir. bir çarpı ile işaretlenmiştir. İç içe matrisin birleştirici temsili, tüm sütunlar için oluşturulmuş ayrımların bir birleşimi olarak oluşturulur. Tüm ilişkiler, örtük tablonun birleştirici temsiline uygulanabilir. boole cebiri basitleştirmek için anahtarlama işlevleri. Köşeli parantezleri açtıktan ve olası tüm absorpsiyonları gerçekleştirdikten sonra, her biri bir çıkmaz DNF'nin tüm anlamlarını içeren bir bağlaçların ayrılması elde edilir.

Bu, bir çıkmaz DNF'nin iki basit ima içerdiği anlamına gelir (
ve aynı zamanda C=x 1 x 2 x 3) ve şu şekildedir:

Quine-McCluskey yöntemi.

Yöntem, Quine'in yönteminin bilgisayar odaklı resmileştirilmesidir. Biçimlendirme, birimin bileşenlerinin (SDNF üyeleri) ikili sayılarıyla yazılmasından oluşur. Tüm sayılar, ikili sayıdaki birlerin sayısına göre örtüşmeyen gruplara ayrılır. Bağlama sadece komşu gruplar arasında yapılır. Tasfiye kategorisi "-" ("tire") işaretiyle belirtilir. Elde edilen implikantlardan başka gruplar, tirenin aynı düzenlemesi dikkate alınarak oluşturulur. Bu imaların gösterimine genelleştirilmiş kodlar denir. Mantıksal fonksiyon verilsin

111101001000110.

Bu birim bileşenlerini birim sayısına göre gruplandıralım:

Daha fazla yapıştırma mümkün değildir. Minimum DNF'nin bulunması, daha sonra ilgili tabloya göre gerçekleştirilir (Tablo 36):

Bu, çıkmaz DNF'lerin her birinin üç basit ima içerdiği ve şu forma sahip olduğu anlamına gelir:

(iki inversiyon);

(üç inversiyon).

Tablo 36

Quine-McCluskey dolaylı tablo

	imalar			birimlerin bileşenleri

İki imanın bir tire ile yapıştırılmasının ancak uygun şekilde yerleştirilmişlerse mümkün olduğunu unutmayın, örneğin:

Elde edilen TDNF'den herhangi birini seçebilir ve ilkini daha az sayıda ters çevirmeyi hesaba katabilirsiniz.

Blake-Poretsky yöntemi.

Yöntem, genelleştirilmiş yapıştırma yasasını kullanarak Quine ve Quine-McCluskey yöntemlerinde olduğu gibi SDNF'den değil, keyfi DNF'sinden bir Boole işlevinin azaltılmış DNF'sini elde etmeye izin verir. Yöntem, aşağıdaki iddiaya dayanmaktadır: bir Boole işlevinin keyfi bir DNF'sinde, genelleştirilmiş yapıştırmanın tersi olan tüm olası işlemler gerçekleştirilirse ve ardından tüm absorpsiyonlar gerçekleştirilirse, sonuç işlevin azaltılmış bir DNF'si olacaktır. .

Bir DNF işlevi verilsin:

x 1 değişkenine göre genelleştirilmiş yapıştırma yasasının birinci ve ikinci bağlaçlara uygulanabileceği görülebilir; elde ederiz:

Benzer şekilde birinci ve üçüncü bağlaçlar için:

şunlar. her şey olduğu gibi kalır!

İkinci ve üçüncü bağlaçlar, x 2'de genelleştirilmiş yapıştırmaya izin verir:

DNF'ye geçelim:

Bağımsızlık (tekrar) ve emilim yasasını uyguladıktan sonra şunu elde ederiz:

Genelleştirilmiş yapıştırma ve emilim uygulama girişimleri herhangi bir sonuç vermez. Bu nedenle, azaltılmış bir DNF işlevi elde edilir.

Tablo 37

Blake-Poretsky yöntemini gösteren impliant tablosu

imalar			Özellik Setleri ve anlamı

Böylece, çalışma (birim) kümeleri, örneğin, üç basit ima ile kapsanabilir,
,
,
. Çekirdek imaları içerir
,
. O zaman çıkmaz DNF'ler şu şekle sahiptir:

(tersine çevirme sayısı açısından daha iyi).