Минимизация логических функций

Задача минимизации логической функции заключается в том, чтобы найти наиболее компактное ее представление в виде нормальной формы минимальной сложности – минимальной дизъюнктивной нормальной формы (МДНФ) или минимальной конъюнктивной нормальной формы (МКНФ).

Минимальная нормальная форма – это нормальная форма, содержащая минимальное количество переменных, использованных с отрицанием или без.

Минимальная дизъюнктивная нормальная форма – это дизъюнкция минимального числа конъюнкций переменных, взятых с отрицанием или без.

Минимальная конъюнктивная нормальная форма – это конъюнкция минимального числа дизъюнкций переменных, взятых с отрицанием или без.

Метод эквивалентных логических преобразований

Получение МДНФ (МКНФ) через упрощение СДНФ (СКНФ) по правилам преобразования.

Диаграмма Вейча (карта Карно)

Графический способ минимизации логических функций. Работает на основе операций склеивания и поглощения. Представляет собой особым образом переупорядоченную таблицу истинности.

Операция склеивания осуществляется между двумя совершенными конъюнктами (дизъюнктами), у которых совпадают все литералы, кроме одного. По правилам склеивания совпадающие литералы выносятся за скобки, а оставшиеся подвергнуть склейке.

В диаграмме Вейча ячейки таблицы истинности сгруппированы таким образом, что переход из одной ячейки в другую по вертикали или горизонтали связан с изменением значения только одной переменной. В результате этого наборы, между которыми возможно склеивание, получаются сгруппированными вместе и их легко заметить. Метод Вейча подходит для минимизации функций до 7 переменных. При большем количестве теряются достоинства метода.

Интервал логической функции от  переменных – это такое множество наборов значений переменных, что:

· Значение функции на этом множестве постоянно;

· Мощность (величина, размер интервала) этого множества равна , ;

·  является количеством переменных, которые упрощаются на этом множестве, а оставшихся () переменных достаточно для описания логической функции на данном множестве;

· Если , то каждый следующий набор отличается от предыдущего значением только одной переменной.

Типы интервалов

*		*		*	*		*
		*		*	*		*
*							*
		*		*	*		*
*		*		*	*
*

Интервал размера 1

Вырожденный случай. Упрощения не происходит. Интервал может встречаться на любых диаграммах.

Интервал размера 2

Упрощается одна переменная. Интервалы могут встречаться на любых диаграммах.

Интервал размера 4

Упрощается 2 переменных. Некоторые интервалы встречаются, начиная с диаграммы Вейча для функции от 3 переменных.

Интервалы размером 8

Упрощается 3 переменных. Некоторые интервалы встречаются, начиная с диаграммы Вейча для функции от 4 переменных.

Алгоритм минимизации

1. Нарисовать исходную таблицу диаграммы и сделать ее разметку в зависимости от количества переменных функции.

2. Заполнить таблицу значениями функции с учетом цели минимизации (удобно выписывать только 1 для МДНФ и только 0 для МКНФ).

3. Выделить контурами интервалы из единиц (МДНФ) или нулей (МКНФ), соблюдая следующие правила:

a. Необходимо стараться выделить максимально большие интервалы;

b. Каждый новый интервал должен содержать хотя бы одно значение, принадлежащее только ему;

c. Необходимо выделить минимально возможное количество интервалов.

4. Выписать формулу МДНФ (МКНФ), для чего:

a. Для каждого интервала выписать конъюнкт (дизъюнкт), в который будут входить только те переменные или их отрицания, которые сохраняют свое значение на интервале. Остальные переменные упростятся.

b. Соединить выписанные конъюнкты (дизъюнкты) через дизъюнкцию (конъюнкцию).