748
правок
Изменения
→Задача о минимизации контактной схемы
{{Теорема
|statement = Любой булеву функцию можно представить контактной схемой, сложностью <tex>O(2^n)</tex>
|proof =
1)Пусть дана функция <tex>f(x_1,x_2 \dots, x_n</tex> и она представлена в ДНФ.
[[Файл:tree_for_two.png | 250px | thumb | Дерево конъюнктов для 2-х переменных]]
2)Построю дерево конъюнктов для <tex>n</tex> переменных (см. картинку). Очевидно, что от вершины <tex>U</tex> до "нижних" вершин дерево можно добраться за <tex>O(n)</tex>, а ребер у такого дерева <tex>O(2^n)</tex>.
3)Соединим нижние вершины, которые соответствуют конъюнктам функции, с вершиной <tex>V</tex> контактами, над которыми написана <tex>1</tex>. От этого в схему добавится не более, чем <tex>2^n</tex> вершин и тогда сложность останется <tex>O(2^n)</tex>.
В результате можно построить контактную схему для любой функции со сложностью <tex>O(2^n)</tex>
}}
