Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

5.4. Упрощение логических (булевских) выражений [30, 50, 51, 67, 44, 43]

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

Эта задача, кроме того, эквивалентна задаче построения «простейшей» переключательной (контактной) схемы, реализующей данную логическую формулу.

<< Предыдущий параграф Следующий параграф >>
Оглавление