210  HW SUPPLEMENT   2006 Apr 3  MATH 210 :   DISCRETE MATH    Dr. Luft

Lesson 4     §1.3

Y1-4     Learn to prove all four theorems (a), (b), (c), (d) in the composed functions study document.

Lesson 5/5a     §1.4

Y1     Draw a digraph for this relation R on A={a,b,c,d} and tell whether it is reflexive, symmetric, antisymmetric, transitive.
R = { (a,a), (a,b), (a,c), (a,d), (b,b), (b,c), (b,d), (c,d) }     ANS:  AT

Lesson 5a / 6     §1.4-5

Y1     Draw a digraph for this relation R on A={a,b,c,d,e} and tell whether it is reflexive, symmetric, antisymmetric, transitive.
R = { (a,a), (a,b), (b,a), (b,b), (c,c), (c,d), (d,c), (d,d), (e,e) }   .   Is R an equivalence relation?  If so, give the equivalence classes.     ANS:  RST,  {a,b}, {c,d}, {e}

Y2     Explain why  1000 and  95 are or are not congruent  mod 6.   ANS:  1000-95=905  is not a multiple of 6.

Y3     Find the remainder of 50  mod 13.     ANS:  11

Lesson 7     §1.6

Y1     Draw a digraph for this relation R on A={a,b,c,d,e} and tell whether it is reflexive, symmetric, antisymmetric, transitive.
R = { (a,a), (a,b), (a,c), (a,d), (a,e), (b,b), (b,c), (b,d), (c,c), (c,d), (d,d), (e,d), (e,e) }   .   Is R a partial order?  If so, draw the Hasse diagram.          ANS:  RAT

Lesson 9     §2.1

Y1     Use mathematical induction to prove that the sum of the first n even integers is n(n+1) :
          2 + 4 + 6 + 8 + ... + (2n)   =   n(n+1)
(You may be able to prove this without induction, but this is a lesson on induction.)

Y2     Use mathematical induction to prove this sum :
          1 + 5 + 9 + ... + (4n-3)   =   n(2n-1)

Lesson 13/13a     §3.1

Y1     How many ways can we arrange five people A, B, C, D, E  around a (circular) table?            ANS:   24

Lesson 14     §3.1

Y1     How many ways can five people A, B, C, D, E  line up?                                           ANS:   120
Y2     How many ways can five people A, B, C, D, E  line up so that A, B are next to each other?             ANS:   24
Y3     How many ways can five people A, B, C, D, E  line up so that A, B are not next to each other?       ANS:  96

Lesson 15     §3.2

Y1     A club has 8 sophomores, 10 juniors, and 12 seniors.  How many ways can we choose a committee of 2 sophomores, 3 juniors, and 4 seniors?   ANS:  1,663,200

Y2     A university president wants to choose a search committee of faculty to find a new provost.  The numbers of eligible faculty are 24 in liberal arts, 12 in science, and 18 in education.  The president wants the committee to consist of 4 from liberal arts, 2 from science, and 3 from education.  How many ways are there to choose the committee?   ANS 577,270,000

Lesson 21a     §4.5

Consider the graphs A, K5, B, K3,3 in the slides for Lesson 21.  For each graph, answer the following questions.
(a)  Can we use the edge-vertex inequality to prove the graph does not have a planar representation?
(b)  If not, try to redraw the graph in planar form.


Review and Extra Credit

Z1-4     Prove one of the theorems (a), (b), (c), (d) in the composed functions study document at the blackboard without notes.

Presenters of the following problems must provide enough copies for all class members. 

Z5     Prove that congruence (mod m) is an equivalence relation.

Z6     Draw a digraph for this relation R on A={a,b,c,d,e,f,g} and tell whether it is reflexive, symmetric, antisymmetric, transitive.   R = { (a,a), (a,b), (b,a), (b,b), (c,c), (c,d), (c,e), (d,c), (d,d), (d,e), (e,c), (e,d), (e,e), (f,f), (f,g), (g,f), (g,g) } .   If R is an equivalence relation, describe the equivalence classes.     If R is a partial order, draw the Hasse diagram.    

Z7     Draw a digraph for this relation R on A={a,b,c,d,e} and tell whether it is reflexive, symmetric, antisymmetric, transitive.   R = { (a,a), (a,b), (a,c), (a,d), (a,e), (b,b), (b,c), (b,d), (b,e), (c,c), (c,e), (d,d), (d,e), (e,e) }   .   If R is an equivalence relation, describe the equivalence classes.     If R is a partial order, draw the Hasse diagram.   

Z8     Use mathematical induction to prove that for every n > 2  :
          1/(1)(2)  +  1/(2)(3)  +  ...  +   1/(n-1)n    =    1  -  1/n
 
Z9     Use mathematical induction to prove that for every n > 10  :
          2^n > n^3

Z10     How many ways can we arrange six people A, B, C, D, E, F  around a table?                                   ANS:   120

Z11     How many ways can six people A, B, C, D, E, F  line up so that A, B are next to each other?             ANS:  240
Z12     How many ways can six people A, B, C, D, E, F  line up so that A, B are not next to each other?       ANS:  480

Z13    A club has 9 sophomores, 11 juniors, and 13 seniors.  How many ways can we choose a committee of 3 sophomores, 4 juniors, and 5 seniors?   ANS:  35,675,640

Z14    ?Decide whether a graph has an Euler cycle.

Z15    ?Draw a graph, given its adjacency matrix or its cost matrix.

Z16    ?Spanning Trees and Minimal Spanning Trees.

Z17    ?Pre-, In-, Post-order Searches

Z18    ?Construct the minimal spanning tree for a graph and find its (total) cost.

Z19    Prove Euler's theorem by induction, at the board, without notes.  (We will help you.)

Z20    Apply Euler's theorem to a planar connected graph.

Z21    Answer the following questions regarding the graph P in the slides for Lesson 21:

(a)  Can we use the edge-vertex inequality to prove the graph does not have a planar representation?
(b)  If not, try to redraw the graph in planar form.

Z22   Use a truth table to prove a law of Propositional Calculus from Theorem 5.1.1 :
         (a)  Statement  7     (b)  Statement  8     (c)  Statement  11

          FINAL EXAM REVIEW

Z23    Use a truth table to prove statements in propositional calculus.

Z24    Simplify an expression in the propositional calculus.

Z25    Simplify an expression in Boolean Algebra.

Z26    (Be able to apply De Morgan's laws in set algebra, propositional calculus, and Boolean algebra.)

Z27    Prove (or disprove) that a specific function is (or is not) one-to-one or onto.

Z28    Boolean Algebra:  simplify an expression; find a minterm expansion.