Контактная Схема

Специальная управляющая система, одна нз математических моделей реальных устройств, построенных из контактов реле. К. с.- модельный класс управляющих систем, и для него рассматриваются все те же задачи, что и для прочих классов управляющих систем; он особенно удобен при изучении "геометрических" свойств управляющих систем. К. с. получается в результате приписывания каждому ребру нек-рого графа с выделенными вершинами одной из букв конечного алфавита Выделенные вершины наз. полюсами схемы. Ребро с приписанной ему буквой наз. замыкающим (размыкающим) контактом. Последовательность контактов между полюсами аи b схемы S, соответствующая простой цепи (см. Граф )в графе схемы S, наз. цепью между полюсами аи bсхемы S;конъюнкция соответствующих букв наз. проводимостью данной цепи. Проводимость между полюсами a и b схемы есть функция алгебры логики fab(x1, ..., х п), равная дизъюнкции проводимостей всех цепей между этими полюсами (в случае, если множество цепей между аи bпусто, f аb=0; при а, совпадающем с b, f аа=1). Всякой К. с. сопоставляется матрица проводимостей ||f аb||, элементами к-рой являются проводимости между парами полюсов. При этом Обратно, если задана матрица из функций алгебры логики ||fab|| такая, что f аa=1, fab=fba и для любых а, b, с, то существует К. с. с данными полюсами, для которых проводимости совпадают с заданными fab. В частности, для любой f существует двухполюсная схема, проводимость между полюсами к-рой равна f. В этом случае говорят, что схема реализует функцию f. Напр., схема рис. 1 реализует линейную функцию f = x1+... + х n+1 (mod 2). Всякая функция алгебры логики реализуема некоторой К. с. Иногда в К. с. множество всех полюсов разбито на два подмножества — входов и выходов. К. с. с r входами и s выходами называется контактным (r, s)-полюсником. К. с, проводимости между любыми парами выходов (входов) которой равны нулю, называется разделительной относительно выходов (входов). Примером разделительного (относительно выходов) (1, 2n )-полюсника может служить контактное дерево (рис. 2). К. с. наз. плоской, если соответствующий ей граф, дополненный источниковым ребром (т. е. ребром, соединяющим полюсы, к-рому не приписана никакая буква рассматриваемого алфавита), является плоским (см. Граф плоский). Плоская К. с. S* наз. двойственной к плоской К. с. S, если граф Г* схемы S* (с источниковым ребром) является двойственным к аналогичному графу Г схемы S, причем источниковому ребру графа Г соответствует таковое в графе *, а остальные соответствующие друг другу ребра несут одинаковые буквы (рис. 3). Схемы Sи S* имеют одинаковое число контактов и реализуют двойственные функции (принцип двойственности). При замене контактов в схеме S* на противоположные получается схема для отрицания функции, реализуемой схемой S. Для неплоских К. с, вообще говоря, не существует возможности перехода к схемам с тем же числом контактов, реализующим двойственные функции. П-схема (параллельно-последовательная схема) может быть определена индуктивно: К. с, состоящая из единственного контакта, соединяющего полюсы, есть П-схема; К. с, построенная из двух П-схем, соединенных параллельно или последовательно, есть П-схема. Существуют К. с, не являющиеся П-схемами, напр, схема рис. 4. К. с, двойственная к П-схеме, есть П-схема. Существует соответствие между П-схемамии формулами в базисе При этом всякая П-схема реализует ту же самую функцию, что и соответствующая ей формула, и содержит столько же контактов, сколько букв содержит формула. Напр., схеме рис. 5 соответствует ф-ла Под сложностью К. с. понимается число всех ее контактов. Минимальное число контактов, достаточное для реализации контактной схемой произвольной функции алгебры логики, зависящей от ппеременных, асимптотически равно 2n/n; минимальное число контактов, достаточное для реализации П-схемой, асимптотически равно 2n/log n(см. Синтеза задачи). Две К. с. наз. эквивалентными (при заданном взаимно однозначном соответствии между их полюсами), если проводимости между любой парой соответствующих полюсов этих схем совпадают. При замене в любой К. с. Sлюбой ее подсхемы S' на эквивалентную получается схема, эквивалентная S. (При замене необходимо рассматривать как полюсы S' все попавшие в S' полюсы S и все вершины S', инцидентные не попавшим в S' контактам S. )Если S1, S2 — эквивалентные К. с, то правило эквивалентного преобразования К. с. разрешает в любой схеме заменить подсхему, полученную из S1 (или S2) переименованием букв, на К. с, полученную из S2 (S1) тем же переименованием. Для каждого псуществует конечная полная система правил (рис. 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. Я. А. Карпова.