Pages Navigation Menu

ISSN 2227-6017 (ONLINE), ISSN 2303-9868 (PRINT), DOI: 10.18454/IRJ.2227-6017
ПИ № ФС 77 - 51217, 16+

DOI: https://doi.org/10.23670/IRJ.2019.88.10.002

Скачать PDF ( ) Страницы: 11-16 Выпуск: № 10 (88) Часть 1 () Искать в Google Scholar
Цитировать

Цитировать

Электронная ссылка | Печатная ссылка

Скопируйте отформатированную библиографическую ссылку через буфер обмена или перейдите по одной из ссылок для импорта в Менеджер библиографий.
Сдвижков О. А. МАТРИЧНОЕ ИСЧИСЛЕНИЕ В АЛГЕБРЕ ЛОГИКИ / О. А. Сдвижков, Н. П. Мацнев // Международный научно-исследовательский журнал. — 2019. — № 10 (88) Часть 1. — С. 11—16. — URL: https://research-journal.org/physics-mathematics/matrichnoe-ischislenie-v-algebre-logiki/ (дата обращения: 07.12.2019. ). doi: 10.23670/IRJ.2019.88.10.002
Сдвижков О. А. МАТРИЧНОЕ ИСЧИСЛЕНИЕ В АЛГЕБРЕ ЛОГИКИ / О. А. Сдвижков, Н. П. Мацнев // Международный научно-исследовательский журнал. — 2019. — № 10 (88) Часть 1. — С. 11—16. doi: 10.23670/IRJ.2019.88.10.002

Импортировать


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

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

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

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

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

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

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

Аннотация

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

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

MATRIX CALCULATION IN LOGIC ALGEBRA

Research article

Sdvizhkov O.A.1, *, Matsnev N.P.2

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

2 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.

Введение

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

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

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

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

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

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

Матрицу 29-10-2019 11-26-03, где 29-10-2019 11-26-10 – бинарное число, противоположное числу  29-10-2019 11-26-10, естественно назвать противоположной матрице А.

Произведение матрицы А на константу 29-10-2019 11-26-20 определяется обычным образом:

29-10-2019 11-30-28

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

29-10-2019 11-30-35

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

29-10-2019 11-35-02

Пример:

29-10-2019 11-35-18

Столбец j матрицы А назовем бинарной линейной комбинацией столбцов j1, j2, …, jr, если:

29-10-2019 11-35-52

где все коэффициенты принимают значения из множества Е2.

Столбцы j1, j2, …, jr назовем бинарно линейно независимыми, если

29-10-2019 11-38-37

выполняется только при 29-10-2019 11-39-40. В противном случае, столбцы – бинарно линейно зависимые.

Бинарно линейно независимые столбцы j1, j2, …, jr назовем сильно независимыми, если:

29-10-2019 11-38-44

Пусть столбцы j1, j2, …, jr  бинарно линейно зависимые, причем, например, 29-10-2019 11-40-14. Тогда можно записать:

29-10-2019 11-50-15

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

29-10-2019 11-50-23

Пусть столбцы j1, j2, …, jr сильно независимые. Тогда можно записать:

29-10-2019 11-50-32

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

29-10-2019 12-00-30

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

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

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

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

29-10-2019 12-01-10

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

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

29-10-2019 12-05-20

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

29-10-2019 12-05-28

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

Примеры:

29-10-2019 12-08-36

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

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

29-10-2019 12-12-33

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

29-10-2019 12-13-27

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

| Δ | mod 2 = Δ*

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

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

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

Назовем матрицу 29-10-2019 12-23-50 обратной по булевому произведению для матрицы 29-10-2019 12-23-59 и будем обозначать ее 29-10-2019 12-24-33 – единичная матрица.

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

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

29-10-2019 12-30-36

Примеры:

1.29-10-2019 12-32-54

Проверка:

29-10-2019 12-33-04

2. 29-10-2019 12-33-14

Проверка:

29-10-2019 12-33-26

3.29-10-2019 12-33-35

Проверка:

29-10-2019 12-33-41

4. Системы линейных уравнений с суммами по модулю 2

Рассмотрим систему линейных уравнений с суммами по модулю 2:

29-10-2019 12-44-00

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

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

29-10-2019 12-44-43

Пример:

29-10-2019 12-44-50

Замечание

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

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

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

29-10-2019 12-47-36

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

29-10-2019 12-47-46

Заключение

В статье впервые приводятся, и иллюстрируются на примерах, основные формулы матричного исчисления в алгебре логики, включая формулы решения систем линейных уравнений с суммами по модулю 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]

Оставить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Лимит времени истёк. Пожалуйста, перезагрузите CAPTCHA.