Conversely, Let x A B
∈ ∩ ′. Then
x A B
x A
x B
x A
x B
x A B
∈ ∩ ′ ⇒ ∈
∈
⇒ ∈
∉
⇒ ∈ −
and
and
(2)
Hence from (1) and (2)
A B A B
− = ∩ ′
(b) We have A B
∩ = ∅. Then
A
A B
A B
A A B
A B
A A B
=
−
∪
∩
⇒ = − ∪ ∅
∩ = ∅
⇒ = −
(
) (
)
.
since
Again we have A B A
− = . Then
A
A B
A B
A B A A
A B A
A B
=
−
∪
∩
⇒ ∩ = −
− =
⇒ ∩ = ∅
(
) (
)
.
Since
(c) We have A B
⊆ . Then
A B A
A B A A B
A B A A
A B A
A B
∩ =
− = −
∩
⇒ − = −
∩ =
⇒ − = ∅
(
)
.
Since
If A B
− = ∅, then
A B A A B
A B A
A B A
A B
∩ = −
−
⇒ ∩ = − ∅
⇒ ∩ =
⇒ ⊆
(
)
.
Ì Exam ple 0.1.3: Given three sets A, B and C, prove that
A
B C
A B
C
∪
∪
=
∪
∪
(
) (
)
.
Solu tion
(i) Let us show that
A
B C
A B
C
∪
∪
⊂ ∪
∪
(
) (
)
x A
B C
x A
x B C
x A
∈ ∪
∪
⇒ ∈
∈ ∪
⇒ ∈
(
)
(
),
or
by definition of union
or
or
or
or
(
)
(
)
x B
x C
x A
x B
x C
∈
∈
⇒ ∈
∈
∈
4
Theory of Automata, Formal Languages and Computation