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?
These are all common notations for the complement of A.
Set difference, , is defined in terms of complements.
Now your instructor surely said the first step is: .
You follow the names of the rules as they appear in your textbook; unfortunately these are not standard by any means.
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 C) is a subset of
...............(A-B)U(A-C) in a step by step way.
1) xε[A-(B C)].................................................. ..............assumption
2)xε[A-(B C)] <-------> xεA ^~ xε(Β C)........................by the definition of subtraction of sets
3) xε[A-(B C)] -------> xεA ^~ xε(Β 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ε(Β C)................................................ .....................from 1 and 3 and using M.Ponens
5) xεA............................................... ..................from 4 and using addition elimination
6) ~xε(Β C)................................................ ...from 4 and using addition elimination
7) ~xε(Β C) <-------> ~[ xεΒ ^ xεC]................................from the definition of intersection of sets
8)~xε(Β 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 C) --------> xε[(A-B)U(A-C)]........................................from 1 to 20 and using the conditional rule
..........................HENCE we have proved that A-(B 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