КОНТАКТНАЯ СХЕМА

- специальная управляющая система, одна нз математических моделей реальных устройств, построенных из контактов реле. К. с.- модельный класс управляющих систем, и для него рассматриваются все те же задачи, что и для прочих классов управляющих систем; он особенно удобен при изучении "геометрических" свойств управляющих систем.

К. с. получается в результате приписывания каждому ребру нек-рого графа с выделенными вершинами одной из букв конечного алфавита Выделенные вершины наз. полюсами схемы. Ребро с приписанной ему буквой наз. замыкающим (размыкающим) контактом. Последовательность контактов между полюсами аи b схемы S, соответствующая простой цепи (см. Граф )в графе схемы S, наз. цепью между полюсами аи bсхемы S;конъюнкция соответствующих букв наз. проводимостью данной цепи. Проводимость между полюсами a и b схемы есть функция алгебры логики f_ab(x₁, ..., х _п), равная дизъюнкции проводимостей всех цепей между этими полюсами (в случае, если множество цепей между аи bпусто, f _аb=0; при а, совпадающем с b, f _аа=1). Всякой К. с. сопоставляется матрица проводимостей ||f _аb||, элементами к-рой являются проводимости между парами полюсов. При этом Обратно, если задана матрица из функций алгебры логики ||f_ab|| такая, что f _аa=1, f_ab=f_ba и для любых а, b, с, то существует К. с. с данными полюсами, для которых проводимости совпадают с заданными f_ab. В частности, для любой f существует двухполюсная схема, проводимость между полюсами к-рой равна f. В этом случае говорят, что схема реализует функцию f. Напр., схема рис. 1 реализует линейную функцию f = x₁+... + х _n+1 (mod 2). Всякая функция алгебры логики реализуема некоторой К. с.

Иногда в К. с. множество всех полюсов разбито на два подмножества - входов и выходов. К. с. с r входами и s выходами называется контактным (r, s)-полюсником. К. с, проводимости между любыми парами выходов (входов) которой равны нулю, называется разделительной относительно выходов (входов). Примером разделительного (относительно выходов) (1, 2ⁿ )-полюсника может служить контактное дерево (рис. 2). К. с. наз. плоской, если соответствующий ей граф, дополненный источниковым ребром (т. е. ребром, соединяющим полюсы, к-рому не приписана никакая буква рассматриваемого алфавита), является плоским (см. Граф плоский). Плоская К. с. S* наз. двойственной к плоской К. с. S, если граф Г* схемы S* (с источниковым ребром) является двойственным к аналогичному графу Г схемы S, причем источниковому ребру графа Г соответствует таковое в графе *, а остальные соответствующие друг другу ребра несут одинаковые буквы (рис. 3). Схемы Sи S* имеют одинаковое число контактов и реализуют двойственные функции (принцип двойственности).

При замене контактов в схеме S* на противоположные получается схема для отрицания функции, реализуемой схемой S. Для неплоских К. с, вообще говоря, не существует возможности перехода к схемам с тем же числом контактов, реализующим двойственные функции. П-схема (параллельно-последовательная схема) может быть определена индуктивно: К. с, состоящая из единственного контакта, соединяющего полюсы, есть П-схема; К. с, построенная из двух П-схем, соединенных параллельно или последовательно, есть П-схема. Существуют К. с, не являющиеся П-схемами, напр, схема рис. 4. К. с, двойственная к П-схеме, есть П-схема.

Существует соответствие между П-схемамии формулами в базисе При этом всякая П-схема реализует ту же самую функцию, что и соответствующая ей формула, и содержит столько же контактов, сколько букв содержит формула. Напр., схеме рис. 5 соответствует ф-ла

Под сложностью К. с. понимается число всех ее контактов. Минимальное число контактов, достаточное для реализации контактной схемой произвольной функции алгебры логики, зависящей от ппеременных, асимптотически равно 2ⁿ/n; минимальное число контактов, достаточное для реализации П-схемой, асимптотически равно 2ⁿ/log n(см. Синтеза задачи).

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

Лит.:[1] Шeстаков В. И., "Автоматика и телемеханика", 1941, т. 6, №2, с. 15-24; [2] Шеннон К., Работы по теории информации и кибернетике, пер. с англ., М., 1963, с. 9-45; [3] Nakasima A., "Nippon Electr. Comm. Eng.", 1938, №№ 9, 10, 13, 14; [4] Яблонский С. В., "Тр. Матем. ин-та АН СССР", 1958, т. 51, с. 5-142; [5] Кузнецов А. В., там же, с. 174-85; [6] Чегис И. А., Яблонский С. В., там же, с. 270-360; [7] Лупанов О. Б., "Проблемы кибернетики", 1963, в. 10, с. 63-97; [8] Мурский В. Л., там же, 1961, в. 5, с. 61-76.

Я. А. Карпова.