Page 203 - Discrete Mathematics and Its Applications

182 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

Solution: We find that the join of A and B is

1 ∨ 0 0 ∨ 1 1 ∨ 0 1 1 1
A ∨ B = = .
0 ∨ 1 1 ∨ 1 0 ∨ 0 1 1 0

The meet of A and B is

1 ∧ 0 0 ∧ 1 1 ∧ 0 0 0 0
A ∧ B = = .
0 ∧ 1 1 ∧ 1 0 ∧ 0 0 1 0 ▲
We now define the Boolean product of two matrices.

DEFINITION 9 Let A =[a ij ] be an m × k zero–one matrix and B =[b ij ] be a k × n zero–one matrix. Then
the Boolean product of A and B, denoted by A B,isthe m × n matrix with (i, j)th entry
c ij where
c ij = (a i1 ∧ b 1j ) ∨ (a i2 ∧ b 2j ) ∨ ··· ∨ (a ik ∧ b kj ).

Note that the Boolean product of A and B is obtained in an analogous way to the ordinary
product of these matrices, but with addition replaced with the operation ∨ and with multiplication
replaced with the operation ∧. We give an example of the Boolean products of matrices.

EXAMPLE 8 Find the Boolean product of A and B, where

⎡ ⎤
1 0
1 1 0
⎣ 0
A = 1 ⎦ , B = 0 1 1 .
1 0

Solution: The Boolean product A B is given by

⎡ ⎤
(1 ∧ 1) ∨ (0 ∧ 0) (1 ∧ 1) ∨ (0 ∧ 1) (1 ∧ 0) ∨ (0 ∧ 1)
A B = ⎣ (0 ∧ 1) ∨ (1 ∧ 0) (0 ∧ 1) ∨ (1 ∧ 1) (0 ∧ 0) ∨ (1 ∧ 1) ⎦
(1 ∧ 1) ∨ (0 ∧ 0) (1 ∧ 1) ∨ (0 ∧ 1) (1 ∧ 0) ∨ (0 ∧ 1)
⎡ ⎤
1 ∨ 0 1 ∨ 0 0 ∨ 0
= ⎣ 0 ∨ 0 0 ∨ 1 0 ∨ 1 ⎦
1 ∨ 0 1 ∨ 0 0 ∨ 0
⎡ ⎤
1 1 0
= ⎣ 0 1 1 ⎦ .
1 1 0 ▲

We can also define the Boolean powers of a square zero–one matrix. These powers will
be used in our subsequent studies of paths in graphs, which are used to model such things as
communications paths in computer networks.