Results 1 to 10 of 10

Math Help - Couple of Discrete Math problems

  1. #1
    Newbie
    Joined
    Dec 2008
    Posts
    8

    Couple of Discrete Math problems

    1. Prove: is a solution to the recurrence relation for when and

    2. Show that if A and B are sets then

    3. Let be a symetric and transitive relation on a set A. Assume for every there exists a with . Prove that R is an equivalence relation.

    4. Let G be a graph with vertices and let be distinct vertices on G. Prove that if there is a walk from to , then it has length less than or equal to

    Would really appreciate some help with these. Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by DemonEyesBob View Post
    1. Prove: is a solution to the recurrence relation for when and
    can't help you here, sorry

    2. Show that if A and B are sets then
    show that [/COLOR] A - B \subseteq A \cap B^c and A \cap B^c \subseteq A - B and you will have the desired result

    do so by showing that if x \in (A - B), then x \in (A \cap B^c) and if x \in (A \cap B^c), then x \in (A - B)

    3. Let be a symetric and transitive relation on a set A. Assume for every there exists a with . Prove that R is an equivalence relation.
    it remains only to show that R is reflexive.

    so let
    a \in A, then there is b \in A so that aRb. but R is symmetric, so that means we have bRa, so ...
    4. Let G be a graph with vertices and let be distinct vertices on G. Prove that if there is a walk from to , then it has length less than or equal to
    can't help you here either, sorry
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2008
    Posts
    8
    show that [/color][/color] A - B \subseteq A \cap B^c and A \cap B^c \subseteq A - B and you will have the desired result

    do so by showing that if x \in (A - B), then x \in (A \cap B^c) and if x \in (A \cap B^c), then x \in (A - B)

    Thanks for your help on these two. Still a little confused though.

    Where did the 'c' come from in B^c?
    Last edited by DemonEyesBob; December 13th 2008 at 02:41 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by DemonEyesBob View Post
    Thanks for your help on these two. Still a little confused though.

    Where did the 'c' come from in B^c?
    it is just alternate notation for that bar you had. it just means B-compliment
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Dec 2008
    From
    Indiana
    Posts
    127
    Quote Originally Posted by DemonEyesBob View Post
    Thanks for your help on these two. Still a little confused though.

    Where did the 'c' come from in B^c?
    The 'c' means its complement. That is, B^c means the complement of B.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2008
    Posts
    19
    For your question 2, i suggest drawing venn diagrams.

    at least that way you can visually see the relation.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Dec 2008
    Posts
    8
    Quote Originally Posted by Storm20 View Post
    For your question 2, i suggest drawing venn diagrams.

    at least that way you can visually see the relation.
    show that and and you will have the desired result

    do so by showing that if , then and if , then



    First: just in case I misinterpreted it - I'm using \ni as 'not in'.

    I'm actually (lol) having a bit of trouble with this than I expected (big surprise). Even without a venn diagram I can see that they are the same, and if you just look at their definitions they're the same (ie. A-B = { x | x \in A \wedge x \ni B}
    which is the same as A\cap B^c since \cap is just ANOTHER bleeping way of saying AND). Sorry about the crassness, I've just been staring at these problems for a while now and I've realized that discrete and theory have simply killed my love of math.

    OK. Back to the problem. I understood what Jhevon was saying, but I don't know how to 'show' something is a subset of something else. I'm simply stuck (my prof. has not been very helpful). I'm also still stuck on the equivalence relation... I'm just not sure how to 'prove' this.

    edit: If anyone has any advice on the other two I'd still like to hear it please!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by DemonEyesBob View Post



    First: just in case I misinterpreted it - I'm using \ni as 'not in'.

    I'm actually (lol) having a bit of trouble with this than I expected (big surprise). Even without a venn diagram I can see that they are the same, and if you just look at their definitions they're the same (ie. A-B = { x | x \in A \wedge x \ni B}
    which is the same as A\cap B^c since \cap is just ANOTHER bleeping way of saying AND). Sorry about the crassness, I've just been staring at these problems for a while now and I've realized that discrete and theory have simply killed my love of math.

    OK. Back to the problem. I understood what Jhevon was saying, but I don't know how to 'show' something is a subset of something else.
    i told you how to prove it. and in fact, you were off you a good start by stating the definition of the set difference. just write out what it means and observe that the meaning is the same for the other definition.

    I'm simply stuck (my prof. has not been very helpful). I'm also still stuck on the equivalence relation... I'm just not sure how to 'prove' this.
    i started you off, using one of the properties given. use the last one to finish it off.

    do you know what "reflexive", "symmetric" and "transitive" mean?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Dec 2008
    Posts
    8
    Quote Originally Posted by Jhevon View Post
    i told you how to prove it. and in fact, you were off you a good start by stating the definition of the set difference. just write out what it means and observe that the meaning is the same for the other definition.
    Do you think this is a sufficient way of proving it? It was giving me issues because the examples for proving set identities were usually more complicated then A-B=A \cap B^c (such as proving De Morgan's Laws), and all the "by definition of"'s were applying to both A and B in the equation (if that makes sense). I think my teacher wants me to use 'set builder' notation, so that's what I've used here o.o

    A-B=A \cap B^c
    = {x| x \in A \wedge x \ni B } -> by definition of Difference
    = {x| x \in A \wedge x \in B^c } -> by definition of Compliment
    = {x| x \in A \cap B^c } -> by definition of Intersection
    = A \cap B^c -> by meaning of set builder notation
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Dec 2008
    Posts
    8
    edit: sorry for the dp, accident >_>

    Think I solved the relation one. Still really need help on recurrence relation please!!!!
    Last edited by DemonEyesBob; December 15th 2008 at 02:23 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Discrete Math problems
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 5th 2010, 10:05 PM
  2. Couple math problems
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 22nd 2009, 12:20 PM
  3. couple math 95 problems
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 21st 2009, 10:44 AM
  4. another discrete math problems
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 22nd 2007, 03:03 PM
  5. couple problems math help
    Posted in the Algebra Forum
    Replies: 2
    Last Post: December 5th 2006, 11:48 PM

Search Tags


/mathhelpforum @mathhelpforum