基本情報技術者 2016年 秋期 午前（科目A） 問23

3入力多数決回路の真理値表【午前2 解説】

要点まとめ

• 結論: 真理値表は「2つ以上が1のとき1」になる多数決であり、3つの2入力ANDをORで合成する回路、アが正解です。
• 根拠: 出力1の組合せは (0,1,1),(1,0,1),(1,1,0),(1,1,1) で、論理式は $AB+BC+CA$ と表せます。
• 差がつくポイント: 図の左側がANDかORか、右端のバブル（否定）の有無で論理式が大きく変わる点に注意してください。

正解の理由

よくある誤解

• 「入力を先にORして後でANDすれば同じになる」と思い込み、式の順序（分配・結合）の違いを見落とす誤り。
• バブル（小丸）を見落としてNANDとANDを混同し、出力極性を逆に解釈してしまう。
• 中央と右端のゲートが複数段でも結合律で同値になることを忘れて、図の段数だけで不正解と判断する。

解法ステップ

1. 真理値表から出力1となる行を列挙する: (0,1,1),(1,0,1),(1,1,0),(1,1,1)。
2. 各行に対応する積項（ミンターン）を書き出すと $BC,CA,AB,ABC$。ただし $ABC$ は既に $AB,BC,CA$ のいずれかでカバーされる。
3. したがって簡約した論理式は $AB+BC+CA$。
4. この式をそのまま回路に対応させると、各ペアの2入力ANDを取り、その出力をORで合成する回路になる（＝選択肢ア）。

選択肢別の誤答解説

• ア（正解）: 左で $(A\wedge B),(B\wedge C),(C\wedge A)$ を作り、それらをORで合成して $AB+BC+CA$ を実現。真理値表と一致。
• イ: 左で $(A\vee B),(B\vee C),(C\vee A)$ を作り、上2つをANDしてから最終的にORする構成。論理式は $(A+B)(B+C)+(C+A)$ で、例えば $(A,B,C)=(1,0,0)$ のとき評価は $1$ になり真理値表の $0$ と不一致。
• ウ: 左はANDだが中央もAND、最終段がバブル付きNAND（出力は否定）になっている。論理式を整理すると最終出力は $\overline{ABC}$ に相当する振る舞いとなり、(1,0,0) 等で期待値と合わない。
• エ: 左はOR、中央はAND、最終がバブル付きNAND。例えば $(1,0,0)$ では中央が0で最終NANDが1となり、真理値表の0と矛盾する。

補足コラム

• 多数決（majority）関数の代表的な表現は $M(A,B,C)=AB+BC+CA$ です。これは「少なくとも2つが1」の論理をそのまま書いた形です。
• 別の形としては $AB+C(A+B)$ と因数分解できます。実装上はコストやゲート遅延を考慮して最適化することがあります。
• 実験用に Python で真理値表を確認するコード例:

from itertools import product
def maj(a,b,c): return (a and b) or (b and c) or (c and a)
for a,b,c in product([0,1], repeat=3):
    print(a,b,c, int(maj(a,b,c)))

FAQ