DOC PREVIEW
UMD CMSC 250 - Homework #16

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CMSC 250 Fall 2004 — Homework 16Due Never at the beginning of your discussion section.You must write the solutions to the problems single-sided on your own lined paper,with all sheets stapled together, and with all answers written in sequential order oryou will lose points.1. Let R1and R2be the relation on {0, 1, 2, 3} defined as follows. Draw the directed graphs forR1and R2and indicate which relations are antisymmetric.(a) R1= {(0, 1), (1, 2), (1, 3), (2, 3), (3, 1)}(b) R2= {(0, 0)(0, 1), (3, 2), (2, 1), (3, 0), (3, 3)}2. Let A = {a, b, c, d, e, f, g}. Let R be a binary relation on A with the following pairs related:aRb, dRe, eRf , gRe. Write the following sets using ordered pair notation.(a) R(b) The reflexive closure of R.(c) The symmetric closure of R.(d) The transitive closure of R.3. Redo number 3 representing each relation as a matrix.4. Redo number 3 representing each relation as a directed graph.5. Let R be a relation defined by1 0 0 0 1 00 1 1 0 0 11 1 1 0 0 11 0 1 1 1 00 0 0 0 1 10 1 1 1 0 0Write the matrices representing the reflexive and symmetric closures of R. Is R asymmetric?Is R antisymmetric? Is R reflexive? Is R irreflexive? Give reasons for your answers.6. Let A = {1, 2, 3, 4}. Let R be a binary relation defined on A defined by: a1Ra2if a1≤ a2.Write the the relation using ordered pair notation, and show that the relation is antisymmetric.7. Using the subset inclusion partial order relation, give an example of two elements that arenot comparable.8. Define a relation R on the set of all integers as follows:∀x, y ∈ Z,xRy ↔ x + y is even.Is R a partial order relation? Prove or give counterexample.19. Let A = {1, 2, 3, 4, 5, 6}. Let R be the partial order relation defined by inclusion of subsets ofA. Write a chain C of maximal length contained in R.10. Let R be a partial order relation on A = {a, b, c, d, e, f} given by:R = {(a, a), (b, b), (c, c), (d, d), (e, e), (f, f),(a, b), (a, c), (a, d), (a, e), (a, f ), (b, c), (b, d),(b, e), (b, f ), (d, f), (e, f )}Draw the Hasse diagram for R.11. In the following, the relation R is an equivalent relation on the set A. Find the distinctequivalence classes of R.(a) X = {−1, 0, 1} and A = P (X). R is defined on P (X) as follows: For all sets s and t inP (X),s R t ⇔ the sum of the elements in s equals the sum of the elements in t(b) A is the set of all strings of length 2 in 0’s, 1’s, and 2’s. R is defined on A as follows:For all strings s and t in A,s R t ⇔ the sum of the characters in s equals the sum of the characters in t12. Let P be the set of all points in the Cartesian plane except the origin. R is the relation definedas follows: For all p1and p2in P ,p1R p2⇔ p1and p2lie on the same half-line emanating from the origin.Proof that the relation is and equivalence relation, and describe the distinct equivalenceclasses.13. Let R be a binary relation on a set A and suppose R is symmetric and transitive. Prove thefollowing: If for every x in A there is a y in A such that x R y, then R is an equivalencerelation.14. For each of the following either prove that it is a partial order relation or indicate why it isnot a partial order relation.(a) Define a relation R on the set Z of all integers as follows: For all m, n ∈ Z,m R n ⇔ every prime factor of m is a prime factor of n(b) Define a relation R on the set R of all real numbers as follows: For all x, y ∈ R,x R y ⇔ x2≤ y215. Let A = {a, b, c, d}, and let R be the relationR = {(a, a), (b, b), (c, c), (d, d), (c, b), (a, d), (b, a), (b, d), (c, d), (c, a)}Is R a total order on A? justify your


View Full Document

UMD CMSC 250 - Homework #16

Download Homework #16
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Homework #16 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework #16 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?