748
правок
Изменения
→Задача о минимизации контактной схемы
[[Файл:tree_for_two.png | 250px | thumb | Дерево конъюнктов для 2-х переменных]]
Построю дерево конъюнктов для <tex>n</tex> переменных (см. картинку). Очевидно, что от вершины <tex>Uu</tex> до "нижних" вершин дерево можно добраться за <tex>O(n)</tex>, а ребер у такого дерева <tex>O(2^n)</tex>
Соединим нижние вершины, которые соответствуют конъюнктам функции, с вершиной <tex>Vv</tex> контактами, над которыми написана <tex>1</tex>. От этого в схему добавится не более, чем <tex>2^n</tex> ребер и тогда сложность останется <tex>O(2^n)</tex>.
В результате можно построить контактную схему для любой функции со сложностью <tex>O(2^n)</tex>
