Пример. Найти минимальную ДНФ функции

Найти минимальную ДНФ функции .

Запишем исходную карту Карно для заданной функции (табллица 3.24).

Таблица 3.24 − Исходная карта Карно для заданной функции

Используем графический способ склеивания, объединяя соседние единицы таблицы в группы (нули опускаем). Результатом являются две импликанты А и В (рис. 3.1).

Рисунок 3.1 − Определение импликант функции

Импликанта .

Импликанта .

Таким образом, получим минимальную ДНФ в виде .

Карта Карно для функции четырех переменных имеет размер . Правила склеивания ячеек и записи результирующей формулы остаются прежними.

Рассмотрим построение карты Карно для функции пяти переменных, которая представляет в пространстве двухслойный параллелепипед, где каждый слой соответствует карте Карно от первых четырех переменных функции. Первый слой представляет собой на плоскости всевозможные интерпретации, при которых пятая переменная равна нулю. Вторым слоем являются всевозможные интерпретации, при которых пятая переменная равна единице. Каждая ячейка на карте Карно для функции пяти переменных имеет пять соседних ячеек: четыре на своем слое карты и пятую − на соседней, т.е. ячейку, которая совпадает с данной, если разместить слои карты один поверх другого. Объединение ячеек в группы на каждом слое карты осуществляется, как и в случае четырех переменных. В данном случае можно склеивать две одинаковые группы, находящиеся на разных слоях карты, расположение которых совпадает, если поместить один слой карты поверх другого.

Пример. Построить минимальную ДНФ для функции

.

Построим карту Карно для данной функции (рис. 3.2).

Рисунок 3.2 − Карта Карно для функции

Простые импликанты, входящие в минимальную ДНФ, имеют вид: , , , , .

Минимальная ДНФ записывается при объединении импликант знаками дизъюнкции: .

Минимизация на множестве КНФ. Для минимизации булевой функции на множестве КНФ используются диаграммы Вейча, построение которых аналогично построению карт Карно. Отличие заключается в том, что на карте помечаются ячейки, соответствующие интерпретациям, на которых функция равна нулю. После этого производится склеивание ячеек, содержащих нули и формирование минимальной КНФ. Для склеивания ячеек используются те же правила, что и при получении минимальной ДНФ. Каждая группа ячеек, полученная в результате склеивания, соответствует дизъюнкции только тех переменных, которые имеют одинаковое значение для всех ячеек группы. Переменные берутся без отрицания, если им соответствует нулевое значение, и с отрицанием − в противном случае. Конъюнкция полученных элементарных дизъюнкций является результатом минимизации формулы.

Дата добавления: 2014-10-22; Просмотров: 4169; Нарушение авторских прав?; Мы поможем в написании вашей работы!