Минимизация представлений булевых функций

Одной из важнейших задач, возникающих при синтезе переключательных схем, является минимизация представления БФ путем тождественных преобразований.

Представление БФназывается минимальным, если оно включает минимальное количество вхождений букв (обозначений переменных) по сравнению с другими эквивалентными представлениями.

В настоящее время при решении практических задач синтеза переключательных схем пользуются различными алгоритмами упрощения представлений БФ. Необходимо отметить, что применение любого из алгоритмов не гарантирует получения минимальных форм, но позволяет достаточно эффективно получать формы, близкие к минимальным. Это обусловлено тем, что упрощение может быть достигнуто различными путями. Кроме того, неоднозначно определяется минимальное представление функций алгебры логики. Одна и та же функция может иметь несколько минимальных форм. Так, например, для функции

существуют две эквивалентные минимальные ДНФ:

и .

Чаще всего упрощение представления БФ осуществляется посредством использования в различной последовательности и интерпретации свойств склеивания и поглощения.

Мы ограничимся рассмотрением двух распространенных способов минимизации представления БФ: минимизации с помощью карт Карно и метода неопределенных коэффициентов. Представление БФ с помощью карт Карно является одним из самих наглядных и позволяет оценить расположение функции в пространстве, а метод неопределенных коэффициентов наиболее формализован и удобен для программирования.