Results 1 to 12 of 12

Math Help - discrete math.proof.set theory.

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    5

    discrete math.proof.set theory.

    Theorem: A\(BUC)=(A\B)intersection(A\C)
    How to proof ?Any ideas would be useful.


    Thanks,
    Sasha
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by sasha1111 View Post
    Theorem: A\(BUC)=(A\B)intersection(A\C)
    How to proof ?Any ideas would be useful.


    Thanks,
    Sasha
    Don't you dare look until you've tried it yourself. Ok?

    Spoiler:

    A-\left(B\cup C\right)=A\cap\left(B\cup C\right)'=A\cap\left(B'\cap C'\right)=A\cap A\cap B'\cap C'= \left(A\cap B'\right)\cap\left(A\cap C'\right)=\left(A-B\right)\cap\left(A-B\right)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2010
    Posts
    5
    A\(BUC) = (A\B) ∩ (A\C)

    PROOF:
    x are A\(BUC) => (x arenít (A)) and (x are (BUC)) => (x arenít (AUA)) and (x are (BUC)) => (x arenít (A)) or (x are (B∩C)) => ((x arenít A) or (x are B)) and ((x arenít A) or (x are C)) => (x are (A\B)) and (x are (A\C)) => x are ((A\B) ∩ (A\C))
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by sasha1111 View Post
    A\(BUC) = (A\B) ∩ (A\C)

    PROOF:
    x are A\(BUC) => (x aren’t (A)) and (x are (BUC)) => (x aren’t (AUA)) and (x are (BUC)) => (x aren’t (A)) or (x are (B∩C)) => ((x aren’t A) or (x are B)) and ((x aren’t A) or (x are C)) => (x are (A\B)) and (x are (A\C)) => x are ((A\B) ∩ (A\C))
    It's not a proof per se. but drawing a diagram will let you see what is going on better:



    (diagram is "borrowed" from wikipedia.)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by sasha1111 View Post
    A\(BUC) = (A\B) ∩ (A\C)

    PROOF:
    x are A\(BUC) => (x arenít (A)) and (x are (BUC)) => (x arenít (AUA)) and (x are (BUC)) => (x arenít (A)) or (x are (B∩C)) => ((x arenít A) or (x are B)) and ((x arenít A) or (x are C)) => (x are (A\B)) and (x are (A\C)) => x are ((A\B) ∩ (A\C))
    Quote Originally Posted by Swlabr View Post
    It's not a proof per se. but drawing a diagram will let you see what is going on better:



    (diagram is "borrowed" from wikipedia.)
    Really, the God-honest simple way is to do what I showed you in the first post. Use the algebra of sets.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Drexel28 View Post
    Really, the God-honest simple way is to do what I showed you in the first post. Use the algebra of sets.
    I hate to disagree, but I do!

    What you did required some sort of knowledge of what was actually going on, or at least someone telling you some rules. The other two ways don't.

    I've never been able to derive proofs just using what I know about sets...I prefer to either look at an element or draw a diagram.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Swlabr View Post
    I hate to disagree, but I do!

    What you did required some sort of knowledge of what was actually going on, or at least someone telling you some rules. The other two ways don't.

    I've never been able to derive proofs just using what I know about sets...I prefer to either look at an element or draw a diagram.
    I wasn't directing that comment at you by the way. My point was, using the algebra of sets is just as fundamental, and even more intuitive, than showing the inclusion/reverse-inclusion method. I quoted your picture so that although each step I made was valid, she can verify logically with your picture!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by sasha1111 View Post
    A\(BUC) = (A\B) ∩ (A\C)

    PROOF:
    x are A\(BUC) => (x arenít (A)) and (x are (BUC)) => (x arenít (AUA)) and (x are (BUC)) => (x arenít (A)) or (x are (B∩C)) => ((x arenít A) or (x are B)) and ((x arenít A) or (x are C)) => (x are (A\B)) and (x are (A\C)) => x are ((A\B) ∩ (A\C))
    sasha,

    Your method is called proof of implication. Drexel did it by set algebra, and Swlabr is by Venn Diagram. I use all of them, but I think if you can do it by set algebra, you can also do logic. The set algebra can make you very smart with logic.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Doing it by implication is just long-winded.

    Let
    x\in A-\left(B\cup C\right)

    \Longleftrightarrow x\in A\text{ and }x\notin \left(B\cup C\right)

    \Longleftrightarrow x\in A\text{ and }\left(x\notin B\text{ and }x\notin C\right)

    \Longleftrightarrow \left(x\in A\text{ and }x\in A\right)\text{ and }\left(x\in B'\text{ and }x\in C'\right)

    \Longleftrightarrow \left(x\in A\text{ and }x\in B'\right)\text{ and }\left(x\in A\text{ and }x\in C'\right)

    \Longleftrightarrow \left(x\in A\text{ and }x\notin B\right)\text{ and }\left(x\in A\text{ and }x\notin C\right)

    \Longleftrightarrow x\in\left(A-B\right)\text{ and }x\in\left(A-C\right)

    \Longleftrightarrow x\in\left(\left(A-B\right)\cap\left(A-C\right)\right)


    I accidentally made some redundant steps. But, you get the picture.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jan 2010
    Posts
    5
    Thank you.Smooth way!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Drexel28 View Post
    Doing it by implication is just long-winded.

    Let
    x\in A-\left(B\cup C\right)

    \Longleftrightarrow x\in A\text{ and }x\notin \left(B\cup C\right)

    \Longleftrightarrow x\in A\text{ and }\left(x\notin B\text{ and }x\notin C\right)

    \Longleftrightarrow \left(x\in A\text{ and }x\in A\right)\text{ and }\left(x\in B'\text{ and }x\in C'\right)

    \Longleftrightarrow \left(x\in A\text{ and }x\in B'\right)\text{ and }\left(x\in A\text{ and }x\in C'\right)

    \Longleftrightarrow \left(x\in A\text{ and }x\notin B\right)\text{ and }\left(x\in A\text{ and }x\notin C\right)

    \Longleftrightarrow x\in\left(A-B\right)\text{ and }x\in\left(A-C\right)

    \Longleftrightarrow x\in\left(\left(A-B\right)\cap\left(A-C\right)\right)


    I accidentally made some redundant steps. But, you get the picture.
    Drexel,

    I am so glad you showed the above. The method is called prove by definition. I may say we have all the methods laid out for our friend, sasha.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Jan 2010
    Posts
    5
    Well done Drexel.Looking forward for cooperation.


    Greetings from Lithuania
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. discrete math probability theory
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 25th 2010, 02:14 PM
  2. discrete math: graph theory
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 27th 2009, 06:02 AM
  3. discrete math proof
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 5th 2008, 11:56 AM
  4. I need some help with a discrete math proof
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: September 28th 2008, 07:49 AM
  5. Discrete math (proof by contradiction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 26th 2007, 10:47 AM

Search Tags


/mathhelpforum @mathhelpforum