基本情報技術者 2013年秋期午後問01

論理演算と加算器に関する次の記述を読んで、設問1～4に答えよ。

　真を1、偽を0として、主要な論理演算の真理値表を、表1に示す。基本情報技術者試験（平成25年午後問1 表1）

設問1：

　AND, OR, XOR, NOTの各論理演算を行う論理回路を用いて、NANDとNORの論理演算を行う論理回路を作成した。次の記述中のに入れる正しい答えを、解答群の中から選べ。ここで、X, Yは1ビットの入力、Zは1ビットの出力とする。　 (1) NANDの論理回路はaである。 (2) NORの論理回路はbである。　 a, bに関する解答群基本情報技術者試験（平成25年午後問1 設問1 a, bに関する解答群）

模範解答

a：イ、b：ア

解説

解答の導き方

この問題では、図の候補がどの論理演算を表しているかを、入力と出力の関係から確かめます。

ANDは、入力が両方とも1のときだけ1になります。ORは、入力の少なくとも一方が1なら1になります。NOTは、0と1を反対にする演算です。XOR（Exclusive OR：排他的論理和）は、2つの入力が異なるときに1になります。

まず、NAND（NOT AND：ANDの結果を否定する演算）を考えます。表1のNAND欄では、入力が両方1のときだけ出力が0で、それ以外は出力が1です。

解答群のイは、XとYをそれぞれNOTで反転してから、ORを行います。つまり、出力は「NOT X OR NOT Y」です。各入力の場合を確かめると、次のようになります。

X	Y	イの出力
0	0	1
0	1	1
1	0	1
1	1	0

これはNANDの出力と一致するため、NANDの論理回路はイです。

次に、NOR（NOT OR：ORの結果を否定する演算）を考えます。表1のNOR欄では、入力が両方0のときだけ出力が1で、それ以外は出力が0です。

解答群のアは、XとYをそれぞれNOTで反転してから、ANDを行います。XとYが両方0のときは反転後の入力が両方1になるため、ANDの出力は1です。それ以外の場合は、反転後の入力の少なくとも一方が0になるため、出力は0です。これはNORの出力と一致するため、NORの論理回路はアです。

誤りやすいポイント

入力をNOTで反転することと、演算結果をNOTで反転することは別です。イとアは入力を反転してからORまたはANDを行います。一方、エはXORの結果を反転しています。
解答群のウは、両方の入力を反転してからXORを行います。両方を反転しても、2つの入力が同じか異なるかは変わらないため、出力はXORと同じです。NANDにもNORにもなりません。
解答群のエは、XORの結果をNOTで反転します。XとYが両方1のときも出力が1になりますが、NANDの出力はそのとき0です。

FAQ

Q: NANDは、どのように考えると分かりやすいですか？
A: まずANDを行い、その結果をNOTで反転すると考えます。ANDの結果が1になるのは入力が両方1のときだけなので、NANDの出力はその場合だけ0になります。

Q: なぜアはNORになるのですか？
A: アでは、XとYをそれぞれ反転してからANDを行います。反転後の両方の入力が1になるのは、元のXとYが両方0のときだけです。したがって、NORの出力と一致します。

Q: XORの入力を両方反転しても、XORの結果は変わらないのですか？
A: XORは、2つの入力が異なるときに1になる演算です。両方の入力を反転しても、入力同士が同じか異なるかは変わらないため、結果も変わりません。

関連キーワード: 論理演算、真理値表、AND演算、OR演算、排他的論理和

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

設問2：

問題文を見る

　各1ビットの入力X, Yを加算して、その結果を各1ビットのZと桁上がりCに出力する“半加算器”の真理値表を表2に、論理回路を図1に示す。図1中のに入れる正しい答えを、解答群の中から選べ。

解答群　ア：AND 　イ：NAND 　ウ：NOR 　エ：OR 　オ：XOR

模範解答

オ

解説

解答の導き方

この問題では、図1の上側の論理回路に入れる演算を、半加算器の真理値表から判断します。

まず、問題文では、入力

X

と

Y

を加算した結果を、1の位の値

Z

と桁上がりの値

C

に分けています。たとえば

1 + 1 = 10

なので、

Z

は

0

、桁上がりの

C

は

1

です。

表2を

Z

の値に注目して見ると、次のようになります。

$X$	$Y$	$Z$
0	0	0
0	1	1
1	0	1
1	1	0

この表から、

X

と

Y

が異なるときは

Z = 1

、同じときは

Z = 0

だと分かります。この動きをする演算が、XOR（Exclusive OR：排他的論理和）です。したがって、図1の上側の回路にはXORを入れます。解答群ではオです。

一方、表2の

C

は、

X

と

Y

の両方が

1

のときだけ

1

です。この動きをする演算は AND（論理積）で、図1の下側の回路に使われています。

誤りやすいポイント

$Z$ を OR と間違えないようにします。OR は、入力のどちらか一方でも $1$ なら出力が $1$ です。そのため $X = 1 、 Y = 1$ の場合も出力が $1$ になり、表2の $Z$ とは一致しません。
$1 + 1$ の結果を $Z = 1$ と考えないようにします。2進数では $1 + 1 = 10$ なので、 $Z = 0$ で、桁上がりの $C = 1$ です。
$Z$ と $C$ は別の値です。 $Z$ は加算結果の1の位、 $C$ は桁上がりを表します。

FAQ

Q: XORは、どのようなときに出力が

1

になりますか？
A: 入力が異なるときです。

0

と

1

、または

1

と

0

の組合せで出力が

1

になります。

X = 1 、 Y = 1

のとき、なぜ

Z = 0

なのですか？
A:

1 + 1

は2進数で

10

だからです。1の位は

0

で、桁上がりが

1

になります。

Q: AND とXORはどう見分ければよいですか？
A: AND は両方の入力が

1

のときだけ出力が

1

です。XORは入力が異なるときに出力が

1

です。

関連キーワード: 半加算器、排他的論理和、論理積、真理値表、桁上がり

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

設問3：

問題文を見る

　各1ビットの入力X, Yと、下位桁からの1ビットの桁上がり

C_{in}

を加算して、その結果を各1ビットのZと桁上がりのCに出力する“全加算器”の真理値表を表3に、論理回路を図2に示す。図2中のに入れる正しい答えを、解答群の中から選べ。

解答群　ア：AND 　イ：NAND 　ウ：NOR 　エ：OR

模範解答

エ

解説

解答の導き方

図2では、半加算器を2つ使って全加算器を作っています。空欄は、2つの半加算器から出る桁上がりをまとめる論理演算です。

まず、半加算器は2つの1ビットの値を加算し、和と桁上がりを出力します。表1を見ると、和は入力が異なるときに1になるのでXOR、桁上がりは入力の両方が1のときに1になるので AND です。

1つ目の半加算器には

X

と

Y

が入力されます。その出力を、和を

Z_{1}

、桁上がりを

C_{1}

とすると、次のようになります。

$Z_{1} = X XOR Y$
$C_{1} = X AND Y$

2つ目の半加算器には、1つ目の和

Z_{1}

と、下位桁からの桁上がり

C_{in}

が入力されます。ここから、最終的な和

Z

と、もう1つの桁上がり

C_{2}

が出ます。

$Z = Z_{1} XOR C_{in}$
$C_{2} = Z_{1} AND C_{in}$

全加算器の桁上がり

C

は、1つ目の半加算器で発生した

C_{1}

と、2つ目の半加算器で発生した

C_{2}

のどちらかが1なら、1になります。そのため、2つの桁上がりをまとめる演算は OR です。

表3でも確かめられます。

C_{in} = 0

、

X = 0

、

Y = 0

のときは、どちらの半加算器でも桁上がりが発生せず、

C = 0

です。この場合、NANDやNORでは出力が1になってしまいます。

一方、

C_{in} = 0

、

X = 1

、

Y = 1

のときは、1つ目の半加算器で桁上がりが発生し、

C = 1

です。ANDでは出力が0になってしまいます。両方の結果に合うのは、少なくとも片方が1なら1を出す OR です。

誤りやすいポイント

2つの半加算器の出力を、そのまま最終的な桁上がりと考えないようにします。2つの桁上がりを、右端の論理演算でまとめて $C$ にします。
ANDは、入力の両方が1のときだけ1です。桁上がりは、2つの発生経路のどちらか一方で生じても出力する必要があります。
1つ目の半加算器から出る和は、最終的な和ではありません。これを2つ目の半加算器に入力し、 $C_{in}$ と合わせて最終的な和を求めます。

FAQ

C_{in}

と

C

は何が違いますか？
A:

C_{in}

は下位桁から受け取る桁上がりです。

C

は、この桁の加算によって上位桁へ渡す桁上がりです。

Q: なぜ半加算器を2つ使うのですか？
A: まず

X

と

Y

を加算し、その結果に

C_{in}

を加えるためです。半加算器は2つの値を加算する回路なので、この2段階で3つの入力を扱えます。

Q: ORは、両方の入力が1のときも1を出しますか？
A: はい。ORは、入力のうち少なくとも1つが1なら出力が1です。この回路では2つの桁上がりが同時に1になることはありませんが、どちらか一方が1になった場合に桁上がりを出せます。

関連キーワード: 半加算器、全加算器、桁上がり、排他的論理和、論理和

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

設問4：

問題文を見る

　2の補数表現による4ビットの符号付き2進整数を加算する加算器を図3に示す。加算器は、2進整数

A_{4} A_{3} A_{2} A_{1}

と

B_{4} B_{3} B_{2} B_{1}

を加算して、結果

S_{4} S_{3} S_{2} S_{1}

を出力する。添字は桁の位置を示しており、値が大きいほど上位の桁を表す。

　最上位ビットの加算において、

A_{4}

B_{4}

C_{3}

の値が表3の全加算器の真理値表のそれぞれX, Y,

C_{in}

の値のβ部分の組合せになるとき、桁あふれが生じる。これを検出するための論理回路を図4に、

S_{1}

～

S_{4}

が全て0となる場合を検出する論理回路を図5に示す。図4中と図5中のに入れる正しい答えを、解答群の中から選べ。

c, dに関する解答群　ア：AND 　イ：NAND 　ウ：NOR 　エ：OR 　オ：XOR

模範解答

c：オ、d：ウ

解説

解答の導き方

図4の

c

と図5の

d

は、それぞれ論理演算を表す記号です。表1の真理値表を使い、どの演算なら図の目的を満たすかを考えます。

図4では、符号付き加算の桁あふれを検出します。

図3では、下位の桁から順に加算し、桁からあふれた値を次の桁へ渡しています。たとえば、最上位ビットの加算には $A_{4}$ と $B_{4}$ に加えて、下位の桁からの繰上り $C_{3}$ が入ります。その加算結果から、最上位ビットの和 $S_{4}$ と、さらに外へ出る繰上り $C_{4}$ が得られます。

2の補数表現は、正の数と負の数を決められたビット数で表す方法です。この表現で桁あふれが起きるのは、最上位ビットに入る繰上りと、最上位ビットから出る繰上りが異なるときです。つまり、 $C_{3}$ と $C_{4}$ が異なるかどうかを調べます。

表1のXOR（排他的論理和）は、二つの入力が異なるときだけ値が1になります。したがって、 $C_{3}$ と $C_{4}$ の違いを検出する演算として、 $c$ にはXORが入ります。これは解答群のオです。
図5では、 $S_{1}$ ～ $S_{4}$ が全て0であることを検出します。

図5の上段のブロックには $S_{1}$ と $S_{2}$ が入り、下段のブロックには $S_{3}$ と $S_{4}$ が入ります。それぞれのブロックが「入力された二つの値が両方とも0のとき」に1を出せば、最後の AND（論理積）で二つのブロックの出力を組み合わせたとき、4つの値が全て0の場合だけ $Z F$ が1になります。

表1では、NOR（否定論理和）は二つの入力が両方とも0のときだけ1になります。したがって、各ブロックに入る $d$ はNORです。これは解答群のウです。

誤りやすいポイント

$C_{4}$ が1かどうかだけでは、符号付き加算の桁あふれは判断できません。最上位ビットに入る繰上り $C_{3}$ と、出る繰上り $C_{4}$ が異なるかを調べます。
XORは、入力が同じときではなく、異なるときに1になります。 $C_{3}$ と $C_{4}$ の比較に使えるのはこの性質によります。
図5では、各ブロックが1を出すのは入力が両方0のときです。ORではなくNORを使います。
図5の最後のANDは、上段と下段の両方の出力が1のときだけ $Z F$ を1にします。片方の組だけが0でも、 $Z F$ は1になりません。

FAQ

Q: なぜ図4では、繰上りを二つとも比べる必要があるのですか？
A: 符号付き加算の桁あふれは、最上位ビットに入る繰上りと、最上位ビットから出る繰上りが食い違ったときに起きるためです。どちらか一方だけでは判断できません。

Q: 図5の各ブロックがNORで1を出したあと、なぜANDを使うのですか？
A: 上段と下段の両方が1になったときだけ、

S_{1}

～

S_{4}

の全てが0だと判断できるからです。

Q: XORとNORは、どのようなときに1になりますか？
A: XORは二つの入力が異なるときに1になります。NORは二つの入力が両方とも0のときに1になります。

関連キーワード: 2の補数表現、半加算器、全加算器、XOR、NOR、桁あふれ検出

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！

基本情報技術者 2013年 秋期 午後 問01

論理演算と加算器に関する次の記述を読んで、設問1～4に答えよ。

.css-epvm6{white-space:nowrap;}設問1：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

設問2：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

設問3：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

設問4：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

基本情報技術者 2013年秋期午後問01

設問1：