Matrices over $\{0,1\}$ equipped with AND and OR

Question

Consider $S = \{0, 1\}$ equipped with the binary operations AND (represented by multiplication) and OR (represented by addition). Is there a name for this algebraic structure? Given that AND and OR are used frequently in computer science, I assume this object has already been studied extensively. However, I couldn't find anything online about it.

Particularly I am wondering if any work has been done regarding matrices over this structure, where matrix multiplication is carried out in the usual manner, but with scalar multiplication replaced by AND and scalar addition replaced by OR.

Thanks!

Answer 1

The structure is called Boolean algebra, and is defined as a bounded distributive lattice with complements. In particular, it is a semiring, and the matrix multiplication can be defined as for every semiring.

In some contexts where matrix multiplication is important the structure $(\{0,1\}, \vee, \wedge)$ is actually often called the Boolean semiring, for example, in the classical book on algebraic automata theory "Semirings, Automata, Languages" by W.Kuich and A.Salomaa. You can read this book to learn about some application of semiring matrix multiplication and Boolean matrix multiplication in theoretical CS.

But the term "Boolean semiring" is also used to mean any semiring with idempotent multiplication, in this terminology the Boolean ring $(\{0,1\}, +, \cdot)$ is also a Boolean semiring.

Answer 2

This is the simplest example of a Boolean Ring. Another simple example would be $S^n$ with addition and multiplication done component-wise. The key property is that all elements are idempotent.

You can work with matrices over rings using a module which is a generalization of vector spaces to rings that aren't fields. One application of Boolean matrices are Hamming Codes which are useful in communications to detect and correct errors in signals. So there is a lot of theory here since applications are abundant.