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

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

Процедура упрощения функции, заданной в виде СДНФ, сводится к следующему.

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

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

Пример 3.7 Минимизировать функцию, полученную в примере 3.5.

Для исходной формулы функции в виде СКНФ после выполнения операций полного склеивания вида (x+y)(x+ )раскрывают скобки, пользуясь распределительным законом, приводят подобные члены и применяют операцию поглощения. Полученную. ДНФ, если требуется, минимизирует, как было указано выше,

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

Другой пример минимизации:

.

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

Контрольные вопросы

1) Как формируются нормальные дизъюнктивные и конъюнктивные формы?

2) Как формируются совершенные нормальные дизъюнктивные и конъюнктивные формы?

3) Как минимизируются логические функции?