Sayısal otomatlar tasarlanırken, ekonomik devreler elde etmeyi mümkün kılan Boolean fonksiyonlarını en aza indirme yöntemleri yaygın olarak kullanılmaktadır. Genel görev Boole fonksiyonlarının minimizasyonu formüle edilebilir Aşağıdaki şekilde: mümkün olan minimum sayıda harf içeren biçimde belirli bir boole işlevi için analitik bir ifade bulun.

Minimizasyon yöntemleri, yapıştırma işlemine dayanır (bitişik ikili sayıları birleştirmek için bir algoritma):

burada A temel bir bağlaçtır.

İfadede, terimler bitişiktir ikili sayılar birbirinden sadece bir hane ile farklılık gösterir. İki bitişik sayı üzerinde bir yapıştırma işlemi gerçekleştirirken, bir sayıyı diğerinden ayıran kümeden bir değişken, dört çift bitişik sayı - iki değişken, sekizden fazla - üç değişken vb.

Bir Boole işlevinin minimum ayırıcı normal biçimi (MDNF), en az sayıda harf içeren bir DNF'dir (belirli bir Boole işlevini temsil eden diğer tüm DNF'lere göre).

Fonksiyonları simge durumuna küçültün, yani en basit ifadeyi bulun. orijinal işlev Yapabilmek farklı yöntemler... Hepsi pratik olarak sadece ilk aşamada farklılık gösterir - kısaltılmış bir DNF elde etme aşaması. Ne yazık ki, MDNF arayışının her zaman bir tür çözüm numaralandırmasıyla ilişkili olduğuna dikkat edilmelidir. Bunlardan bazılarına bir göz atalım.

Karnot Matrisini Kullanarak Karmaşık Boole İfadelerini En Aza İndirme

Birleşim algoritmasını uygulamak için, tüm zorunlu bileşenler kümesinden mükemmel bir ayrıştırmada gereklidir. normal biçim mantık cebirinin bitişik işlevlerini bulmak. Komşu bileşenleri bulmak için Carnot matrisleri, komşu sayıların bir kafesi, komşu bileşenlerin tabloları kullanılır.

2, 3, 4, 5 ve 6 değişkenli kümelerde FAL'yi en aza indirmek için Carnot matrislerinin kullanılması tavsiye edilir. Karnot matrislerindeki sütun numaraları en az anlamlı bitleri, satır numaraları ise kümelerin en anlamlı bitlerini oluşturur. Hücre numaraları, satır ve sütun numaralarından oluşur ve değişken kümelerine karşılık gelir.

4 değişkenli kümelerde Boole cebiri işlevi için Carnot matrisini düşünün (Tablo 1).

Tablo 1. Karnot matrisi

Bu matristeki sütunlar ve satırlar, ikili bitişik sayılarla gösterilir: 00-0I-II-I0. Bu nedenle, yatay ve dikey olarak bitişik hücrelerin yanı sıra satır ve sütunlardaki en dıştaki hücrelerin sayıları bitişik sayılardır, örneğin:

sayılar içeren hücreler ve;

sayılar içeren hücreler;

sayılar içeren hücreler;

sayıları olan hücreler.

Carnot matrisini kullanarak, mükemmel ayırıcı normal formda verilen mantık cebirinin işlevini en aza indirmek için şunları yapmak gerekir: gerekli bileşenlere karşılık gelen hücrelere birimler yazarak Carnot matrisini hazırlamak, hücreleri "alt küplerdeki"lerle birleştirmek ", mantık cebirinin küçültülmüş fonksiyonunu ayrık normal formda yazın.

"Alt küpler" birleşir:

• - bir değişken hariç tutularak, bitişik sayılar olan sayılara sahip iki hücre;
• - iki değişken hariç dört hücre (satır, sütun, kare, köşe hücreleri);
• - üç değişken hariç sekiz hücre (iki bitişik veya aşırı satır (sütun)).

Mümkün olduğunca çok değişkenin hariç tutulmasını sağlamak için "alt küplerin" boyutu mümkün olduğunca büyük olmalı ve sayıları mümkün olduğunca az. Bu amaçla, bir ve aynı hücre, farklı “alt küpler” de dahil olmak üzere birkaç kez kullanılabilir. Mantık cebirinin küçültülmüş işlevindeki terimlerin sayısı, alt küplerin ve alt küplerde birleştirilmeyen hücrelerin sayısına eşittir.

Mantık cebirinin aşağıdaki işlevini en aza indirmek gerekli olsun:

Bu formüle göre doldurulan Karnot matrisi tablo 2 şeklinde gösterilebilir:

Tablo 2. Karnot matrisi

Bu matriste iki iki hücreli alt küp ayırt edilebilir. Minimizasyon sonucunda elde ettiğimiz sonraki işlev mantık cebirleri:

Quine'ın yöntemi

Mantıksal bir fonksiyonun minimum formunu elde etmek için, fonksiyonun mükemmel ayırıcı normal formunda (SDNF) olası tüm yapıştırma ve absorpsiyonun gerçekleştirilmesi gerekir, böylece sonuç fonksiyonun indirgenmiş bir ayırıcı normal formu olacaktır. (DNF) Kısaltılmış DNF Genel dava minimizasyonun ikinci aşamasında tanımlanması gereken gereksiz basit imalar içerebilir.

İlk aşamada DNF şeklinde verilen fonksiyondan kısaltılmış DNF'ye geçiş gerçekleştirilir. Yöntemin özü, tutarlı uygulama tüm olası yapışmalar ve ardından tüm absorpsiyonlar, bu da azaltılmış bir DNF'ye yol açar. Yöntem, mükemmel DNF'ye uygulanabilir. Absorpsiyon ilişkisinden, keyfi bir temel ürünün onun herhangi bir parçası tarafından emildiği sonucu çıkar. Bunu kanıtlamak için, keyfi bir basit impimant p = x olduğunu göstermek yeterlidir. i1 x i2... x içinde elde edilebilir. Gerçekten de, genişletme işlemini p'ye uygulamak (yapıştırma işleminin tersi):

tüm eksik değişkenler üzerinde x ik, ..., x ben orijinal f fonksiyonundan, birliğin bileşenlerinin S kümesini elde ederiz. Tüm bileşenleri S'den yapıştırırken, p olası p'yi elde ederiz. İkincisi açıktır, çünkü yapıştırma işlemi açma işleminin tersidir. Bileşenlerden oluşan S kümesi, p dolaylı olduğu için bir f fonksiyonunun mükemmel bir DNF'sinde mutlaka mevcuttur.

Yapıştırmanın bir sonucu olarak, n-1 düzeyinde bir bağlaç elde edilir ve bağlaçlar orijinal ifadede kalır ve SDNF'nin diğer üyeleriyle karşılaştırmaya katılır. Böylece terimlerin sıralamasını azaltmak mümkündür.

İkili karşılaştırmaya katılmayan terimler olduğu sürece yapıştırma ve emilim yapılır. Yapıştırma işleminden geçen terimler işaretlenir. İşaretlenmemiş terimler basit imalardır ve kısaltılmış DNF'ye dahil edilmiştir. Sıra n-1'in tüm işaretli bağlaçları, n-2 sıra terimlerini elde etmek için tekrar yapıştırılır ve bu, işaretlenmemiş bağlaçların sayısı 2'den büyük olana kadar devam eder. İlk aşamanın bir sonucu olarak, indirgenmiş bir DNF elde edilir.

Ortaya çıkan mantıksal ifade her zaman minimal değildir. İkinci aşamada, kısaltılmış DNF'den çıkmaz DNF'lere geçerler ve aralarından MDNF'yi seçerler.

Çıkmaz DNF'lerin oluşumu için, satırları kısaltılmış DNF'nin basit göstergeleri ile işaretlenen ve sütunlar orijinal SDNF'nin biriminin bileşenleri olan bir örtük tablo (matris) oluşturulur. Her basit implikantın karşısındaki satırda, 1 değerini aldığı kümelerin (birliğin bileşenleri) altına bir etiket konur.

Asal sayıların toplam sayısından, gereksiz olanlar hariç, minimum sayılarını seçmek gerekir. Çıkmaz formların oluşumu ve minimum kapsamın seçimi, zorunlu basit imaların, yani belirli bir başlangıç ​​kümesini kapsayanların (ve sadece onlar) tanımlanmasıyla başlar. Mantıksal bir işlevi en aza indirme örneğini düşünün:

f SDNF = V (1,2,5,6,7) = x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3

1 2 3 4 5

Yapıştırma işlemini gerçekleştirelim:

• 1 - 3 (x 1 ) x 2 x 3 1
• 2 - 4 (x 1 ) x 2 x 3 2
• 3 - 5 (x 2 ) x 1 x 3 3
• 4 - 5 (x 3 ) x 1 x 2 4

Yapıştırmanın ilk adımını gerçekleştirmenin bir sonucu olarak, dört yeni bağlaç elde ediyoruz; basit bir anlam tanımlanmadı. Ortaya çıkan bağlaçlar artık birbirine yapışmaz ve kısaltılmış bir DNF oluşturur.

f kısaltılmış SDNF = x 2 x 3 + x 2 x 3 + x 1 x 3 + x 1 x 2

Zorunlu basit imaları belirlemek ve bunlara dayalı olarak minimum kapsamı formüle etmek için bir ima tablosu oluşturulmuştur (Tablo 3). Basit imalar, ima edilen tablonun satırlarına yazılır ve bileşenler sütunlarda birdir. Basit ima, bağlamı kapsıyorsa bir yıldız işareti kullanılır.

Tablo 3. Etki tablosu

	x 1 x 2 x3	1 x 2 x3	x 1 x 2 x3	x 1 x 2 x3	x 1 x 2 x3

Yalnızca bileşenleri kapsadıkları için basit imalar gereklidir ve asgari teminat kapsamına dahildir. Geriye bir tane ortaya çıkmamış bileşen var. 1 x 2 x 3 kalan iki basit imadan biri tarafından kapsanabilir. Bu, iki çıkmaz formla sonuçlanır.

Blake-Poretsky yöntemi

Yöntem, kişinin keyfi DNF'sinden bir Boole fonksiyonu f'nin indirgenmiş bir DNF'sini elde etmesine izin verir. Genelleştirilmiş yapıştırma formülünün uygulanmasına dayanarak:

geçerliliğini kanıtlamak kolaydır. Yok canım,

Buradan,

Yöntem aşağıdaki ifadeye dayanmaktadır: bir Boolean fonksiyonunun rastgele bir DNF'sinde, tüm olası genelleştirilmiş yapıştırmaları gerçekleştirirsek ve ardından tüm absorpsiyonları gerçekleştirirsek, sonuç f fonksiyonunun azaltılmış bir DNF'si olacaktır.

Bir örneğe bakalım. Bir Boole işlevi f keyfi bir DNF tarafından verilsin.

f fonksiyonunun kısaltılmış DNF'sini elde etmek için Blake - Poretsky yöntemini kullanmak gereklidir. Genelleştirilmiş yapıştırma yapıyoruz. Orijinal DNF'nin birinci ve ikinci elemanlarının, x 1 değişkenine göre genelleştirilmiş yapıştırmayı kabul ettiğini görmek kolaydır. Yapıştırma sonucunda şunları elde ederiz:

Orijinal DNF'nin birinci ve üçüncü öğeleri, hem x 1 değişkeninde hem de x'te genelleştirilmiş yapıştırmaya izin verir. 2 ... x boyunca yapıştırdıktan sonra 1 sahibiz:

x 2'yi yapıştırdıktan sonra elimizde:

DNF'nin ikinci ve üçüncü öğeleri, x2 değişkenine göre genelleştirilmiş yapıştırmaya izin verir. Yapıştırdıktan sonra şunları elde ederiz:

Son genelleştirilmiş yapıştırmayı gerçekleştirdikten sonra DNF'ye ulaşıyoruz:

Alımları gerçekleştirdikten sonra şunları elde ederiz:

Genelleştirilmiş yapıştırma ve emme işlemini daha fazla uygulama girişimleri sonuç vermez. Sonuç olarak, f fonksiyonunun kısaltılmış bir DNF'sini elde ettik. Ayrıca, minimum DNF'yi bulma sorunu, Quine yönteminde olduğu gibi, dolaylı matris kullanılarak çözülür.

Eksik tanımlanmış FAL'leri en aza indirme

Bazı FAL n değişkenlerini uygulayan bir mantık devresi sentezlenirken, toplam 2 sayısının bazı kümelerinin olduğu ortaya çıkar. n devrenin girişlerinde asla görünemez, o zaman verilen mantık fonksiyonu bu setlerde tanımlanmaz. sonra 2 n değişken kümeleri üç gruba ayrılabilir: işlevin tek bir L değeri aldığı kümeler, sıfır değeri D ve işlevin tanımlanmadığı bir küme grubu N (tanımsız kümeler). Tanımsız kümeler içeren bir FAL, eksik veya kısmen tanımlanmış olarak adlandırılır. Minimizasyonun kalitesini artırmak için tanımsız kümeler kullanılabilir. Bu durumda, tanımsız kümeler (örneğin, Weich ve Karnot haritaları tarafından küçültüldüğünde), hem tekli hem de sıfır kümelerle kontur oluşumuna katılabilir. Bu, daha basit bir minimize edilmiş mantık fonksiyonunun oluşumuna yol açar.

Evrensel bir minimizasyon yöntemi, herhangi bir sayıda değişken için FAL'yi en aza indirmeye izin veren mantık cebirinin yasalarının ve ilişkilerinin kullanılmasıdır.

Fonksiyonların minimize edilmesinde en sık kullanılan işlem yapıştırma işlemidir.

AB + BB = B (A + B) = B.

En yaygın minimizasyon tekniklerinden üçüne bakalım.

1. Mantıksal fonksiyonun birim değerini aldığı dört değişkenli küme sayıları verilsin: f (2,5,6,7,10,12,13,14) = 1.

Bu mantıksal işlevi SDNF'de ifade edelim (bağlaç sembolünü yazmayacağız):

F(0010,0101, 0110, 0111, 1010, 1100, 1101, 1110) =

Minimizasyonun ilk aşamasında, orijinal SDNF, yapıştırma kanunu kullanılarak basitleştirilebilir, sonra şunu elde ederiz:

Bağımsızlık yasası Boole'un mantığında işlediğinden, aynı bileşenin (implicant) diğer bileşenlerle (implicant) birçok kez yapıştırılabileceği gerçeğine dikkat çekiyoruz:

bu nedenle, herhangi bir bileşen çoğaltılabilir.

İkinci aşamada, buna göre Quine tablosunu (Tablo 8) kullanacağız. Bu method minimizasyon adını aldı - Quine yöntemi. Tabloda, sadeleştirmenin ilk aşamasında elde edilen tüm çıkarımlar dikey olarak, orijinal bileşenler ise yatay olarak listelenmiştir. Sekmedeki birim. 8, ima edenin kurucuyu "örttüğü" yerde durur. Gerçek şu ki, bir bileşen, absorpsiyon yasasına göre her zaman ima edilen veya hatta ayrı bir terimle değiştirilebilir:

Tablo 8

Quine'ın tablosunu doldurduktan sonra, hemen hemen her sütunda iki birim bulduk; bu arada, grafikte bir birimin olması yeterlidir. Bu nedenle, mümkünse fazla birimler ortadan kaldırılmalıdır. Birim seçimi, minimum terim sayısı dikkate alınarak yapılır (seçilen birimler gölgelenir). Sonuç olarak, altı yerine sadece üç ima ile başa çıkabileceğiniz ortaya çıktı:

Doğruluk tablolarını kullanarak, MNF'de elde edilen fonksiyonun orijinal fonksiyonun tüm değerlerini yeniden üretip üretmediğini kontrol etmek kolaydır. Genel durumda, minimum terim kriterine göre birkaç çözüm olabileceğine dikkat edin.

2. Daha az değil etkili yol en aza indirmek mantıksal işlevler indeksleri birleştirme yöntemidir. Sunumu için tablo oluşturacağız. 9, olası endeks kombinasyonlarının yazıldığı grafiklerde. Son sütun, işlevin değerlerini içerir. Tablonun analizi, sol sütundan sütun sütun başlar. i, j_code'un ortadan kaldırılması ilkesi aşağıdaki gibidir. Örneğin, i_column'un 23 indeksleri ve j_string, örneğin 3_th kombinasyonu ile kesiştiği noktada, olasıya karşılık gelen bir kod 10 vardır. Bu nedenle, bu sütunda, kod 10'un geçtiği her yerde, yani 2, 3, 10 ve 11. satırlarda, 3. satırdaki fonksiyonun değeri sıfıra eşit olduğu için bu kodlar hariç tutulur. Şimdi 124 indekslerinin bir kombinasyonunu içeren bir sütun alalım. Burada 2. ve 6. satırlarda 010 kodları ve 10. ve 14. satırlarda - 011 kodu kaldı. Bu yapılır çünkü bu kodlar sadece satırlarda bulunur bire eşit bir fonksiyon değeri ile. Aksine, aynı sütunun 110 kodu, hem fonksiyonun tekli değerleri için hem de sıfır değerleri için oluşur.

Tablo 9

Böylece, sıfır fonksiyon değerleri ile biten satırlardaki tüm kodlar otomatik olarak hariç tutulur. Bu kodlar tek bir fonksiyon değeri ile biten satırlara denk geliyorsa onlar da yok sayılır. Yalnızca tek bir işlev değerine sahip satırlarda bulunan kodlar kalır (bu kodlar gölgelenir).

Ayrıca, aşağıdaki kural tarafından yönlendirilirler. Fonksiyonun bir değer alabilmesi için, bire eşit, satır başına yalnızca bir implikantın tek bir değer alması yeterlidir. Her şeyden önce, 2, 6, 10 ve 14. satırlardakilerle örtüşen minimum implikant'ı bırakıyoruz. Ardından, doğal olarak 12. satıra dönüyoruz. Burada, satıra karşılık gelen 011 kodunu bırakıyoruz. Aynı ima, aynı zamanda bir ile biten 13. satırdan da sorumludur. 5. ve 7. satırları dikkate almaya devam ediyor. Onlar için ortak olan şey şudur: Böylece, Quine tabloları temelinde elde edilen sonuçla örtüşen fonksiyonun tüm birim değerlerini üç çıkarımla ele aldık.

3. var grafiksel yol Karnot harita yöntemi olarak adlandırılan yapıştırma (Tablo 10'da sunulmuştur). Bitişik birimleri seçiyoruz, bunlar fonksiyonumuzun terimleri olacak.

Tablo 10

iki terimimiz var

Tablo olmasına rağmen. 9 tablodan daha hantaldır. 8'de, endeksleri birleştirme yönteminin Quine yönteminden daha karmaşık olmadığı düşünülürse, Quine tablolarını derlemeden önce, bileşenlerin ve imaların çok sayıda yapıştırılmasının gerekli olduğunu hatırlarsak. Bir bilgisayarda endeksleri birleştirme yönteminin algoritmasının uygulanmasının nispeten basit olduğu ortaya çıkıyor. Tersine, Karnot haritalarını kullanarak mantıksal işlevleri en aza indirmenin üçüncü yönteminin dış basitliği ve netliği, karmaşık program Algoritmayı bir bilgisayarda uygularken.

Tablo 11

Tablo 12

Dört değişken için Karnot haritası bir tablo şeklinde sunulmuştur. 11. Kartın her hücresi bir bileşene karşılık gelir. Tamamlanan kart tabloda sunulmaktadır. 12 (işlev ilk iki yöntemdekiyle aynıdır). Yapıştırma yasasına göre, karşılık gelen anlamı elde etmek için birim değerlere sahip iki bitişik bileşen her zaman birleştirilebilir. Ayrıca, haritanın sınırlarında kalanlar bitişik olarak kabul edilir. Uygun bir implikant elde etmek için tam olarak hangi birimlerin birleştirilmesi gerektiğini görsel olarak belirlemek kolaydır. Unutulmamalıdır ki, eşitsizlik yasasına göre, tablonun aynı birimi. 12, iki veya üç bitişik ünite ile yapıştırılabilir.

minimizasyon prosedürü

Sıfır sıcaklıkta deformasyonu simüle etmek için, sistemin her zaman yerel bir enerji minimumuna yakın tutulmasına izin veren bir minimizasyon prosedürü kullanılır. Deformasyon ve minimizasyon aynı anda gerçekleştirilir. Minimizasyon algoritması, değiştirilmiş bir MD algoritmasıdır. Her atom için MD'nin her zaman adımından sonra, nokta ürün momentum ve kuvvet arasında hesaplanır. Nokta çarpımı negatif olan atomlar için, bu atomlar potansiyel enerjinin arttığı yönde hareket ettiğinden, momentum kaybolur. Böylece atomların kinetik enerjisi ortadan kalkarken, potansiyel enerji atomun hareket yönü boyunca yerel bir minimum enerjiye yaklaşır. Böyle bir minimizasyon prosedürü, sistemi hızlı bir şekilde yerel bir enerji minimumunun yakınına kaydırır, ancak tam yakınsama, sistemin serbestlik derecesi sayısı sırasına göre bir dizi zaman adımı gerektirdiğinden, tam yakınsama elde edilmez. Bununla birlikte, genellikle minimizasyon prosedüründeki adımların sayısındaki bir artış, sistemin evriminde sadece küçük değişikliklere yol açar.

kuvvetlerin hesaplanması

Atomlar arasında etki eden kuvvetleri hesaplamak için en büyük hesaplama çabası gereklidir. Bu nedenle, kuvvetlerin hesaplanması için algoritmanın optimizasyonuna özel dikkat gösterilmelidir. Bu yöndeki adımlardan biri, kuvvetler için hesaplanması zor ifadeleri (örneğin, bir üs içeren) hesaplaması kolay ifadelerle (örneğin, üçüncü dereceden spline'lar) değiştirmektir. İkinci adım, sınırlı bir etki aralığına sahip potansiyelleri kullanmak veya yukarıda belirtildiği gibi, potansiyel aralığı sonsuz ise potansiyelin önemsiz bölgesini kesmektir. Bu durumda, yalnızca en yakın atomların yanından etki eden kuvvetleri hesaplamak gerekir, yani. kesme yarıçapına eşit bir yarıçapa sahip bir kürenin (iki boyutlu durumda daire) içinde bulunur.

Üçüncü adım, verilen atoma en yakın atomları aramak için algoritmayı optimize etmektir. Gerçek şu ki, tüm atomların doğrusal bir sayımı, onlara olan mesafeleri hesaplamak ve bu atomları atmak, mesafenin kesme yarıçapını aşan bir dizi orantılı işlem gerektirir, burada sistemdeki atom sayısı. Sonuç olarak, bir artışla, gerekli işlemlerin sayısı hızla artar ve bu nedenle hesaplamaların yürütülmesi büyük ölçüde yavaşlar ve büyük olanlar için pratik olarak imkansız hale gelir. Bu nedenle, bu yavaşlamayı önlemek için, gerekli işlemlerin sayısının ikinci dereceden değil, doğrusal olarak arttığı bir algoritmaya ihtiyaç vardır. Prensip olarak, böyle bir algoritma basittir - tüm atomları değil, yalnızca yeterince yakın olanları yinelemeniz gerekir. Böyle bir ifade, yakın aralıklı atomlar kavramı somutlaştırılıncaya kadar bir totolojidir. Bunu yapmak için simülasyon hücresini daha küçük alt hücrelere böldük. Daha sonra verilen atoma yakın olan atomlar, verilen atomu içeren alt hücreye bitişik alt hücrelerde veya komşu alt hücrelere bitişik alt hücrelerde bulunur.

Simülasyon hücresini alt hücrelere - paralel yüzlülere (iki boyutlu durumda dikdörtgenler) bölmek uygundur. Küçük mesafelerdeki güçlü itme nedeniyle atomlar birbirine yaklaşamaz. Bu nedenle, her biri birden fazla atom içermeyecek büyüklükte alt hücreler seçmek mümkündür.

Bu nedenle, belirli bir atomdan uzaktaki atomları arama algoritması daha fazla yarıçap sünnet buna benziyor. Atom numarasına göre atomun koordinatlarını ve bunlara göre atomun bulunduğu alt hücreyi buluruz. Daha sonra, alt hücreleri en fazla olmayan bir mesafede buluruz. Bu alt hücrelerde bulunan atomlar arzu edilenler olacaktır (bkz. Şekil 1). Belirli bir alt hücrede depolanan atom sayısını bulmak için, her elemanı belirli bir alt hücreye karşılık gelen bir dizi girmek uygundur. Bu dizi elemanı, bu alt hücrede bulunan atom sayısını veya alt hücre boşsa sıfırı saklayacaktır. Bu dizinin elemanları her MD zaman adımında güncellenir. Açıklanan algoritmanın, sistemdeki atom sayısındaki artışla işlem sayısında doğrusal bir artış sağladığı açıktır. Bu algoritmanın varyasyonları “Gromex”, “MOLDY”, “DL_POLY” vb. MD programlarında kullanılır.

Paralel hesaplamaları organize etmek için uygun olacak başka bir hesaplama organizasyonu da mümkündür. Belirli bir atoma etki eden kuvvetleri hesaplamak için, yakındaki atomlar üzerinden toplamadan yakındaki alt hücrelere toplamaya gidilebilir (bkz. Şekil 1). İlk satırın alt hücreleri arasında sırayla hareket edeceğiz. İlk satırın sonuna ulaştıktan sonra ikinci satırın başına geçiyoruz, vb.

1 En yakın atomlar için arama şeması.

Bir alt hücrede bir atom varsa, ona etki eden kuvveti, yakındaki alt hücrelerde bulunan en yakın atomların yanından hesaplarız. Alt hücre boşsa, bir sonrakine gidin. Örneğin, 6. alt hücrede bulunan bir atom için (bkz. Şekil 1), 1, 2, 3, 7 alt hücrelerinde bulunan atomlardan etki eden kuvveti hesaplamak gerekir. Alt hücrelerde bulunan atomlardan etki eden kuvvetler. 5, 9, 10, 11 Newton'un üçüncü yasası sayesinde zaten işaretler içinde biliniyor. Bu alt hücrelerde bulunan atomlara etkiyen kuvvetler hesaplandığında bunlar hesaplanmıştır. Bu nedenle, belirli bir hesaplama organizasyonunda, en yakın alt hücrelerin sadece yarısını dikkate almak gerekir. Ayrıca, bitişik alt hücreye 7 geçerken, içlerinde bulunan yakındaki atomları aramak için yakındaki tüm alt hücreleri keşfetmeye gerek yoktur. Sadece 4 ve 8 numaralı hücreleri incelemek gerekir ve bunlarda bulunan atomlara, 1 ve 6 numaralı alt hücrelerde bulunan atomlar hariç, 6 numaralı hücre için bulunan atomları ekleyin. kaybolmaz, ancak bitişik bir alt hücre için en yakın atomları ararken kullanılır. Bu doğal olarak daha hızlı hesaplamalara yol açar.

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.

Bunu tanımsız k katsayıları ile DNF şeklinde gösterelim:

(**)

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.

Tüm kümelerde bize verilen işlevi göz önünde bulunduracağız ve her bir kümedeki (**) ifadesini (sıfır bağlaçları atarak) işlevin karşılık gelen değerine eşitleyeceğiz. Formun bir denklem sistemi elde ederiz:

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

Örnek

(**) ifadesini kullanarak sistemi kuruyoruz.

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

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

2.2. Quine - Mac - Clusky Yöntemi

Değerlendirilen tanımsız katsayılar yöntemi, işlev argümanlarının sayısı 5 - 6'dan fazla değilse etkilidir. Bunun nedeni, denklem sayısının 2 n'ye eşit olmasıdır. Bir işlev için tüm olası bağlaçları değil, yalnızca belirli bir işlevin DNF'sinde bulunabilecek bağlaçları yazmak daha verimlidir. Quine'ın yöntemi buna dayanmaktadır. Bu durumda, işlevin SDNF biçiminde belirtildiği varsayılı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. Birincil etkileri bulma

Fonksiyonun her mini terimine sırayla bakarız ve 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)-mertebesinin minitermlerini elde ederiz. Yapıştırma işlemine katılan rank n minitermleri işaretlenmiştir. Daha sonra (n-1) -th sırasının mini terimlerini ele alır ve onlara yapıştırma işlemini uygularız. (n-1) -th sırasının yapıştırma minitermlerini işaretliyoruz ve yapıştırma vb. sonucunda elde edilen (n-2) -th sırasının minitermlerini yazıyoruz. Yeni elde edilen minitermler ise aşama sona erer ben rütbe artık birbirine yapışmaz. Tüm işaretlenmemiş mini terimlere birincil imalar denir. Onların ayrılığı Abbr. DNF işlevleri.

4. sıradaki mini terimleri yapıştırıyoruz ve yapıştırma mini terimlerini yıldızlarla işaretliyoruz

2. sıranın mini terimlerini oluşturalım:

Birincil (basit) imalar şunlardır:

2. Etiketlerin yerleştirilmesi

Bu fonksiyon için Abbr. DNF şu şekildedir:

Çıkmaz DNF'ler ve Abbr oluşturmak için. DNF'nin fazladan aralıklarla atılması gerekir. Satırları birincil çıkarımlara karşılık gelen ve sütunlar SDNF mini terimlerine karşılık gelen bir tablo oluşturuyoruz. Bazı mini terimler, olası anlamlardan herhangi birini içeriyorsa, ilgili satır ve sütunun kesişimine bir etiket konur, örneğin, 1.

Örneğin devamı

3. Önemli imalar bulma

Herhangi bir sütun yalnızca bir birim içeriyorsa, o zaman bu satırı tanımlayan birincil implikeant esas olarak adlandırılır. Örneğin, önemli bir dolaylıdır. Temel ima, Kısaltma'dan çıkarılamaz. DNF, çünkü sadece bazı SDNF mini terimlerini kapsayabilmektedir. Bu nedenle, bu imalara karşılık gelen satırları ve bu satırlarda olan 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 çizin. Bundan sonra tablo görünürse boş satırlar, sonra onları çaprazlayın.

5. Maksimum aralıklarla minimum kapsamı seçme

Sonuç tablosunda, tüm sütunlarda birimleri içeren bir dizi satır seçin. 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ı

Minimum tablo kapsamı, ilgililere karşılık gelen satırlardan oluşur. Daha sonra MDNF aşağıdaki forma sahiptir:

Quine'ın yönteminde, Kısaltma'nın oluşturulması aşamasında mini terimlerin tam bir ikili karşılaştırma ihtiyacı ile ilişkili önemli bir uygunsuzluk vardır. DNF. 1956'da McCluskey, Quine yönteminin ilk aşamasının modernizasyonunu önerdi, bu da mini terimlerin karşılaştırma sayısını önemli ölçüde azaltacaktı.

McCluskey yönteminin arkasındaki fikir aşağıdaki gibidir. Tüm mini terimler ikili sayılar şeklinde 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 1 birim olan sayıları içerir. . Yapıştırmaya uygun mini terimler sadece bir kategoride birbirinden farklı olduğundan, sadece 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

3. sıradaki mini terimler

2. derecenin mini terimleri

İşaretlenmemiş mini terimler veya basit imalar

Bir etiket tablosu oluşturma

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

Konu üzerinde çalışın

MİNİMİZASYON YÖNTEMLERİ
MANTIĞIN FONKSİYONLARI

Anahtar kavramlar: mantıksal ifadeler, mantıksal fonksiyonlar, minimizasyon yöntemleri, ters çevirme, bağlaç, ayırma, ima, denklik.

İçerik

Tanıtım

Teknolojiden uzak insanlar genellikle bilgisayarlara ve diğer dijital cihazlara bakarlar. elektronik aletler gizemli ve anlaşılmaz bir şey olarak. Bununla birlikte, tüm bu cihazlar açık mantıksal yasalara sıkı sıkıya göre çalışır. Bu yasaların bilgisi ve anlaşılması, bir bilgisayar ve diğer dijital cihazlarla iletişim kurmaya yardımcı olur.

Dijital bir cihazın devresini oluşturma ilkeleri, mantıksal işlevlerle belirlenir. 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ı. Prensipte, herhangi bir mantıksal işlev, mantığın aksiyomları ve teoremleri kullanılarak 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ştirmeye izin veren özel algoritmik minimizasyon yöntemlerini kullanmak daha uygundur.

Basitleştirilmiş bir işlev daha az işlem ve argüman kombinasyonu içerecektir, bu da işlevi uygulayan devrenin şunları içereceği anlamına gelir. daha az öğe, yani daha ucuz ve daha güvenilir olacaktır.

Bu bağlamda, mantıksal fonksiyonların minimizasyonu özellikle önemlidir.

Amaç iş, mantık cebirinin işlevlerini en aza indirme yöntemlerinin incelenmesidir.

NesneÇalışma, mantıksal işlevleri en aza indirme süreci haline geldi.

Kalem araştırma - mantıksal işlevleri en aza indirme yöntemleri ve bu konuyu özel sınıflarda öğretme yöntemleri.

Görevler Araştırma:

matematiksel mantığın temel unsurlarını incelemek;

mantıksal işlevleri en aza indirme yöntemlerini keşfetmek;

bağımsız çalışma için görevler alın;

açıklanan yöntemleri kullanarak seçilen problemleri çözer.

Çalışma bir giriş, iki bölüm, bir sonuç ve kullanılmış literatür listesinden oluşmaktadır.

Giriş, konunun alaka düzeyini doğrular, çalışmanın amacını ve hedeflerini tanımlar.

İlk bölüm, bilgisayarların çalışmasının mantıksal temellerini tartışır.

İkinci bölümde, mantıksal işlevleri en aza indirme yöntemleri açıklanmış, açıklanan yöntemlerle problem çözme örnekleri verilmiştir.

Sonuç bölümü, çalışmanın genel sonuçlarını özetlemektedir.

Bilgisayar işleyişinin mantıksal temelleri

Matematiksel mantığın unsurları

Bilgisayarlar otomatik cihazlar, ilkeleri ikili mantığın temel yasalarına dayanan.

bilgi işlem makineleri tüm nesillerin, mantıksal öğelerden ve iki değer (bit) 0 ve 1 alan bellek öğelerinden oluşuyor ve oluşuyor. Bilgisayardaki tüm mantıksal blokların tüm bilgi işlemesi, mantık devreleri ve cihazlar matematiksel mantığın yasa ve ilkelerine dayandırılmıştır ve olacaktır.

Mantık ("kelime, düşünce, kavram, akıl yürütme, yasa" anlamına gelen eski Yunanca logos'tan gelir), yargıların, akıl yürütmenin ve kanıtların doğruluğunu inceleyen en eski bilimdir.

Matematiksel mantık, ispat tekniğini inceleyen matematiksel bir disiplindir.

Matematiksel mantığın kurucusu, büyük Alman matematikçi Gottfried Wilhelm Leibniz'dir (1646 - 1716). Matematiksel sembolleri kullanma ve mantıkta mantıksal hesabın inşası fikrini ortaya koydu, matematiğin mantıksal temelinin görevini belirledi, oynadı. önemli rol elektronik bilgisayarların yaratılış tarihinde: hesaplamalı matematik amacıyla ikili bir sayı sistemi kullanmayı önerdi. İrlandalı matematikçi George Boole, binayı Leibniz tarafından atılan temel üzerine inşa etti. yeni bilim- matematiksel mantık, - sıradan cebirin aksine, sayılarla değil, ifadelerle çalışan. D. Boole'un onuruna, Pascal programlama dilindeki mantıksal değişkenler daha sonra Boolean olarak adlandırıldı.

Matematiksel mantık çalışmaları uygulama sorunları matematiksel yöntemler mantık problemlerini çözmek ve herhangi bir bilgisayarın çalışmasının altında yatan mantık devreleri oluşturmak. Matematiksel mantıktaki yargılara önermeler veya mantıksal ifadeler denir.

Bir ifade, doğru veya yanlış olduğu söylenebilecek herhangi bir ifadedir, yani. gerçeğe uygun olup olmadığı; mantıksal işlemlerle (bağlayıcılar) birleştirilen mantıksal değerlerden (sabitler veya değişkenler) oluşan sembolik bir gösterimdir.

Çeşitli mantıksal ifadeler (ifadeler) yalnızca iki değer alabilir: "doğru" veya "yanlış". Her boole değişkeni yalnızca bir değer alabilir. var farklı varyantlar doğruluk ve yanlışlık tanımları:

NS

VE

NS

T

1

Yalan

L

YANLIŞ

F

0

İfadeler basit veya karmaşık olabilir. Basit olanlar cebirsel değişkenlere karşılık gelir ve karmaşık olanlar cebirsel fonksiyonlara benzer. İşlevler, mantıksal eylemler (işlemler) kullanılarak değişkenleri birleştirerek elde edilebilir.

Herhangi bir mantıksal ifadeyi yazmak için kullanılabilecek mantıksal işlemleri düşünün.

En basit mantıksal işlem DEĞİLDİR (aksi halde genellikle olumsuzlama, tümleyen veya ters çevirme olarak adlandırılır ve şu şekilde gösterilir: ). Olumsuzlama sonucu her zaman bağımsız değişken değerinin tersidir. Diğerleri basit kelimeler, bu operasyon"değil" parçacığının veya "yanlış olduğu" kelimelerinin orijinal mantıksal ifadeye eklendiği anlamına gelir.

Böylece, olumsuzlama yoluyla bazı ifadeler olduğunda doğru olan bir ifade denir yanlış ve ne zaman yanlış NS.

Mantıksal işlem tekli DEĞİLDİR, yani. tek işleneni vardır. Olumsuzluğun tanımı, olumsuzluğun hangi doğruluk değerlerini (1, 0) aldığını gösteren doğruluk tablosu kullanılarak yazılabilir. orijinal ifadenin doğruluk değerlerine bağlı olarak :

1

0

0

1

Mantıksal VE (mantıksal çarpma veya bağlaç), ancak ve ancak her ikisinin birden olması durumunda doğru kabul edilen karmaşık bir mantıksal ifadedir. basit ifadeler doğrudur, aksi takdirde karmaşık ifade yanlıştır. İfadelerin birleşimi ve şunu belirtir: , ve bazen sadece yazarlar ... Bağlaçtaki ifadeler "ve" bağlacı ile bağlanır. Bir bağlantının tanımı, ilk ifadelerin dört olası değer kümesinin her biri için bir doğruluk tablosu şeklinde yazılabilir. ve bağlacın karşılık gelen değeri ayarlanır :

1

1

1

1

0

0

0

1

0

0

0

0

İki ifadenin birleşiminin tanımı doğal olarak herhangi bir sonlu sayıda bileşene kadar uzanır: bağlaç A 1 & A 2 & A 3 & ... & A n true ancak ve ancak tüm ifadeler doğruysa A 1 , A 2 , A 3 , ... A n(ve bu nedenle, bu ifadelerden en az biri yanlış olduğunda yanlış).

Mantıksal VEYA (mantıksal toplama veya ayırma), basit mantıksal ifadelerden en az birinin doğru olması durumunda doğru ve yalnızca her iki basit mantıksal ifadenin de yanlış olması durumunda yanlış olan karmaşık bir mantıksal ifadedir. ifadelerin ayrılması ve sembolü ile belirtiyoruz ve okuyacağız: veya ... Bir ayrılmanın tanımı bir doğruluk tablosu olarak yazılabilir:

1

1

1

1

0

1

0

1

1

0

0

0

İki ifadenin ayrılmasının tanımı doğal olarak herhangi bir sonlu sayıda bileşene kadar uzanır: ayırmaA 1 A 2 A 3 ... A n ancak ve ancak ifadelerden en az birinin olması durumunda doğrudurA 1 , A 2 , A 3 , ..., A n (ve bu nedenle, tüm bu ifadeler yanlış olduğunda yanlıştır).

İşlemler VE, VEYA, YAPMAYIN komple sistem keyfi olarak karmaşık bir mantıksal ifade oluşturabileceğiniz mantıksal işlemler. Ancak bunların yanında başka mantıksal işlemler de vardır.

Mantıksal sonuç (ima), gerçeğin bir yalanı izlemesi dışında her durumda doğru olan karmaşık bir mantıksal ifadedir. Yani, bu mantıksal işlem, birincisi bir koşul olan iki basit mantıksal ifadeyi birbirine bağlar (), ve ikinci ( ) bir sonucudur. Anlamı sembolle gösteriyoruz ve giriş " "Okuyacağız:" Kimden takip eder."

Bu tanımı bir doğruluk tablosu şeklinde yazalım:

1

1

1

1

0

0

0

1

1

0

0

1

Mantıksal bir bakış açısından "eğer öyleyse" ifadesi, "yanlıştır, bu doğru ve yanlıştır" ifadesi ile aynı anlama sahiptir. Bu, çıkarım işlevinin iki işlevin (olumsuzlama ve bağlaç) birleşimiyle değiştirilebileceği anlamına gelir.

Mantıksal özdeşlik (eşdeğerlik), ancak ve ancak her iki basit mantıksal ifadenin de aynı gerçeğe sahip olması durumunda doğru olan karmaşık bir mantıksal ifadedir. Sembol eşdeğerini belirtin ve "" gösterimi "eşdeğer" veya "eşdeğer" veya " ancak ve ancak », « ancak ve ancak ". Eşdeğerliğin tanımı bir doğruluk tablosu şeklinde yazılabilir:

1

1

1

1

0

0

0

1

0

0

0

1

Mantık fonksiyonları ve dönüşümleri

Mantıksal bir işlev, yalnızca iki değer alabilen mantıksal değişkenlerin bir işlevidir: 0 veya 1. Sırayla, mantıksal değişkenin kendisi de (mantıksal bir işlevin argümanı) yalnızca iki değer alabilir: 0 veya 1.

Her mantık işlevi ayarlanabilir büyük miktarçeşitli türlerin işlevleri. Ancak oldukça karmaşık herhangi bir mantıksal işlev bile, nispeten basit bir dizi temel mantıksal işlemle gerçekleştirilebilir. En ünlü temel, bir dizi "ve", "veya", "değil" işlevidir.

Bağlama, ayırma ve ters çevirme işlemleri için, mantıksal ifadelerin özdeş (eşdeğer) dönüşümlerini gerçekleştirmeyi mümkün kılan yasalar tanımlanmıştır:

;

.

Yasalara dayanarak, karmaşık mantıksal ifadeleri basitleştirebilirsiniz.

Başlangıçta, sonraki dönüşümlerin kolaylığı nedeniyle, aşağıdaki iki kanonik formlar fonksiyon temsilleri: mükemmel ayırıcı normal biçim (SDNF) ve mükemmel birleşik normal biçim (SKNF).

SDNF ve SKNF'ye geçmeden önce bazı kavramları tanıtalım.

Temel bir bağlaç, olumsuzlamalı veya olumsuzlamasız alınan birkaç değişkenin birleşimidir ve değişkenler arasında aynı olabilir.

Temel bir ayırma, olumsuzlamalı veya olumsuzlamasız alınan ve değişkenler arasında aynı olabilen birkaç değişkenin ayrılmasıdır.

Temel bağlaçların herhangi bir ayrılmasına ayrık normal biçim, yani DNF denir.

Örneğin, ifade DNF'dir.

Temel ayrımların herhangi bir birleşimine birleştirici normal form, yani CNF denir.

Örneğin, ifade CNF'dir.

Mükemmel bir DNF'ye (SDNF), eşit temel bağlaçların olmadığı ve hepsinin aynı değişkenleri ve her değişkeni yalnızca bir kez (muhtemelen olumsuzlama ile) içerdiği bir DNF denir.

Örneğin, ifade DNF'dir, ancak SDNF değildir; ifade SDNF'dir.

Mükemmel bir CNF'ye (SKNF), eşit temel ayrımların olmadığı ve hepsinin aynı değişkenleri ve her değişkeni yalnızca bir kez (muhtemelen olumsuzlama ile) içerdiği bir CNF denir.

Örneğin, ifade .

Bir formdan diğerine geçişler için algoritmalar vereceğim. Doğal olarak, içinde özel durumlar(belirli bir yaratıcı yaklaşımla) algoritmaların uygulanması, algoritmaların uygulanmasından daha zahmetli olabilir. basit dönüşümler bu formun belirli bir türünü kullanarak:

bir fonksiyonun keyfi atamasından DNF'ye geçiş

Bu geçiş, birkaç değişken için ortak olan ters çevirmelerin ihmal edilmesine, parantezlerin genişletilmesine ve ortaya çıkarsa, yasaları kullanarak aynı terimlerin birleştirilmesine indirgenir:

Örneğin:

DNF'den CNF'ye geçiş

Bu geçiş için algoritma şu şekildedir: DNF'nin üzerine iki olumsuzlama koyarız ve de Morgan kurallarını kullanarak (üst olumsuzluğa dokunmadan) DNF'nin olumsuzluğunu DNF'ye geri getiririz. Bu durumda parantezleri absorpsiyon kuralını kullanarak açmanız gerekir. Elde edilen DNF'nin (yine de Morgan kuralına göre) olumsuzlanması (üst) bize hemen CNF'yi verir:

DNF'den CNF'ye geçmenin ikinci yolu, dağıtım yasasını kullanmaktır:

CNF'den DNF'ye geçiş

Bu geçiş, parantezleri basitçe genişleterek gerçekleştirilir (yine soğurma kuralı kullanılarak):

CNF'den SKNF'ye geçiş

Bu geçiş, öncekine benzer bir şekilde gerçekleştirilir: basit bir ayırmada bazı değişkenler yoksa, örneğin,z , ardından ifadeyi ekleyin (bu, ayrılığın kendisini değiştirmez), ardından parantezleri dağıtım yasasını kullanarak genişletiriz:

DNF'den SDNF'ye geçiş

Bazı basit bağlaçların bir değişkeni yoksa, örneğin,z , sonra tamamlanmamış bağlacı formun bir ifadesi ile çarparız , ardından parantezleri genişletiriz (bu durumda tekrarlanan ayrık terimler yazmayız). Örneğin:

Doğruluk tablolarından SDNF ve SKNF elde etmek için algoritmanın aşağıdaki 4 noktasını gerçekleştirmek gerekir:

SDNF

SKNF

SDNF ve SKNF'nin oluşturulması bir doğruluk tablosu ile başlar.

Çıktıları eşit olan tablonun satırlarını işaretleyelim.

1

0

İşaretli her satır için, işaretle ayrılmış değişkenlerin bir kombinasyonunu yazıyoruz.

bağlaç (&)

ayrılma (V)

Olumsuzlama işleminin işaretlerini aşağıdaki gibi düzenliyoruz:

değişken 1'e eşitse, bu değişkenin kendisini yazarız, 0'a eşitse olumsuzluğunu yazarız.

değişken 0'a eşitse, bu değişkenin kendisini yazarız, 1'e eşitse olumsuzluğunu yazarız.

Elde edilen tüm ifadeleri işlemle birleştiriyoruz

ayrılıklar

bağlaçlar

SDNF veya SKNF aldıktan sonra, elektronik devre bu mantıksal işlevi uygular. 3 sürer mantıksal öğeler :

çevirici

bağlaç

ayırıcı

Ancak çoğu zaman SDNF birçok terim içerir ve görev, bunların sayısını azaltmak ve mantıksal ifadeyi basitleştirmektir. Mantıksal işlevleri basitleştirmek için yukarıda verilen mantık yasalarını kullanabilirsiniz. Aynı amaçla, bir sonraki bölümde tartışılacak olan özel yöntemler geliştirilmiştir.

Boole İşlevlerini En Aza İndirme

Önceki bölümde belirtildiği gibi, mantıksal bir fonksiyon bir doğruluk tablosu şeklinde veya SDNF (mükemmel ayrık normal form) veya SKNF (mükemmel birleşik normal form) şeklinde temsil edilebilir ve bir mantık diyagramı elde etmek için kullanılabilir. bir cihaz. Bununla birlikte, ortaya çıkan mantık genellikle optimal olmayacaktır. Bu yüzden önemli bir kilometre taşı mantık devrelerinin sentezi, mantık fonksiyonlarının minimizasyonudur.

Minimizasyon, mantıksal fonksiyonların analitik temsillerini basitleştirmek için dönüştürülmesidir.

Minimizasyonun iki yönü vardır:

En kısa gösterim (bu, KDNF, KKNF, KPNF'nin en kısa biçimlerini verir);

Minimum yazma biçimini elde etmek (tüm işlevi bir kerede yazmak için minimum karakter sayısını almak).

Ancak minimizasyon yöntemlerinden hiçbirinin evrensel olmadığı belirtilmelidir.

Mantık cebirinin işlevlerini en aza indirmek için bir dizi yöntem geliştirilmiştir:

mantıksal fonksiyonların doğrudan dönüşüm yöntemi;

Karnot haritalarını kullanarak mantıksal fonksiyonları en aza indirme yöntemi;

Quine-McCluskey yöntemi;

Blake-Poretsky yöntemi;

Petrik'in yöntemi ve diğerleri.

İlk iki yöntem üzerinde daha ayrıntılı olarak duralım.

Mantıksal fonksiyonların doğrudan dönüşümleri yöntemi

Biri basit yöntemler minimizasyon, mantık cebirinin temel teoremleri kullanılarak gerçekleştirilen bir doğrudan dönüşüm yöntemidir.

Bu yöntemi kullanırken:

Mantıksal fonksiyonların SDNF'si yazılır,

Form, mantık cebirinin aksiyomları kullanılarak dönüştürülür ve basitleştirilir, özellikle orijinal SDNF'de, çakışmayan bir değişkenin olduğu komşu terimler (üyeler) tanımlanır.

Bitişik terimlerle ilgili olarak, yapıştırma yasası uygulanır.

Yapıştırma ile oluşturulan terimlere imalar denir.

Yapıştırıldıktan sonra elde edilen çıkarımlar, yapıştırma imkansız hale gelene kadar mümkün olduğunca yapıştırılır.

Ortaya çıkan minimizasyon işlevine çıkmaz sokak denir.

Bir fonksiyon verilsin

Yukarıda açıklanan yöntemi kullanarak en aza indiriyoruz. Bunu yapmak için bir terim daha ekleyin ve yapıştırma yasalarını kullanın.

Minimal işlevi var

Doğrudan dönüşümlerle göz önünde bulundurulan minimizasyon yöntemi, özellikle aşağıdakiler için oldukça basittir. Olumsuz Büyük bir sayı değişkenler. Bu yöntemin dezavantajı, kesin olarak resmileştirilmiş bir minimizasyon yolunu göstermemesidir. Çok sayıda değişkenle, mintermler farklı şekillerde gruplandırılabilir, bu da çeşitli basitleştirilmiş formlarla sonuçlanır. belirli bir işlev... Aynı zamanda, bu formlardan herhangi birinin minimal olduğundan emin olamaz. Minimal olmamakla birlikte artık basitleştirilmeyen çıkmaz formlardan birinin elde edilmiş olması mümkündür.

Karnot haritalarını kullanarak mantıksal işlevleri en aza indirme yöntemi

Karnaugh haritası veya Veitch haritası (şema), mantık cebirinin işlevlerini en aza indirmenin grafiksel bir yoludur.

Karnot haritaları az sayıda değişken için uygundur.

Karnaugh haritaları temsil eder belirli bir tablo doğruluk tabloları genellikle iki, üç ve dört değişken içindir ve doğruluk tablolarının satır ve sütunlarını gösterme biçimleri bakımından birbirlerinden farklıdırlar.

İncirde. Şekil 1 sırasıyla iki, üç ve dört değişken için Weich haritalarını göstermektedir.

pilav. 1

Değişken gruplarının düzenlenmesi x önemli değil, sadece her hücrenin herhangi bir komşu hücreden sadece bir değişken ile farklı olması gerekir. Kabul edilen bina haritaları biçimine göre, birinci ve son satır, ilk ve son sütunların hücreleri. Haritadaki hücre sayısı, değişken değerlerinin (terimler) olası kombinasyonlarının sayısına ve buna karşılık gelen mantıksal bir fonksiyonun değerine eşittir. bu set değişkenler. Fonksiyon kaydının mükemmel ayırıcı normal formunda (SDNF) olası kombinasyonlardan herhangi biri mevcutsa, Karnot kartının ilgili hücresine bir "1" konur. Elde edilen fonksiyonda terim yoksa, Karnot haritasının ilgili hücresine "0" konur.

Örneğin, önceki örnekte ele alınan fonksiyon

tablo tarafından verilen doğruluk (Şekil 2 a), Karnot haritaları kullanılarak minimize edilebilir. Bunun için Karnot haritası, Şekil 2'de gösterilen forma sahip olacaktır. 2 b.

pilav. 2

Bir Karnaugh haritasında, mantıksal 1 bitişik hücrelere yazılanlar, karşılık gelen 1 bağlaçlar (ürünler), birbirini tamamlayan ve atlanabilen yalnızca bir değişkende farklılık gösterir.

Yani Karnot haritasının ilk satırında (bkz. Şekil 2 b) değişken NS ile birlikte bulunan NS 1 ve NS 2 birbirini tamamlayan:

Böylece, iki bitişik hücreyi gruplamak üst çizgi(Şekil 2 b'deki kontur), bir değişken hariç tutulabilir - NS 1 .

Benzer şekilde, iki bitişik hücreyi sol sütunda gruplayarak (Şekil 2 b'deki anahat) ve farklı değişkenleri hariç tutarak, basitleştirilmiş bir ifade elde ederiz - NS 2 .

Ortaya çıkan basitleştirilmiş ifadeler VEYA işlemi kullanılarak birleştirilir.

Böylece, Karnot haritasının bitişik hücreleri, bir değişkeni hariç tutmak için gruplandırılabilir. Gruplanacak hücre sayısı ikiden fazla olabilir, ancak sayıları çift olmalı ve birbirleriyle temas halinde (bitişik) olmalıdır.

Az önce tartışılan örnekte olduğu gibi, birkaç üst üste binen hücre grubuna sahip olmasına da izin verilir.

İlk ve son sıranın hücreleri, ilk ve son sütunlar da gruplanabilir, yani harita hem dikey hem de yatay eksen boyunca bir silindire katlanabilir.

hariç tutmak n değişkenler, gruplanacak toplam hücre sayısı şuna eşit olmalıdır: 2 n... Bu nedenle, bir değişkeni hariç tutmak için iki bitişik hücreyi birleştirmek gerekir ve üç değişkeni hariç tutmak için sekiz komşu hücreyi birleştirmek zaten gereklidir.

Bu nedenle, en aza indirilmiş bir mantıksal fonksiyon elde etmek için, 1 içeren Karnaugh haritasının tüm bitişik hücrelerini gruplamak ve ardından elde edilen grupları OR işlemini kullanarak birleştirmek gerekir. Diğer hücrelerle birleştirilemeyen 1 içeren hücreler, her biri tüm değişkenleri içeren minimize edilmiş mantıksal fonksiyonda bağımsız üyeler oluşturur.

Basitleştirilmiş bir mantıksal işlev elde etmek için bir grup komşu hücrenin dış hatlarını oluşturma yöntemlerini ve Weich haritalarının birkaç örneğini ele alalım.

Böylece, mantıksal bir fonksiyon için Weich haritası

Şekil 3'te gösterilmiştir.

pilav. 3

Bu şekil gösterir Doğru yol birleşmeler komşu hücreler, yani, Weich haritası, olduğu gibi, dikey olarak yerleştirilmiş bir silindire katlanır.

Mantıksal fonksiyonun basitleştirilmiş ifadesi

Böylece, komşu hücreleri tek bir karede gruplayarak iki değişkeni hariç tutmayı başardık ( NS 1 ve NS 2 ) ve mantıksal işlev için basit bir ifade alın.

Mantıksal bir işlevi en aza indirmenin bir örneğini düşünün

Bu fonksiyon için Karnaugh haritası Şekil 4'te gösterilmektedir:

pilav. 4

Gruplandırılacak hücreler iki ana hat ile özetlenir. Alt kontur, bir değişkeni hariç tutmayı mümkün kılarNS 3 ve bundan sonra içinde bir üye kalır.

Üst döngüde iki değişken hariç tutulabilir (NS 2 ve NS 4 ) ve bundan sonra terim içinde kalır. Mantıksal bir işlevin basitleştirilmiş bir Boole ifadesi şu şekildedir:

Weich haritası Şekil 2'de gösterilen mantıksal bir fonksiyonun minimizasyonunu düşünün. 5.

pilav. 5

Bu fonksiyonun boole ifadesi şu şekildedir:

Dört köşe hücresi bir grup halinde birleştirilebilir. Bu birleşim iki değişkenin elimine edilmesini sağlar (NS 1 ve NS 2 ) ve üyeyi alın.

İlk satırdaki iki ünite, ilk satırdaki iki ünite ile birleştirilebilir. Sonuç olarak, iki değişkeni hariç tutmanıza izin veren dört hücreli bir grup alın (NS 1 ve NS 3 ) ve üyeyi alın.

Son olarak, kalan tek birim (ikinci satırdan ve son sütundan) üstündeki hücreyle birleştirilebilir ve bu bir değişkeni ortadan kaldıracaktır (NS 4 ) ve üyeyi alın.

Böylece, minimize edilmiş mantıksal işlevi elde ederiz.

Karnot haritaları yöntemi (Weich diyagramları), özünde, orijinal mantıksal işlevin SDNF'sine yapıştırılacak bağlaçları bulmayı basitleştirir.

Boole Cebir Fonksiyonlarının Tanımlanan Yöntemlerle Minimizasyonu

Bu bölüm, yukarıda tartışılan yöntemleri kullanarak seçilen işlevleri ve bunların minimizasyon örneklerini sunar.

2 değişkenli bir fonksiyon için Karnot çizelgelerini kullanmayı basitleştirin:

Bu fonksiyon için Karnaugh haritası (Weich diyagramı) şöyle görünecektir:

İlk satırda değişkeni hariç tutabilirsiniz. NS 2 ve basitleştirilmiş bir ifade elde edin NS 1 .

İkinci sütunda değişkeni hariç tutabilirsiniz.NS 1

Böylece, mantıksal işlevin basitleştirilmiş ifadesi şöyle görünecektir:

İlk sütunda değişkeni hariç tutabilirsiniz. NS 1 ve basitleştirilmiş bir ifade elde edin NS 2 .

İkinci satırda, değişkeni hariç tutabilir ve basitleştirilmiş bir ifade elde edebilirsiniz.

OR işlemini kullanarak elde edilen basitleştirilmiş ifadeleri bağlarız.

Böylece, mantıksal işlevin basitleştirilmiş ifadesi şöyle görünecektir:

3 değişkenli işlev için Karnot çizelgelerini kullanarak basitleştirin:

Bu fonksiyon için Weich diyagramı şöyle görünecektir:

NS 3 ve basitleştirilmiş bir ifade elde edin.

NS 3 ve basitleştirilmiş bir ifade elde edin.

Son sütunda değişkeni hariç tutabilirsiniz.NS 1 ve basitleştirilmiş bir ifade elde edin.

OR işlemini kullanarak elde edilen basitleştirilmiş ifadeleri bağlarız.

Böylece, mantıksal işlevin basitleştirilmiş ifadesi şöyle görünecektir:

Bu fonksiyon için Weich diyagramı şöyle görünecektir:

İlk satırda değişkeni hariç tutabilirsiniz.NS 3 ve basitleştirilmiş ifade ve değişken elde edinNS 2 ve basitleştirilmiş bir ifade elde edin.

OR işlemini kullanarak elde edilen basitleştirilmiş ifadeleri bağlarız.

Böylece, mantıksal işlevin basitleştirilmiş ifadesi şöyle görünecektir:

Bu işlevi en aza indirmenin ikinci bir yolunu da bulduk.

Daha sonra bu fonksiyon için Veitch diyagramı şöyle görünecektir:

İlk satırda değişkeni hariç tutabilirsiniz.NS 3 ve basitleştirilmiş bir ifade elde edin.

İlk satır ifadeyi içerir .

Ortaya çıkan ifadeleri VEYA işlemi ile bağlarız.

Böylece, mantıksal işlevin basitleştirilmiş ifadesi şöyle görünecektir:

Açıkçası, sonuçta ortaya çıkan fonksiyon minimal değildir, bu yüzden mantıksal fonksiyonların doğrudan dönüşümleri yöntemini kullanacağız. Parantezlerin dışındaki değişkeni çıkaralımNS 1 ve parantez içindeki ifade için katlama kuralını uygulayın. NS ilk durumda olduğu gibi aynı sonuç.

Bu, komşu hücrelerin gruplanabileceği anlamına gelir. Farklı yollar, asıl şey temel kuralı unutmamaktır: dışlamak n değişkenler, gruplanacak toplam hücre sayısı şuna eşit olmalıdır: 2 n .

Bu fonksiyon için Weich diyagramı şöyle görünecektir:

ilk satır değişkeni hariç tutabilir NS 3 ve basitleştirilmiş bir ifade elde edin.

0 1 0 0

İkinci sütun hakkında, değişken hariç tutulabilir NS 1 .

OR işlemini kullanarak elde edilen basitleştirilmiş ifadeleri bağlarız.

Böylece, mantıksal işlevin basitleştirilmiş ifadesi şöyle görünecektir:

Bu fonksiyon için Weich diyagramı şöyle görünecektir:

İlk satırda değişkeni hariç tutabilirsiniz.NS 3 ve basitleştirilmiş bir ifade elde edin.

İkinci satırda değişkeni hariç tutabilirsiniz.NS 3 ve basitleştirilmiş bir ifade elde edin.

OR işlemini kullanarak elde edilen basitleştirilmiş ifadeleri bağlarız.

Böylece, mantıksal işlevin basitleştirilmiş ifadesi şöyle görünecektir:

Bu fonksiyon için Weich diyagramı şöyle görünecektir:

Değişkenler ilk ve son sütunda hariç tutulabilirNS 1 ve NS 2 ve basitleştirilmiş bir ifade elde edin.

İkinci satırda değişkeni hariç tutabilirsiniz.NS 2 ve basitleştirilmiş bir ifade elde edin. Ö .

OR işlemini kullanarak elde edilen basitleştirilmiş ifadeleri bağlarız.

Böylece, mantıksal işlevin basitleştirilmiş ifadesi şöyle görünecektir:

Bu bölümde, Weich diyagramları kullanılarak minimize edilmiş iki, üç ve dört değişkenli fonksiyonlar sunulmuştur. Bu minimizasyon yönteminin uygulanmasının özelliklerini açık bir şekilde gösterdim ve açıkladım. farklı işlevler mantık cebirinin işlevlerinin doğrudan dönüşüm yöntemiyle birlikte dahil olmak üzere.

Çözüm

Sunulan çalışma, mantık cebirinin işlevlerini en aza indirme yöntemlerine ayrılmıştır. Çalışma sürecinde şunlar vardı:

1. matematiksel mantığın ana unsurları incelenmiştir;

   mantıksal fonksiyonların minimizasyonu yöntemleri araştırılır;

   bağımsız çalışma için seçilen görevler;

   seçilen problemler açıklanan yöntemlerle çözülür.

Mantıksal işlevleri en aza indirmenin 2 yöntemini ayrıntılı olarak düşündüm:

mantık cebiri teoremleri kullanılarak gerçekleştirilen mantıksal fonksiyonların doğrudan dönüşüm yöntemi;

Veitch diyagramlarını (Karnaugh haritaları) kullanarak minimizasyon yöntemi.

İlk yöntem, bilgisayar bilimi okul kitaplarında (örneğin, N. Ugrinovich, L. Shchautsukova tarafından 10-11. sınıf ders kitapları) bile yaygınlaştı, çünkü mantık cebirinin işlevlerini basitleştirmenin basit yöntemlerinden biri. . Bu yazarların ders kitaplarında sunulan görevler oldukça çeşitlidir:

basitleştirmek mantıksal formül mantık cebir yasalarını kullanmak;

verilen bir fonksiyon için bir mantık devresi kurmak;

anahtarlama devresini basitleştirmek için;

bir doğruluk tablosu kullanarak mantıksal bir ifadeyi kanıtlayın;

bu işlev için bir doğruluk tablosu oluşturun.

İkinci yöntem, farklı değişkenleri hızlı ve kolay bir şekilde ortadan kaldırmanıza ve her zaman minimal olmayabilecek basitleştirilmiş bir ifade elde etmenize olanak tanır. Bu nedenle, bu yöntem, mantıksal işlevlerin doğrudan dönüşümleri yöntemiyle birlikte düşünülmelidir.

Bu konu sahip pratik önem mikroelektronikte. Ayrıca, Bilişim ve BİT Birleşik Devlet Sınavı, 4 gruba ayırdığımız mantık cebiri ile ilgili bir takım görevler içermektedir.

İlk grup, verilene eşdeğer bir mantıksal ifade belirlemenizi gerektiren görevlerden oluşur.

İkinci grup - belirli bir ifadeye karşılık gelen doğruluk tablolarının parçalarını bulma görevleri.

Üçüncü grup, değişkenlerin herhangi bir değeri için ifade içgüdüsünü bulma görevlerini içerir. NS ve NS .

Dördüncü grup, verilen mantıksal şemaya karşılık gelen yapısal formülü belirleme görevidir.

Özellikle mantıksal fonksiyonların minimizasyonu ile ilgili herhangi bir göreve rastlamadım, ancak testlerde mevcut olan görevler mantık cebiri alanında yeterince derin bilgi gerektiriyor.

Giriş sınavlarının karmaşıklığı nedeniyle, yüksek Eğitim kurumları yakında testlerde olduğunu varsayabiliriz ve bu nedenle Eğitim programları, mantıksal işlevleri basitleştirme ve en aza indirme görevleri görünebilir.

bibliyografya

Gavryukova GA Bilişimde Mantık [Elektronik kaynak]. - Erişim modu: Ekim. 2010).

Ivin A.A.Logic: öğretici... - 2. baskı. - M.: Bilgi, 1998 .-- 233 s.

Igoshin VI Matematiksel mantık ve algoritma teorisi: Öğrenciler için ders kitabı. daha yüksek. ders çalışma. kurumlar. - 2. baskı, Silindi. - M.: Akademi, 2008 .-- 448 s.

Bilişim ve BİT. Sınava hazırlık-2009. Giriş testleri. / Ed. FF Lysenko. - Rostov n / a: Legion-M, 2009 .-- 208 s.

Bilişim: Ders Kitabı / BV Sobol [ve diğerleri]. - 3. baskı, Ekle. ve revize - Rostov n / a: Phoenix, 2007 .-- 446 s.

Bilişim: Ders Kitabı / A. V. Mogilev, N. I. Pak, E. K. Henner. - 3. baskı. - E.: Akademi, 2004 .-- 848 s.

Kalabekov B.A. Dijital cihazlar ve mikroişlemci sistemleri: Teknik iletişim okulları için ders kitabı. - M .: sıcak hat- Telekom, 2000 .-- 336 s.

Kaimin V.A.Bilişim: Ders Kitabı. - 2. baskı, Rev. ve Ekle. - E.: INFRA-M, 2001 .-- 272 s.

Kovalenko A. A, Petropavlovsky M. D. Mikroelektroniğin temelleri: ders kitabı. - E.: Akademi, 2006 .-- 240 s.

Lvovskiy M.B. araç seti IBM PC [Elektronik kaynak] üzerinde çalışan 9-11. sınıflardaki öğrenciler için bilişim üzerine. - Erişim modu: Eylül. 2010).

Bilgisayar biliminin matematiksel temelleri. Seçmeli ders: Ders Kitabı / E. V. Andreeva, L. L. Bosova, I. N. Falina. - M.: BİNOM. Bilgi laboratuvarı, 2005. - 328 s.

Mantıksal fonksiyonların minimizasyonu [Elektronik kaynak]. - Erişim modu: Ağustos. 2010).

Mikroelektroniğin temelleri: Üniversiteler için ders kitabı / N. A. Avaev, Yu. E. Naumov, V. T. Frolkin. - M.: Radyo ve iletişim, 1991. - 288 s.: hasta.

Bilişim ve Bilgi Teknolojileri Çalıştayı / N. D. Ugrinovich, L. L. Bosova, N. I. Mikhailova. - 2. baskı, Rev. - M.: BİNOM. Bilgi Laboratuvarı, 2004 .-- 394 s.

Uygulamalı Matematik: Manuel / I.N. Revchuk, V.K. Pchelnik. - Grodno: GrSU im. Y. Kupala, 2007 .-- 128 s.

Rabkin E.L., Farforovskaya Yu.B. Ayrık matematik: boole fonksiyonları ve grafik teorisinin unsurları: Metodik talimatlar ve kontrol görevleri [Elektronik kaynak]. - Erişim modu: 7 Ağustos 2010).

Saveliev A. Ya. Bilişimin Temelleri: Üniversiteler için ders kitabı. - M.: MGTU im. N.E.Bauman, 2001. - 328 s., Ill.

Stepanenko I.P. Mikroelektroniğin temelleri: üniversiteler için ders kitabı. - 2. baskı, Rev. ve Ekle. - M.: Laboratuvar Temel bilgi, 2001 .-- 488 s.

Bilgisayar bilimi öğretimi teorisi ve yöntemleri: Ders Kitabı / [M. P. Lapchik, I.G. Semakin, E.K. Henner, M.I. Ragulina ve diğerleri]; ed. M.P. Lapchik. - M.: Akademi, 2008 .-- 592 s.

Ugrinovich N.V. Bilişim ve BİT. Sınıf 10. Profil seviyesi. - 3. baskı, Rev. - M.: Binom. Bilgi Laboratuvarı, 2008 .-- 387 s.

Ugrinovich N.V. Bilişim ve bilgi Teknolojisi: 10-11. sınıflar için ders kitabı. - M .: BİNOMİAL. Bilgi Laboratuvarı, 2003 .-- 512 s.

Shautsukova L.Z.Informatics 10 - 11. - M .: Eğitim, 2004 .-- 420 s.