Imath уики - минимизиране на булеви функции

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

В тази връзка, че има проблем с минимизиране на логически функции в един клас от формули. По-специално, класовете ИЕЯС и CNF.

Тази минимална DNF DNF, която има най-малък общ брой повторения на променливи, в сравнение с всички равносилно на нея DNF. Тази минимална CNF CNF, която има най-малък общ брой повторения на променливи, в сравнение с всички CNF еквивалентен на него.

Процесът на намиране на минимални форми, всъщност, се нарича минимизиране. С прости случаи, достатъчно, за да сведе до минимум трансформации за самоличност. В по-сложна - с помощта на специални алгоритми.

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

По същия начин, за CNF:

Възможността за усвояване следва от очевидно равенство

По този начин, основната задача, като същевременно минимизират PDNF и SKNF е да се намери членове подходящ за залепване с последващо усвояване че за големи форми може да бъде доста предизвикателство.

Графичен метод за минимизиране булеви функции. Това е по двойки операция непълна свързване и елементарна усвояване. Karnaugh карти се считат за вградени съответно истина функция на маса.

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

Karnaugh карта е изобретен през 1952 г. от Едуард У. Veitch и подобрена през 1953 г. Morisom на Карно, физик от «Bell Labs", и са предназначени да помогнат на опростяване на цифрова схема.

На Karnaugh картата булеви променливи се предават от таблицата на истината и подредени с помощта на код на Грей, в която всяко следващо число се различава от предходния само един бит.

Булеви функции \ (N \) променливи, представени под формата на PDNF SKNF или могат да бъдат съставени от \ (2 ^ N \) различни елементарни членове.

Начални членове PDNF SKNF форма или структура е топологично еквивалент \ (N \) тримерно куб. Действително, ако вземем предвид множеството от стойности на функцията \ (x_1, \, \ ldots, \, x_N \), тъй като \ (от N \) двумерен вектор \ (\\). ние получаваме набор от точки на векторите на единични \ (N \) тримерно координатна система и отдалечен от друг \ (1 \). С други думи, ние получаваме \ (М \) двумерен хиперкуб с ръб \ (1 \).

Например, за функция на две променливи, определени от таблицата на истината:

може да се изгради равностоен квадрат:

0 01 1 11 0 00 1 10

Или, ако означим върховете на съответните съюзи и маркирайте елементарни върхове, които са във връзка PDNF:

X̅₁x₂ x₁x₂ 0 1 0 1 x̅₁x̅₂ x₁x̅₂

X₁∨x̅₂ x̅₁∨x̅₂ 0 1 0 1 x₁∨x₂ x̅₁∨x₂

Може да се отбележи, че членовете на които са от едната страна на квадрата могат да бъдат залепени. Съответно, ако се прави DNP, операцията се извършва само по върховете, при които функцията е настроен на \ (1 \) (в зависимост от правилата на строителството PDNF). Ако подготвени CNF, а след това в продължение на върховете, при които функцията е настроен на \ (0 \) (в зависимост от правилата на строителството SKNF).

По този начин, променливите се съхраняват, на стойност от страната, която е постоянно.

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

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

Като цяло можем да кажем, че \ (2 ^ K \) члена, които принадлежат към една и съща \ (K \) -face хиперкуба, залепени един член, с абсорбират \ (K \) променливи.

Karnaugh карта е едно сканиране на хиперкуб върху равнина. Например, един триизмерен куб на предишния пример може да се разгърне, както следва:

X̅₁x̅₂x̅₃ x̅₁x̅₂x₃ 1 1 0 0 x̅₁x₂x̅₃ x̅₁x₂x₃ x₁x₂x₃ 0 0 1 x₁x₂x̅₃ x₁x̅₂x₃ 1 x₁x̅₂x̅₃

Karnaugh карта е представяне на двуизмерен сканиране под формата на таблица.

В този случай, всички крайни клетки са съседни един на друг. Тя може да си представим, дърпане на почистване на тор ( "поничка"):

Също така е възможно да се изгради класациите за функции Карно 5 и 6 променливи, но работата с тях е значително затруднено. В продължение на няколко променливи, повече от 6, използването на карти на Карно просто непрактични.

Да разгледаме функцията като следната таблица истина:

\ (F (x_1, x_2, x_3, x_4) \)

Препишете тази таблица като карта Karnaugh:

Лесно разделени в три групи. Съответно, записани DNP:

метод Куайн-MakKlassi се основава на същата машина като картата Karnaugh, но това е по-практично за по-голям брой променливи.

Алгоритъмът е в съответствие лепене, а след това в резултат на намалението.

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

След това, членовете на които се различават по една променлива (един бит), могат да бъдат залепени. В този случай, устройството се заменя с "-". Очевидно е, че могат да бъдат залепени само членовете на съседни групи

Членовете, които не могат да се държим заедно, означени със звездичка "*".

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

Когато нито един член не може да бъде свързана, от членовете, маркирани с "*", кратката форма е направена. които не е задължително да е минимално. Това е последвано от редукция.

За намалението, маса, в която редовете са включени членове на редуцираната форма, както и в колоните - перфектни членове.

Клетките постави марка (например, на кръст "х"), ако съответния срок на редуцираната форма на съответния елемент абсорбира перфектна форма (т.е., ако заглавието на ред е част от заглавието на колона).

Избрани колони, съдържащи само един "х". Sootvetsvtuyuschie техните членове съставляват ядрото на редуцираната форма. и да влезе в минимална форма.

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

Намерете минимална форма на функцията