Macierz logiczna: Różnice pomiędzy wersjami

Jeśli zbiór {0, 1} zostanie potraktowany jako [[półpierścień]], gdzie [[Funkcja addytywna (algebra)|działanie addytywne]] jest interpretowane jako [[alternatywa]], a [[Funkcja multiplikatywna|działanie multiplikatywne]] jako [[Koniunkcja (logika)|koniunkcja]], to macierzowa reprezentacja [[Złożenie relacji|złożenia]] dwóch relacji jest równa wynikowi [[Mnożenie macierzy|mnożenia]] macierzy logicznych odpowiadających tym relacjom. Wynik tego mnożenia może być obliczony w czasie <math>O(n^2)</math><ref>{{cytuj pismo |autor = Patrick E. O’Neil, Elizabeth J. O’Neil |tytuł = A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure |url = http://www.sciencedirect.com/science/article/pii/S0019995873902283/pdf?md5=37b2d0aafda0b0639e48370c73d5e82a&pid=1-s2.0-S0019995873902283-main.pdf |czasopismo=Information and Control |rok = 1973 |wolumin = 22 |wydanie = 2 |strony = 132–138 |doi = 10.1016/s0019-9958(73)90228-3}} – Algorytm korzysta z [[Idempotentność|idempotentności]] działania addytywnego, patrz s. 134 (dół).</ref>.