Эксперт по сдаче вступительных испытаний в ВУЗах
Лабораторная работа по дисциплине «Информатика»
Цель работы
Изучить метод Квайна–Мак-Класки минимизации логических функций.
Задание на лабораторную работу
Минимизировать методом Квайна–Мак-Класки логическую функцию (таблица 1).
Таблица 1 — Варианты заданий на работу
Вариант f(a, b, c, d, e)
5 ⋁_1▒〖(9,11,13,18,24,26)〗
Ход работы
Найдем минимальную форму для функции
f(x_1,x_2,x_3,x_4,x_5 )=⋁_1▒〖(9,11,13,18,24,26)〗
1
Таблица 2 — Первичные импликанты С0
Кубический комплекс Число единиц Кубы Метки
С0 2 01001 *
10010 *
11000 *
3 01011 *
01101 *
11010 *
Затем производится поглощение 0-кубов 1-кубами (таблица 3). Сам процесс аналогичен поглощению 0-кубов.
Таблица 3 — Первичные импликанты С1
Кубический комплекс Число единиц Кубы Метки
С1 2 010*1 *
01*01 *
1*010 *
110*0 *
В результате выполнения нескольких циклов получается искомая совокупность простых импликант. Для выбора минимально
необходимой совокупности строится еще одна таблица (таблица 4).
В данном случае импликанты из первой, второй, третьей и четвертой строк обеспечивают минимальное покрытие.
Таблица 4 — Таблица покрытий
01001 01011 01101 10010 11000 11010
010*1 V V
01*01 V V
1*010 V V
110*0 V V
Ответ:f(x_1,x_2,x_3,x_4,x_5 )=x ̅_1 x_2 x ̅_3 x_5 x ̅_1 x_2 x ̅_4 x_5 x_1 x ̅_3 x_4 x ̅_5 x_1 x_2 x ̅_3 x ̅_5
Ответы на контрольные вопросы
В каком виде должна быть представлена функция для минимизации по методу Квайна–Мак-Класки?
При минимизации по методу Квайна предполагается, что минимизируемая функция представлена в СДНФ.
Как в методе Квайна–Мак-Класки называются непоглощенные n-кубы?
Непоглощенные кубы называются «первичная импликанта».
Какова особенность минимизации n-кубов в методе Квайна – Мак-Класки?
Суть метода в следующем. Члены СДНФ записываются в виде их двоичных номеров. Все номера разбиваются на группы по числу единиц в них. При этом в i-ю группу входят все номера, которые имеют в своем двоичном коде количество единиц равное i. Затем выполняется попарное сравнение членов соседних по номеру групп (т.е. реализуется закон склеивания по отношению к кодовым комбинациям), так, как только члены этих групп отличаются лишь в одном разряде. При образовании членов с рангом (числом единиц) выше нулевого в разряды, соответствующие исключенным переменным, пишется знак тире (прочерк). В остальном методика не отличается от метода Квайна.
Для чего в методе Квайна–Мак-Класки строится таблица покрытий?
Понятно, что для нахождения минимальной формы покрытия необходимо удалить из покрытия некоторые простые или неотмеченные импликанты. Для этого используют таблицу, строки которой составляют импликанты покрытия, а столбцы — 0-кубы (минтермы) исходной функции. Если импликанта отличается от 0-куба (кроме независимых координат), то на их пересечении не ставится метка *.
По какому принципу производится выбор подмножества простых импликант?
Заданные логические функции могут быть построены из любой совокупности импликант, совместно перекрывающих все колонки импликантной матрицы. Задача состоит в выборе подмножества импликант с минимальным числом букв. Для выбора такого помножества прежде всего найдем колонки с меткой Fi и конституентой Кj, имеющие единственный крестик. Соответствующая данному крестику импликанта должна обязательно входить в функцию Fi, так как только она поглощает конституенту Кj.
В какой форме представляется результат минимизации по методу Квайна–Мак-Класки?
Полученный результат записывается следующим образом:
— выписываются дизъюнкции, соответствующие полученному решению (интервалам): если входит как 0, он вписывается без изменений в дизъюнкцию, если входит как 1, то в дизъюнкцию вписывается его отрицание;
— все полученные дизъюнкции соединяются между собой знаками конъюнкции.
Выводы по проделанной работе
Изучил метод Квайна–Мак-Класки минимизации логических функций. В методе Квайна есть одно существенное неудобство. Оно связано с необходимостью полного попарного сравнения на этапе- нахождения простых импликант. С ростом числа минитермов, определяющих ДСНФ данной функции, растет число этих сравнений. Этот рост характеризуется факториальной функцией. Поэтому при достаточно большом числе ммнитермов применение метода Квайна становится затруднительным.
Ссылка на первоисточник:
https://rosakademy.ru
