Метод на карта на Карно за намиране на минималната dnf
Картата на Карно е равнинна интерпретация на 4-измерен булев куб.
00
Смятаме, че левият ръб е залепен към десния, а горният ръб е залепен към дъното.
Ако таблицата на Карно е сгъната по този начин, тогава ще получите тор (торусът е геометрична фигура, наподобяваща поничка).
Правила за намиране на интервали.
Интервал от ранг 1 може да бъде 2 съседни реда (2 съседни колони)
Интервал от ранг 2 може да бъде целият ред, цялата колона или квадрат 2x2.
Интервал от ранг 3 е всеки 2 хоризонтално и вертикално съседни клетки.
Един единствен връх ще бъде интервал от ранг 4.
Алгоритъмът е същият.
Лекция 6 Метод на Quine-McCloskey за намиране на минималната dnf
Този метод е удобен за намиране на минималната DNF функция на произволен брой променливи.
Дефиниция.Елементарната конюнкция K1 покрива ECK2, ако всяка променлива в K1 също е в K2.
K е конюнкция на други променливи.
__ _ _ __ _ _
Свързване на две ЕК
Идея за метода на Куайн (алгоритъм)
Всички елементарни конюнкции се изписват от функцията SDNF.
Извършват се всички възможни залепвания между тези ЕК. Получените нови КИ се записват заедно със старите.
Между тях отново извършваме всички възможни залепвания възможно най-дълго. В резултат на това всички прости импликанти на функцията ще се появят сред ЕК.
Извършваме поглъщането между всички получени ЕК, тоест оставяме само тези ЕК, които не са покрити от други.
В резултат на това се получават само прости импликанти. Тяхната дизюнкция е съкратено ДНФ. Тогава всичко върви според тривиалния алгоритъм за минимизиране.
Формализация на Макклоски.
Всеки EC е свързан с булев вектор. (x с отрицание - 0, безотрицания - 1).
Изписваме всички EC от функцията SDNF във формализиран вид в колона, като ги подреждаме във възходящ ред на броя на единиците във векторите и ги разделяме на класове според броя на единиците.
Между ЕК извършваме всички възможни залепвания. Резултатът се записва в нова колона вдясно, а ЕК, участвали в залепването, са отбелязани със звездичка.Могат да се залепват само EC от съседни класове.
За получената колона приложете отново стъпка 2.
Всички ЕК, които не са маркирани със звездичка, са прости импликанти.
Изграждаме таблица Quine според следното правило:
A) Свържете всеки ред с проста импликанта Pi.
B) Всяка колона - EC от SDNF Kj.
Ако Pi покрива Kj, тогава поставяме знака + в съответната клетка.
Търсят се основни импликанти (колона, съдържаща само знак 1 +). Тази линия е звуковата линия (линията, в която се съдържа този кръст).
Изграждаме съкратена таблица (Задраскваме звуковите линии, а след това колоните, където има зачеркнати кръстове).
Допълваме ядрото до безизходица DNF (Търсим минималната комбинация от редове, така че всяка колона да включва поне един кръст). Дизюнкцията на тези низове ще даде DNF в задънена улица.
Измежду всички задънени DNF избираме минималния.