Логическая матрица

Матрица двоичных значений истинности

Логическая матрица , бинарная матрица , матрица отношений , булева матрица или (0, 1)-матрица — это матрица с элементами из булевой области B = {0, 1}. Такая матрица может быть использована для представления бинарного отношения между парой конечных множеств . Это важный инструмент в комбинаторной математике и теоретической информатике .

Матричное представление отношения

Если R — это бинарное отношение между конечными индексированными множествами X и Y (так что R ⊆ X × Y ), то R можно представить логической матрицей M, индексы строк и столбцов которой индексируют элементы X и Y , соответственно, так что элементы M определяются как

${\displaystyle m_{i,j}={\begin{cases}1&(x_{i},y_{j})\in R,\\0&(x_{i},y_{j})\not \in R.\end{cases}}}$

Для обозначения номеров строк и столбцов матрицы множества X и Y индексируются положительными целыми числами : i изменяется от 1 до мощности (размера) X , а j изменяется от 1 до мощности Y. Более подробную информацию см. в статье об индексированных множествах .

Пример

Бинарное отношение R на множестве {1, 2, 3, 4} определяется так, что aRb выполняется тогда и только тогда, когда a делит b нацело, без остатка. Например, 2 R 4 выполняется, потому что 2 делит 4 без остатка, но 3 R 4 не выполняется, потому что когда 3 делит 4, есть остаток 1. Следующий набор — это набор пар, для которых выполняется отношение R.

{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.

Соответствующее представление в виде логической матрицы имеет вид

${\displaystyle {\begin{pmatrix}1&1&1&1\\0&1&0&1\\0&0&1&0\\0&0&0&1\end{pmatrix}},}$

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

Другие примеры

• Матрица перестановок — это (0, 1)-матрица, все столбцы и строки которой содержат ровно один ненулевой элемент.
  • Массив Костаса является частным случаем матрицы перестановок.
• Матрица инцидентности в комбинаторике и конечной геометрии содержит элементы, указывающие инцидентность между точками (или вершинами) и линиями геометрии, блоками блочной конструкции или ребрами графа .
• Матрица плана в дисперсионном анализе представляет собой (0, 1)-матрицу с постоянными суммами строк.
• Логическая матрица может представлять собой матрицу смежности в теории графов : несимметричные матрицы соответствуют ориентированным графам , симметричные матрицы — обычным графам , а единица на диагонали соответствует петле в соответствующей вершине.
• Матрица бисмежности простого неориентированного двудольного графа является (0, 1)-матрицей, и любая (0, 1)-матрица возникает таким образом.
• Простые множители списка из m свободных от квадратов , n -гладких чисел можно описать как матрицу m × π( n ) (0, 1), где π — функция подсчета простых чисел , а a _ij равно 1 тогда и только тогда, когда j -е простое число делит i -е число. Это представление полезно в алгоритме факторизации квадратного решета .
• Растровое изображение, содержащее пиксели только двух цветов, можно представить в виде (0, 1)-матрицы, в которой нули представляют пиксели одного цвета, а единицы — пиксели другого цвета.
• Двоичную матрицу можно использовать для проверки правил игры в Го . [ ^1]
• Четырехзначная логика из двух битов, преобразованная логическими матрицами 2x2, образует систему переходов .
• Рекуррентная диаграмма и ее варианты представляют собой матрицы, которые показывают, какие пары точек находятся ближе определенного порога близости в фазовом пространстве .

Некоторые свойства

Умножение двух логических матриц с использованием булевой алгебры .

Матричное представление отношения равенства на конечном множестве — это единичная матрица I , то есть матрица, все элементы которой на диагонали равны 1, а все остальные равны 0. В более общем случае, если отношение R удовлетворяет условию I ⊆ R , то R является рефлексивным отношением .

Если рассматривать булеву область как полукольцо , где сложение соответствует логическому ИЛИ , а умножение — логическому И , то матричное представление композиции двух отношений равно матричному произведению матричных представлений этих отношений. Это произведение может быть вычислено за ожидаемое время O( n ² ). ^[2]

Часто операции над бинарными матрицами определяются в терминах модульной арифметики mod 2, то есть элементы рассматриваются как элементы поля Галуа . Они возникают в различных представлениях и имеют ряд более ограниченных специальных форм. Они применяются, например, в XOR-выполнимости . ${\displaystyle {\mathbf {GF}}(2)=\mathbb {Z} _{2}}$

Число различных двоичных матриц размером m на n равно 2mn ^и , таким образом, конечно.

Решетка

Пусть даны n и m , и пусть U обозначает множество всех логических матриц m × n . Тогда U имеет частичный порядок , заданный как

${\displaystyle \forall A,B\in U,\quad A\leq B\quad {\text{when}}\quad \forall i,j\quad A_{ij}=1\implies B_{ij}=1.}$

Фактически, U образует булеву алгебру с операциями и & или между двумя матрицами, применяемыми покомпонентно. Дополнение логической матрицы получается путем замены всех нулей и единиц на их противоположности.

Каждая логическая матрица A = ( A _ij ) имеет транспонированную A ^T = ( A _ji ). Предположим, что A — логическая матрица без столбцов или строк, тождественно равных нулю. Тогда произведение матриц, используя булеву арифметику, содержит единичную матрицу m × m , а произведение содержит единичную матрицу n × n . ${\displaystyle A^{\operatorname {T} }A}$ ${\displaystyle AA^{\operatorname {T} }}$

Как математическая структура, булева алгебра U образует решетку, упорядоченную по включению ; кроме того, она является мультипликативной решеткой из-за умножения матриц.

Каждая логическая матрица в U соответствует бинарному отношению. Эти перечисленные операции над U и упорядочение соответствуют исчислению отношений , где умножение матриц представляет композицию отношений . ^[3]

Логические векторы

Если m или n равно единице, то логическая матрица m × n ( m _ij ) является логическим вектором или битовой строкой . Если m = 1, вектор является вектором-стркой, а если n = 1, то это вектор-столбец. В любом случае индекс, равный 1, опускается из обозначения вектора.

Предположим , что и — два логических вектора. Внешнее произведение P и Q дает прямоугольное отношение m × n ${\displaystyle (P_{i}),\,i=1,2,\ldots ,m}$ ${\displaystyle (Q_{j}),\,j=1,2,\ldots ,n}$

${\displaystyle m_{ij}=P_{i}\land Q_{j}.}$

Переупорядочивание строк и столбцов такой матрицы может собрать все единицы в прямоугольную часть матрицы. ^[4]

Пусть h — вектор всех единиц. Тогда, если v — произвольный логический вектор, отношение R = vh ^T имеет постоянные строки, определяемые v . В исчислении отношений такой R называется вектором. ^[4] Частным случаем является универсальное отношение . ${\displaystyle hh^{\operatorname {T} }}$

Для данного отношения R максимальное прямоугольное отношение, содержащееся в R, называется понятием в R. Отношения можно изучать, разлагая на понятия, а затем отмечая индуцированную решетку понятий .

Рассмотрим таблицу группоподобных структур, где «ненужное» можно обозначить 0, а «нужное» — 1, образуя логическую матрицу Для вычисления элементов необходимо использовать логическое скалярное произведение пар логических векторов в строках этой матрицы. Если это скалярное произведение равно 0, то строки ортогональны. Фактически, малая категория ортогональна квазигруппе , а группоид ортогонален магме . Следовательно, в есть нули , и оно не может быть универсальным отношением . ${\displaystyle R.}$ ${\displaystyle RR^{\operatorname {T} }}$ ${\displaystyle RR^{\operatorname {T} }}$

Суммы строк и столбцов

Сложение всех единиц в логической матрице может быть выполнено двумя способами: сначала суммированием строк или сначала суммированием столбцов. Когда суммируются суммы строк, сумма такая же, как и при сложении сумм столбцов. В геометрии инцидентности матрица интерпретируется как матрица инцидентности со строками, соответствующими «точкам», а столбцы — как «блоки» (обобщающие линии, сделанные из точек). Сумма строки называется ее степенью точки , а сумма столбца — степенью блока . Сумма степеней точки равна сумме степеней блока. ^[5]

Ранней проблемой в этой области было «нахождение необходимых и достаточных условий для существования структуры инцидентности с заданными степенями точек и степенями блоков; или на матричном языке, для существования (0, 1)-матрицы типа v  ×  b с заданными суммами строк и столбцов». ^[5] Эта задача решается теоремой Гейла–Райзера .

Смотрите также

• Список матриц
• Бинаторикс (двоичный тор Де Брейна)
• Битовый массив
• Дизъюнктная матрица
• Матрица Редхеффера
• Таблица истинности
• Трехзначная логика

Примечания

1. Петерсен, Кьельд (8 февраля 2013 г.). «Бинматрица» . Проверено 11 августа 2017 г.
2. О'Нил, Патрик Э.; О'Нил, Элизабет Дж. (1973). «Быстрый алгоритм ожидаемого времени для умножения булевых матриц и транзитивного замыкания». Информация и управление . 22 (2): 132–8. doi :10.1016/s0019-9958(73)90228-3.— Алгоритм основан на идемпотентности сложения , см. стр. 134 (внизу).
3. Копиловиш, Ирвинг (декабрь 1948 г.). «Матричная разработка исчисления отношений». Журнал символической логики . 13 (4): 193–203. doi :10.2307/2267134. JSTOR  2267134.
4. Schmidt, Gunther (2013). "6: Relations and Vectors". Реляционная математика . Cambridge University Press. стр. 91. doi :10.1017/CBO9780511778810. ISBN 978-0-511-77881-0.
5. Например, см. Бет, Томас; Юнгникель, Дитер ; Ленц, Ханфрид (1999). "I. Примеры и основные определения". Теория проектирования . Энциклопедия математики и ее приложений . Т. 69 (2-е изд.). Cambridge University Press . С. 18. doi :10.1017/CBO9780511549533.001. ISBN 978-0-521-44432-3.

Ссылки

• Brualdi, Richard A. (2006). "Комбинаторные матричные классы". Энциклопедия математики и ее приложений . Том 108. Cambridge University Press. doi :10.1017/CBO9780511721182. ISBN 978-0-521-86565-4.
• Brualdi, Richard A.; Ryser, Herbert J. (1991). "Комбинаторная теория матриц". Энциклопедия математики и ее приложений . Том 39. Cambridge University Press. doi :10.1017/CBO9781107325708. ISBN 0-521-32265-0.
• Botha, JD (2013), "31. Матрицы над конечными полями §31.3 Двоичные матрицы", в Hogben, Leslie (ред.), Handbook of Linear Algebra (Discrete Mathematics and Its Applications) (2-е изд.), Chapman & Hall/CRC, doi :10.1201/b16113, ISBN 978-0-429-18553-3
• Ким, Ки Ханг (1982), Теория булевых матриц и ее применение , Деккер, ISBN 978-0-8247-1788-9
• Райзер, Х. Дж. (1957). «Комбинаторные свойства матриц из нулей и единиц». Канадский математический журнал . 9 : 371–7.
• Райзер, Х. Дж. (1960). «Следы матриц нулей и единиц». Канадский математический журнал . 12 : 463–476. doi :10.4153/CJM-1960-040-0.
• Райзер, Х. Дж. (1960). «Матрицы нулей и единиц» (PDF) . Бюллетень Американского математического общества . 66 : 442–464.
• Фулкерсон, DR (1960). "Ноль-единичные матрицы с нулевым следом" (PDF) . Pacific Journal of Mathematics . 10 : 831–6.
• Фулкерсон, DR; Райзер, HJ (1961). «Ширина и высота (0, 1)-матриц». Канадский математический журнал . 13 : 239–255. doi :10.4153/CJM-1961-020-3.
• Ford Jr., LR ; Fulkerson, DR (2016) [1962]. "II. Теоремы осуществимости и комбинаторные приложения §2.12 Матрицы, состоящие из нулей и единиц". Потоки в сетях . Princeton University Press . стр. 79–91. doi :10.1515/9781400875184-004. ISBN 9781400875184. МР  0159700.

Внешние ссылки

• «Логическая матрица», Энциклопедия математики , EMS Press , 2001 [1994]