Расчетный метод минимизации

Каждый из конкретных методов минимизации состоит из тех же трех шагов, что указывалось выше. Но эти шаги в каждом методе могут иметь свою особенность.

1.Склеивание всевозможных членов исходной СНД(К)Ф, т.е. сначала конституент, затем импликант ранга и т.д., пока склеивание возможно.

2. Проверка каждой простой импликанты в сНД(К)Ф на избыточность с целью её удаления. Проверка состоит в следующем. Так как любая импликанта равна 1 для НДФ (0 для НКФ) лишь на одном наборе переменных, то если на этом наборе сумма остальных членов также обращается в 1 (0), то рассматриваемая импликанта не влияет на значение истинности данной логической функции, т.е. она является избыточной. Удаляя все такие импликанты, получим ТНД(К)Ф.

3. Упрощение полученной ТНД(К)Ф путем применения операции отрицания и распределительного закона 1-го или 2-го рода.

Пример. Минимизировать функцию

1. Выполняя склеивание, получим сНД(К)Ф:

.

2.Удаляем избыточные импликанты: на наборе так как то импликанта - избыточная; на наборе ; а так как , то импликанта не является избыточной; на наборе а так как , то импликанта не является избыточной.

Таким образом, отбросив избыточную импликанту, получим ТНДФ

.

3. Дальнейшему упрощению функция не поддается.

Если исходной является СНКФ, то методика выполнения 1-го шага не меняется. Но реализация 2-го шага имеет свою специфику. На значение истинности функции, представленной в СНКФ, не влияет та импликанта, которая сама равна 0. Но любая импликанта становится нулем только при одном наборе переменных. Следовательно, правило проверки на избыточность можно сформулировать так:

· для каждого члена СНКФ определяется набор переменных, которые обращают данный член в 0;

· если произведение остальных членов также равно 0, то данный член избыточен.

Пример. Получить исходную СНКФ, эквивалентную СНДФ в предыдущем примере, и упростить её. Исходную СНКФ проще всего получить из таблицы истинности, составив ее по СНДФ в предыдущем примере. Упрощенная таблица истинности, т.е. без подробного выписывания всех операций, и соответствующая СНКФ имеют вид:

1. В результате всевозможных склеиваний получаем сНКФ

2. Дизъюнкция при так как , то импликанта – неизбыточна.

Дизъюнкция при ; так как , то импликанта – избыточна. Дизъюнкция при , ; так как , то импликанта не является избыточной.

Таким образом,

3. Упрощаем полученную ТНКФ, применив закон де Моргана ко 2-му её члену. В результате получим минимальную форму (МФ)

Это действительно минимальная форма, так как число операций в ТНКФ уменьшилось от 5 до 4 при том же числе переменных