458
Relations, Functions, and Matrices
Boolean Matrices
In Chapter 6 we will be interested in matrices with only 0s and 1s as entries,
called boolean matrices (after George Boole, a nineteenth-century English mathematician; Boole also lent his name to Boolean algebra, which we will consider
later in this book). Matrix r of Example 62 is a Boolean matrix. We can define
an o peration of Boolean matrix multiplication a × b on Boolean matrices using
Boolean multiplication and Boolean addition instead of regular multiplication and
addition. These are defined as follows:
Boolean multiplication: x ` y = min(x, y)
Boolean addition: x ~ y = max(x, y)
PRaCtiCe 56 Fill-in the following operation tables for Boolean multiplication and Boolean addition.
x
y
x ` y
1
1
1
0
0
1
0
0
x
y
x ~ y
1
1
1
0
0
1
0
0
■
example 75
Let a and b be Boolean matrices,
a = £
1 1 0
0 1 0
0 0 1
§ b = £
1 0 0
1 1 1
0 0 1
§
Now take the tables from Practice 56 and substitute T for 1 and F for 0. They
become the truth tables for conjunction and disjunction, respectively; for this reason, these operations are often called boolean and (or logical and) and boolean
or (or logical or), which also explains the notation used for these operations. The
operation of Boolean matrix multiplication a × b (on Boolean matrices of appropriate dimensions) is then defined by
c ij = ~
m
k=1
(a ik ` b kj )
We can also define two analogues of ordinary matrix addition (on Boolean
matrices of the same dimensions): A ` B, where corresponding elements are
combined using Boolean multiplication, and A ~ B, where corresponding elements are combined using Boolean addition.