Понятие о минимизации

Логических функций

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

Рассмотрим последовательность действий минимизации ЛФ на примере. Пример. Найти минимальную дизъюнктивную форму функции, заданной таблицей истинности

Таблица истинности функции

x1 x2 x2	y
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

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

y=x₁x₂x₃ v x₁x₂x₃ v x₁x₂x₃ v x₁x₂x₃ v x₁x₂x₃ v x₁x₂x₃

Пунктирными линиями в этом выражении отмечены пары конъюнкций, к которым можно применить операцию склеивания типа FxvFx=F.

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