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

Логическая матрица , бинарная матрица , матрица отношений , булева матрица или (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{когда}}\quad \forall i,j\quad A_{ij}=1\подразумевает 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 ,м}$${\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 Р.}$${\displaystyle RR^{\operatorname {T} }}$${\displaystyle RR^{\operatorname {T} }}$

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

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

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

На Викискладе есть медиафайлы по теме Двоичная матрица .

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