View source for Relay-contact scheme

''relay-contact network, relay-contact circuit''

A mathematical model of electrical devices consisting of contacts and intermediate relays that function at discrete moments of time. The relay-contact circuit is one of the first classes of control systems (cf. [[Control system|Control system]]) considered from the mathematical point of view, as well as one of the first versions of the concept of a finite automaton (cf. [[Automaton, finite|Automaton, finite]]). Relay-contact circuits were first described in 1938–1944 (see [[#References|[1]]]–[[#References|[3]]]).

Mathematically, a relay-contact circuit is a finite [[Graph|graph]] in which all edges and some distinguished vertices are ascribed symbols of alphabets

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r0811601.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r0811602.png" /></td> </tr></table>

in the following way. Each distinguished vertex of the graph (these vertices are called poles) is assigned a symbol from the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r0811603.png" /> such that to different poles are assigned different symbols. The set of edges of the graph is divided into three non-intersecting subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r0811604.png" />. The edges from each of these subsets are ascribed symbols from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r0811605.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r0811606.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r0811607.png" /> in the following way: Each edge from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r0811608.png" /> is assigned a symbol from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r0811609.png" />, all edges from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116010.png" /> being assigned different symbols and all symbols from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116011.png" /> being assigned to edges from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116012.png" />. With each edge of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116013.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116014.png" />, respectively) is assigned a symbol from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116015.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116016.png" />, respectively) such that each symbol may be assigned to several edges and some symbols may not be assigned to any edge. If the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116017.png" /> is empty, then the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116018.png" /> is also empty. In this case (if only <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116019.png" /> is non-empty) the relay-contact circuit is a [[Contact scheme|contact scheme]]. Two relay-contact circuits are called isomorphic if their graphs are isomorphic and if corresponding edges and poles are assigned identical symbols.

The pole <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116020.png" /> is called the input pole and the poles <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116021.png" /> are called output poles. The pole <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116022.png" /> may also sometimes be an output pole. The edges to which are assigned symbols from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116023.png" /> are known as contacts of basic relays (or basic contacts); the set of all edges marked by the symbols <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116024.png" /> is called the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116026.png" />-th intermediate relay, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116027.png" />; edges marked by symbols from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116028.png" /> are called contacts of intermediate relays; edges marked by symbols from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116029.png" /> are called windings. A sequence of contacts and windings between several vertices of a relay-contact circuit corresponding to a simple chain of the graph is called a chain.

A relay-contact circuit functions at discrete moments of time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116030.png" /> and the functioning is considered in terms of conductivities that at each moment are (in the model under consideration) Boolean functions. The conductivity of the contacts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116031.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116032.png" />, at any moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116033.png" /> is equal to the value of the corresponding variable (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116034.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116035.png" />). The conductivity of a contact <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116036.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116037.png" />, of an intermediate relay at the moment 1 is equal to zero, the conductivity of the contact <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116038.png" /> at the moment 1 being equal to one; the conductivity of a winding is always equal to one. Every winding at a moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116039.png" /> can be in various states. The state of the winding at a moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116040.png" /> (in the two-valued model in question, 1 and 0 are  "excited"  and  "non-excited" ) can be defined in various ways. For example, a winding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116041.png" /> is in state 1 at the moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116042.png" /> if and only if either: a) there is a chain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116043.png" /> between the poles <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116044.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116045.png" /> that passes through <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116046.png" /> and that has conductivity 1 at the moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116047.png" />; or b) condition a) is fulfilled but there is no chain consisting only of contacts having conductivity 1 at the moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116048.png" />, and joining two vertices of the chain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116049.png" /> situated on different sides of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116050.png" />.

The conductivity of an intermediate contact <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116051.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116052.png" /> at a moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116053.png" /> depends on the state of the winding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116054.png" /> at the moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116055.png" />; more precisely, the conductivity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116056.png" /> coincides with it and the conductivity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116057.png" /> is opposite to it. The conductivity of a chain of a relay-contact circuit between two poles at a moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116058.png" /> is equal to the conjunction of the conductivities at the moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116059.png" /> formed by its contacts and windings. Thus, the state of the windings at a moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116060.png" /> is, generally speaking, dependent on the sequence of sets of values of the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116061.png" /> at the preceding moments of time. If at successive moments of time the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116062.png" /> are supplied with sequences of choices of values between a pair of poles <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116063.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116064.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116065.png" />, and in a particular case also between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116066.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116067.png" />, a finite-state sequential function is defined. Isomorphic relay-contact circuits realize the same finite-state sequential function. If the relay-contact circuit is such that by supplying the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116068.png" /> with the same set of values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116069.png" />, starting from a specific moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116070.png" />, the windings of the intermediate relays do not change their state (and this for each set of values of the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116071.png" />), then the state of the windings is said to be  "steady" , and the relay-contact circuit realizes Boolean functions. If stabilization of the windings from a moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116072.png" /> starts immediately for all choices of values of the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116073.png" />, then the relay-contact circuit is called a one-cycle; if stabilization starts at a moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116074.png" />, then the relay-contact scheme is called a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116076.png" />-cycle.

The complexity of a relay-contact circuit is defined as the sum of the weights (or of the complexity indices) of all basic contacts, intermediate contacts and windings of the circuit. An asymptotic expression for the complexity of the simplest relay-contact circuit realizing the most complexly-realizable Boolean function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116077.png" /> variables possible takes the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116078.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r081/r081160/r08116079.png" /> is a constant depending on the chosen manner of functioning, the topology of the circuit and the complexity of the relay contacts and windings.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  C. Shannon,   "A symbolic analysis of relay and switching circuits"  ''AIEE Trans.'' , '''57'''  (1938)  pp. 713–723</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  M.A. Gavrilov,   "Relaisschalttechnik" , Deutsch. Verlag Wissenschaft.  (1953)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  V.I. Shestakov,   "On a logical calculus applicable to the theory of relay-contact circuits"  ''Uchen. Zap. Moskov. Gosudarstv. Univ. Mat.'' , '''73''' :  5  (1944)  pp. 45–48  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  O.B. Lupanov,   "Complexity of relay-contact circuits realization by functions of the algebra of logic"  ''Probl. Kibernetiki'' , '''11'''  (1964)  pp. 25–47  (In Russian)</TD></TR></table>