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-х переменных]]
