基本情報技術者 2011年 春期 午前（科目A） 問24

偶数パリティ判定回路【午前解説】

正解の理由

解法ステップ

1. 問題文から目的関数を特定する。4入力で「1の個数が偶数のとき1」→偶数パリティ関数 $f=\neg (A\oplus B\oplus C\oplus D)$。
2. 回路図を記号で読み取る。
   • OR記号の入力側にもう1本の弧があるのがXOR、三角形の先端に丸（バブル）があるのがNOT（インバータ）。
   • 4つの選択肢は左側の2つのXORが共通で、右側のゲートの種類と最後のNOTの有無だけが異なる。
3. 偶数パリティは「XOR → 全体をNOT」または「適切に組んだXNORの組合せ」で実現できる。図の各ゲートと反転の有無を確認し、論理式へ対応付ける。
4. 各選択肢を論理式に置き換え、目的関数と一致するかを検証する。これによりエが一致することを確認する。

選択肢別の誤答解説

• ア:
  • 右側がANDなので、出力は $(A\oplus B)\wedge (C\oplus D)$ です。2組ともちょうど1個ずつ1を含むときだけ1になり、例えば入力がすべて0（1の個数0個）のとき0になるので条件に合いません。
• イ:
  • 右側がORで最後にNOTなので、出力は $\neg ((A\oplus B)\vee (C\oplus D))$ です。2組とも0同士・1同士のときだけ1になり、例えば $A=1,B=0,C=1,D=0$（1の個数2個）のとき0になるので条件に合いません。
• ウ:
  • 右側がXORで最後の反転がないので、出力は $A\oplus B\oplus C\oplus D$ です。1の個数が奇数のとき1になり、問題文の「偶数で1」と逆になります。
• エ:
  • XORを3つ組み合わせて $A\oplus B\oplus C\oplus D$ を作り、最後にNOTで反転しているので $\neg (A\oplus B\oplus C\oplus D)$ を実現しており、問題の条件に合致します。

よくある誤解

1. XNORは常に結合律（結合則）を満たすと思い込む
   • XNOR（同値）は一般に結合則（任意の括りで同じ結果になる性質）を満たすとは限りません。例えば $(A\odot B)\odot C$ と $A\odot (B\odot C)$ が等しくならない場合があります。したがって「複数入力のXNORを任意に括って組めば同じ」と短絡的に考えるのは誤りです。
2. 図中の小さな線や丸の意味を見落とす
   • 入力側や出力側の小さな記号（バブルや短い並行線）は論理の極性（反転）に直結します。これを誤って読み取ると、正しい/逆の関数を読んでしまいます。
3. XORチェーンとXNORチェーンを同一視する
   • XORチェーン（A⊕B⊕C⊕D）とその否定であるXNOR（偶数パリティ検出）は出力が逆なので、最終段に反転が必要かどうかを必ず確認してください。

補足コラム

• XORを連結して全体を反転する: $f=\neg (A\oplus B\oplus C\oplus D)$
• XNORのペア結合で実現する: たとえば $(A\odot B)\odot (C\odot D)$ が $\neg (A\oplus B\oplus C\oplus D)$ と等価になることを利用する（ただし、この等価性は括り方と中間の極性に注意して扱う必要があります）。

• $\odot$ をXNOR、$\oplus$ をXORとすると $X\odot Y=\neg (X\oplus Y)$。
• $(A\odot B)\odot (C\odot D)=\neg (\neg (A\oplus B)\oplus \neg (C\oplus D))$。
• 一般に $\neg P\oplus \neg Q=P\oplus Q$ なので式は $\neg ((A\oplus B)\oplus (C\oplus D))=\neg (A\oplus B\oplus C\oplus D)$ となり、偶数パリティを表します。
• つまり、XNOR自体が任意に結合律を満たすわけではないが、適切にペアに分けることで4入力偶数パリティを正しく実現できる、という点が重要です。

FAQ