基本情報の論理回路は、途中の配線に名前を付け、入力が確定したゲートから順に計算すると読み解けます。半加算器と全加算器も、和と桁上がりを分けて考えれば、特別な暗記に頼らず出力を求められます。
この記事では、複数のゲートを通る信号の追跡から、真理値表による等価回路の判定、加算器をつないだ計算までを自作例題で解説します。ANDやORの名前は覚えたものの、回路全体を見ると手が止まる人向けの内容です。
- 途中の配線へ名前を付けて出力まで追跡する手順
- 反転する位置と分岐先を読み違えない確認方法
- 半加算器と全加算器の真理値表を自分で作る考え方
- 桁上がりを引き継ぐ加算と答えを確かめる検算方法
基本情報の論理回路を入力から追う方法
最初に入力と出力の役割を分ける
論理回路の問題を開いたら、ゲートの個数より先に、外から入る入力と、求める出力を確認します。ここで扱うのは、入力の組合せに応じて出力が決まる組合せ回路です。以前の状態を記憶するフリップフロップなどの順序回路とは分けて考えます。
A・B・Cは入力、P・Q・Rは途中の信号、Yは最終出力というように、役割を分けると混乱しにくくなります。回路図で線が枝分かれしていれば、同じ信号が複数の行き先へ渡ります。分岐したから値を割ったり、枝の数だけ足したりするわけではありません。
問題文に演算や信号の向きの説明があれば、それを先に読みます。MIL記号を使う図では、ANDは入力側が直線で出力側が丸い形、ORは入力側も曲線の形、XORはORの入力側へ曲線をもう一本加えた形が目印です。小さな丸の位置にも注意してください。
出力側に小さな丸があれば、そのゲートの結果を反転する意味になります。ANDの出力を反転するのがNAND、ORの出力を反転するのがNORです。見慣れない図でも、まず「何を計算し、どこで反転するか」を読み取れば、いつもの0と1の計算に戻せます。
ゲートの名称と基本動作は、東芝の「CMOSロジックICの基礎」でも確認できます。基本の出力条件を復習したい場合は、AND・OR・XORと真理値表の基本を先に押さえると、このあとの追跡に集中できます。
IPAの基本情報技術者試験シラバスVer.9.2では、基礎理論の「論理演算」で論理式、基本法則、真理値表などを学習項目としています。本記事の加算器は、それらを回路へ当てはめて理解するための具体例です。シラバスの記載から特定の問題の出題を保証するものではありません。
中間出力を置いて段ごとに計算する
自作例題として、三つの入力A・B・Cから、Y＝(A AND NOT B) OR (B AND C)を出力する回路を考えます。接続は「BをNOTへ」「AとNOT BをANDへ」「BとCを別のANDへ」「二つのANDの出力をORへ」です。図の代わりにこの接続順を追ってください。
最初にBを反転した線をP、AとPのAND出力をQ、BとCのAND出力をRと名付けます。これで、P＝NOT B、Q＝A AND P、R＝B AND C、Y＝Q OR Rという四つの小さな計算に分かれます。最後のORへAやBを直接入れないことが大切です。
A＝1、B＝0、C＝1を入れてみましょう。PはBの反転なので1、Qは1 AND 1なので1、Rは0 AND 1なので0です。最後はY＝1 OR 0となり、答えは1です。途中を一つずつ書けば、複雑に見える式も二入力の計算だけで処理できます。
| 段階 | 入力する値 | 計算結果 |
|---|---|---|
| Pを求める | B＝0 | NOT 0＝1 |
| Qを求める | A＝1、P＝1 | 1 AND 1＝1 |
| Rを求める | B＝0、C＝1 | 0 AND 1＝0 |
| Yを求める | Q＝1、R＝0 | 1 OR 0＝1 |
QとRは、必要な入力がどちらも分かっていれば、先にどちらを求めても構いません。一方、Qを計算するにはPが必要です。紙面の上下ではなく、計算に必要な入力がそろっているかを基準に順番を決めます。折り返した配線でも、この見方は変わりません。
この例ではBが二か所へ分岐していますが、両方へ渡る元の値は0です。P＝1へ反転したからといって、別の枝にあるBまで1に変わることはありません。反転するのはNOTを通った先だけです。分岐点から先の経路を指で追うと、元の入力と途中出力の取り違えに気付きやすくなります。
練習としてA＝1、B＝1、C＝0へ変えてみてください。P＝0、Q＝0、R＝0なので、Y＝0になります。最初の例と同じA＝1でも結果は変わります。「Aが1だから出力も1」と近道せず、実際に通るゲートを確かめましょう。
反転の位置を間違えない
NOTがある回路では、反転がかかる範囲を先に確定します。NOT (A AND B)は、AとBをANDで計算した結果を反転します。一方、(NOT A) AND Bは、Aだけを反転した後でBとのANDを求めます。見た目が近くても別の回路です。
A＝0、B＝0で比べると違いが分かります。前者は0 AND 0＝0を反転して1、後者はNOT 0＝1とB＝0のANDなので0です。NOTを見落としたときだけでなく、勝手に別の入力まで反転したときにも答えが変わります。
| A | B | NOT (A AND B) | (NOT A) AND B |
|---|---|---|---|
| 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
論理式では、上線がどこまで伸びているかも同じ意味を持ちます。AとBの積全体の上に線があれば全体の否定、Aの上だけに線があればAだけの否定です。文字で書き直すなら、NOTの後にかっこを補い、反転する範囲を明示すると安全です。
ド・モルガンの法則を使うと、NOT (A AND B)は(NOT A) OR (NOT B)へ変形できます。全体の反転を入力側へ移すときは、ANDをORへ替え、両方の入力を反転します。「丸を移すだけ」と覚えるとANDのまま残してしまうので、式と一組で確認してください。
また、線が交差しているように見えても、すべてが接続されているとは限りません。接続点の印や問題図の説明を見て、入力から行き先まで一本ずつたどります。線の交差をゲートと勘違いしたり、途中で別の枝へ飛び移ったりしないようにします。
真理値表で等価な回路を判定する
二つの回路が等価かどうかは、同じ入力に対してすべて同じ出力になるかで判定できます。見た目のゲート数や配線の形が違っても、入出力の関係が一致すれば同じ論理機能です。一つでも結果が異なる入力が見つかれば、その時点で等価ではないと分かります。
ただし、一つの入力で一致しただけでは等価と断定できません。先ほどの三入力回路なら、入力の組合せは2³＝8通りです。次の表ではP、Q、Rも残してあり、答えが違ったときにどの段階でずれたかを確かめられます。
| A | B | C | P＝NOT B | Q＝A AND P | R＝B AND C | Y＝Q OR R |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 |
途中結果のP・Q・Rを表へ追加しても、入力の種類が増えるわけではありません。この表はあくまで三入力なので8行です。途中列を新しい独立入力として扱い、16行や32行へ増やす必要はありません。入力が同じ行の横方向だけを見て、計算をつないでいきます。
この回路は、B＝0の行ではQ＝A、R＝0なのでY＝Aになります。B＝1の行ではQ＝0、R＝CなのでY＝Cです。つまりBが0ならAを、1ならCを出力する機能だと読めます。真理値表を作ったあとで条件ごとにまとめると、式の意味まで把握できます。
別の自作例題として、NANDを四つ使う回路を考えます。U＝NOT (A AND B)、V＝NOT (A AND U)、W＝NOT (B AND U)、Y＝NOT (V AND W)という接続です。Uは二つのNANDへ分岐しています。ここでも分岐前後のUは同じ値として使います。
| A | B | U | V | W | Y |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 |
最終列は、AとBが異なるときだけ1です。このため回路全体はXORと等価です。たとえばA＝B＝1なら、U＝0なのでVとWはどちらも1、最後のNANDは0になります。最初のNANDの出力だけを見て回路全体をNANDと決めないようにしましょう。
このように、問題で求められるのは部品名ではなく、全体の入出力の関係である場合があります。最終列が分かってからAND・OR・XORなどの条件と照らし合わせると、ゲートの外見に引っ張られずに判定できます。
選択肢は違いの出る入力から試す
選択肢が複数ある問題では、全部の表を同時に作る前に、結果が分かれそうな入力を試す方法も使えます。たとえばORとXORを区別するなら、A＝B＝1が有効です。両者は00・01・10で同じ結果になるため、その三つだけを試しても違いを発見できません。
自作問題として「Y＝NOT ((A OR B) AND C)と等価なのはどれか」を考えます。選択肢を、ア：(NOT A) OR (NOT B) OR (NOT C)、イ：((NOT A) AND (NOT B)) OR (NOT C)、ウ：((NOT A) AND (NOT B)) AND (NOT C)とします。
C＝0を入れると、元の式ではANDの出力が0となるため、Yは必ず1です。ウはA＝1、B＝0、C＝0で0になるので除外できます。次にA＝1、B＝0、C＝1を入れると、元の式はNOT (1 AND 1)＝0ですが、アは0 OR 1 OR 0＝1となり一致しません。残るのはイです。
最後にイを確認します。全体のNOTを分配すると、NOT (A OR B) OR (NOT C)となり、さらにNOT (A OR B)は(NOT A) AND (NOT B)に変わります。したがってイと一致します。選択肢を落とす入力を探す方法と、式変形で一致を確かめる方法を組み合わせています。
値を試すだけで解きたい場合は、残った候補について必要な入力をすべて確認してください。特に三入力で全0と全1だけを試すと、途中の条件が違う回路を見逃す可能性があります。途中結果へ名前を付ける基本は維持し、計算する行だけを工夫するのが使いやすい進め方です。
基本情報の論理回路を加算器の例題で解く
半加算器は和と桁上がりを出力する
半加算器は、二つの1ビット入力AとBを足し、和の下位ビットSと、上位への桁上がりCを出力します。入力も出力もそれぞれ二本ありますが、出力の二本は同じ意味ではありません。Sは今の桁に書く値、Cは次の桁へ送る値です。
2進数では1＋1＝10₂なので、A＝B＝1ならS＝0、C＝1になります。「1＋1なのに和が0なのはおかしい」と感じたら、SだけではなくCと合わせて結果を表していることを思い出してください。出力を二桁の数として読む順番はCSです。
| A | B | 和S | 桁上がりC | 結果CS |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 00₂ |
| 0 | 1 | 1 | 0 | 01₂ |
| 1 | 0 | 1 | 0 | 01₂ |
| 1 | 1 | 0 | 1 | 10₂ |
Sが1になるのはAとBが異なるときなので、S＝A XOR Bです。Cが1になるのは両方が1のときなので、C＝A AND Bです。この対応は、中部大学の「組合せ回路」の加算器教材でも確認できます。
自作の確認問題です。半加算器でA＝1、B＝1を入力したとき、SとCの組は「0と1」です。「1と1」はSをORで求めた誤り、「0と0」は桁上がりを消した誤り、「1と0」は入力の片方を足し忘れた結果です。正答だけでなく、誤答が何を取り違えたのかも確認してみてください。
検算にはA＋B＝S＋2×Cを使えます。この式の＋は、論理和のORではなく普通の数の足し算です。A＝B＝1なら左辺は2、右辺は0＋2×1＝2で一致します。Cは一つ上の桁なので、二倍の重みを持っています。
半加算器では、出力から入力を逆に考える練習もできます。S＝0、C＝1ならAとBは両方1です。一方、S＝1、C＝0なら入力は01か10の二通りあり、どちらか一方には決まりません。S＝1、C＝1という出力は、入力の合計が3になるため、二つの1ビット入力を足す半加算器では現れません。
半加算器の「半」は、半分の値を出すという意味ではありません。下位桁から来る桁上がりを入力として受け取れない点が、次に扱う全加算器との違いです。二つの数の最下位桁を足し、外部から桁上がりが来ない場面では、半加算器で処理できます。
全加算器は三つの入力を足す
全加算器はA・Bに加えて、下位桁から届く桁上がりCinを受け取ります。出力は、その桁の和Sと、上位へ渡す桁上がりCoutです。CinとCoutをどちらもCとだけ書くと混乱するので、入ってくる値と出ていく値を区別します。
A・B・Cinの各値は0か1なので、合計は0・1・2・3の四種類です。その合計を二桁の2進数に直せば、CoutとSが決まります。合計2なら10₂なのでCout＝1、S＝0、合計3なら11₂なので両方1です。
| A | B | Cin | 普通の合計 | 和S | Cout |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 2 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 2 | 0 | 1 |
| 1 | 1 | 0 | 2 | 0 | 1 |
| 1 | 1 | 1 | 3 | 1 | 1 |
三入力のうち1の個数が奇数ならS＝1、偶数ならS＝0です。式ではS＝(A XOR B) XOR Cinとなります。二入力XORを二段つなぐと、1の個数が一つのときも三つのときも1になります。「XORは一つだけ1のとき」と三入力へそのまま拡張しない点に注意しましょう。
Cout＝1になるのは、三つの入力のうち少なくとも二つが1のときです。式の一つはCout＝(A AND B) OR (A AND Cin) OR (B AND Cin)です。三つの組のうち、どれか一組が両方1なら、合計が2以上になると読めます。
ここでも普通の足し算でA＋B＋Cin＝S＋2×Coutと検算できます。A＝0、B＝1、Cin＝1なら、左辺は2、S＝0とCout＝1で右辺も2です。Coutを0と答えると右辺が0になり、桁上がりの見落としがすぐ分かります。
Cin＝0に固定した全加算器は、AとBについて半加算器と同じ入出力になります。このため、最下位桁に全加算器を使い、そのCinを0へ固定する構成も可能です。「最下位には必ず半加算器」と決めつけず、回路がどう接続されているかを見てください。
全加算器でS＝0、Cout＝1から入力を逆算する場合、合計が2なので、A・B・Cinは011・101・110の三通りです。桁上がりが1だからといってAとBの両方が1とは限りません。二つ目の入力組では、AとCinが1でBは0です。半加算器と全加算器で、同じ出力から分かる範囲が違うことも押さえましょう。
全加算器を二つの半加算器で組む
全加算器は、半加算器二つとOR一つを使って構成できます。最初にAとBを半加算器で足し、その和TとCinを次の半加算器で足します。最後に、二つの半加算器から出た桁上がりをORでまとめればCoutです。構成の確認には、法政大学のマルチビット加算回路の講義資料も参考になります。
| 部品 | 入力 | 和の出力 | 桁上がりの出力 |
|---|---|---|---|
| 一つ目の半加算器 | A、B | T＝A XOR B | C1＝A AND B |
| 二つ目の半加算器 | T、Cin | S＝T XOR Cin | C2＝T AND Cin |
| 最後のOR | C1、C2 | Cout＝C1 OR C2 | ― |
自作例題としてA＝1、B＝0、Cin＝1を入れます。一つ目は1＋0なのでT＝1、C1＝0です。二つ目はT＝1とCin＝1を足すのでS＝0、C2＝1です。最後にCout＝0 OR 1＝1となり、全体の結果は10₂です。
次にA＝1、B＝1、Cin＝0なら、一つ目でT＝0、C1＝1となります。二つ目は0＋0なのでS＝0、C2＝0ですが、Coutは1 OR 0＝1です。「二つ目の半加算器の桁上がりだけをCoutにする」と、最初の加算で出た桁上がりが消えてしまいます。
A＝B＝Cin＝1の場合も見ておきましょう。一つ目はT＝0、C1＝1、二つ目は0＋1なのでS＝1、C2＝0、Cout＝1です。結果は11₂で、普通の足し算1＋1＋1＝3と一致します。二つの段を通るからといって、三つの1が全部消えるわけではありません。
なお、この接続ではC1とC2が同時に1になることはありません。C1＝1ならA＝B＝1なのでT＝0となり、C2＝T AND Cinは必ず0です。そのため最後をXORへ替えても、この構成に限れば同じ結果になります。ただしORとXORが一般に同じという意味ではなく、入力に制約があるためです。
式の穴埋めでは、和の線と桁上がりの線を別々に追ってください。二つ目の半加算器へ入るのはTとCinであり、C1とCinではありません。接続先を取り違えると、公式を覚えていても違う回路を計算してしまいます。
複数桁は下位から桁上がりを渡す
複数桁の加算器では、一つの桁のCoutを、一つ上の桁のCinへ渡します。各桁に同じ全加算器を置き、右の下位桁から順に計算すれば、回路全体を一度に暗算する必要はありません。このように桁上がりを順に伝える構成は、リップルキャリー加算器と呼ばれます。
自作例題として、符号なしの4ビット数1011₂と0110₂を加算します。右端を0桁目として、Aの各桁は右から1・1・0・1、Bは0・1・1・0です。最下位桁への入力桁上がりC0は0とします。
| 計算する桁 | Aのビット | Bのビット | 入る桁上がり | 合計 | 和のビット | 次への桁上がり |
|---|---|---|---|---|---|---|
| 0桁目・右端 | 1 | 0 | 0 | 1 | 1 | 0 |
| 1桁目 | 1 | 1 | 0 | 2 | 0 | 1 |
| 2桁目 | 0 | 1 | 1 | 2 | 0 | 1 |
| 3桁目・左端 | 1 | 0 | 1 | 2 | 0 | 1 |
各桁の和を上位から並べるとS3S2S1S0＝0001です。ただし最上位からの桁上がりC4＝1が残ります。結果を五桁で表すなら、C4を左へ付けて10001₂です。4ビットの出力だけを問われた場合は0001、桁上がりは1、と分けて答えます。
検算すると1011₂＝11、0110₂＝6なので、普通の足し算は17です。10001₂は16＋1＝17となり一致します。4ビットだけで17は表せないため、上位への桁上がりを落とした0001だけでは、元の加算結果全体を表せません。2進数の桁の重みが曖昧なら、n進数と基数変換の解説で確認できます。
この例の2桁目で、0＋1だけを見て和を1とすると誤りです。1桁目から届いた桁上がり1があるため、合計は2、和は0となります。表には「入る桁上がり」と「出る桁上がり」を別々に書き、計算が終わったら出る値を次の行へコピーしてください。
仕上げに、符号なし4ビットの0111₂＋0001₂も試してみましょう。右端の1＋1で和0・桁上がり1、次の1＋0＋1でも和0・桁上がり1、その次も同じです。最上位は0＋0＋1なので和1・桁上がり0となり、結果は1000₂です。7＋1＝8で検算できます。
桁上がりと、符号付き数のオーバーフローは区別します。今の0111₂＋0001₂では最上位からの桁上がりは0ですが、4ビットの2の補数として読むと7＋1が表現範囲を超えます。本記事の計算例は符号なしを前提としているので、符号の解釈が指定された問題では条件を読み直してください。
まとめ：基本情報の論理回路の解き方
基本情報の論理回路は、入力から出力までを小さな計算へ分けると整理できます。途中の線へ名前を付け、NOTの範囲と分岐先を確認し、入力がそろったゲートから順に埋めていきましょう。等価回路の判定では、一つの不一致で候補を除外できますが、一致の証明には全組合せの確認や正しい式変形が必要です。
半加算器は二つの入力、全加算器は桁上がりを含む三つの入力を足します。和と桁上がりを別々に出し、普通の足し算で「入力の合計＝S＋2×Cout」を確かめれば、答えの取り違えを見つけられます。複数桁では、一つ前のCoutを次のCinへ渡すことを忘れないでください。
次に練習するときは、この記事のNAND四個の回路の表と、1011₂＋0110₂の表を隠して、自分で再現してみてください。答えが違ったら最終列だけを直さず、最初に値がずれた途中列へ戻ると、反転・接続・桁上がりのどこが苦手かを確認できます。
回路の追い方を確認できたら、無料の基本情報過去問アプリで演習する方法もあります。正誤だけで終わらせず、入力、途中結果、最終出力を自分のメモで説明できるか確かめてみましょう。
コメント