⇒ ∈
∈
∈
⇒ ∈
∈
∈
⇒ ∈
∈ ∩
⇒
(
)
(
)
y A
y B
y C
y A
y B
y C
y A
y B C
y
and
and
and
and
and
∈ ∩
∩
A
B C
(
)
There fore we have
(
)
(
)
A B
C A
B C
∩
∩ ⊂ ∩
∩
(2)
From (1) and (2), we have
A
B C
A B
C
∩
∩
=
∩
∩
(
) (
)
Ì Exam ple 0.1.5: For any two sets A and B, prove the DeMorgan’s Laws
(a) (
)
A B
A
B
∪ ′ = ′ ∩ ′
(b) (
)
A B
A
B
∩ ′ = ′ ∪ ′
Solu tion
(a) x A B
x A B
x A
x B
x A
x B
x A
B
∈ ∪ ′ ⇔ ∉ ∪
⇔ ∉
∉
⇔ ∈ ′
∈ ′
⇔ ∈ ′ ∩ ′
(
)
and
and
(b) y A B
y A B
y A
y B
y A
y B
y A
∈ ∩ ′ ⇔ ∉ ∩
⇔
∉
∉
⇔
∈ ′
∈ ′
⇔ ∈
(
)
either
or
either
or
′ ∪ ′
B
Hence we have (
)
.
A B
A
B
∩ ′ = ′ ∪ ′
Ì Exam ple 0.1.6: If the symmetric difference of the two sets A and B is
refined as (
) (
)
A B
B A
−
∪
− and denoted by A B
∆ , prove that
(a) A B B A
∆
∆
=
(b) (
) (
)
.
A B
A B
A B
∪
−
∩
= ∆
Solu tion
(a) A B
A B
B A
B A
A B
B A
∆
∆
=
−
∪
−
=
−
∪
−
=
(
) (
)
(
) (
)
(b) (
) (
) (
) (
)
(
)
(
) (
)
A B
A B
A B
A B
x y x y
A B
A
B
∪
−
∩
=
∪
∩
∩ ′
− = ∩ ′
=
∪
∩ ′ ∪ ′
=
Q
((
)
) ((
)
)
(
) (
) (
)
(
)
A B
A
A B
B
A A
B A
A B
B B
∪
∩ ′ ∪
∪
∩ ′
=
∩ ′ ∪
∩ ′ ∪
∩ ′
∪
∩ ′
6
Theory of Automata, Formal Languages and Computation