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})$.

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

Bibliografia

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

Linki zewnętrzne

• Logical matrix. Michiel Hazewinkel (red.). w: Encyclopaedia of Mathematics Kluwer Academic Publishers, 2001. ISBN 978-1556080104. (ang.).brak strony w książce
• Macierz logiczna w WolframAlpha