Proving ~Au~B= ~(AnB): A Comprehensive Explanation with Examples

[jlemus85]

Hi everyone,

Was hoping I could get some help with the following:

Note= ~ indicates the complement of
Prove that:

~Au~B= ~(AnB)
So far I have: Let x belong to ~Au~b then x belongs to ~A or x belongs to ~B.
If x belongs to ~A then x is not in A thus x is not in ~AnB so x belongs to ~(AnB).
If x belongs to ~B then x is not in B thus x is not in ~AnB so x belongs to ~(AnB)

I am having trouble going the other way because if x belongs to ~(AnB) then x is not in AnB, but does this mean it's not in AuB? When I picture AnB I see two circles that overlap each other (not completely), and that small part where they over lap, that is AnB. But if x is not in AnB, how can we say with certainty that it isn't in the Complement of AuB? Is it because the complement of AuB IS the intersection of A, B? Hope that makes sense!

 

[Tac-Tics]

All the steps are essentially reversible. The hard part is that you are effectively "lifting" De Morgan's Law from the logical domain to a set domain. The critical step, in effect, looks almost dubious because it's so obvious.

Let x be in ~(AnB). Thus, x is in not in AnB. (definition of complement)

If x is in A and x is in B, then x is in AnB. (definition of intersection)

If x is not in AnB, then it is not true that x is in A and x is in B. (contrapositive)

It is not true that x is in A and x is in B. (Inference)

Either x is not in A or x is not in B. (Logical de morgan's law, this is the critical step)

Either x is in ~A or x is in ~B. (Def. of complement).

x is in ~Au~B. (Def of union)