応用情報技術者試験または基本情報技術者試験の過去問対策で、集合の問題になると多くのサイト・参考書がベン図を書いて解説をしています。
それもいいですが、集合論で解いたほうが個人的には納得感があるので、集合論で解いてみます。
全体集合S内に異なる部分集合AとBがあるとき,$\overline A∩\overline B$に等しいものはどれか。ここで,$A∪B$は$A$と$B$の和集合,$A∩B$はAとBの積集合,$\overline A$は$S$における$A$の補集合,$A-B$は$A$から$B$を除いた差集合を表す。
(ア)$\overline A-B$
(イ)$(\overline A∪\overline B)-(\overline A∩\overline B)$
(ウ)$(S-A)∪(S-B)$
(エ)$S-(A∩B)$
(出典:令和4年春期 問2)
まず、差集合の定義は
X-Y=\lbrace x \in X | x \notin Y\rbrace=X∩\overline Y
です。
つまり、
\displaylines{
X \longrightarrow X \\
- \longrightarrow ∩ \\
Y \longrightarrow \overline Y
}
の変換とみなせるので、
\overline A∩\overline B=\overline A - B
となり、解答は(ア)です。
差集合の定義さえ覚えていれば、ベン図書くより簡単かも。
なお、
(イ)は
\begin{align}
&(\overline A∪\overline B)-(A∩B)\\
=&(\overline A∪\overline B)∩\overline{(A∩B)}\\
=&(\overline A∪\overline B)∩(\overline A∪\overline B)\\
=&(\overline A∪\overline B)
\end{align}
(ウ)は、
\begin{align}
&(S-A)∪(S-B)\\
=&(S∩\overline A)∪(S∩\overline B)\\
=&(\overline A∪\overline B) \hspace{10pt}(\because Sは全体集合)\\
\end{align}
(エ)は
\begin{align}
&S-(A∩B)\\
=&S∩(\overline{A∩B})\\
=&(\overline A∪\overline B) \hspace{10pt}(\because Sは全体集合)\\
\end{align}
と変形できます。
なお、(エ)の式変形から分かるように(イ)(ウ)(エ)はいずれもNANDゲートです。
(ア)だけがNORゲートとなっています。
$\overline{(A∪B)∩(\overline A∪\overline B)}$と等価な集合はどれか。ここで,$∪$は和集合,$∩$は積集合,$\overline X$は$X$の補集合を表す。
(ア)$(\overline A∪B)∩(A∪\overline B)$
(イ)$(\overline A∪\overline B)∩(A∪B)$
(ウ)$(\overline A∩B)∪(A∩\overline B)$
(エ)$(\overline A∩\overline B)∪(A∩B)$
(出典:平成25年春期 問2)
まず一番上の否定を外すと、
\overline{(A∪B)∩(\overline A∪\overline B)}=(\overline A∩\overline B)∪(A∩B)
です。
ここから分配法則を用いると
\begin{align}
&(\overline A∩\overline B)∪(A∩B)\\
=&((\overline A∩\overline B)∪A)∩((\overline A∩\overline B)∪B)\\
=&((\overline A∪A)∩(\overline B∪A))∩((\overline A∪B)∩(\overline B∪B))\\
=&(\overline B∪A)∩(\overline A∪B)\hspace{10pt}(\because \overline X∪Xは全体集合)\\
=&(\overline A∪B)∩(A∪\overline B)
\end{align}
なので、解答は(ア)です。
かなり古いですが、基本情報技術者試験の問題もやっておきます。
集合$S-(T∪R)$に等しいものはどれか。ここで,$∩$は積集合,$∪$は和集合,$-$は差集合の各演算を表す。
(ア)$(S-T)-R$
(イ)$(S-T)∪(S-R)$
(ウ)$(S-T)∪(T-R)$
(エ)$(S-T)∩(T-R)$
(出典:平成17年春期 問8)
まず差集合の定義を再掲します。
X-Y=\lbrace x \in X | x \notin Y\rbrace=X∩\overline Y
これに沿うと
\begin{align}
&S-(T∪R)\\
=&S∩\overline{(T∪R)}\\
=&S∩(\overline T∩\overline R)\\
=&(S∩\overline T)∩\overline R\\
=&(S-T)∩\overline R\\
=&(S-T)-R\hspace{10pt}(\because (S-T)とRの差集合)\\
\end{align}
となるので、解答は(ア)です。