Реле́йно-конта́ктная схе́ма, математическая модель электротехнических устройств, состоящих из контактов и промежуточных реле, функционирующих в дискретные моменты времени. Релейно-контактная схема – один из первых классов управляющих систем, рассмотренных с математической точки зрения, а также один из первых вариантов понятия конечного автомата. Первые описания релейно-контактной схемы появились в 1938–1944 гг. (Шестаков. 1944; Гаврилов. 1950; Шеннон. 1963).

Математически релейно-контактная схема представляет собой конечный граф, всем рёбрам и некоторым выделенным вершинам которого приписаны символы из алфавитов$$\begin{gathered} x=\left\{x_1, \bar{x}_1, \ldots, x_n, \bar{x}_n\right\},\quad Y=\left\{Y_1, \ldots, Y_m\right\}, \\ y=\left\{y_1, \bar{y}_1, \ldots, y_m, \bar{y}_m\right\},\quad a=\left\{a_{+}, a_{-}, a_1, \ldots, a_s\right\} \end{gathered}$$следующим образом. Каждой выделенной вершине графа (эти вершины называются полюсами) приписан символ из алфавита $a$ так, что различным полюсам приписаны различные символы. Множество рёбер графа разбито на три непересекающихся подмножества: $R$, $K_1$, $K_2$. Рёбрам каждого из этих подмножеств приписаны символы из $Y$, $x$, $y$ следующим образом. Каждому ребру из $R$ приписан символ из $Y$, всем рёбрам из $R$ приписаны различные символы, и все символы из $Y$ приписаны рёбрам из $R$. Каждому ребру множества $K_1$ (соответственно $K_2$) приписаны символы из $x$ (соответственно $y$) так, что каждый символ может быть приписан нескольким рёбрам, некоторые символы могут быть не приписаны никаким рёбрам. Если множество $Y$ пусто, то пусто и множество $K_2$. В таком случае (если непусто только $K_1$) релейно-контактная схема является контактной схемой. Две релейно-контактные схемы называются изоморфными, если изоморфны их графы и соответствующим рёбрам и полюсам приписаны одинаковые символы.

Полюс $a_{+}$ называется входным, полюсы $a_1, \ldots, a_s$ называются выходными, полюс $a_{-}$ может иногда также быть выходным. Рёбра, которым приписаны символы из $x$, называются контактами основных реле (или основными контактами); множество всех рёбер, помеченных символами $Y_i$, $y_i$, $\bar{y}_i$, называется $i$-м промежуточным реле, $i=1, \ldots, m$; рёбра, помеченные символами из $y$, называются контактами промежуточных реле; рёбра, помеченные символами из $Y$, называются обмотками. Последовательность контактов и обмоток между некоторыми вершинами релейно-контактной схемы, соответствующая простой цепи графа, называется цепью.

Функционирование релейно-контактной схемы происходит в дискретные моменты времени $1,2, \ldots, t, \ldots$ и рассматривается в терминах проводимостей, которые в каждый момент представляют собой (в рассматриваемой модели) функции алгебры логики. Проводимость контактов $x_j$,$\overline{x_j}$, $j=1, \ldots, n$, в любой момент $t$ равна значению соответствующей переменной ($x_j$ или $\bar{x}_j$). Проводимость контакта $y_i$, $i=1, \ldots, m$, промежуточного реле в момент $1$ равна нулю, проводимость контакта $y_i$ в момент $1$ равна единице; проводимость обмотки всегда равна единице. Всякая обмотка в момент $t$ может находиться в различных состояниях. Состояние обмотки в момент $t$ (в рассматриваемой двузначной модели – $1$ и $0$ – «возбуждена» и «не возбуждена») может определяться по-разному. Например, обмотка $Y_i$ находится в состоянии $1$ в момент времени $t$ тогда и только тогда, когда либо а) существует цепь $\sigma$ между полюсами $a_{+}$ и $a_{-}$, проходящая через $Y_i$ и имеющая в момент $t$ проводимость $1$; либо б) выполнено условие а) и не существует цепи, состоящей только из контактов, имеющей в момент $t$ проводимость $1$ и соединяющей некоторые вершины цепи $\sigma$, расположенные по разные стороны от $Y_i$.

Проводимость промежуточного контакта $y_i\left(\bar{y_i}\right)$ в момент $t$ зависит от состояния обмотки $Y_i$ в момент $t-1$, а именно: проводимость $y_i$ с ним совпадает, проводимость $\bar{y}_i$ – противоположна. Проводимость цепи релейно-контактной схемы между двумя вершинами в момент $t$ равна конъюнкции проводимостей в момент $t$ образующих её контактов и обмоток. Состояния обмоток, таким образом, в момент $t$, вообще говоря, зависят от последовательности наборов значений переменных $x_1, \ldots, x_n$ в предыдущие моменты времени. При подаче в последовательные моменты времени на переменные $x_1, \ldots, x_n$ последовательности наборов значений между парой полюсов $a_{+}$ и $a_k$, $k=1, \ldots, s$, а в частном случае и между $a_{+}$ и $a_{-}$, реализуется ограниченно-детерминированная функция. Изоморфные релейно-контактные схемы реализуют одну и ту же ограниченно-детерминированную функцию. Если релейно-контактная схема такова, что при подаче на переменные $x_1, \ldots, x_n$ одного и того же набора значений $\left(\sigma_1, \ldots, \sigma_n\right)$ начиная с некоторого момента $t$ обмотки промежуточных реле не меняют своих состояний (и так для каждого набора значений переменных $x_1, \ldots, x_n$), то говорят об «установившихся» состояниях обмоток, и посредством релейно-контактной схемы реализуются функции алгебры логики. Если стабилизация обмоток с момента $t$ наступает сразу для всех наборов значений переменных $x_1, \ldots, x_n$, то релейно-контактная схема называется однотактной; если стабилизация наступает в момент $t+\tau$, то релейно-контактная схема называется $\tau$-тактной.

Сложность релейно-контактной схемы определяется как сумма весов (или индексов сложности) всех основных контактов, промежуточных контактов и обмоток релейно-контактной схемы. Асимптотическое выражение для сложности самой простой релейно-контактной схемы, реализующей самую сложнореализуемую функцию алгебры логики, имеет вид $\rho 2^{n / n}$, где $\rho$ – константа, зависящая от выбранного способа функционирования, топологии схем и сложности контактов и обмоток реле.