Results 1 to 5 of 5

Math Help - Prove or Disprove

  1. #1
    Newbie
    Joined
    Sep 2008
    Posts
    20

    Prove or Disprove

    Hey everyone

    I'm having a little trouble on this homework trying to prove or disprove this problem.

    Let A, B, and C be sets. Prove or disprove that A − (B C) = (A − B) U (A − C).
    Hint: difference of two sets, De Morganís law, distributive law for intersection over union.

    The teacher said the first step to this is:

    Step 1: A − (B C) = A B C

    But I don't see where he got the A n B n C from anywhere, or where to go after wards, any suggestions?


    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,714
    Thanks
    1642
    Awards
    1
    \begin{array}{rcl}   {A\backslash \left( {B \cap C} \right)} &  =  & {A \cap \left( {B \cap C} \right)^c }  \\<br />
   {} &  =  & {A \cap \left( {B^c  \cup C^c } \right)}  \\<br />
   {} &  =  & {\left( {A \cap B^c } \right) \cup \left( {A \cap C^c } \right)}  \\<br />
   {} &  =  & {\left( {A\backslash B} \right) \cup \left( {A\backslash C} \right)}  \\\end{array}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2008
    Posts
    20
    What are the C's? is that the not symbol? And what are the recommended laws used for each of these steps, i can name a few but I don't know much.

    Thanks again
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,714
    Thanks
    1642
    Awards
    1
    These A^c  = \overline A  = A' are all common notations for the complement of A.
    Set difference, A - B = A\backslash B = A \cap B^c , is defined in terms of complements.
    Now your instructor surely said the first step is: A - \left( {B \cap C} \right) = A \cap \left( {B \cap C} \right)^c .
    You follow the names of the rules as they appear in your textbook; unfortunately these are not standard by any means.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Aug 2008
    Posts
    42
    Quote Originally Posted by BlakeRobertsonMD View Post
    What are the C's? is that the not symbol? And what are the recommended laws used for each of these steps, i can name a few but I don't know much.

    Thanks again
    Only if you do a step by step proof you will be able to know exactly the laws of logic involved in the proof.

    So let us 1st prove that A-(B \capC) is a subset of
    ...............(A-B)U(A-C) in a step by step way.

    1) xε[A-(B \capC)].................................................. ..............assumption

    2)xε[A-(B \capC)] <-------> xεA ^~ xε(Β \capC)........................by the definition of subtraction of sets

    3) xε[A-(B \capC)] -------> xεA ^~ xε(Β \capC)........................from 2 and by the definition of bi conditional and addition elimination

    NOTE that the definition of bi conditional , p<---->q , is that: p<----->q is (p----->q) ^ (q------>p) and then using the law in logic called addition elimination,where from P^Q ====> P OR Q WE conclude that from p<---->q we can infer p---->q or q----->.p

    4) xεA ^~ xε(Β \capC)................................................ .....................from 1 and 3 and using M.Ponens

    5) xεA............................................... ..................from 4 and using addition elimination

    6) ~xε(Β \capC)................................................ ...from 4 and using addition elimination

    7) ~xε(Β \capC) <-------> ~[ xεΒ ^ xεC]................................from the definition of intersection of sets

    8)~xε(Β \capC) -------> ~[ xεΒ ^ xεC].................................................. from 7 and using the definition of bi conditional and addition elimination

    9) ~[ xεΒ ^ xεC].................................................. ....from 6 and 8 and using M.Ponens

    10) ~xεB v ~xεB.............................................. ............from 9 and using De Morgan law

    11) xεA ^(~xεB v ~xεC)............................................. .......from 5 and 10 and using addition introduction

    12) xεA ^(~xεB v ~xεC) <-------> (xεA ^ ~xεB)v(xεA ^ ~xεC)..............................from 11 and using distributive law

    13) xεA ^(~xεB v ~xεC) -------> (xεA ^ ~xεB)v(xεA ^ ~xεC)....................................from 12 and using the definition of biconditional and addition elimination

    14) (xεA ^ ~xεB)v(xεA ^ ~xεC)............................................. ....from 11 and 13 and using M.Ponens

    15) (xεA ^ ~xεB)v(xεA ^ ~xεC)<------->xε( A-B) v xε( Α-C).............................from the definition of subtraction of sets

    16) (xεA ^ ~xεB)v(xεA ^ ~xεC)------->xε( A-B) v xε( Α-C)..........................................from 15 and using the definition of biconditionals and addition elimination

    17) xε( A-B) v xε( Α-C)................................................ .....from 14 and 16 and using M.Ponens

    18) xε( A-B) v xε( Α-C) <------> xε[(Α-Β)U(A-C)].................................from the definition of the union of sets

    19)) xε( A-B) v xε( Α-C) ------> xε[(Α-Β)U(A-C)]....................................from 18 and using the definition of biconditionals and addition elimination

    20) xε[(Α-Β)U(A-C).......................................from 17 and 19 and using M.Ponens.

    21) xε[A-(B \capC) --------> xε[(A-B)U(A-C)]........................................from 1 to 20 and using the conditional rule

    ..........................HENCE we have proved that A-(B \capC) is a subset of (A-B)U(A-C)................................

    For the converse we do it in a similar way

    In the above proof one can easily single out the laws of logic involved
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove or Disprove the Following:
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 8th 2010, 05:35 AM
  2. Prove or Disprove
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: February 20th 2010, 10:53 AM
  3. Set Prove or Disprove
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 1st 2009, 02:08 AM
  4. prove or disprove
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 25th 2008, 07:41 AM
  5. Prove or disprove help
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 27th 2008, 08:06 PM

Search Tags


/mathhelpforum @mathhelpforum