Булева проблем функция минимизиране е да се намери равностоен формула, с минимална сложност. Сложността на формула съответства на количеството на съставните букви. Най-добре разработени методи за минимизиране Bellevue функции, представени в DNF. Тези методи се основават на концепцията за прости implicants.
Ако булева функция # 966; нула на един и същи набор, който е нула F. Друга функция, както и на някои други групи, а след това ние казваме, че функцията # 966; част от функция F и е implicant. влизане условия е написано, както следва: кÌF. Например, да разгледаме функция F = ХÅY. Нейните функции са implicants
Prime implicants на булева функция F е такива елементарни съюзи, които от своя страна са част от тази функция, но нито някой частен част от тези съюзи в F не е част от функцията. Лично част е продукт, получен чрез изключване от тази работа един или повече фактори. Например, продуктът има собствена част:
Например, за среден и са главни implicants функционира F.
Прости implicants са най-кратките елементарни съюзи, включени в дадена Булева функция.
Всеки Булева функция може да се представи като разделяне на всички свои председатели implicants. Разделение на всички председатели implicants наречена съкращение функция DNF Булева. Има няколко алгоритми за получаване на намалената функция DNF Булева. Един от най-добре развита е метод за Куайн.
метод Куайн. Този метод се основава на превръщането PDNF чрез частични операции на абсорбция и свързване.
залепване операция (пълна) се дава от
Твърди се, че два члена на XY и залепени на променливата Y.
Операция непълна залепване се определя от
От дясната страна, с изключение на член X. получени чрез залепване, написана и двамата членове, участващи в свързване.
Операция на коефициента на поглъщане от
теорема Куайн е. Ако функцията PDNF Булева за провеждане на всички операции на непълно свързване, а след това всички операцията на абсорбция, можете да получите съкратен DNF на тази функция, т.е. разединяване на всички свои председатели implicants.
Почти съкращение DNP се намира в следната последователност.
PDNF проведе във всички възможни операции на непълни свързващи съставки на единство и на всички възможни операции на поглъщане.
След това, за да се тества всички операции на непълно свързване и абсорбиращи елементи (N -1) писмо.
Извършва всички възможно действието на частичното свързване и абсорбиращи елементи с редица писма равна на (п -2) и така нататък. D.
Ние извършваме всички възможни работа на частично свързването и усвояването на четири съюзи. Резултатът е показан:
Несвързана Резултати
Напишете стенограмите формула, която трябва да включва съюзи в резултат от свързване, както и тези изходни съставки единици, които не се държим заедно:
В този израз отново изпълни всичко възможно операции свързване и усвояване:
На първия и четвъртия, втората и третата условията са залепени по двойки. Петата и шестата членовете остават. По този начин, ние получаваме:
В този израз, има членове, които се държим заедно, така че е съкратена разделителен нормална форма. За да намерите минимална дизюнктивен формата, можете да използвате implikantnoy матрица. В колони маркиран матрични съставки implikantnoy дадени функционални единици и линии - implicants, получени в резултат на сцепление (Таблица 5.).
Ако implicant е правилно подмножество на съставките на единица клетка на матрицата, съответстваща на тази единица implicants и съставки, се маркира с кръст. За да се получи минимален разделителен нормална форма предварително определена функция, за да се намери на минималния брой implicants които заедно покриват цялата матрица кръстоски implikantnoy колона. В този пример, минималната разделителния формата, дадена функция има формата
.
То може да бъде, че функцията има минимален брой различни форми на една и съща сложност.
Karnaugh карта (Veitch). Karnaugh карта е правоъгълник, разделен на клетки, броят на които е равен на броя на всички възможни набори от независими променливи, посочени логика функция. За две променлива функция карта съдържа 4 клетки за 3 променливи функция - 8 клетки, и т.н.
Помислете карта в продължение на две променливи (фиг. 21). Всяка клетка отговаря на съставна единица на картата.
Фиг. 21. Karnaugh карта за фиг. 22. Karnaugh карта за
функции на 2 променливи функционират 3 променливи
С добавянето на променливи картата се удвоява. Фиг. 22 показва карта Karnaugh за функцията на 3 променливи.
При изграждането на картата, можете да използвате следното правило: Karnaugh карта за функцията на наш променливи се получава от картата за функцията н -1 променливи, ако последният не е да се удвои, като добавите към него точно същото разположени симетрично по отношение на дългата страна. В този случай, половината от новата карта е белязана с ново писмо утвърдително и втората половина - една и съща буква, но с отказ. Фиг. 23 показва карта Karnaugh за функцията на 4 променливи получени от картата е показано на фиг. 22. При правилно маркирани нагоре карта на всеки две клетки разположен следващия мач
Ние ги лепят съставки на единство. В допълнение, всеки две клетки, разположени на краищата на картата симетрично ляво и дясно или отгоре и отдолу, също съответстват на лепило заедно съставна единица.
Минимизиране на предварително определена логическа функция използване Karnaugh карта се извършва в следната последователност.
1. Определете функцията се превръща в PDNF.
2. Всяка съставна единица на дадена функция е отбелязано в съответната единична клетка Karnaugh карта.
3. Единици са разположени един до друг, или симетрично по краищата на картата, обхванати от редовните правоъгълници. В същото време отговаря на следните изисквания:
- на броя на единиците, включени в един правоъгълник, за да бъде равна на 2 к. където К - цяло число;
- всеки правоъгълник трябва да покрива най-много единици, тъй като броят на правоъгълници покритието трябва да бъде възможно най-малък;
- една и съща единица може да бъде покрит няколко пъти от различни правоъгълници.
4. За всеки правоъгълник, покриващ устройството, моля, напиши съюзът, който трябва да въведете буквите, които са общи за единиците, покрити с този правоъгълник.
5. Напиши минимум DNF. което следва да включва съюзи, обхващащи всички съответни правоъгълници. Ако картата е единица стоящи изолира от другите и не са обхванати от правоъгълник, след това се прибавя към получения дизюнкцията напълно подходящи съставки единици.
6. Ако е възможно, нарязани с формула получен чрез общите членовете на конзолите.
Пример. Да разгледаме функцията на четири променливи. Нека PDNF предварително определена функция е в следния формат:
Всяка съставна единица на по-горе функция, имайте предвид, устройството в подходяща кутия Karnaugh картата (вж. Фиг. 23). За по-голяма яснота, правоъгълници, които обхващат уреда, обърнете внимание на овални линии. Минимална DNP тази функция има следния вид:
Karnaugh карта за функцията на пет променливи е показано на фиг. 24. Функцията на шест променливи ¾ на фиг. 25. Karnaugh Карти за функции на пет или шест променливи имат следните характеристики. Съюзи adherend съответстват единици, разположени вътре в картата симетрично по отношение на централната ос на симетрия.
Пример. Нека функция от пет променливи представени единици са маркирани на картата Karnaugh на фиг. 24. В резултат на това, ние получаваме най-малко следната DNP покритие:
Минимизиране на функциите на шестте променливи, помислете примера на функционални единици, отбелязани в картата на фиг. 25. В резултат на това, ние получаваме покритие:
При изпълнение на implicants, полученото покритие единици Karnaugh карта, е възможно да се контролира използването на следните зависимости: L = п-к. m = 2 к. където L - брой на букви в implicants получени чрез покритие, m - брой на единици, обхванати от данните на правоъгълник, к - брой на писма абсорбира в резултат на свързване, п - брой независими променливи във функцията.
Фиг. 25. Karnaugh карта за функция 6 променливите на
Свързани статии