Расширенные полиномиальные матрицы и алгебраизация контактных схем

Abstract

Над кольцами полиномов с идемпотентными переменными (над произвольными полями) найдены классы расширенных матриц (с одним выделенным столбцом), реализующих булевы функции. В последних классах расширенных матриц (над любыми полями) определена система эквивалентных преобразований (сохраняющих реализуемые матрицами булевы функции), обобщающая известную систему элементарных преобразований (строк и столбцов) обычных многочленных матриц. Доказана полнота этой системы для простейшего (двузначного) случая – в классе расширенных матриц над кольцом полиномов Жегалкина. В частности, дан метод приведения произвольной расширенной матрицы над кольцом полиномов Жегалкина с помощью этой системы преобразований к однозначно определяемому одноэлементному виду. Для того же (двузначного) случая показано, что класс двоичных матриц инциденций контактных схем является, по существу, подклассом класса расширенных матриц над кольцом полиномов Жегалкина. Таким образом, получено простейшее «вполне алгебраическое» расширение класса контактных схем – одного из базовых модельных классов математической теории управляющих систем. = Over rings of polynomials with idempotent variables (over arbitrary fields) there are defined classes of augmented matrices (with one distinguished column) that realize Boolean functions. In the latter classes of augmented matrices (over any fields) there is defined a system of equivalent transformations (preserving realized Boolean functions) that generalizes the known system of elementary transformations (of rows and columns) of usual polynomial matrices. It is proved the completeness of this system for the simplest (binary) case – in the class of augmented matrices over the ring of Zhegalkin polynomials. In particular, there is given a method for reducing of an arbitrary augmented matrix over the ring of Zhegalkin polynomials by means of this system to a uniquely determined one-element form. For the same (binary) case, it is shown that the class of binary incidence matrixes of switching circuits is, in essence, a subclass of the class of augmented matrices over the ring of Zhegalkin polynomials. This reveals the simplest «completely algebraic» extension of the class of switching circuits – one of the basic model classes of mathematical theory of control systems.