応用情報技術者 2022年 秋期 午前2 問02

4変数カルノー図の簡約【午前2解説】

正解の理由

解法ステップ

1. カルノー図の1の位置を最小項に対応づける（行AB、列CDの組合せで $m_0,m_2,m_5,m_7,m_{13},m_{15}$）。
2. 隣接してまとめられる最大ブロックを作る：
   • $m_5,m_7,m_{13},m_{15}$ の4つは、B=1かつD=1 が共通なので 4個グループで $B\cdot D$。
   • $m_0,m_2$ は同じ行（AB=00）で D=0 が共通なので 2個グループで $\overline{A}\overline{B}\overline{D}$。
3. これらの和で被覆できるため、簡約式は $\overline{A}\overline{B}\overline{D}+BD$（選択肢エ）となる。

選択肢別の誤答解説

• ア: $A\cdot B\cdot \overline{C}\cdot D+\overline{B}\cdot \overline{D}$
  $\overline{B}\overline{D}$ は B=0 かつ D=0 のすべて（AB=00 と AB=10 の該当セル）を含みます。問題の図では AB=10 の行はすべて0なので、$\overline{B}\overline{D}$ は存在しない1（例えば $m_8,m_{10}$）も含んでしまいます。また $AB\overline{C}D$ だけでは $m_{13},m_{15}$ の一部しかカバーせず、全体の被覆になりません。したがって過剰包含と未包含が混在し不適切です。
• イ: $\overline{A}\cdot \overline{B}\cdot \overline{C}\cdot \overline{D}+B\cdot D$
  第2項 $B\cdot D$ は確かに $m_5,m_7,m_{13},m_{15}$ を全てカバーしますが、第1項は $m_0$（$A=B=C=D=0$）のみを追加するに過ぎず、$m_2$（AB=00, CD=10）を含みません。よって一部の1が未包含になります。
• ウ: $A\cdot B\cdot D+\overline{B}\cdot \overline{D}$
  ここでの誤りは二点あります。まず、項 $A\cdot B\cdot D$ は AB=11 かつ D=1（すなわち $m_{13},m_{15}$）を表し、図中に存在する組合せです。しかしこの項は $B\cdot D$ を過度に限定しており、AB=01（$m_5,m_7$）を含まないため図を完全に覆えません。さらに $\overline{B}\overline{D}$ は AB=10 の行に該当する最小項（例：$m_8,m_{10}$）も含んでしまい、不要な1を生成します。したがって未包含と過剰包含の両方の問題があり不正解です。
• エ: $\overline{A}\cdot \overline{B}\cdot \overline{D}+B\cdot D$
  上記のとおり $m_0,m_2$ を $\overline{A}\overline{B}\overline{D}$ で、残る4つを $B\cdot D$ で完全に被覆でき、過剰包含もありません。したがって正しい簡約式です（選択肢エ）。

よくある誤解

• カルノー図の隣接性（ラップアラウンド）を見落とし、00 と 10 が隣接することに気づかないため $m_0,m_2$ をまとめられない。
• 積項の意味を誤解し、$A\cdot B\cdot D$ を「B と D が1ならよい」と読み替えてしまう（実際は A=1 も要求する）。
• 最大グループ（可能なら4や8のまとまり）を優先せず、冗長な小グループに分けてしまうため最小化ができない。

補足コラム

• まず可能な最大ブロック（8→4→2→1の順）を探す。大きいブロックほど変数を多く消去できる。
• ブロックは重複しても良い（重複によりより大きく単純な項を作れる場合がある）。
• 行・列の並びはグレイコード順（1ビットだけ変化）であることを常に意識する。これがラップアラウンドの正当性を説明します。

• 対象の1集合を $F=\sum m(0,2,5,7,13,15)$ とすると、 $BD$ が $m(5,7,13,15)$ をカバー、残り $m(0,2)$ は $\overline{A}\overline{B}\overline{D}$ によって表せます。従って $F=\overline{A}\overline{B}\overline{D}+BD$。

FAQ