Contact scheme

contact network, contact circuit, switching circuit

A representation of a class of special control systems, one of the mathematical models of actual structures built from relay contacts. A contact network is a modelling class of control systems, and the same problems are considered for it as for other classes of control systems; it is particularly useful in the study of the "structural" properties of control systems.

A contact network <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c0254601.png" /> is obtained by attaching to each edge of some graph with selected vertices one of the letters of a finite alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c0254602.png" />. The selected vertices are called the terminals or nodes of the network. An edge with a letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c0254603.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c0254604.png" />) attached to it is called a make (respectively, break) contact. A sequence of contacts between two terminals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c0254605.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c0254606.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c0254607.png" /> corresponding to a simple chain (or path) (see Graph) in the graph of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c0254608.png" /> is called a chain between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c0254609.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546010.png" />; the conjunction of the corresponding letters is called the conductivity of the given chain. The conductivity between two terminals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546012.png" /> of the scheme is a Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546013.png" />, equal to the disjunction of the conductivities of all chains between these terminals (when the set of chains between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546015.png" /> is empty, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546016.png" />; when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546017.png" /> coincides with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546018.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546019.png" />). Associated with each contact network is a conductivity matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546020.png" />, the elements of which are the conductivities between pairs of terminals. Here, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546021.png" />. Conversely, given a matrix of Boolean functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546022.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546024.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546025.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546026.png" />, there exists a contact network with given terminals for which the conductivities are the given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546027.png" />. In particular, there exists for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546028.png" /> a two-terminal network the conductivity between the terminals of which is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546029.png" />. In this case one says that the network realizes the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546030.png" />. For example, the network of Fig. arealizes the linear function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546031.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546032.png" />).

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/c025460a.gif" />

Figure: c025460a

Every Boolean function is realized by some contact network. Sometimes the set of all terminals in a contact network is divided into two subsets, the inputs and outputs. A contact network with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546033.png" /> inputs and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546034.png" /> outputs is called a contact <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546036.png" />-terminal network. A contact network the conductivity between any pairs of outputs (or inputs) of which is zero, is called separating with respect to its outputs (or inputs). An example of a separating (with respect to outputs) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546037.png" />-terminal network is given by a contact tree (Fig. b).

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/c025460b.gif" />

Figure: c025460b

A contact network is called planar if its graph with a source edge (that is, the edge joining the terminals to which no letter of the alphabet is attached) added is planar (see Graph, planar). A planar contact network <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546038.png" /> is said to be dual to a planar contact network <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546039.png" /> if the graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546040.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546041.png" /> (with source edge) is dual to the corresponding graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546042.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546043.png" />, where the source edge of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546044.png" /> corresponds to that of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546045.png" />, while the remaining corresponding edges are ascribed the same letters (Fig. c).

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/c025460c.gif" />

Figure: c025460c

The networks <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546046.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546047.png" /> have the same number of contacts and realize dual functions (the duality principle). If the contacts of a network <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546048.png" /> are replaced by their opposites, one obtains a network for the negation of the function realized by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546049.png" />. In general, it is not possible to pass from non-planar contact networks to networks with the same number of contacts realizing dual functions. A <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546051.png" />-network (parallel-series network) can be defined inductively: A contact network consisting of a single contact joining terminals is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546052.png" />-network; a contact network constructed from two <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546053.png" />-networks joined in parallel or in series is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546054.png" />-network. There exists contact networks that are not <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546055.png" />-networks, for example the network of Fig. d.

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/c025460d.gif" />

Figure: c025460d

The dual of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546056.png" />-network is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546057.png" />-network. There is a correspondence between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546058.png" />-networks and formulas in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546059.png" />. Under this connection every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546060.png" />-network realizes the same function as the formula corresponding to it and contains as many contacts as there are letters in the formula. For example, corresponding to the network of Fig. e is the formula

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546061.png" />

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/c025460e.gif" />

Figure: c025460e

The complexity of a contact network is the number of its contacts. The minimum number of contacts that suffice for the realization of an arbitrary Boolean function depending on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546062.png" /> variables by a contact network is asymptotically equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546063.png" />; the minimum number of contacts sufficient for the realization by a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546064.png" />-network is asymptotically equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546065.png" /> (see Synthesis problems).

Two contact networks are said to be equivalent (under a given one-to-one correspondence between their terminals) if the conductivities between any pair of corresponding terminals of these networks are the same. On replacing some subnetwork <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546066.png" /> of a contact network <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546067.png" /> by an equivalent one, one obtains a network equivalent to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546068.png" />. (In this replacement it is necessary to consider as terminals of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546069.png" /> all terminals of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546070.png" /> occurring in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546071.png" /> and all the vertices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546072.png" /> that are incident to contacts of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546073.png" /> that are not in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546074.png" />.) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546075.png" /> are equivalent networks, then the rule <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546076.png" /> of equivalent transformation of contact networks enables one to replace, in any network, a subnetwork obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546077.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546078.png" />) by a renaming of the letters, by the contact network obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546079.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546080.png" />) by the same renaming.

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/c025460f.gif" />

Figure: c025460f

There exists for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546081.png" /> a finite complete system of rules (Fig. f) enabling one to transfer between any two equivalent contact networks with number of variables not exceeding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546082.png" />. There does not, however, exist for the class of all contact networks (without restriction on the number of variables) a finite complete system of rules (if on applying the rules only renaming of letters is permitted).

References

[1]	V.I. Shestakov, "Algebra of two-terminal networks built from two-terminal elements only (algebra of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546083.png" />-networks)" Avtomatika i Telemekhanika , 6 : 2 (1941) pp. 15–24 (In Russian)
[2]	C. Shannon, "A symbolic analysis of relay and switching circuits" AIEE Transact. , 57 (1938) pp. 713–723
[3]	A. Nakasima, M. Hanzawa, "Theory of equivalent transformation of simple partial parts in relay circuits" Nippon Electr. Comm. Eng. : 9 (1938) pp. 32–39
[4]	S.V. Yablonskii, "Functional constructions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025460/c02546084.png" />-valued logic" Trudy Math. Inst. Steklov. , 51 (1958) pp. 5–142 (In Russian)
[5]	A.V. Kuznetsov, "On a property of functions realizable by non-planar non-repetitive networks" Trudy Mat. Inst. Steklov. , 51 (1958) pp. 174–185 (In Russian)
[6]	I.A. Chegis, S.V. Yablonskii, "Logical methods for testing the operation of electrical circuits" Trudy Mat. Inst. Steklov. , 51 (1958) pp. 270–360 (In Russian)
[7a]	O.E. Lupanov, "On the synthesis of some class of control problems" Probl. Kibernet. , 10 (1963) pp. 63–97 (In Russian)
[7b]	O.B. Lupanov, "Complexity of formula realization of functions of logical algebra" Probl. Cybernetics , 3 (1962) pp. 782–811 Probl. Kibernet. , 3 (1960) pp. 61–80
[7c]	O.B. Lupanov, "Ueber den Schaltaufwand bei den Realizierung logischer Funktionen" Probleme der Kibernetik , 3 (1963) pp. 68–90 Probl. Kibernet. , 3 (1960) pp. 61–80
[8a]	V.L. Murskii, "On the equivalent transformations of switching circuits" Probl. Cybernetics , 5 (1964) pp. 77–98 Probl. Kibernet. , 5 (1961) pp. 61–76
[8b]	W.L. Murski, "Ueber äquivalente Transformationen von Kontakt-Schaltungen" Probleme der Kibernetik , 5 (1964) pp. 44–64 Probl. Kibernet. , 5 (1961) pp. 61–76

References

[a1]	S. Eilenberg, "Automata, languages and machines" , A , Acad. Press (1973)