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{array}{cc}1& (x_i,y_j)\in R\\ 0& (x_i,y_j)\in ̸R\end{array}$

Przykład

Niech $R$ będzie relacją dwuargumentową określoną na zbiorze $A=\{1,2,3,4,5\}.$ Niech $a,b\in A,aRb\iff 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:

$\left[\begin{array}{ccccc}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{array}\right].$

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

• Szablon:Cytuj książkę, rozdział 31.3, Binary Matrices
• Szablon:Cytuj książkę

Linki zewnętrzne

• Szablon:Springer
• Macierz logiczna w WolframAlpha