 8.8.1: a) What is a relation on a set? b) How many relations are there on ...
 8.8.2: a) What is a reflexive relation? b) What is a symmetric relation? c...
 8.8.3: Give an example of a relation on the set { I , 2, 3, 4} that is a) ...
 8.8.4: a) How many reflexive relations are there on a set with n elements?...
 8.8.5: a) Explain how an nary relation can be used to represent informati...
 8.8.6: a) Explain how to use a zeroone matrix to represent a relation on ...
 8.8.7: a) Explain how to use a directed graph to represent a relation on a...
 8.8.8: a) Define the reflexive closure and the symmetric closure of a rela...
 8.8.9: a) Define the transitive closure of a relation. b) Can the transiti...
 8.8.10: a) Define an equivalence relation. b) Which relations on the set {a...
 8.8.11: a) Show that congruence modulo m is an equivalence relation wheneve...
 8.8.12: a) What are the equivalence classes of an equivalence relation? b) ...
 8.8.13: Explain the relationship between equivalence relations on a set and...
 8.8.14: a) Define a partial ordering. b) Show that the divisibility relatio...
 8.8.15: Explain how partial orderings on the sets Al and A2 can be used to ...
 8.8.16: a) Explain how to construct the Hasse diagram of a partial order on...
 8.8.17: a) Define a maximal element of a poset and the greatest element of ...
 8.8.18: a) Define a lattice. b) Give an example of a poset with five elemen...
 8.8.19: a) Show that every finite subset of a lattice has a greatest lower ...
 8.8.20: a) Define a wellordered set. b) Describe an algorithm for producin...
 8.8.1: Let S be the set of all strings of English letters. Determine wheth...
 8.8.2: Construct a relation on the set {a, b, c, d} that is a) reflexive, ...
 8.8.3: Show that the relation R on Z x Z defined by (a , b) R (c, d) if an...
 8.8.4: Show that a subset of an anti symmetric relation is also anti symme...
 8.8.5: Let R be a reflexive relation on a set A. Show that R R 2 .
 8.8.6: Suppose that R\ and R2 are reflexive relations on a set A. Show tha...
 8.8.7: Suppose that R\ and R2 are reflexive relations on a set A. Is R\ n ...
 8.8.8: Suppose that R is a symmetric relation on a set A. Is R also symmet...
 8.8.9: Let R\ and R2 be symmetric relations. Is R\ n R2 also symmetric? Is...
 8.8.10: A relation R is called circular if aRb and b R c imply that eRa. Sh...
 8.8.11: Show that a primary key in an nary relation is a primary key in an...
 8.8.12: Is the primary key in an nary relation also a primary key in a lar...
 8.8.13: Show that the reflexive closure of the symmetric closure of a relat...
 8.8.14: Let R be the relation on the set of all mathematicians that contain...
 8.8.15: a) Give an example to show that the transitive closure of the symme...
 8.8.16: a) Let S be the set of subroutines of a computer program. Define th...
 8.8.17: Suppose that R and S are relations on a set A with R S such that th...
 8.8.18: Show that the symmetric closure of the union of two relations is th...
 8.8.19: Devise an algorithm, based on the concept of interior vertices, tha...
 8.8.20: Which of these are equivalence relations on the set of all people? ...
 8.8.21: How many different equivalence relations with exactly three differe...
 8.8.22: Show that {(x, y) I x  Y E Q} is an equivalence relation on the se...
 8.8.23: Suppose that PI = {AI , A2, ... , Am } and P2 = {BI , B2, , Bn} are...
 8.8.24: Show that the transitive closure of the symmetric closure of the re...
 8.8.25: Let R( S) be the set of all relations on a set S. Define the relati...
 8.8.26: Let P( S) be the set of all partitions ofthe set S. Define the rela...
 8.8.27: Schedule the tasks needed to cook a Chinese meal by specifying thei...
 8.8.28: Find all chains in the po sets with the Hasse diagrams shown in Exe...
 8.8.29: Find all antichains in the po sets with the Hasse diagrams shown in...
 8.8.30: Find an anti chain with the greatest number of elements in the pose...
 8.8.31: Show that every maximal cha,in in a finite poset (S, ) contains a m...
 8.8.32: Show that every finite poset can be partitioned into k chains, wher...
 8.8.33: Show that in any group ofmn + 1 people there is either a list of m ...
 8.8.34: Show that no separate basis case is needed for the principle of wel...
 8.8.35: Show that the principle of wellfounded induction is valid. A relat...
 8.8.36: Let R be the relation on the set of all functions from Z+ to Z+ suc...
 8.8.37: Let R be a quasiordering on a set A. Show that R n R I is an equi...
 8.8.38: Let R be a quasiordering and let S be the relation on the set of e...
 8.8.39: Show that the following properties hold for all elements x, y, and ...
 8.8.40: Show that if x and y are elements of a lattice L, then x v y = y if...
 8.8.41: Show that if L is a bounded lattice with upper bound I and lower bo...
 8.8.42: Show that every finite lattice is bounded.
 8.8.43: Give an example of a lattice that is not distributive.
 8.8.44: Show that the lattice (P(S), ) where P(S) is the power set of a fin...
 8.8.45: Is the lattice (Z+ , I) distributive?
 8.8.46: Give an example of a finite lattice where at least one element has ...
 8.8.47: Show that the lattice (P(S), ) where P(S) is the power set of a fin...
 8.8.48: Show that if L is a finite distributive lattice, then an element of...
 8.8.49: Show that the game of Chomp with cookies arranged in an m x n recta...
 8.8.50: Show that if (S, ) has a greatest element b, then a winning strateg...
 8.8.1: Given the matrix representing a relation on a finite set, determine...
 8.8.2: Given the matrix representing a relation on a finite set, determine...
 8.8.3: Given the matrix representing a relation on a finite set, determine...
 8.8.4: Given a positive integer n, display all the relations on a set with...
 8.8.5: Given a positive integer n , determine the number of transitive rel...
 8.8.6: Given a positive integer n, determine the number of equivalence rel...
 8.8.7: Given a positive integer n, display all the equivalence relations o...
 8.8.8: Given an nary relation, find the projection of this relation when ...
 8.8.9: Given an m ary relation and an nary relation, and a set of common...
 8.8.10: Given the matrix representing a relation on a finite set, find the ...
 8.8.11: Given the matrix representing a relation on a finite set, find the ...
 8.8.12: Given the matrix representing a relation on a finite set, find the ...
 8.8.13: Given the matrix representing a relation on a finite set, find the ...
 8.8.14: Given the matrix representing a relation on a finite set, find the ...
 8.8.15: Given a partial ordering on a finite set, find a total ordering com...
 8.8.1: Display all the different relations on a set with four elements.
 8.8.2: Display all the different reflexive and symmetric relations on a se...
 8.8.3: Display all the reflexive and transitive relations on a set with fi...
 8.8.4: Determine how many transitive relations there are on a set with n e...
 8.8.5: Find the transitive closure of a relation of your choice on a set w...
 8.8.6: Compute the number of different equivalence relations on a set with...
 8.8.7: Display all the equivalence relations on a set with seven elements.
 8.8.8: Display all the partial orders on a set with five elements.
 8.8.9: Display all the lattices on a set with five elements.
 8.8.10: Discuss the concept of a fuzzy relation. How are fuzzy relations used?
 8.8.11: Describe the basic principles of relational databases, going beyond...
 8.8.12: Look up the original papers by Warshall and by Roy (in French) in w...
 8.8.13: Describe how equivalence classes can be used to define the rational...
 8.8.14: Explain how Helmut Hasse used what we now call Hasse diagrams
 8.8.15: Describe some of the mechanisms used to enforce information flow po...
 8.8.16: Discuss the use of the Program Evaluation and Review Technique (PER...
 8.8.17: Discuss the use ofthe Critical Path Method (CPM) to find the shorte...
 8.8.18: Discuss the concept of duality in a lattice. Explain how duality ca...
 8.8.19: Explain what is meant by a modular lattice. Describe some of the pr...
Solutions for Chapter 8: Relations
Full solutions for Discrete Mathematics and Its Applications  6th Edition
ISBN: 9780073229720
Solutions for Chapter 8: Relations
Get Full SolutionsThis expansive textbook survival guide covers the following chapters and their solutions. Chapter 8: Relations includes 104 full stepbystep solutions. Since 104 problems in chapter 8: Relations have been answered, more than 39999 students have viewed full stepbystep solutions from this chapter. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073229720. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 6.

Adjacency matrix of a graph.
Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected). Adjacency matrix of a graph. Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected).

Cofactor Cij.
Remove row i and column j; multiply the determinant by (I)i + j •

Complete solution x = x p + Xn to Ax = b.
(Particular x p) + (x n in nullspace).

Distributive Law
A(B + C) = AB + AC. Add then multiply, or mUltiply then add.

Free columns of A.
Columns without pivots; these are combinations of earlier columns.

GramSchmidt orthogonalization A = QR.
Independent columns in A, orthonormal columns in Q. Each column q j of Q is a combination of the first j columns of A (and conversely, so R is upper triangular). Convention: diag(R) > o.

Incidence matrix of a directed graph.
The m by n edgenode incidence matrix has a row for each edge (node i to node j), with entries 1 and 1 in columns i and j .

Left nullspace N (AT).
Nullspace of AT = "left nullspace" of A because y T A = OT.

Linear combination cv + d w or L C jV j.
Vector addition and scalar multiplication.

Lucas numbers
Ln = 2,J, 3, 4, ... satisfy Ln = L n l +Ln 2 = A1 +A~, with AI, A2 = (1 ± /5)/2 from the Fibonacci matrix U~]' Compare Lo = 2 with Fo = O.

Nilpotent matrix N.
Some power of N is the zero matrix, N k = o. The only eigenvalue is A = 0 (repeated n times). Examples: triangular matrices with zero diagonal.

Permutation matrix P.
There are n! orders of 1, ... , n. The n! P 's have the rows of I in those orders. P A puts the rows of A in the same order. P is even or odd (det P = 1 or 1) based on the number of row exchanges to reach I.

Pivot.
The diagonal entry (first nonzero) at the time when a row is used in elimination.

Polar decomposition A = Q H.
Orthogonal Q times positive (semi)definite H.

Skewsymmetric matrix K.
The transpose is K, since Kij = Kji. Eigenvalues are pure imaginary, eigenvectors are orthogonal, eKt is an orthogonal matrix.

Special solutions to As = O.
One free variable is Si = 1, other free variables = o.

Spectrum of A = the set of eigenvalues {A I, ... , An}.
Spectral radius = max of IAi I.

Triangle inequality II u + v II < II u II + II v II.
For matrix norms II A + B II < II A II + II B II·

Volume of box.
The rows (or the columns) of A generate a box with volume I det(A) I.

Wavelets Wjk(t).
Stretch and shift the time axis to create Wjk(t) = woo(2j t  k).