# Math Help - Prove or Disprove

1. ## 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?

2. $\begin{array}{rcl} {A\backslash \left( {B \cap C} \right)} & = & {A \cap \left( {B \cap C} \right)^c } \\
{} & = & {A \cap \left( {B^c \cup C^c } \right)} \\
{} & = & {\left( {A \cap B^c } \right) \cup \left( {A \cap C^c } \right)} \\
{} & = & {\left( {A\backslash B} \right) \cup \left( {A\backslash C} \right)} \\\end{array}$

3. 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

4. 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.

5. Originally Posted by BlakeRobertsonMD
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 $\cap$C) is a subset of
...............(A-B)U(A-C) in a step by step way.

1) xε[A-(B $\cap$C)].................................................. ..............assumption

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

3) xε[A-(B $\cap$C)] -------> xεA ^~ xε(Β $\cap$C)........................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ε(Β $\cap$C)................................................ .....................from 1 and 3 and using M.Ponens

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

6) ~xε(Β $\cap$C)................................................ ...from 4 and using addition elimination

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

8)~xε(Β $\cap$C) -------> ~[ 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 $\cap$C) --------> xε[(A-B)U(A-C)]........................................from 1 to 20 and using the conditional rule

..........................HENCE we have proved that A-(B $\cap$C) 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