|statement = Любой булеву функцию можно представить контактной схемой, сложностью <tex>O(2^n)</tex>
|proof=Построим дерево конъюнктов для n переменных и их отрицаний. Это дерево будет содержать <tex>O(2^n)</tex> контактов. Внизу дерева получится <tex>2^n</tex> вершин. Очевидно, что каждая вершина соответствует одному конъюнкту. Если соединить часть из этих вершин с вершиной <tex>v</tex> ребрами, на которых написана <tex>1</tex>, то сложность полученной схемы не изменится.
Поэтому любую булевую функцию можно представить контактной схемой, сложностью <tex>O(2^n)</tex>
