Augmented polynomial matrices and algebraization of switching circuits

Authors

  • Yury G. Tarazevich Belarusian State University, Niezaliežnasci Avenue, 4, 220030, Minsk, Belarus

Keywords:

polynomial with idempotent variables, augmented polynomial matrix, full reverse metamorphosis, algebraization of switching circuits, contact hypergraph
Supporting Agencies
The author expresses his gratitude to full professor F. Y. Lomovtsev for his assistance in the preparation of the article

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.

Author Biography

  • Yury G. Tarazevich, Belarusian State University, Niezaliežnasci Avenue, 4, 220030, Minsk, Belarus

    PhD (physics and mathematics); senior lecturer at the department of mathematical cybernetics, faculty of mechanics and mathematics

References

  1. Yablonsky S. V. [Elements of mathematical cybernetics]. Moscow : Vysshaya shkola, 2007 (in Russ.).
  2. Lupanov O. B. [Asymptotic bounds for the complexity of control systems]. Moscow : Moscow State University, Publ. house, 1984 (in Russ.).
  3. Nigmatullin R. G. [Complexity of Boolean functions]. Moscow : Nauka, 1991 (in Russ.).
  4. Basaker R., Saaty T. [Finite graphs and networks]. Moscow : Nauka, 1974 (in Russ.).
  5. Emelichev V. A., Melnikov O. I., Sarvanov V. I., et al. [Lectures in graph theory]. Moscow : Nauka, 1990 (in Russ.).
  6. Tarazevich Y. G. [Algebraization and generalization of switching circuits]. Diskretnaya matematika i ee prilozheniya [Discrete mathematics and its applications] : materialy XII Mezhdunar. semin. im. akad. O. B. Lupanova (Moscow, 20 –25 June, 2016). Moscow : Faculty of Mechanics and Mathematics, Moscow State University, Publ. house, 2016. P. 170 –172 (in Russ.).
  7. Jablonski S. V. [Introduction to discrete mathematics]. Moscow : Vysshaya shkola, 2003 (in Russ.).
  8. Luntz A. G. [Algebraic methods of analysis and synthesis of switching circuits]. Izv. Akad. nauk SSSR. Ser. mat. 1952. Vol. 16, issue 5. P. 405– 426 (in Russ.).
  9. Vinberg E. B. [Algebra course]. Moscow : Faktorial press, 2001 (in Russ.).
  10. Zariski O., Samuel P. [Commutative algebra] : in 2 vol. Moscow : Inostrannaya literatura, 1963. Vol. 1 (in Russ.).
  11. Maltsev A. I. [Fundamentals of linear algebra]. Moscow : Nauka, 1970 (in Russ.).

Downloads

Published

2018-02-14

Issue

No. 3 (2017): Journal of the Belarusian State University. Mathematics and Informatics

Section

Discrete Mathematics and Mathematical Cybernetics

License

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)

How to Cite

[1]
Tarazevich, Y.G. 2018. Augmented polynomial matrices and algebraization of switching circuits. Journal of the Belarusian State University. Mathematics and Informatics. 3 (Feb. 2018), 85–93.