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

Анотація наукової статті з математики, автор наукової роботи - Сдвижков О.А., Мацнев Н.П.


MATRIX CALCULATION IN LOGIC ALGEBRA

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.


Область наук:
  • Математика
  • Рік видавництва: 2019
    Журнал: Міжнародний науково-дослідний журнал

    Наукова стаття на тему 'матричного числення В алгебрі логіки'

    Текст наукової роботи на тему «матричного числення В алгебрі логіки»

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

    Матричного числення В алгебрі логіки

    Наукова стаття

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

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

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

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

    анотація

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

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

    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.org.ua)

    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. Найпростіші операції з булевими матрицями

    Нехай задана матриця A = (a.), I = 1,2, ..., m; j = 1,2, ..., n, ae Е2. Така матриця називається булевої (бінарної, двійковій, матрицею алгебри логіки).

    Матрицю A = (aj), де aij - бінарне число, протилежне числу aij, природно назвати протилежної

    ij ij У

    матриці А.

    Твір матриці А на константу ae Е2 визначається звичайним чином:

    а-А = (a-ay)

    Під сумою матриць А і В виду m * n в алгебрі логіки, природно, розуміти матрицю С = А Ф В, елементи якої знаходяться за формулою:

    c = a .. 9b..

    у У ч

    Назвемо булевим (бінарним) твором матриці A = (ak), ak e Е2, виду m * p на матрицю В = (by), by e Е2, виду pxn таку матрицю С виду m * n, що позначається А * В mod 2, елементи якої знаходяться за формулою:

    c2 = АА] 8аА} 8||| 8аА

    приклад:

    1 0 1 1

    1 + 1) Г1-18 0 • 0 1-18 0-1

    I тих! 2 = I

    0 1) Ц-181-0 1-181-1

    10

    Стовпець] матриці А назвемо бінарної лінійної комбінацією стовпців] 2, |||,] "якщо:

    а

    а.. > Г а.. >

    • л Ч 2

    А2 Л 8а 2 + 2 А2 J2 8

    а. а .

    шJl V ШJ2 у

    (А \

    8 ... 9а

    а

    V ш>г У

    а

    2]

    а

    V ш1 У

    де всі коефіцієнти приймають значення з безлічі Е2. Стовпці] 1,] 2, |||,] г назвемо бінарному лінійно незалежними, якщо

    (А А

    41

    а

    V шл)

    фа,

    (А. А

    Ч 2

    а

    V шн)

    (АІГ 1 Г01

    Ф ... Фа,

    а

    V ш1,)

    виконується тільки при а. = А = ... = а = 0. В іншому випадку, стовпці - бінарному лінійно залежні.

    J1 J 2 J п

    Бінарному лінійно незалежні столбциJl, J2, | .., Jrназовем сильно незалежними, якщо:

    (А \

    | * 2 Jl

    а

    V шJl)

    і. ^

    Ч 2

    8

    а

    V ш2

    (А .. 1 М

    8 ... 8

    а

    V ШJr)

    Нехай столбциjl, J2, | .., Jr бінарному лінійно залежні, причому, наприклад, а. = 1. Тоді можна записати:

    а,.

    (А ^%

    Л2 Jl

    а

    V шJl

    j 2

    'А J ^

    а

    V ШJ2)

    аа

    8 ... 8

    а

    V ш->г J

    8

    а

    V ШJr)

    Г 01

    V 0)

    ( "\

    8

    а

    V ШJr)

    Звідки випливає, що стовпець Jr є бінарної лінійної комбінацією інших стовпців:

    а

    (А ^

    "1J1

    V aшJl)

    J 2

    ч, ^

    1J 2

    2 J2

    VaШJ2)

    8 ... 8а; _1

    а

    Л1! Г _1

    2 Jr _1

    а

    V шJr-1 У

    а

    а

    V шJr У

    Нехай столбциJl, J2, -. ^ Гсільно незалежні. Тоді можна записати:

    (А \ ^ л

    ^ 2 Jl

    а

    V шJl у

    Г а1, А 1J 2

    8

    ^ 2 J2

    а

    V ШJ2 У

    Га. А Га А

    8 ... 8

    | * 2 Jr

    а

    V ШJr У

    8

    АІГ Г11

    а

    V ШJr У

    8

    (А \

    Л2 Jr

    а

    V ШJr У

    г

    а

    0

    а

    а

    а

    а

    11

    1

    а

    а

    Г

    Г

    Г

    0

    а

    а

    а

    а

    а

    а

    г

    1

    а

    Звідки випливає, що стовпець протилежний одну рг, як і будь-якого іншого колонки, є бінарної лінійної комбінацією інших стовпців:

    (A \ (a \

    -U'l

    | * 2 j

    a

    V тл

    фа,

    Ч У 2

    | * 2 j

    a

    V mh У

    a

    Л1 У, -1

    9 ... ®а -1

    2 j, -1

    V amj, 1У

    in \

    a

    V mJ, У

    Зрозуміло, що аналогічні визначення і міркування мають місце і для рядків матриці А.

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

    §2. Булеві визначники та їх властивості

    Назвемо булевим (бінарним) визначником квадратної матриці n-го порядку A = (a У), a У e Е2, величину

    = 9 a, .- a ". -... -a .

    (., 1 J1 2 J2 nJn

    (J1, ..., Jn)

    де підсумовування по модулю 2 виконується за всіма попарно різним значенням індексів р1, Зірочка справа показує, що величина визначника розраховується за формулою, відмінною від застосовуваної в безлічі Я. Цей визначник будемо позначати також | А | або Д .

    В силу цього визначення, розкладання визначника | А | по / -му рядку має вигляд

    IA | = 9 au- M j

    j = 1

    а розкладання по] -му стовпцю записується у вигляді

    IА | * = (?) А9-М9,

    М р - бінарний визначник матриці, одержуваної викреслюванням / -го рядка і _ / - го стовпця з матриці А. Приклади:

    1.

    2.

    3.

    1 1 1 0

    = 1-0 91-1 = 1

    1 1 1 1 01 01 1

    = 1

    0 1 * 1 1 * 1 0

    91- 91-

    1 1 01 0 1

    = (0 91) 9 (19 0) 9 (19 0) = 1

    1 1 1 1 01 01 1

    0 у середньому 1 1 + 1

    1 91-

    11 11

    9 0 = (0 91) 9 (191) = 1

    a

    h

    a21 a22 ... a2n

    an1 an2 ... ann

    З наведених формул випливають властивості бінарних визначників.

    1. Властивості бінарних визначників, вірні для рядків, справедливі і для стовпців.

    2. При перестановці місцями рядків величина бінарного визначника не змінюється.

    3. Якщо в матриці А є нульова рядок або рівні рядки, то її бінарний визначник дорівнює нулю.

    4. Якщо в матриці А елементи якого-небудь рядка є сумами по модулю 2 двох доданків, то бінарний визначник матриці А дорівнює сумі по модулю 2 двох бінарних визначників.

    5. Якщо в матриці А будь-який рядок є бінарної лінійної комбінацією деяких інших рядків, то бінарний визначник матриці А дорівнює нулю.

    6. Якщо до будь-якої рядку матриці А додати по модулю 2 бінарну лінійну комбінацію деяких інших рядків, то бінарний визначник матриці А не зміниться.

    7. Двоичная сума добутків елементів будь-якого рядка на додаткові бінарні мінори елементів іншого рядка дорівнює нулю:

    © a. • MkJ - 0, i Ф k

    j = i

    Слід зауважити, в силу властивостей 2 і 6, ранг матриці rang (A) можна знайти, переставляючи рядки і додаючи по модулю 2 до елементів одного рядка матриці А елементи іншого рядка, щоб нижче головної діагоналі виявилися нулі. наприклад:

    '1 1 10 0 1 1 0 10 111 А = 1 0 1 0 11 110 100 V0 0 0 1 01 rang (A) = 4

    Г1 1 10 0 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 101 0 0 0 1 01

    1 10 0 1 1 0 1 0 1 1 1 0 0 0 1 01 0 0 1101 0 0 0 1 01

    Г1 1 10 0 1 1 0 10 111 0 0 110 1 0 0 0 1 01 0 0 00 00

    Теорема 1. Нехай Д - визначник бінарної матриці А в безлічі R, | Д | - абсолютна величина визначника Д, | Д | mod 2 - залишок від ділення | Д | на 2. Тоді:

    | Д | mod 2 = Д *

    Слідство 1. Якщо Д = 0, то Д * = 0, а якщо Д * Ф 0, то Д Ф 0.

    Слідство 2. Справедлива оцінка: rang * (A) < rang (A), rang (A) - ранг матриці А в безлічі R. §3. Зворотній матриця по Булевой твору

    Назвемо матрицю В - (Ь ..) Ь .. е Е2 зворотного по Булевой твору для матриці a = (a) a їЇ і будемо

    J J 2 'J J 2 5

    позначати її А-1, якщо А * В mod 2 = Е, Е - одинична матриця.

    В силу властивості 7 визначників і формули розкладання бінарного визначника по i-му рядку, справедлива наступна теорема.

    Теорема 2. Якщо бінарний визначник бінарної матриці А дорівнює 1, то матриця А має єдину зворотну по Булевой твору матрицю В = А * 1, елементи якої знаходяться за формулою:

    приклади:

    1.

    A =

    1 1 1 0

    bj = Mj.

    А * = 1 ^ A-1 -

    0 1

    Перевірка:

    11 Г ") mod 2 = 1 ° © '' © 1 1 = 1 '0

    10 Jh 1J 10 © 0 1 © 0 J 10 1

    2.

    А -

    Г1111 1 01 01 1

    ^ А = 1 ^

    A * -

    Г 0 1 * 11 * 10 * 1

    11 11 11

    1 0 * 10 * 11 *

    11 11 11

    1 0 * 10 * 11 *

    V 0 у середньому 1 11 10 J

    Г1 0 11 1 1 0 111

    Перевірка:

    f 11) f 0 '1 © 1 © 1 0 © 1 © 1 1 © 0 © 1) Г1 0 01

    1 01 1 1 0 mod 2 - 1 © 0 © 1 0 © 0 © 1 1 © 0 © 1 - 0 1 0

    v01 1 v1 1 1J ч0 © 1 © 1 0 © 1 © 1 0 © 0 © 1,, 0 0 I

    3.

    А--

    Г1 1 1 1 ^ 1110 0011

    V0111 /

    ^ А = 1 ^

    А * -

    Г10 0 л 00 11 1110 1100

    Перевірка:

    (1111> '10 0 1 ^ Г1 0 0 0 "

    1110 00 11 0 1 0 0

    шоё 2 -

    0011 1110 0 0 1 0

    V0111 V і 00, 0 0

    §4. Системи лінійних рівнянь з сумами по модулю 2 Розглянемо систему лінійних рівнянь з сумами по модулю 2:

    А11 х1 © а12х2 © ... © а1пхп - ь1 а21х1 © а22х2 © ... © а2пхп - Ь2

    ап1х1 © ап2х2 © ... © аппХп - Іоп

    аа е Е2 'ЬJ е Е2' х е Е2 .

    В силу теореми 2, справедлива наступна теорема.

    Теорема 3. Якщо визначник Д матриці А системи лінійних рівнянь з сумами по модулю 2 дорівнює 1, то система має єдине рішення, яке знаходиться за формулою:

    X - А; 1 • В шо<12

    приклад:

    х1 © х2 © х3 - 0 © х3 - 1 х2 © х3 - 1

    Г Х1 ^

    V хз

    Г1 0 1У 0 ^ Г1 ^

    1 1 0 111

    зауваження

    Зворотній по Булевой твору матриця до матриці системи цього прикладу знайдена в попередньому параграфі.

    За допомогою теореми 3 доводиться наступна теорема.

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

    Л *

    х - А..

    Для останньої системи ці формули дають:

    0 1 1 1 0 1 1 1 1

    1 0 1 1 1 1 011

    1 1 0 1 0 1 011

    11 1 0 Попереднє

    © -1

    11 11

    11 * 11 *

    © - 1

    11 0 1

    01 * 11 *

    © - 0

    11 0 1

    висновок

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

    х

    2

    Х1 =

    *

    Конфлікт інтересів 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, 2012.

    - 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]


    Ключові слова: бінарною матрицею / СУМА ПО МОДУЛЯ ДВА / ВИЗНАЧНИК / ЗВОРОТНА МАТРИЦЯ / РАНГ МАТРИЦІ / СИСТЕМА РІВНЯНЬ / BINARY MATRIX / MODULO TWO SUM / DETERMINANT / INVERSE MATRIX / MATRIX RANK / SYSTEM OF EQUATIONS

    Завантажити оригінал статті:

    Завантажити