Chapter ObjeCtives
After studying this chapter, you will be able to:
• Identify ordered pairs related by a binary relation.
• Test a binary relation for the reflexive, symmetric, transitive, and antisymmetric properties.
• Find the reflexive, symmetric, and transitive closures of a binary relation.
• Recognize partial orderings and construct Hasse diagrams for them.
• Recognize an equivalence relation on a set and describe how it partitions the
set into equivalence classes.
• Draw a PERT chart from a task table.
• Find the minimum time-to-completion and a critical path in a PERT chart.
• Extend a partial ordering on a finite set to a total ordering by doing a topological sort.
• Understand the entity-relationship model and the relational model for an
enterprise.
• Perform restrict, project, and join operations in a relational database.
• Create relational database queries in the languages of relational algebra, SQL,
and relational calculus.
• Determine whether a binary relation is a function.
• Test a function for the onto and one-to-one properties.
• Create composite functions.
• Decide whether a function has an inverse function and what the inverse
function is.
• Manipulate cycle notation for permutation functions.
• Compute the number of functions, onto functions, and one-to-one functions
from one finite set to another.
• Understand order of magnitude as a relative measure of function rate of growth.
• Build a hash table using a modulo hash function.
• Encode and decode messages using RSA public key encryption.
• Use the mod function to compute check digits for various identification codes.
• Perform matrix arithmetic on matrices of appropriate dimensions.
• Solve systems of linear equations using Gaussian elimination.
• Perform Boolean arithmetic operations on Boolean matrices of appropriate
dimensions.
5 5
Relations, Functions,
and Matrices
C h a p t e r
327
After studying this chapter, you will be able to:
• Identify ordered pairs related by a binary relation.
• Test a binary relation for the reflexive, symmetric, transitive, and antisymmetric properties.
• Find the reflexive, symmetric, and transitive closures of a binary relation.
• Recognize partial orderings and construct Hasse diagrams for them.
• Recognize an equivalence relation on a set and describe how it partitions the
set into equivalence classes.
• Draw a PERT chart from a task table.
• Find the minimum time-to-completion and a critical path in a PERT chart.
• Extend a partial ordering on a finite set to a total ordering by doing a topological sort.
• Understand the entity-relationship model and the relational model for an
enterprise.
• Perform restrict, project, and join operations in a relational database.
• Create relational database queries in the languages of relational algebra, SQL,
and relational calculus.
• Determine whether a binary relation is a function.
• Test a function for the onto and one-to-one properties.
• Create composite functions.
• Decide whether a function has an inverse function and what the inverse
function is.
• Manipulate cycle notation for permutation functions.
• Compute the number of functions, onto functions, and one-to-one functions
from one finite set to another.
• Understand order of magnitude as a relative measure of function rate of growth.
• Build a hash table using a modulo hash function.
• Encode and decode messages using RSA public key encryption.
• Use the mod function to compute check digits for various identification codes.
• Perform matrix arithmetic on matrices of appropriate dimensions.
• Solve systems of linear equations using Gaussian elimination.
• Perform Boolean arithmetic operations on Boolean matrices of appropriate
dimensions.
5 5
Relations, Functions,
and Matrices
C h a p t e r
327