also has that property.
Posted: September 15, 1996 Due: September 22, 1996 at 5:00
This assignment is worth a total of 50 points.
This homework is subject to the CS5034 General Rules for Homework
Submission (see the web site).
Be sure to include your name(s) and ID number(s) with your submission.
Homework submissions must be sent by email to
cs5034@ei.cs.vt.edu.
Your email message should contain ONLY the Postscript file for your
homework submission - preferably as an attachment- and should have
a suitable subject line such as ``HW 3 SUBMISSION.''
The email account will automatically reply when a message is received.
Answers to questions should be correct, clear and concise. Solutions will be marked down if they contain extraneous material; gaps, inconsistencies or illogical connections in proofs or explanations; or incorrect results. Be sure to explain all answers. Good, clear English is required. NOTE: The answer to each question is limited to one page. All parts to multi-part questions must fit within the one page limit.
This assignment contains five questions.
Where an exercise number is referenced, the question is from Hein.
1. Exercise 4.1.18b
2. For each of the properties
{reflexive, symmetric, transitive}, prove that if relation R
has the property, then relation also has that property.
3. Exercise 4.2.6
4. Exercise 4.3.10
5. Recall that the powerset on a set of A of n elements
has 
sets as elements.
Consider the poset < Power(A), 
(see Figure 4.12 for an example).
For this poset, how many ways can its
elements be placed in a topological sort?