Sets Part2

From StpmWiki

Jump to: navigation, search

Contents

De Morgan's Law

a)\left( A \cup B\right)' = A' \cap B'

b)\left( A \cap B\right)' = A' \cup B' Bring complement from "outside" bracket "into" bracket. REMEMBER to CHANGE operation.

Using De Morgan's Law

Try these. Remember there is basically 3 things you need to do

  • complement the first set
  • complement the second set
  • change the operation between them
  • \left( A \cup B'\right)'= A' \cap B
  • \left( A' \cup B \right)'= A \cap B'
  • \left( A \cap B'\right)'= A' \cup B
  • \left( A' \cap B\right)'= A \cup B'
  • \left( A' \cup B'\right)'= A \cap B
  • \left( A' \cap B' \right)'= A \cup B


Order of brackets are very IMPORTANT. We can again use the "apple" and "orange" to help us. Lets see how we apply it to something like \left[A \cap \left(B \cup C \right) \right]'

First, take note of the "two" sets which will become our "apple" and "orange" \left[ {\color{Blue} A} \cap {\color{Red} \left(B \cup C \right)} \right]'. Apply De Morgan's Law to these "two" sets. {\color{Blue} A}' \cup {\color{Red} \left(B \cup C \right)}'. We can then apply De Morgan's Law again for the inside bracket.

Thus \left[A \cap \left(B \cup C \right) \right]'= A' \cup \left(B \cup C \right)'= A' \cup \left(B' \cap C' \right)

Try \left[A' \cup \left(B' \cap C \right) \right]' =A \cap \left(B \cup C' \right)

  • \left[A' \cup \left(B' \cap C \right) \right]' = A \cap \left(B' \cap C \right)' = A \cap \left(B \cup C' \right)


DO NOT

Do not try to mix this law with other laws. De Morgan's must be used to "get the complement into the bracket" FIRST, BEFORE applying any other laws.

Thus, A \cap \left( A \cap B\right)'=\left( A \cap A' \right) \cap B' is WRONG (trying to rearrange and rebracket before dealing with the complement outside)

How about \left( A \cap B\right)' \cup \left( A \cap B' \right)' = \left[A \cap \left(B \cup B' \right) \right]'? It is also WRONG (trying to factor before dealing with the complement outside)


Let's look at these examples :

A' \cup \left( B \cap A' \right)'

Question : Should we do rearranging or expanding?

Answer : NEITHER. We MUST deal with the complement outside the bracket first BEFORE we decide. Looking at the operations and common sets before dealing with the complement is futile.

Thus

A' \cup \left( B \cap A' \right)'

  • =A' \cup \left( B' \cup A \right) ... NOW only we analyze it and see that we just need to rearrange
  • =\left(A' \cup A \right) \cup B'
  • =\xi \cup B'
  • =\xi \,


How about this?\left( A \cap B \right) \cup \left( A \cap B \right)'

It should be =\left( A \cap B \right) \cup \left( A' \cup B' \right)

Which we can then do by associative first

Right? You Sure? Look carefully....

Technically, it is RIGHT. But look carefully at the question and you will see \heartsuit \cup \heartsuit', so those steps are actually NOT needed.

So if the question is instead \left( A \cap B \right) \cup \left( A' \cup B' \right),

We can actually do it like this

\left( A \cap B \right) \cup \left( A' \cup B' \right)

  • =\left( A \cap B \right) \cup \left( A \cap B \right)'
  • =\xi \,

Exercise 6

Simplify the following using set algebra

1)A \cap \left( A' \cup B \right)' =A \cap B'

    • \begin{align} A \cap \left( A' \cup B \right)' & = A \cap \left( A \cap B' \right) \\ & = \left( A \cap A \right) \cap B' \\ & = A \cap B' \end{align}

2)\left(B' \cap A \right)' \cup A = \xi \,

    • \begin{align} \left(B' \cap A \right)' \cup A & = \left(B \cup A' \right) \cup A \\ & = B \cup \left(A' \cup A \right) \\ & = B \cup \xi \\ & = \xi \end{align}

3)A \cup \left( A \cup B\right)' =A \cup B'

    • \begin{align} A \cup \left( A \cup B\right)' & = A \cup \left( A' \cap B'\right) \\ & = \left( A \cup A'\right) \cap \left( A \cup B'\right) \\ & = \xi \cap \left( A \cup B'\right) \\ & = A \cup B' \end{align}

4)\left(A' \cap B \right) \cap \left(A \cup B' \right) = \phi\,

    • \begin{align} \left(A' \cap B \right) \cap \left(A \cup B' \right) & = \left(A' \cap B \right) \cap \left(A' \cap B \right)' \\ & = \phi \end{align}
    • This can also be solved using associative and then distributive, but of course the above is MUCH simpler

5)\left(B \cup A \right)' \cup \left(B' \cap A \right) = B'\,

    • \begin{align} \left(B \cup A \right)' \cup \left(B' \cap A \right) & = \left(B' \cap A' \right) \cup \left(B' \cap A \right) \\ & = B'\cap \left(A' \cup A \right) \\ & = B'\cap \xi \\ & = B' \end{align}

6)\left(A \cap B \right) \cup \left(A' \cap B \right)' = A \cup B'

    • \begin{align} \left(A \cap B \right) \cup \left(A' \cap B \right)' & = \left(A \cap B \right) \cup \left(A \cup B' \right) \\ & = A \cup \left[ B' \cup \left( A \cap B \right) \right] \\ & = A \cup \left[ \left( B' \cup A \right) \cap \left( B' \cup B \right) \right] \\ & = A \cup \left[ \left( B' \cup A \right) \cap \xi \right] \\ & = A \cup \left( B' \cup A \right) \\ & = \left( A \cup A \right) \cup B' \\ & = A \cup B' \end{align}

7)A \cap \left[A \cup \left(B' \cap C \right) \right]' = \phi \,

    • \begin{align} A \cap \left[A \cup \left(B' \cap C \right) \right]' & = A \cap \left[A' \cap \left(B' \cap C \right)' \right] \\ & = \left( A \cap A' \right) \cap \left(B' \cap C \right)' \\ & = \phi \cap \left(B' \cap C \right)' \\ & = \phi \end{align}
    • It is not needed (but can be done) to apply De Morgan's on the second bracket law since we know it will simplify to null set in the end

8)\left[\left(A \cup B \right) \cap C \right]' \cup A = A \cup B' \cup C'

    • \begin{align} \left[\left(A \cup B \right) \cap C \right]' \cup A & = \left[\left(A \cup B \right)' \cup C' \right] \cup A \\ & = \left[\left(A' \cap B' \right) \cup C' \right] \cup A \\ & = C' \cup \left[ A \cup \left(A' \cap B' \right)\right] \\ & = C' \cup \left[ \left(A \cup A' \right) \cap \left(A \cup B' \right) \right] \\ & = C' \cup \left[ \xi \cap \left(A \cup B' \right) \right] \\ & = C' \cup \left(A \cup B' \right) \\ & = A \cup B' \cup C' \end{align}

Absorption Laws

a)A \cup \left( A \cap B\right) = A \,

b)A \cap \left( A \cup B\right) = A \, Common set absorb other set into itself. Note the common set, different operation

Identifying and using Absorption law

Absorption laws can't be proved from the other laws, thus it is VERY important to identify it.

Let's try to see what happen if we can't identify it

A \cup \left( A \cap B \right) ... lets try expand

  • = \left(A \cup A \right) \cap \left(A \cup B\right) ... simplify
  • = A \cap \left(A \cup B \right) ... hmmm... can't do anything but expand again
  • = \left(A \cap A \right) \cup \left(A \cap B\right) ... simplify
  • = A \cup \left( A \cap B \right) ... expand again? BUT look carefully and see that we have are just GOING IN CIRCLES

In fact, next time if you find yourself going in circles in other questions, it could be because you didn't notice the place where adsorption law must be used


So lets see how to identify it :

{\color{Blue} A} \cup \left( {\color{Blue} A} \cap B\right) & {\color{Blue} A} \cap \left( {\color{Blue} A} \cup B\right) Notice the common set. How about the operation?

{\color{Blue} A} {\color{Red} \cup} \left( {\color{Blue} A} {\color{Red} \cap} B\right) & {\color{Blue} A} {\color{Red} \cap} \left( {\color{Blue} A} {\color{Red} \cup} B\right) The operation is different.

And both will give us back {\color{Blue} A}, which is the common set.

Notice that the second set does not appear on the right hand side.

In other words, the common set absorb any other set into itself.

Thus

  • A \cup \left( A \cap B\right) {\color{Blue} A} {\color{Red} \cup} \left( {\color{Blue} A} {\color{Red} \cap} B\right) =A \,
  • A \cap \left( A \cup C\right) {\color{Blue} A} {\color{Red} \cap} \left( {\color{Blue} A} {\color{Red} \cup} C\right) =A \,
  • A \cup \left[ A \cap \left( B \cap C' \right) \right] {\color{Blue} A} {\color{Red} \cup} \left[ {\color{Blue} A} {\color{Red} \cap} \left( B \cap C' \right) \right] =A \,
  • A' \cap \left( A' \cup B\right) {\color{Blue} A'} {\color{Red} \cap} \left( {\color{Blue} A'} {\color{Red} \cup} B\right) =A' \,
  • \left( A \cup B\right)\cap B \left( A {\color{Red} \cup} {\color{Blue} B} \right){\color{Red} \cap}{\color{Blue} B} =B \,
  • \left( A \cup B\right) \cup \left[ \left( A \cup B\right) \cap C \right] {\color{Blue} \left( A \cup B\right)} {\color{Red} \cup} \left( {\color{Blue} \left( A \cup B\right)} {\color{Red} \cap} C \right) =\left( A \cup B\right)

Now, lets try something more complicated\left(A \cup B \right) \cup \left(A \cap B \right)

\left(A {\color{Red} \cup} B \right) {\color{Red} \cup} \left(A {\color{Red} \cap } B \right) Looking at the operations, we have to do associative first. Normally we will try to pair a set with its inverse, but there isn't any here, so we have no choice but to pair the one with the common set. In this, it can be either A\, or B\, to pair with \left( A \cap B \right)

\left(A \cup B \right) \cup \left(A \cap B \right)

  • = A \cup \left[ B \cup \left( A \cap B \right) \right] Look carefully to see we need to apply absorption law here. Expanding will be futile.
  • = A \cup B

Comparison

A \cap \left( A \cap B\right) Common set, same operation Rearrange (Associative)

A \cap \left( A' \cap B\right) No common set, same operation Rearrange (Associative)

A \cup \left( A' \cap B\right) No common set, different operation Expand (Distributive)

A \cup \left( A \cap B\right) Common set, different operation Absorb (Absorption)


\left(A \cup B\right) \cup \left( A' \cap B\right) \left({\color{Red}A} {\color{Blue}\cup} {\color{Red}B}\right) {\color{Blue}\cup} {\color{Red}\left( A' \cap B\right)} Pair A\, with \left( A' \cap B\right)

\left(A' \cup B\right) \cup \left( A' \cap B\right) \left({\color{Red}A'} {\color{Blue}\cup} {\color{Red}B}\right) {\color{Blue}\cup} {\color{Red}\left( A' \cap B\right)} Nothing can be paired that will simplify. Thus use absorption law

Note: Do note use adsorption law unless absolutely necessary as it might not be accepted in STPM marking scheme.

Exercise 7

Simplify the following using set algebra

1)\left( A \cup B \right) \cap B =B \,

2)A \cap \left( B' \cup A \right) =A \,

3)\left( B' \cup A' \right) \cap A' =A' \,

4)A' \cup \left( B \cap A' \right) =A' \,

5)\left( B \cup A' \right) \cap B =B \,

6)\left[A \cap \left(B \cup C' \right) \right] \cup A =A\,

7)\left(A \cap B \right) \cap \left[ \left( A \cap B \right) \cup C \right] =A \cap B

8)\left[ \left( A \cup B' \right) \cap \left( B \cup C \right) \right] \cup \left(A \cup B' \right) =A \cup B'

9)\left(A \cup B \right) \cap \left(A \cap B \right) =B \cap A

    • \begin{align} \left(A \cup B \right) \cap \left(A \cap B \right) & = B \cap \left[ A \cap \left(A \cup B \right)\right] \\ & = B \cap A \end{align}

10)\left(A \cap B' \right) \cap \left(A \cup B' \right) = A \cap B'

    • \begin{align} \left(A \cap B' \right) \cap \left(A \cup B' \right) & = A \cap \left[ B' \cap \left(A \cup B' \right)\right] \\ & = A \cap B' \end{align}

11)\left(A \cup B \right) \cup \left(B \cap C \right) =A \cup B

    • \begin{align} \left(A \cup B \right) \cup \left(B \cap C \right) & = A \cup \left[ B \cup \left(B \cap C \right)\right] \\ & = A \cup B \end{align}

12)\left(A' \cap B \right) \cup \left(A' \cup C \right) = C \cup A'

    • \begin{align} \left(A' \cap B \right) \cup \left(A' \cup C \right) & = C \cup \left[ A' \cup \left(A' \cap B \right)\right] \\ & = C \cup A' \end{align}

Difference of Sets

A - B \, = A \cap B'

This is NOT a law. It is an OPERATION. And the above formula is its DEFINITION. Always apply this BEFORE any law.

Remember the definition as

\heartsuit - \bigcirc= \heartsuit \cap \bigcirc'

Thus, we just write back the "apple" and then intercept with complement of the "orange"

So if we have something as complicated as

\left(A \cup B' \right)' - \left(A' \cup B \right)'

Simply draw an apple around everything before the − and orange everything after

{\color {Blue} \left(A \cup B' \right)'} - {\color {Red} \left(A' \cup B \right)'}

= {\color {Blue} \left(A \cup B' \right)'} \cap \left[ {\color {Red} \left(A' \cup B \right)'} \right]'

The complements at the end, of course, will cancel each other out.

Try these

  • B-A \, =B \cap A'
  • A-B' \, =A \cap B
  • A'-\left( B \cap C \right) =A' \cap \left( B \cap C \right)'
  • A-\left( B \cup C' \right)' =A \cap \left( B \cup C' \right)
  • \left( A \cup B \right)-\left( A \cap B \right) =\left( A \cup B \right)\cap \left( A \cap B \right)'
  • \left( A-B\right)-C =\left( A \cap B '\right) \cap C'
  • A-\left( B-C\right) =A \cap \left( B \cap C' \right)'
  • \left( A-B\right)-\left(B-A \right) = \left( A \cap B '\right) \cap \left( B \cap A' \right)'
    • You can do it in a few steps if needed, such as
    • \left( A-B\right)-\left(B-A \right)
    • =\left( A-B\right) \cap \left(B-A \right)'
    • =\left( A \cap B' \right) \cap \left(B \cap A' \right)'


Lets try simplifying\left( A'-B'\right)-\left(A-B' \right)

\left( A'-B'\right)-\left(A-B' \right)

  • =\left( A'-B'\right) \cap \left(A-B' \right)' ... be especially careful when there are already existing complements
  • =\left( A' \cap B \right) \cap \left(A \cap B \right)' ... apply De Morgan's
  • =\left( A' \cap B \right) \cap \left(A' \cup B' \right) ... the rest of the working is the same as before
  • =A' \cap \left[ B \cap \left(A' \cup B' \right)\right]
  • =A' \cap \left[ \left( B \cap A'\right) \cup \left( B \cap B'\right)\right]
  • =A' \cap \left[ \left( B \cap A'\right) \cup \phi \right]
  • =A' \cap \left( B \cap A'\right)
  • =\left( A' \cap A'\right) \cap B
  • =A' \cap B

Thus, normally, we should apply difference first, followed by De Morgan's if necessary, and then the other laws as suitable.

Exercise 8

Simplify the following using set algebra

1)\left( A-B\right)\cap A = A \cap B'

    • \begin{align} \left( A-B\right)\cap A & = \left( A \cap B' \right)\cap A \\ & = \left( A \cap A \right)\cap B' \\ & = A \cap B' \end{align}

2)B \cup \left(A-B \right) = A \cup B

    • \begin{align} B \cup \left(A-B \right) & = B \cup \left(A \cap B' \right) \\ & = \left(B \cup A \right) \cap \left(B \cup B' \right) \\ & = \left(B \cup A \right) \cap \xi \\ & = A \cup B \end{align}

3)\left(A \cup B \right) - \left(A \cap B' \right) = B \,

    • \begin{align} \left(A \cup B \right) - \left(A \cap B' \right) & = \left(A \cup B \right) \cap \left(A \cap B' \right)' \\ & = \left(A \cup B \right) \cap \left(A' \cup B \right) \\ & = B \cup \left(A \cap A' \right) \\ & = B \cup \phi \\ & = B \end{align}

4)A'-(A \cap B)' = \phi \,

    • \begin{align} A'-(A \cap B)' & = A'\cap (A \cap B) \\ & = (A' \cap A) \cap B \\ & = \phi \cap B \\ & = \phi \end{align}

5)A-\left( A-B\right) = A \cap B

    • \begin{align} A-\left( A-B\right) & =A-\left( A \cap B ' \right) \\ & =A \cap \left( A \cap B' \right)' \\ & =A \cap \left( A' \cup B \right) \\ & =\left( A \cap A' \right) \cup \left( A \cap B \right) \\ & = \phi \cup \left( A \cap B \right) \\ & = A \cap B \end{align}

6)\left(A-B \right)-B = A \cap B'

    • \begin{align} \left(A-B \right)-B & = \left(A \cap B' \right) \cap B' \\ & = A \cap \left(B' \cap B' \right) \\ & = A \cap B' \end{align}

7)\left( A-B'\right)- \left( A'-B'\right) =A \cap B

    • \begin{align} \left( A-B'\right)- \left( A'-B'\right) & =\left( A-B'\right) \cap \left( A'-B'\right)' \\ & =\left( A \cap B\right) \cap \left( A' \cap B \right)' \\ & =\left( A \cap B\right) \cap \left( A \cup B' \right) \\ & =A \cap \left[ B \cap \left( A \cup B' \right)\right] \\ & =A \cap \left[ \left(B \cap A \right) \cup \left( B \cap B' \right)\right] \\ & =A \cap \left[ \left(B \cap A \right) \cup \phi \right] \\ & =A \cap \left(B \cap A \right) \\ & =\left(A \cap A \right) \cap B \\ & =A \cap B \end{align}

8)\left( A-B\right)-\left( C-B\right) = A \cap B' \cap C'

    • \begin{align} \left( A-B\right)-\left( C-B\right) & = \left( A-B \right)\cap \left( C-B\right)' \\ & = \left( A \cap B' \right)\cap \left( C \cap B'\right)' \\ & = \left( A \cap B' \right)\cap \left( C' \cup B\right) \\ & = A \cap \left[ B'\cap \left( C' \cup B\right)\right] \\ & = A \cap \left[ \left(B' \cap C'\right) \cup \left(B' \cap B\right) \right] \\ & = A \cap \left[ \left( B' \cap C'\right) \cup \phi \right] \\ & = A \cap B'\cap C' \end{align}

9)\left( A-B\right)-\left( A-C\right) = A \cap B' \cap C

    • \begin{align} \left( A-B\right)-\left( A-C\right) & = \left( A-B\right)\cap \left( A-C\right)' \\ & = \left( A \cap B' \right)\cap \left( A \cap C'\right)' \\ & = \left( A \cap B' \right)\cap \left( A' \cup C\right) \\ & = B' \cap \left[ A \cap \left( A' \cup C \right)\right] \\ & = B' \cap \left[\left (A \cap A'\right) \cup \left(A \cap C\right) \right] \\ & = B' \cap \left[ \phi \cup \left(A \cap C\right) \right] \\ & = A \cap B' \cap C \end{align}
Retrieved from "http://www.stpmwiki.com/index.php/Sets_Part2"
Personal tools