Построить дизъюнктивную нормальную форму (ДНФ) заданной переключательной функции и представить ПФ картой Карно

Построить дизъюнктивную нормальную форму (ДНФ) заданной переключательной функции и представить ПФ картой Карно.
Минимизировать ПФ с помощью карты Карно по «единицам» и «нулям». Выбрать минимальное покрытие.
Построить минимальные дизъюнктивную (ДНФ) и конъюнктивную (КНФ) нормальные формы ПФ.

Решение:

Задана ПФ трех (n=3) переменных в виде совершенной ДНФ (СДНФ)
(1)
Карта Карно для данной ПФ (рис.1) состоит из клеток. Каждая клетка карты описывается тремя (n=3) координатами, причем любые соседние клетки отличаются одной координатой [4, 5].

Рисунок 1. Карта Карно для функции трех переменных

Для минимизации ПФ по «единицам» при определении минимальной ДНФ на карте Карно ставится «1» в клетке, описываемой набором координат, на котором функция принимает единичное значение (рис.2, а). Затем находится покрытие единиц карты Карно минимальным количеством прямоугольников максимальных размеров со сторонами длиной, кратной степени двойки, т.е. , где i, j целые числа. Минимальное покрытие единиц для функции f1 (см. рис.2, а) выделено прямоугольниками, содержащими и клеток.
Один прямоугольник (см. рис.2, а) образует 2-куб, поскольку объединяет четыре соседние клетки карты Карно, отличающиеся попарно по одной координате, и, следовательно, подвергается операции склеивания:. Клетки, лежащие на границах карты Карно, также является соседними:
Отсюда следует, что каждому полученному прямоугольнику карты ставится в соответствии некоторая конъюнкция, в которой отсутствуют переменные, изменяющие в данном прямоугольнике свои значения.
Дизъюнкция элементарных конъюнкций, описывающих полученные на карте Карно (рис.2, а) прямоугольники, образует минимальную ДНФ функции:

Читайте также:  Составить размеченный граф состояний соответствующий матрице Λ

Для построения ПФ в виде минимальной КНФ целесообразно произвести минимизацию обратного значения ПФ по «нулям». Для этого на карте Карно в клетки с координатами, соответствующими наборам переменных, на которых ПФ принимает нулевые значения, ставиться «0». Далее для нулевых клеток находится минимальное покрытие.
Карта Карно для обратного значения ПФ , имеет вид (рис. 2, б), ей соответствует минимальная ДНФ
. (2)
Используя правила Моргана, из (2) получаем минимальную КНФ ПФ:

Рисунок 2. Минимизация ПФ f1 по «единицам»(а) и нулям(б) с помощью карты Карно

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...