Въведение в теорията на цифрови автомати, минимизиране на Булева алгебра изрази

Опростяване на Булева функционира изрази при разработването на проекти информационни устройства се направи, за да се намали количеството на оборудване, необходимо за изпълнение на тези функции.

Предпочитаната форма на получения експресията е DNF, който беше показан в предишния раздел, е по-лесно, отколкото CNF. Също така беше показано, че DNP е с удобно графично представяне и DNP преход от техническата база на "И-НЕ" е много лесно.

DNF се нарича минимално. ако той съдържа най-малък брой писма, в сравнение с други еквивалентни изрази като DNF. Под "буквата" означава всяка поява на аргумента във формулата. Например, изразът се състои от осем писма на всички три аргумента.

Минимизиране проблем дадена логическа формула може да бъде решен по принцип чрез конвенционални методи на булевата алгебра чрез постепенно опростяване на тази формула използват главно операции на абсорбция и свързване. Например:

Получената DNF вече опростена чрез свързване и усвояване, но има един трик за по-нататъшно опростяване:

Последният израз е минимална DNF, и междинно съединение резултатът не е податлив на опростяване чрез свързване и усвояване се нарича застой DNF.

Този начин на минимизиране неефективно. Това е почти невъзможно да се докаже, че в резултат на използване на опростената формула е наистина минимално, а не само до задънена улица. Ето защо, минимизиране работи един от най-специфичните, повече или по-малко формални методи, които гарантират получаване на минималната DNF.

Всички тези методи са базирани на концепцията: implicants и председатели implicants.

Ако г = 1, тогава непременно F = 1. обратна условие не е определен. Единици implicants като единици принадлежат на набор функция F. Оттам идва и името implicants (Латинска implicire -. Влиза в нещо, да се включат). Следователно това се случи, и името на функцията "косвено".

Да разгледаме функциите на истината маса на горния пример и да се покаже в същата таблица донякъде произволно избрани implicants на тази функция (таблица. 2.6).

Prime implicants наричат ​​такива implicant дадена функция, която е съчетание на няколко писма, както и от отпадане някои букви не успя да отправи израз, който също е implicant.

Някои implicants на булева функция е (а, б, в)

В нашия прост пример е само implicant г 4 = а. Implicants грама 1 грам и 3 не са съюзи, и г 2 - не е проста, защото когато го пуснете се превръща в друг, неидентифициран нас implicant.

Общата идея на формални методи за минимизиране на булеви изрази е да се намери на минимален набор от първокласни implicants че техните единици биха покрили целия набор от единици на дадена функция. Намирането на набор от implicants, че е възможно да си представим дадена функция като дизюнкция

Формални методи за свеждане до минимум включва следните последователно изпълняват работните стъпки:

а) подходящо представяне на първоначалното данни;

б) идентификация на основните implicants;

в) implicants намаляване на определени до необходимия минимум;

ж) намери минимум под формата на презентация, както се изисква за по-нататъшна работа.

Когато минимизиране от алгебрични представяне компютърна програма на оригиналната функция се заменя със запис във формата на кубичен комплекс. Такъв запис може да се използва в някои относително прости алгоритми (например - алгоритъм Quine-McCluskey), предназначени да изпълняват ръчно.

Ние се само запознаване с един от най-формални методи, най-простите ограничи и фокусирана единствено върху ръчно изпълнение. Методът, предложен в 1953 М. Карно (М. Karnaugh) и се нарича метод на Karnaugh карти.

Karnaugh карта - тя се трансформира в таблицата истината на булева функция, съдържаща 2n клетки, където п - брой аргументи на функция. По този начин, всеки от наборите на стойностите на аргумента съответства на една клетка карта, и тези клетки отговарят нули или такива, които представляват стойностите на функцията на този набор.

Наименования аргументи, взети извън ръба на картата, но основната разлика от таблицата с обичайната истина не е така, и че относителното положение на картата е приведено в съответствие с клетките на върховете на единица куб. Можем да кажем, че Карно карта сканирани самолет наш тримерно единица куб. Поради това, съседните клетки отговарят на съседни карти 0 кубчета, и операцията по свързване получава визуална представа за това как клетките Асоциацията на работа с карти.

Фиг. 2.4 показва три начина да се отнасят до аргументите от ръбовете на картата за функцията на два аргумента.

Фиг. 2.4. Начини за посочване на булеви на аргументите

Букви, цифри и условни графични наименования са приемливи начини еднакво, но увеличаване на броя на аргументи, предпочитание се дава условно графичен като най-компактен.

Frame разпределени свързан, на- единица при извършване на операцията по свързване.

Фиг. 2.5 Veitch диаграма, показваща функциите на три аргументи. Тези карти трябва да се разглеждат като триизмерно сканиране на куба, т.е. Той трябва да се разглеждат като свързани помежду си наляво и надясно край на картата.

Фиг. 2.5. Veitch диаграми

Цифрата показва как можете да комбинирате клетки, за да извършите свързване. Очевидно е, че една и съща единица могат да участват (ако е необходимо) в известно време свързване.

Когато определен брой аргументи п и м комбиниран известен брой клетки се определя лесно от броя на букви в резултат л съюзът (прости implicants): L = N - log2 м.

Може да се комбинират 2, 4, 8, и като цяло т = 2k клетки, където к £ m - цяло число, равно на броя на координати в получената свободна к тримерно куба. Когато свързването не се случи, т.е. с единична клетка се изолира, т = 1, k = 0, и ако всички карти са залепени клетки (това е възможно само за "постоянен 1" функция), след което m = 2n; К = н и минимално DNF не съдържа никакви писма.

Karnaugh карта (Veitch и графики) са удобен и може да се използва вместо обичайните истината таблиците в решаването на практическите проблеми, които, разбира се, с не твърде много аргументи, за да функционират.

Покриването на нула карта, вместо единици, ние получаваме минимална DNF за инверсия на дадена функция.

Запълване на карти Карно не изисква разполагането на дадена функция незаменим в PDNF като в определен умение можете да попълните картата директно на DNF за произволна форма.

Фиг. 2.6 е диаграма Veitch напълнена с израза Þ ,

Фиг. 2.6. Veitch схема за

Единственият недостатък на Karnaugh карти е бързото им сложност с увеличаването на броя на аргументи. След като броят на клетките се удвоява, когато броят на аргументите по един.

Специална роля в процеса на намаляване на логически формули играе частични функции - булеви функции, определянето на площ е по-малка от пълната множество комплекти от стойности на п аргументи. Таблицата истина частично функция в някои клетки съдържат тирета показва, че функцията стойност набор от данни не е определено (Таблица. 2.7).

Пример функция частично истина маса

Частични функции осигуряват допълнителни възможности за свеждане до минимум, така че логично синтез на цифрови устройства се опитват да използват всяка възможност, за да представляват функциите се използват под формата на частични функции. За тази цел могат да бъдат включени следните причини:

а) определя неосъществима. Например, когато кодиране на двоични цифри след десетичната тетради не могат да използват шест тетрадки на шестнадесет. В бъдеще, ако има доверие в невъзможността на появата на непродадените комплекти може да се счита безразличен към съответната стойност на функцията;

б) невалидни комплекти. Има устройства, които не могат да работят правилно при определени комбинации от входни сигнали. източник на сигнал, докато никога не трябва да се създадат такива комбинации. На практика това означава, че същата ситуация, както в претенциите. "А";

в) безразлични буквално стойностите на някои от комплектите, докато всички тези комплекти може да се реализира (отново по желание инсталация или рестартирането и т.н.).

Всеки от тези бази могат да бъдат използвани, за да се обявят някои набори от стойности на аргументите забранено. и стойностите на избираеми или опционални нули съответстващи.

След като се започне да се разгледа тази функция през целия диапазон на аргумент стойности (т.е. обикновено включва домен на забранените комплекти).

Тези промени позволява да се опише функцията на формула като PDNF сключване забранени съставни елементи в скоби. За е показано в таблица. 2.7 Функцията на тези формули:

В първата формула затворени в скоби са по избор единица на функцията F. а вторият - факултативния нула или, еквивалентно, обратна функция на уреда.

Основното, което, обаче, не е така, и в това, минимизиране може произволно да се предефинира функцията, като изберете тези стойности на своите забранени комплекти, които позволяват на покритието за производство на най-добрите.

Тъй като определянето на най-добрите покрития частична функция престава да съществува, и установеното минимално DNP, и на която се основава логическият блок е определен навсякъде.

При използване на Veitch диаграми (Карно картографиране) на проблема за определяне на най-добър обхват частична функция се решава лесно. Фиг. 2.7 показва схема за функцията на раздела. 2.7.

Фиг. 2.7. Veitch диаграма за F (а, Ь, с), предварително определена маса. 2.7

Местоположение елементи от картата, показва, че трябва да сложим функцията равна на единство на снимачната 110 до нула и - при другите три забранени комплекти. В резултат на това на функцията получава много просто израз.

Формално, машинни ориентирани техники оптимална завършвания проблем е решен по-сложен начин.