Изменения

'''Контактная схема''' (англ. ''contact shemecircuit'') представляет собой [[Основные определения теории графов|ориентированный ациклический граф]], на каждом ребре которого написана переменная или ее отрицание.

'''Контакт''' (англ. ''contact'') {{---}} ребро схемы, помеченное символом переменной или ее отрицанием

Пусть <tex>u</tex> и <tex>v</tex> {{---}} 2 два полюса контактной схемы <tex>S</tex>, <tex>[u,v]</tex> {{---}} некоторая цепь, соединяющая <tex>u</tex> и <tex>v</tex>, <tex>K(u,v)</tex> {{---}} конъюнкция букв прописанных на ребрах <tex>[u,v]</tex>. Пусть функция <tex>f(x^n)</tex> определяется формулой: <tex>f(x^n)={\bigvee\limits_{[u,v]} (K(u,v))}</tex> в которой дизъюнкция берется по всем простым цепям схемы, соединяющие полюса <tex>u</tex> и <tex>v</tex>. Говорят, что схема <tex>S</tex> реализует функцию <tex>g(x^n)</tex>, если <tex>f(x^n)=g(x^n)</tex>.

Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к [[ДНФ|ДНФ]] или [[КНФ|КНФ]], а затем построить, используя комбинации 3 трех логических элементов:

Две контактные схемы называются '''эквивалентными''' (англ. ''equivalent contact circuits)'', если они реализуют одну и ту же булеву функцию.

'''Сложностью контактной схемы''' {{---}} (англ. ''the complexity of the contact schemecircuit'') называется число

|definition='''Минимальная контактная схема''' {{---}} (англ. ''Minimal contact schemecircuit'') схема, имеющая наименьшую сложность среди эквивалентных ей схем.

* [[Реализация_булевой_функции_схемой_из_функциональных_элементов|Построение функциональной схемы]]