Macierz logiczna

Macierz logiczna – macierz, której elementy należą do dwuelementowego zbioru {0, 1}. Wartości 1 i 0 interpretuje się kolejno jako wartości logiczne prawda i fałsz. Taka macierz może być wykorzystywana do reprezentacji relacji dwuargumentowej pomiędzy parą skończonych zbiorów.

Macierzowa reprezentacja relacji

Niech $R$ będzie relacją dwuargumentową pomiędzy skończonymi zbiorami indeksowanymi $X$ i $Y$ (więc $R\subseteq X\times Y$ ), wówczas $R$ może być reprezentowane przez macierz sąsiedztwa $M.$ Przyjmijmy, że $i$ to liczba całkowita z zakresu od 1 do moc zbioru $X,$ a $j$ jest liczbą całkowitą z zakresu od 1 do mocy zbioru $Y.$ Niech $x_{i}\in X\wedge y_{j}\in Y.$ Odpowiednie elementy macierzy $M$ są zdefiniowane jako:

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

Przykład

Niech $R$ będzie relacją dwuargumentową określoną na zbiorze $A=\{1,2,3,4,5\}.$ Niech $a,b\in A,aRb\Leftrightarrow a=b-1\vee a=b+2.$ Można z tego wywnioskować, że:

R=\{(1,2),(2,3),(3,1),(3,4),(4,5),(4,2),(5,3)\}.

Odpowiadający zapis w postaci macierzy logicznej:

{\begin{bmatrix}0&1&0&0&0\\0&0&1&0&0\\1&0&0&1&0\\0&1&0&0&1\\0&0&1&0&0\end{bmatrix}}.

Inne przykłady

Macierz sąsiedztwa reprezentująca graf prosty, gdzie kolumny i wiersze reprezentują wierzchołki, a elementy macierzy o wartości 1 reprezentują krawędzie.
Macierz permutacji (forma zapisu permutacji).
Zbiór $m$ liczb B-gładkich takich, że żaden czynnik pierwszy nie jest więcej niż jednokrotny, może być reprezentowany jako macierz logiczna wymiaru $m\times \pi (B),$ gdzie $\pi$ to funkcja określająca ilość liczb pierwszych mniejszych od $B.$ Element $a_{ij}$ macierzy równa się 1 wtedy i tylko wtedy gdy, $j$ -ta liczba pierwsza dzieli $i$ -tą liczbę. Taka reprezentacja może być użyteczna w sicie kwadratowym.
Reprezentacja bitmapy zawierającej dwa kolory.
Użycie macierzy logicznych do zaimplementowania zasad gry Go [1].

Niektóre własności

Reprezentacja macierzowa relacji równości na zbiorze skończonym jest macierzą identycznościową.

Jeśli zbiór {0, 1} zostanie potraktowany jako półpierścień, gdzie działanie addytywne jest interpretowane jako alternatywa, a działanie multiplikatywne jako koniunkcja, to macierzowa reprezentacja złożenia dwóch relacji jest równa wynikowi mnożenia macierzy logicznych odpowiadających tym relacjom. Wynik tego mnożenia może być obliczony w czasie $O(n^{2})$ ^[1].

Liczba różnych macierzy logicznych wymiaru $m\times n$ jest równa $2^{mn}$ z czego wynika, że jest skończona.

Zobacz też

spis macierzy

Przypisy

↑ Patrick E. O’Neil, Elizabeth J. O’Neil. A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure. „Information and Control”. 22 (2), s. 132–138, 1973. DOI: 10.1016/s0019-9958(73)90228-3. – Algorytm korzysta z idempotentności działania addytywnego, patrz s. 134 (dół).

Bibliografia

Leslie Hogben: Handbook of Linear Algebra (Discrete Mathematics and Its Applications). Boca Raton: Chapman & Hall/CRC, 2006. ISBN 978-1-58488-510-8., rozdział 31.3, Binary Matrices
Ki Hang Kim: Boolean Matrix Theory and Applications. ISBN 0-8247-1788-0.

Linki zewnętrzne

Logical matrix. Michiel Hazewinkel (red.). w: Encyclopaedia of Mathematics Kluwer Academic Publishers, 2001. ISBN 978-1556080104. (ang.).
Macierz logiczna w WolframAlpha

[1] Patrick E. O’Neil, Elizabeth J. O’Neil. A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure. „Information and Control”. 22 (2), s. 132–138, 1973. DOI: 10.1016/s0019-9958(73)90228-3. – Algorytm korzysta z idempotentności działania addytywnego, patrz s. 134 (dół).

[1]