Изменения

'''Контактная схема''' (англ. ''contact sheme'') представляет собой [[Основные определения теории графов|ориентированный ациклический граф]], на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют .}} {{Определение|definition ='''Контакт'контактами'', а вершины {{---}} (англ. ''полюсамиcontact'').ребро схемы, помеченное символом переменной или ее отрицанием

Зафиксируем некоторые значения переменным. Тогда '''замкнутыми''' называются ребраПусть <tex>u</tex> и <tex>v</tex> {{---}} 2 полюса контактной схемы <tex>S</tex>, на которых записана <tex>1[u,v]</tex>{{---}} некоторая цепь, ребра, на которых записан соединяющая <tex>u</tex> и <tex>0v</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>1S</tex> на тех наборах переменных, на которых между реализует функцию <tex>ug(x^n)</tex> и , если <tex>vf(x^n)=g(x^n)</tex> есть путь по замкнутым ребрам.

* Упрощаем <tex>F(S)</tex>, то есть отыскиваем функцию <tex>G</tex> (на том же базисе, что и <tex>F(S)</tex>), равносильную <tex>F(S)</tex> и содержащую меньше вхождений операций дизъюнкции и конъюнкции. Для этой операции удобно использовать [[Сокращенная_и_минимальная_ДНФ| карты Карно]].