1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Определение
|definition =
'''Замкнутый контакт''' (англ. ''closed contact'') {{---}} контакт схемы, над которым написана <tex>01</tex> или значение переменной равно <tex>01</tex>.
}}
{{Определение
|definition =
'''Разомкнутый контакт''' (англ. ''open contact'') {{---}} контакт схемы, над которым написана написан <tex>10</tex> или значение переменной равно <tex>10</tex>.
}}
Пусть <tex>u</tex> и <tex>v</tex> {{---}} два полюса контактной схемы (из вершины <tex>u</tex> ребра только выходят, в вершину <tex>v</tex> ребра только входят), определяющую функцию <tex>g(x_1, x_2 \dots, x_n)</tex>. Тогда <tex>g(x_1, x_2 \dots, x_n)</tex> принимает значение <tex>1</tex> при таком наборе значений переменных, если можно добраться из <tex>u</tex> в <tex>v</tex> только по разомкнутым замкнутым контактам.
==Построение контактных схем==
Пусть задана произвольная булева функция. Требуется построить для нее контактную схему, которая ее реализует.
В качестве примера рассмотрим функцию, представленную в [[ДНФ|ДНФ]]: <tex>f=(\neg x \land y \land \neg z) \lor (x \land \neg y \land \neg z) \lor (x \land y \land z)</tex>. Каждой скобке [[ДНФ|ДНФ]] соответствует цепочка из последовательных соединенных контактов, определяемых переменными содержащимися в скобке. При этом, вся схема состоит из параллельных соединений указанных цепочек. Для приведенного примера соответствует схема приведена ниже.
[[Файл:example10.png|320px]]
{{Теорема
|statement = Любой Любую булеву функцию можно представить контактной схемой, сложностью <tex>O(2^n)</tex>
|proof =
Пусть дана функция <tex>f(x_1,x_2 \dots, x_n)</tex> и она представлена в [[ДНФ|ДНФ]]
