|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>
