Discrete Math is Killing Me!

[I Love Math]

We're currently working on basic set theory and I'm having a little trouble working with subtraction when proving things. My instructor has given us a bunch of problems and since he's not going from a book I'm having trouble coming up with what is appropriate to use while proving things.

I've got to prove statements like these:

For any sets A, B, and C, prove:

1. C-(AUB) = (C-A) intersection (C-B)
2. (A-B)U(B-A) = (AUB) - (A intersection B)
3. B - (B - A) = A intersection B

Can you distribute minus signs as if I'm using De Morgan's Law? Or (on the first one) should I say X is an element of C and X is not an element of AUB and do something from there?

I'm so overwhelmed by this class and nearly everyone has dropped it since the instructor is not very helpful. He's made it clear that we can't use Venn Diagrams for proving sets. He has shown us several examples of proofs in class, but each one is different and he's also made it clear that he can't teach us how to do proofs since there isn't a "cookbook recipe" to follow. I'm pulling my hair out over this class!

We also have to prove that the Euclidean Algorithm terminates in at most half the first remainder. He didn't go out of the book on this one and the books I've looked through use Mod which we haven't used. His exact statement on the worksheet he gave us is this [(sub) means subscript]:

Show R(sub)(i+2)<(1/2)R(sub)i

He started us out with this:

R(sub)(i-1) = Q(sub)(i+1)R(sub)i + R(sub)(i+1)

I don't know what to do!

 

[pka]

Here are two of them.
\(\displaystyle \begin{array}{l}
C\backslash (A \cup B) & = & C \cap \left( {\overline {A \cup B} } \right) \\
& = & C \cap \left( {\overline A \cap \overline B } \right) \\
& = & \left( {C \cap \overline A } \right) \cap \left( {C \cap \overline B } \right) \\
& = & \left( {C\backslash A} \right) \cap (C\backslash B) \\
\end{array}\)

\(\displaystyle \begin{array}{l}
B\backslash (B\backslash A) & = & B\backslash \left( {B \cap \overline A } \right) \\
& = & B \cap \overline {\left( {B \cap \overline A } \right)} \\
& = & B \cap \left( {\overline B \cup A} \right) \\
& = & \left( {B \cap \overline B } \right) \cup \left( {B \cap A} \right) \\
& = & \left( {B \cap A} \right) \\
\end{array}\)

 

[I Love Math]

Thanks! That makes sense.

 

[soroban]

Hello, I Love Math!

pka did #1 and #3 for you . . .

Definition: \(\displaystyle \,A\,-\,B\:=\:A\,\cap\,\overline{B}\;\;\) . . . A intersection B-complement

Theorem #1: \(\displaystyle \,\text{For any set }A,\;A\,\cap\,\overline{A}\:=\:\Phi\)

Theorem #2: \(\displaystyle \,\text{For any set }A,\;A\,\cup\,\Phi\:=\:A\)

\(\displaystyle 2)\;\;(A\,-\,B)\,\cup\,(B\,-\,A)\;=\;(A\,\cup\,B)\,-\,(A\,\cap\,B)\)

The right side is: \(\displaystyle \,(A\,\cup\,B)\,-\,(A\,\cap\,B)\;=\;(A\,\cup\,B)\,\cap\,(\overline{A\,\cap\,B})\;\;\) Definition

\(\displaystyle \;\;\;=\;(A\,\cup\,B)\,\cap\,(\overline A\,\cup\,\overline B)\;\;\) DeMorgan

\(\displaystyle \;\;\;=\;[(A\,\cup\,B)\,\cap\,\overline A]\,\cup\,\,[(A\,\cup\,B)\,\cap\,\overline B]\;\;\) Distributive

\(\displaystyle \;\;\;=\;\left[(A\,\cap\,\overline A)\,\cup\,(B\,\cap\,\overline A\right]\,\cup\,\left[(A\,\cap\,\overline B)\,\cup\,(B\,\cap\,\overline B)\right]\;\;\) Distributive

\(\displaystyle \;\;\;=\;\left[\Phi\,\cup\,(B\,\cap\,\overline A)\right]\,\cup\,\left[(A\,\cap\,\overline B)\,\cup\,\Phi\right]\;\;\) Theorem #1

\(\displaystyle \;\;\;=\;(B\,\cap\,\overline A)\,\cup\,(A\,\cap\,\overline B)\;\;\) Theorem #2

\(\displaystyle \;\;\;=\;(B\,-\,A)\,\cup\,(A\,-\,B)\;\;\) Definition

\(\displaystyle \;\;\;=\;(A\,-\,B)\,\cup\,(B\,-\,A)\;\;\) Commutative

 

[I Love Math]

Thanks so much, guys! I really appreciate it.