1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Discrete Mathematics : Proof : Question 1

  1. Jul 28, 2012 #1
    1. The problem statement, all variables and given/known data

    Question 1 :

    a) Use Venn diagrams to determine whether or not, for all subnets A,B and C of a universal set U, (A-B) ∪ C = (A∪C) - (A∩B)
    b) If the statement appears to hold, give a proof, if not, give a counter example.


    2. Relevant equations


    (A-B) ∪ C = (A∪C) - (A∩B)

    *there are no other variables given
    *no other values are known
    *this question relates to the proof


    3. The attempt at a solution

    a) I have drawn the Venn diagrams, which does not reflect that they equate to each other, so they are not equal.
    b) The counter example is the one I am struggling with, so i will explain how i did it, and basically just adapted an answer from my text book :

    Attempt to prove with counter example :
    ------------------------------------------------------------

    Let : A = {1;2}
    Let : B = {2;3}
    Let : C = {1;4}

    Left hand : (A-B) ∪ C :

    (A-B) = = {1;2} - {2;3} = {1;3}
    (A-B) ∪ C = {1;3} ∪ C = {1;3} ∪ {1;4} = {1;3;4}

    (A-B) ∪ C = {1;3;4}

    Now to find out what the right hand side is :

    (A∪C) - (A∩B) :

    (A∪C) = {1;2}∪{1;4} = {1;2;4}
    (A∩B) = {1;2}∩{2;3} = {2}
    (A∪C) - (A∩B) = {1;4}



    Thus :

    (A-B) ∪ C ≠ (A∪C) - (A∩B)


    -----------------------------------------------------------------------------

    Please let me know if this is right, or where i can improve, this is something new to me, and i still need to work on this alot.
     
  2. jcsd
  3. Jul 28, 2012 #2
    Your steps are not correct. A - B is the difference, so
    A - B = {1,2} - {2,3} = {1}. You are removing elements in AnB from A.

    So, what you have is not a counter example. Try again :)
     
  4. Jul 28, 2012 #3
    Your steps are not correct. A - B is the difference, so
    A - B = {1,2} - {2,3} = {1}. You are removing elements in AnB from A.

    So, what you have is not a counter example. Try again :)
     
  5. Jul 28, 2012 #4
    Thanks,

    =;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;
    Left hand : (A-B) ∪ C :

    (A-B) = = {1;2} - {2;3} = {1;3}
    (A-B) ∪ C = {1;3} ∪ C = {1;3} ∪ {1;4} = {1;3;4}

    (A-B) ∪ C = {1;3;4}
    =;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;

    should be :

    =;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;=;

    Left hand : (A-B) ∪ C :

    (A-B) = = {1;2} - {2;3} = {1}
    (A-B) ∪ C = {1} ∪ C = {1} ∪ {1;4} = {1;4}

    (A-B) ∪ C = {1;4}

    ........

    So that means that they are in fact the same.... (i did not see that from my Venn diagram).

    I will quickly draw the venn diagrams again, is there a way i can show you the venn diagrams on this forum ?
     
  6. Jul 28, 2012 #5
    Ok, i have managed to upload a Venn diagram on these 2.

    Please let me know why my venn diagram does not reflect the calculation..
     

    Attached Files:

  7. Jul 28, 2012 #6

    ehild

    User Avatar
    Homework Helper
    Gold Member

    Ingenious! Your Venn diagrams are correct. If you find 3 sets which obey the original statement it can be still false. Find a counter-example. What about the sets in the attachment?

    ehild
     

    Attached Files:

  8. Jul 28, 2012 #7
    Yes - if A n B n C is not empty, the proposition is false.
     
  9. Jul 28, 2012 #8
    hi Ehild,

    Thank you for the feedback, yes i can see the difference, only if a place a value in every field :)

    The example i used had 'empty fields' - which does not point out the difference.

    So in the process of answering this one (Correct me if i am wrong) :

    1. Draw the venn diagrams
    2. Put a value in every section (piece) of the venn diagram
    3. Then do the calculations - due to the fields of the venn diagram , when writing out the proof it will be clear that the two are not the same

    Just writing out my proof, if you can confirm, i will really appreciate it :


    A = {1;2;6;7}
    B = {2;3;5;7}
    C = {4;5;6;7}

    (A-B) ∪ C = {1;2;6;7} - {2;3;5;7} ∪ C
    = {1;6} ∪ C
    = {1;6} ∪ {4;5;6;7}
    = {1;4;5;6;7}

    Right Hand : ∪ ∩

    (A∪C) - (A∩ B)
    (A∪C) : {1;2;6;7) ∪ {4;5;6;7} = {1;2;4;5;6;7}
    (A∩B) : {1;2;6;7} ∩ {2;3;5;7} = {2;7}
    (A∪C) - (A∩ B) = {1;4;5;6}

    and Thus :

    (A-B) ∪ C ≠ (A∪C) - (A∩B)
     
  10. Jul 28, 2012 #9
    Nice, that works. A simpler example might have been:
    A = B = C = {1}.

    :)
     
  11. Jul 28, 2012 #10
    Who, Ehild,

    thanks alot for your assistance, appreciated!!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook