Реализация булевых функций релейно-контактными схемами

Каждой логической переменной x поставим в соответствие катушку, по обмотке которой идёт или не идёт ток в зависимости от того х=1 или х=0. С каждой катушкой может быть связано любое число контактов. Контакт называется замыкающим, если он проводит ток в том и только в том случае, когда в соответствующей катушке есть ток, и размыкающим, если он проводит ток только в том случае, когда в катушке нет тока.

Конъюнкции логических переменных соответствует последовательное соединение контактов, а дизъюнкцией - параллельное. Контакт будем изображать отрезком (не обязательно прямым), и называть двухполюсником, его концы - полюсами (вершинами). Двухполюснику приписывается символ х или`х в зависимости от того, будет он замыкающим или размыкающим. Если в данный момент двухполюсник проводит ток, то мгновенно ток протекает по всем замкнутым двухполюсникам, имеющим с данным общую вершину.

Специально зафиксированы две вершины: "вход" и "выход". На "вход" всегда подаётся напряжение, а на другие вершины напряжение не подаётся никогда. Ток на "выходе" возникает тогда и только тогда, когда имеется хотя бы одна последовательная цепочка замкнутых двухполюсников, соединяющая "вход" и "выход". Данная схема (или граф) называется контактной.

Каждой контактной схеме можно сопоставить логическую (булеву) функцию, принимающую значение 1 для тех и только тех наборов значений переменных, приписанных двухполюсникам, которым соответствует проводимость в схеме (есть ток от "входа" к "выходу"). Эта функция называется функцией проводимости схемы. В качестве функции проводимости можно взять дизъюнкцию всех конъюнкций, соответствующих всем "существенным" цепям, т.е. таким цепям, соединяющим "вход" и "выход", которые ни через какую вершину не проходят дважды.

С другой стороны, для каждой формулы алгебры высказываний, используя равносильную ей ДНФ (или КНФ) можно построить указанным образом контактную схему, функция проводимости которой равносильна данной формуле. Говорят тогда, что данная контактная схема реализует эту формулу.

Схема называется минимальной, если она содержит минимальное число контактов среди всех схем, имеющих ту же функцию проводимости. В частности, минимальной ДНФ соответствует минимальная контактная схема среди всех схем, являющихся параллельным соединением последовательных цепочек.