Page 206 - Discrete Mathematics and Its Applications

Key Terms and Results 185

24. a) Show that the system of simultaneous linear equations 28. Find the Boolean product of A and B, where

⎡ ⎤
⎡ ⎤ 10
a 11 x 1 + a 12 x 2 + ··· + a 1n x n = b 1 1 0 0 1
⎢0
⎦ .
A = ⎣ 0 1 0 and 1⎥
a 21 x 1 + a 22 x 2 + ··· + a 2n x n = b 2 1 ⎦ B = ⎣ 1 1
. 1 1 1 1
. 10
.
a n1 x 1 + a n2 x 2 + ··· + a nn x n = b n .
29. Let
in the variables x 1 ,x 2 ,...,x n can be expressed as ⎡ 10 0 ⎤
AX = B, where A =[a ij ], X is an n × 1 matrix with A = ⎣ 10 1 ⎦ .
x i the entry in its ith row, and B is an n × 1 matrix 0 1 0
with b i the entry in its ith row.
b) Show that if the matrix A =[a ij ] is invertible (as Find
defined in the preamble to Exercise 18), then the so- [2] [3]
lution of the system in part (a) can be found using the a) A . [2] [3] b) A .
equation X = A −1 B. c) A ∨ A ∨ A .
30. Let A be a zero–one matrix. Show that
25. Use Exercises 18 and 24 to solve the system
a) A ∨ A = A. b) A ∧ A = A.
31. In this exercise we show that the meet and join opera-
7x 1 − 8x 2 + 5x 3 = 5
tions are commutative. Let A and B be m × n zero–one
−4x 1 + 5x 2 − 3x 3 =−3 matrices. Show that
a) A ∨ B = B ∨ A. b) B ∧ A = A ∧ B.
x 1 − x 2 + x 3 = 0
32. In this exercise we show that the meet and join opera-
tions are associative. Let A, B, and C be m × n zero–one
26. Let
matrices. Show that
a) (A ∨ B) ∨ C = A ∨ (B ∨ C).
11 0 1
A = and B = . b) (A ∧ B) ∧ C = A ∧ (B ∧ C).
0 1 10
33. We will establish distributive laws of the meet over the
join operation in this exercise. Let A, B, and C be m × n
Find
zero–one matrices. Show that
a) A ∨ B. b) A ∧ B. c) A B.
a) A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C).
27. Let
b) A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C).
34. Let A be an n × n zero–one matrix. Let I be the n × n
⎡ ⎤ ⎡ ⎤
10 1 0 1 1
identity matrix. Show that A I = I A = A.
A = ⎣ 1 1 0 ⎦ and B = ⎣ 10 1 ⎦ .
35. In this exercise we will show that the Boolean prod-
0 0 1 10 1
uct of zero–one matrices is associative. Assume that A
is an m × p zero–one matrix, B is a p × k zero–one
Find
matrix, and C is a k × n zero–one matrix. Show that
a) A ∨ B. b) A ∧ B. c) A B. A (B C) = (A B) C.
Key Terms and Results
TERMS S ⊆ T (S is a subset of T): every element of S is also an
set: a collection of distinct objects element of T
axiom: a basic assumption of a theory S ⊂ T (S is a proper subset of T): S is a subset of T and
paradox: a logical inconsistency S = T
element, member of a set: an object in a set finite set: a set with n elements, where n is a nonnegative
roster method: a method that describes a set by listing its integer
elements
infinite set: a set that is not finite
set builder notation: the notation that describes a set by stating
a property an element must have to be a member |S| (the cardinality of S): the number of elements in S
∅ (empty set, null set): the set with no members P(S) (the power set of S): the set of all subsets of S
universal set: the set containing all objects under considera- A ∪ B (the union of A and B): the set containing those ele-
tion ments that are in at least one of A and B
Venn diagram: a graphical representation of a set or sets A ∩ B (the intersection of A and B): the set containing those
S = T (set equality): S and T have the same elements elements that are in both A and B.