応用情報技術者 2010年秋期午前2 問24

問題文

図の論理回路と等価な回路はどれか。

🖊️ 解答を隠して解いてみる

ア：

イ：

ウ：（正解）

エ：

🔒 解説は解答すると表示されます

回路全体の出力は

A \lor B

（論理和）になり、これに対応する記号が選択肢の中ではウに該当します。各段の小円（バブル）は入力や出力の否定を表すため、ド・モルガンの法則と吸収律を順に適用すると全体が OR に簡約されます。中間段の動作を式で整理すると、最終的に

A \lor B

と等価になることが明確です。

論理式で段ごとに表現して簡約します。入力を

A, B

とする。

左端のゲート（入力にそれぞれバブル、出力にもバブル）
入力側バブルで各入力が反転し、AND に入るため内部は $\neg A \land \neg B$ 。出力にバブルがあるので全体は否定され、
$G_{1} = (\neg A \land \neg B)^{'} = \neg (\neg A \land \neg B)$
ド・モルガンで
$G_{1} = A \lor B$
中段上（入力は $A$ と $G_{1}$ 、出力にバブル）
中段上の内部は $A \land G_{1} = A \land (A \lor B)$ 。吸収律により $A \land (A \lor B) = A$ 。出力にバブルがあるので
$G_{2} = (A \land G_{1})^{'} = \neg (A) = \neg A$
中段下（入力は $B$ と $G_{1}$ 、出力にバブル）
同様に
$G_{3} = (B \land G_{1})^{'} = \neg (B \land (A \lor B)) = \neg B$
最終段（入力は $G_{2}, G_{3}$ 、出力にバブル）
内部は $\neg A \land \neg B$ 。出力にバブルがあるため
$Y = (\neg A \land \neg B)^{'} = \neg (\neg A \land \neg B) = A \lor B$

したがって回路全体は OR（論理和）であり、対応する記号がウです。

ア：図の形状は標準的な OR/AND とは異なる形で、入力・出力のバブル配置も合致しません。与えられた回路が簡約すると OR になる点と一致しないため不正解です。
イ：左入力面が平坦な形状は AND を表します。AND の出力は $A \land B$ であり、本問の $A \lor B$ と異なります。
ウ：入力の形状から論理和（OR）を表し、出力にバブルがない点も一致するため等価です。
エ：ウと同じ OR 系の形状ですが、出力にバブルがあるため NOR（ $\neg (A \lor B)$ ）を表します。本回路は $A \lor B$ なので不一致です。

バブルを見て「どこかでXOR/XNORになる」と短絡的に判断する。バブルは単に否定を示すだけで、配置とゲート型を正しく式に置き換えれば単純な OR/NAND などになることが多いです。
中間段で $A \land (A \lor B)$ をそのまま複雑だと誤認し、吸収律 $A \land (A \lor B) = A$ を使わないために簡約を誤る。
バブルを「入力だけ」「出力だけ」を反転すると誤解し、バブルの位置（入力側か出力側か）による意味の違いを取り違える。

・バブル（小円）は「信号の否定」を示す標準記法です。入力側にあるバブルはその入力が反転してゲートに入ること、出力側にあるバブルはそのゲートの出力が反転して外へ出ることを意味します。
・よく使う恒等式（本問で使用）：

ド・モルガンの法則： $\neg (X \land Y) = \neg X \lor \neg Y, \neg (X \lor Y) = \neg X \land \neg Y$
吸収律： $A \land (A \lor B) = A, A \lor (A \land B) = A$
・確認用に真理値表を作ると確実です。以下は簡単な Python による検算例。

# 検算：Y = A or B
for A in (0,1):
    for B in (0,1):
        Y = A or B
        print(A,B,int(Y))

Q. バブルが複数あって複雑に見える回路は必ず単純化できる？
A. 多くの場合、ド・モルガンや吸収律などの恒等式で簡約できます。まずは各ゲートをブール式で書き、順に整理するのが確実です。

Q. バブルを「前へ押す（bubble-pushing）」テクニックとは？
A. バブルをゲートの前後に移動させてゲートの種類（AND↔OR）を変換するテクニックです。移動の際は同時に式の否定を扱うことを忘れないでください。

関連キーワード: ブール代数、ド・モルガンの法則、吸収律、バブルプッシング、論理和（OR）

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

すぐに利用可能！