COMP 1805 Discrete Structures I Assignment 5 Date Due: April 10, 2013 Time Due: Before 2pm in the Boxes in Herzberg Room 3115 Write down your name and student number on every page. The questions should be answered in order and your assignment sheets must be stapled. Your assignment will not be graded if you do not follow these instructions. Unless otherwise stated, you must provide a proof or at the very least an explanation for each of your answers. Simply stating an answer is not sufficient. 1. Consider a relation R defined on the set A = f??7;??6;??5;??4;??3;??2;??1; 0; 1; 2; 3; 4; 5; 6; 7g. Determine for the following if the relations are reflexive, symmetric, anti-symmetric, transitive, partial orders, equivalence relations. (a) R = f(a; b)ja bg, if this is a partial order, draw the Hasse diagram. (b) R = f(a; b)ja3 = b3g, if this is a partial order, draw the Hasse diagram. (c) R = f(a; b)jab 0g, if this is a partial order, draw the Hasse diagram. (d) R = f(a; b)ja > b2g, if this is a partial order, draw the Hasse diagram. 2. Let A be the set of all bit strings of length 12. Let R be the relation define on A where two bit strings are related if the first 2 bits, the 4th bit and the 7th bit are the same. Show that R is an equivalence relation and enumerate one bit string from each of the different equivalence classes of R. 3. Consider the Hasse diagram in Figure 1. Answer the following questions on the partial order represented by the diagram. a b c d e f g h i j k l m n p ors tu Figure 1: Hasse Diagram (a) Find the maximal elements. (b) Find the minimal elements. 1
COMP 1805 ASSIGNMENT 5 2 (c) Is there a greatest element? (d) Is there a least element? (e) Find all upper bounds of fm; k; tg (f) Find all lower bounds of fc; d; tg (g) Find the greatest lower bound of fu; k;mg if it exists (h) Find the least upper bound of fb; fg if it exists. (i) Find the greatest lower bound of fp; kg if it exists 4. Consider the Hasse diagram in Figure 1. Use topological sort…