МАТРИЧНОЕ ИСЧИСЛЕНИЕ В АЛГЕБРЕ ЛОГИКИ

МАТРИЧНОЕ ИСЧИСЛЕНИЕ В АЛГЕБРЕ ЛОГИКИ

Научная статья

Сдвижков О.А.^1, *, Мацнев Н.П.²

¹ Российский государственный университет туризма и сервиса, Пушкино, Россия;

² Технологический университет, Королев, Россия

* Корреспондирующий автор (oasdv[at]yandex.ru)

Аннотация

Применяя операцию сложения по модулю два, в алгебре логики определяются фундаментальные понятия матричного исчисления, такие как линейно зависимые и независимые совокупности строк (столбцов) матрицы, ранг матрицы, сумма и произведение матриц, определитель матрицы, обратная матрица. Приводятся свойства определителей алгебры логики. С помощью обратных матриц алгебры логики решаются системы линейных уравнений с суммами по модулю два. Приведены примеры на вычисление в алгебре логики ранга матрицы, определителей, обратных матриц и решение систем линейных уравнений с суммами по модулю два.

Ключевые слова: бинарная матрица, сумма по модулю два, определитель, обратная матрица, ранг матрицы, система уравнений.

MATRIX CALCULATION IN LOGIC ALGEBRA

Research article

Sdvizhkov O.A.^1, *, Matsnev N.P.²

¹ Russian State University of Tourism and Service, Pushkino, Russia;

² University of Technology, Korolev, Russia

* Corresponding author (oasdv[at]yandex.ru)

Abstract

Using the modulo two addition operation, the fundamental concepts of matrix calculus are defined in the logic algebra, such as linearly dependent and independent sets of rows (columns) of a matrix, matrix rank, sum and product of matrices, matrix determinant, inverse matrix. The properties of the determinants of the logic algebra are given. Using inverse matrices of the logic algebra, systems of linear equations with modulo two sums are solved. Examples are given for calculating the rank of a matrix, determinants, inverse matrices and solving systems of linear equations with modulo two sums in the logic algebra.

Keywords: binary matrix, modulo two sum, determinant, inverse matrix, matrix rank, system of equations.

Введение

Алгебра логики, в широком смысле, которого придерживаются авторы, это раздел математики, построенный на множестве Е₂ = {0, 1}.

Некоторые проблемы алгебры логики рассматривались одним из авторов в работах [6], [7], [8], данная статья посвящена формулам алгебры логики, позволяющим выполнять матричные операции.

Фундаментальные формулы матричного исчисления [2], [3], [5] во множестве матриц алгебры логики не имеют смысла, так как в алгебре логики нет операций +, – и так далее, применяемых в этих формулах, как и других чисел кроме 0 и 1.

В статье показывается, что, применяя сложение по модулю два, формулы матричного исчисления можно заменить формулами алгебры логики, корректно выполняющими матричные операции.

1. Простейшие операции с булевыми матрицами

Пусть задана матрица . Такая матрица называется булевой (бинарной, двоичной, матрицей алгебры логики).

Матрицу , где  – бинарное число, противоположное числу  , естественно назвать противоположной матрице А.

Произведение матрицы А на константу  определяется обычным образом:

Под суммой матриц А и В вида m×n в алгебре логики, естественно, понимать матрицу , элементы которой находятся по формуле:

Назовем булевым (бинарным) произведением матрицы вида m×p на матрицу  вида p×n такую матрицу С вида m×n, обозначаемую А*B mod 2, элементы которой находятся по формуле:

Пример: Столбец j матрицы А назовем бинарной линейной комбинацией столбцов j₁, j₂, …, j_r, если: где все коэффициенты принимают значения из множества Е₂. Столбцы j₁, j₂, …, j_r назовем бинарно линейно независимыми, если выполняется только при . В противном случае, столбцы – бинарно линейно зависимые. Бинарно линейно независимые столбцы j₁, j₂, …, j_r назовем сильно независимыми, если: Пусть столбцы j₁, j₂, …, j_r  бинарно линейно зависимые, причем, например, . Тогда можно записать: Откуда следует, что столбец j_r является бинарной линейной комбинацией остальных столбцов: Пусть столбцы j₁, j₂, …, j_r сильно независимые. Тогда можно записать:

Откуда следует, что столбец противоположный столбцу j_r, как и любому другому столбцу, является бинарной линейной комбинацией остальных столбцов:

Понятно, что аналогичные определения и рассуждения имеют место и для строк матрицы А.

Назовем булевым рангом матрицы А, обозначим его rang^*(A), максимальное число бинарно линейно независимых столбцов (строк) матрицы А.

2. Булевы определители и их свойства

Назовем булевым (бинарным) определителем квадратной матрицы n-го порядка  величину

где суммирование по модулю 2 выполняется по всем попарно различным значениям индексов j₁, j₂,…, j_n. Звездочка справа показывает, что величина определителя рассчитывается по формуле, отличной от применяемой во множестве R. Этот определитель будем обозначать также |A|^* или Δ^*.

В силу данного определения, разложение определителя |A|^* по i-й строке имеет вид

а разложение по j-му столбцу записывается в виде

M_ij – бинарный определитель матрицы, получаемой вычеркиванием i-й строки и j-го столбца из матрицы А.

Примеры:

Из приведенных формул вытекают свойства бинарных определителей.

1. Свойства бинарных определителей, верные для строк, справедливы и для столбцов.
2. При перестановке местами строк величина бинарного определителя не изменяется.
3. Если в матрице А есть нулевая строка или равные строки, то ее бинарный определитель равен нулю.
4. Если в матрице А элементы какой-либо строки являются суммами по модулю 2 двух слагаемых, то бинарный определитель матрицы А равен сумме по модулю 2 двух бинарных определителей.
5. Если в матрице А какая-либо строка является бинарной линейной комбинацией некоторых других строк, то бинарный определитель матрицы А равен нулю.
6. Если к какой-либо строке матрицы А прибавить по модулю 2 бинарную линейную комбинацию некоторых других строк, то бинарный определитель матрицы А не изменится.
7. Двоичная сумма произведений элементов какой-либо строки на дополнительные бинарные миноры элементов другой строки равна нулю:

Следует заметить, в силу свойств 2 и 6, ранг матрицы rang^*(A) можно найти, переставляя строки и прибавляя по модулю 2 к элементам одной строки матрицы А элементы другой строки, чтобы ниже главной диагонали оказались нули. Например:

Теорема 1. Пусть Δ – определитель бинарной матрицы А во множестве R, | Δ | – абсолютная величина определителя Δ, | Δ | mod 2 – остаток от деления | Δ | на 2. Тогда:

| Δ | mod 2 = Δ^*

Следствие 1. Если Δ = 0, то Δ^* = 0, а если Δ^* ≠0, то Δ ≠0.

Следствие 2. Справедлива оценка: rang*(A)≤  rang(A), rang(A) – ранг матрицы А во множестве R.

3. Обратная матрица по булевому произведению

Назовем матрицу обратной по булевому произведению для матрицы  и будем обозначать ее  – единичная матрица.

В силу свойства 7 определителей и формулы разложения бинарного определителя по i-й строке, справедлива следующая теорема.

Теорема 2. Если бинарный определитель бинарной матрицы А равен 1, то матрица А имеет единственную обратную по булевому произведению матрицу В= , элементы которой находятся по формуле:

Примеры: 1. Проверка: 2.  Проверка: 3. Проверка: 4. Системы линейных уравнений с суммами по модулю 2 Рассмотрим систему линейных уравнений с суммами по модулю 2:

В силу теоремы 2, справедлива следующая теорема.

Теорема 3. Если определитель Δ^* матрицы А системы линейных уравнений с суммами по модулю 2 равен 1, то система имеет единственное решение, которое находится по формуле:

Пример:

Замечание

Обратная по булевому произведению матрица к матрице системы этого примера найдена в предыдущем параграфе.

С помощью теоремы 3 доказывается следующая теорема.

Теорема 4. Если бинарный определитель матрицы системы линейных уравнений с суммами по модулю 2 равен 1, то система имеет единственное решение, которое находится по формулам, аналогичным формулам Крамера:

Для последней системы эти формулы дают: Заключение

В статье впервые приводятся, и иллюстрируются на примерах, основные формулы матричного исчисления в алгебре логики, включая формулы решения систем линейных уравнений с суммами по модулю 2.

Конфликт интересов Не указан.

Conflict of Interest None declared.

Список литературы / References

1. Гаврилов Г.П. Задачи и упражнения по дискретной математике: Учебное пособие – 3-е изд., перераб. / Г.П. Гаврилов, А.А. Сапоженко – М.: ФИЗМАТЛИТ, 2003. – 416 с.
2. Андре Анго. Математика для электро- и радиоинженеров / Анго Андре – М.: Издательство «Наука», 1967. – 780 с.
3. Беклемишев Д.В. Курс аналитической геометрии и линейной алгебры / Д.В. Беклемишев – М.: Издательство «Наука», 1976. – 320 с.
4. Ерусалимский Я. М. Дискретная математика: теория, задачи, приложения. 3-е издание. / Я. М. Ерусалимский – М.: Вузовская книга, 2000. – 280 с.
5. Корн Г. Справочник по математике. / Г. Корн, Т. Корн – М.: Издательство «Наука», 1973. – 832 с.
6. Сдвижков О. А. Дискретная математика и математические методы экономики с применением VBA Excel / О. А. Сдвижков – М.: ДМК Пресс, 2012. – 212 с.
7. Сдвижков О. А. Характеристические полиномы булевых функций / Сдвижков О. А. // Международный научно-исследовательский журнал. 2017. №9-3 (63). С. 96-102
8. Сдвижков О. А. Применение линейного программирования к задачам алгебры логики / Сдвижков О. А. // Международный научно-исследовательский журнал. 2017. №10-3 (64). С. 116 – 122
9. Супрун В.П. Основы теории булевых функций / В.П. Супрун – М.: ЛЕНАНД, 2017. – 208 с.
10. Яблонский С.В. Введение в дискретную математику: Учебное пособие для вузов / Яблонский С.В., В.А. Садовничего. – 4-е изд., стер. – М.: Высш. шк., 2003. – 384 с.

Список литературы на английском языке / References in English

1. Gavrilov G.P. Zadachi i uprazhneniya po diskretnoj matematike: Uchebnoe posobie - 3-e ed., pererab. [Tasks and exercises on discrete mathematics] / G.P. Gavrilov, A.A. Sapozhenko – M.: FIZMATLIT, 2003. – 416 p. [in Russian]
2. Andre Ango. Matematika dlya jelektro- i radioinzhenerov [Mathematics for elektro- and radioengineers] / Ango Andre – M.: "Science", 1967. – 780 p. [in Russian]
3. Beklemishev D.V. Kurs analiticheskoj geometrii i linejnoj algebry [Rate of analytical geometry and linear algebra]/ D.V. Beklemishev – M.: "Science", 1976. – 320 p. [in Russian]
4. Erusalimskij Ya. M. Diskretnaya matematika: teoriya, zadachi, prilozheniya. 3-e ed. [Discrete mathematics: the theory, task, appendix] / Ya. M. Erusalimskij – M.: high school book, 2000. – 280 p. [in Russian]
5. Korn G. Spravochnik po matemamike [Mathematical handbook] / G. Korn, T. Korn – M.: "Science", 1973. – 832 p. [in Russian]
6. Sdvizhkov O.A. Diskretnaja matematika i matematicheskie metody jekonomiki s primeneniem VBA Excel [Discrete mathematics and mathematical methods of economy with application VBA Excel] / O.A. Sdvizhkov – M.: DMK Press, – 212 p. [in Russian]
7. Sdvizhkov O. A. Kharakteristicheskie polinomy bulevykh funktsij [Characteristic polynomials of Boolean functions] / Sdvizhkov O. A. // the International research magazine. 2017. № 9-3 (63). p. 96-102 [in Russian]
8. Sdvizhkov O. A. Primenenie linejnogo programmirovaniya k zadacham algebry logiki [Application of linear programming to tasks of algebra of logic] / Sdvizhkov O. A. // the International research magazine. 2017. № 10-3 (64). p. 116 – 122 [in Russian]
9. Suprun V.P. Osnovy teorii bulevykh funktsij [Bases of the theory of Boolean functions]/ V.P. Suprun – M.: LENAND, 2017. – 208 p. [in Russian]
10. Yablonskij S.V. Vvedenie v diskretnuyu matematiku: Uchebnoe posobie dlya vuzov [Introduction in discrete mathematics: the manual for high schools] / Yablonskij S.V., V.A. Sadovnichego – M.: “High school”, 2003. – 384 p. [in Russian]