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

Проблема минимизации логических функций решается на основе применения законов склеивания и поглощения с последующим перебо­ром получаемых дизъюнктивных форм и выбором из них оптимальной (минимальной). Существует большое количество методов минимиза­ции ЛФ. Все они отличаются друг от друга спецификой применения операций склеивания и поглощения, а также различными способами сокращения переборов. Среди аналитических методов наиболее извес­тным является метод Квайна — МакКласки, среди табличных — ме­тод с применением диаграмм Вейча [6]. Графические методы миними­зации отличаются большей наглядностью и меньшей трудоемкостью, однако их применение эффективно при малом числе переменных n≤5.

Рассмотрим последовательность действий минимизации ЛФ на примере.

Пример 2.15.Найти минимальную дизъюнктивную форму функции, заданной таблицей истинности (табл. 2.6).

Таблица 2.6 Таблица истинности функцииУ=f(x₁, x₂, x₃)

Эта функция интересна тем, что имеет несколько минимальных форм. По данным таблицы запишем аналитическое выражение:

Пунктирными линиями в этом выражении отмечены пары конъ­юнкций, к которым можно применить операцию склеивания типаFx V Fx =F. Особенно хорошо это видно при использовании диаграммы Вейча, в которой «склеиваемые» конъюнкции находятся по соседству друг с другом. Диаграмма Вейча просто по-другому интерпретирует таблицу истинности (табл. 2.7).

Та б л и ц а 2.7 Диаграмма Вейча функции у