Namespaces
Variants
Actions

Difference between revisions of "Relay-contact scheme"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
 +
<!--
 +
r0811601.png
 +
$#A+1 = 77 n = 0
 +
$#C+1 = 77 : ~/encyclopedia/old_files/data/R081/R.0801160 Relay\AAhcontact scheme,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''relay-contact network, relay-contact circuit''
 
''relay-contact network, relay-contact circuit''
  
Line 5: Line 17:
 
Mathematically, a relay-contact circuit is a finite [[Graph|graph]] in which all edges and some distinguished vertices are ascribed symbols of alphabets
 
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>
+
$$
 +
= \{ x _ {1} , \overline{x}\; _ {1} \dots x _ {n} , \overline{x}\; _ {n} \} ,\ \
 +
= \{ Y _ {1} \dots Y _ {m} \} ,
 +
$$
  
<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>
+
$$
 +
= \{ y _ {1} , \overline{y}\; _ {1} \dots y _ {m} , \overline{y}\; _ {m} \} ,\  a  = \{ a _ {+} , a _ {-} , a _ {1} \dots a _ {s} \}
 +
$$
  
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.
+
in the following way. Each distinguished vertex of the graph (these vertices are called poles) is assigned a symbol from the alphabet $  a $
 +
such that to different poles are assigned different symbols. The set of edges of the graph is divided into three non-intersecting subsets $  R, K _ {1} , K _ {2} $.  
 +
The edges from each of these subsets are ascribed symbols from $  Y $,  
 +
$  x $
 +
and $  y $
 +
in the following way: Each edge from $  R $
 +
is assigned a symbol from $  Y $,  
 +
all edges from $  R $
 +
being assigned different symbols and all symbols from $  Y $
 +
being assigned to edges from $  R $.  
 +
With each edge of the set $  K _ {1} $(
 +
$  K _ {2} $,  
 +
respectively) is assigned a symbol from $  x $(
 +
$  y $,  
 +
respectively) such that each symbol may be assigned to several edges and some symbols may not be assigned to any edge. If the set $  Y $
 +
is empty, then the set $  K _ {2} $
 +
is also empty. In this case (if only $  K _ {1} $
 +
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.
+
The pole $  a _ {+} $
 +
is called the input pole and the poles $  a _ {1} \dots a _ {s} $
 +
are called output poles. The pole $  a _ {-} $
 +
may also sometimes be an output pole. The edges to which are assigned symbols from $  x $
 +
are known as contacts of basic relays (or basic contacts); the set of all edges marked by the symbols $  Y _ {i} , y _ {i} , \overline{y}\; _ {i} $
 +
is called the $  i $-
 +
th intermediate relay, $  i = 1 \dots m $;  
 +
edges marked by symbols from $  y $
 +
are called contacts of intermediate relays; edges marked by symbols from $  Y $
 +
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" />.
+
A relay-contact circuit functions at discrete moments of time $  1 \dots t \dots $
 +
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 $  x _ {j} , \overline{x}\; _ {j} $,  
 +
$  j = 1 \dots n $,  
 +
at any moment $  t $
 +
is equal to the value of the corresponding variable ( $  x _ {j} $
 +
or $  \overline{x}\; _ {j} $).  
 +
The conductivity of a contact $  y _ {i} $,  
 +
$  i = 1 \dots m $,  
 +
of an intermediate relay at the moment 1 is equal to zero, the conductivity of the contact $  \overline{y}\; _ {i} $
 +
at the moment 1 being equal to one; the conductivity of a winding is always equal to one. Every winding at a moment $  t $
 +
can be in various states. The state of the winding at a moment $  t $(
 +
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 $  Y _ {i} $
 +
is in state 1 at the moment $  t $
 +
if and only if either: a) there is a chain $  \sigma $
 +
between the poles $  a _ {+} $
 +
and $  a _ {-} $
 +
that passes through $  Y _ {i} $
 +
and that has conductivity 1 at the moment $  t $;  
 +
or b) condition a) is fulfilled but there is no chain consisting only of contacts having conductivity 1 at the moment $  t $,  
 +
and joining two vertices of the chain $  \sigma $
 +
situated on different sides of $  Y _ {i} $.
  
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 conductivity of an intermediate contact $  y _ {i} $
 +
$  ( \overline{y}\; _ {i} ) $
 +
at a moment $  t $
 +
depends on the state of the winding $  Y _ {i} $
 +
at the moment $  t- 1 $;  
 +
more precisely, the conductivity of $  y _ {i} $
 +
coincides with it and the conductivity of $  \overline{y}\; _ {i} $
 +
is opposite to it. The conductivity of a chain of a relay-contact circuit between two poles at a moment $  t $
 +
is equal to the conjunction of the conductivities at the moment $  t $
 +
formed by its contacts and windings. Thus, the state of the windings at a moment $  t $
 +
is, generally speaking, dependent on the sequence of sets of values of the variables $  x _ {1} \dots x _ {n} $
 +
at the preceding moments of time. If at successive moments of time the variables $  x _ {1} \dots x _ {n} $
 +
are supplied with sequences of choices of values between a pair of poles $  a _ {+} $
 +
and $  a _ {k} $,  
 +
$  k = 1 \dots s $,  
 +
and in a particular case also between $  a _ {+} $
 +
and $  a _ {-} $,  
 +
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 $  x _ {1} \dots x _ {n} $
 +
with the same set of values $  ( \sigma _ {1} \dots \sigma _ {n} ) $,  
 +
starting from a specific moment $  t $,  
 +
the windings of the intermediate relays do not change their state (and this for each set of values of the variables $  x _ {1} \dots x _ {n} $),  
 +
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 $  t $
 +
starts immediately for all choices of values of the variables $  x _ {1} \dots x _ {n} $,  
 +
then the relay-contact circuit is called a one-cycle; if stabilization starts at a moment $  t + \tau $,  
 +
then the relay-contact scheme is called a $  \tau $-
 +
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.
+
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 $  n $
 +
variables possible takes the form $  \rho 2  ^ {n} /n $,  
 +
where $  \rho $
 +
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====
 
====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>
 
<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>

Revision as of 08:10, 6 June 2020


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) 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). Relay-contact circuits were first described in 1938–1944 (see [1][3]).

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

$$ x = \{ x _ {1} , \overline{x}\; _ {1} \dots x _ {n} , \overline{x}\; _ {n} \} ,\ \ Y = \{ Y _ {1} \dots Y _ {m} \} , $$

$$ y = \{ y _ {1} , \overline{y}\; _ {1} \dots y _ {m} , \overline{y}\; _ {m} \} ,\ a = \{ a _ {+} , a _ {-} , a _ {1} \dots a _ {s} \} $$

in the following way. Each distinguished vertex of the graph (these vertices are called poles) is assigned a symbol from the alphabet $ a $ such that to different poles are assigned different symbols. The set of edges of the graph is divided into three non-intersecting subsets $ R, K _ {1} , K _ {2} $. The edges from each of these subsets are ascribed symbols from $ Y $, $ x $ and $ y $ in the following way: Each edge from $ R $ is assigned a symbol from $ Y $, all edges from $ R $ being assigned different symbols and all symbols from $ Y $ being assigned to edges from $ R $. With each edge of the set $ K _ {1} $( $ K _ {2} $, respectively) is assigned a symbol from $ x $( $ y $, respectively) such that each symbol may be assigned to several edges and some symbols may not be assigned to any edge. If the set $ Y $ is empty, then the set $ K _ {2} $ is also empty. In this case (if only $ K _ {1} $ is non-empty) the relay-contact circuit is a 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 $ a _ {+} $ is called the input pole and the poles $ a _ {1} \dots a _ {s} $ are called output poles. The pole $ a _ {-} $ may also sometimes be an output pole. The edges to which are assigned symbols from $ x $ are known as contacts of basic relays (or basic contacts); the set of all edges marked by the symbols $ Y _ {i} , y _ {i} , \overline{y}\; _ {i} $ is called the $ i $- th intermediate relay, $ i = 1 \dots m $; edges marked by symbols from $ y $ are called contacts of intermediate relays; edges marked by symbols from $ Y $ 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 $ 1 \dots t \dots $ 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 $ x _ {j} , \overline{x}\; _ {j} $, $ j = 1 \dots n $, at any moment $ t $ is equal to the value of the corresponding variable ( $ x _ {j} $ or $ \overline{x}\; _ {j} $). The conductivity of a contact $ y _ {i} $, $ i = 1 \dots m $, of an intermediate relay at the moment 1 is equal to zero, the conductivity of the contact $ \overline{y}\; _ {i} $ at the moment 1 being equal to one; the conductivity of a winding is always equal to one. Every winding at a moment $ t $ can be in various states. The state of the winding at a moment $ t $( 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 $ Y _ {i} $ is in state 1 at the moment $ t $ if and only if either: a) there is a chain $ \sigma $ between the poles $ a _ {+} $ and $ a _ {-} $ that passes through $ Y _ {i} $ and that has conductivity 1 at the moment $ t $; or b) condition a) is fulfilled but there is no chain consisting only of contacts having conductivity 1 at the moment $ t $, and joining two vertices of the chain $ \sigma $ situated on different sides of $ Y _ {i} $.

The conductivity of an intermediate contact $ y _ {i} $ $ ( \overline{y}\; _ {i} ) $ at a moment $ t $ depends on the state of the winding $ Y _ {i} $ at the moment $ t- 1 $; more precisely, the conductivity of $ y _ {i} $ coincides with it and the conductivity of $ \overline{y}\; _ {i} $ is opposite to it. The conductivity of a chain of a relay-contact circuit between two poles at a moment $ t $ is equal to the conjunction of the conductivities at the moment $ t $ formed by its contacts and windings. Thus, the state of the windings at a moment $ t $ is, generally speaking, dependent on the sequence of sets of values of the variables $ x _ {1} \dots x _ {n} $ at the preceding moments of time. If at successive moments of time the variables $ x _ {1} \dots x _ {n} $ are supplied with sequences of choices of values between a pair of poles $ a _ {+} $ and $ a _ {k} $, $ k = 1 \dots s $, and in a particular case also between $ a _ {+} $ and $ a _ {-} $, 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 $ x _ {1} \dots x _ {n} $ with the same set of values $ ( \sigma _ {1} \dots \sigma _ {n} ) $, starting from a specific moment $ t $, the windings of the intermediate relays do not change their state (and this for each set of values of the variables $ x _ {1} \dots x _ {n} $), 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 $ t $ starts immediately for all choices of values of the variables $ x _ {1} \dots x _ {n} $, then the relay-contact circuit is called a one-cycle; if stabilization starts at a moment $ t + \tau $, then the relay-contact scheme is called a $ \tau $- 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 $ n $ variables possible takes the form $ \rho 2 ^ {n} /n $, where $ \rho $ 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

[1] C. Shannon, "A symbolic analysis of relay and switching circuits" AIEE Trans. , 57 (1938) pp. 713–723
[2] M.A. Gavrilov, "Relaisschalttechnik" , Deutsch. Verlag Wissenschaft. (1953) (Translated from Russian)
[3] 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)
[4] 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)
How to Cite This Entry:
Relay-contact scheme. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Relay-contact_scheme&oldid=12436
This article was adapted from an original article by N.A. Karpova (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article