基本情報技術者教科書 - 論理演算
エレベーターは、「ドアが閉まっている」ことと「定員を超えていない」ことの両方がそろったときだけ動きます。このように、いくつかの条件の真偽を組み合わせて、全体の真偽を決める計算を「論理演算」と言います。コンピュータの中の処理は、どれも0と1を組み合わせた論理演算が土台になっています。
前のページでは、否定・論理積・論理和を、集合と命題の言葉で学びました。このページでは、それを0と1の世界で使いこなします。まず基本の演算と真理値表を整理し、続いて排他的論理和などの演算、式を変形するための法則、ビット列の一部を取り出したり反転したりする「マスク」の使い方、最後にNANDだけで回路を作る話へと進みます。基本情報技術者試験では、論理式を変形して同じ意味の式を選ぶ問題、ビット列を加工する操作を選ぶ問題、排他的論理和の性質を使う問題が、くり返し出題されています。式が並ぶと身構えてしまいますが、ほとんどは0と1を代入して確かめれば解けます。
もくじ
論理演算の基本
- 真を1、偽を0で表す。NOTは反転、ANDは両方1のときだけ1、ORは1つでも1なら1
- 入力の組合せを全部並べて出力を書いた表が真理値表
真と偽を0と1で表す
論理演算では、真を「1」、偽を「0」で表します。スイッチならONが1でOFFが0、ランプなら点灯が1で消灯が0、といった具合です。論理演算は、この0と1を入力にして、結果の0か1を出力します。ふつうの計算と違って、答えは必ず0か1のどちらかで、2や3にはなりません。
なお、0と1の1桁のことを「ビット」と言います。1ビットなら0か1の2通り、8ビットなら256通りの値を表せます。後半では、8ビットの値にまとめて論理演算をかける話が出てきます。
NOT・AND・OR
基本の演算は、次の3つです。
- 「否定」(NOT)は、0と1をひっくり返す演算です。変数の上に線を引いて、 と書きます。
- 「論理積」(AND)は、2つの入力が両方とも1のときだけ1になる演算です。 と書きます。
- 「論理和」(OR)は、2つの入力の少なくとも一方が1なら1になる演算です。 と書きます。
ANDとORは、スイッチ回路にたとえると分かりやすくなります。スイッチを直列につなぐと、両方をONにしないとランプは点きません(AND)。並列につなぐと、どちらか1つでもONにすれば、ランプが点きます(OR)。
これを表にまとめたものが「真理値表」です。入力のすべての組合せについて、結果を書き並べます。
| A | B | |||
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
論理和の記号「+」は、足し算と同じ形をしていますが、意味は別物です。足し算なら1+1は2ですが、論理和では1+1は1です。「少なくとも一方が1なら1」という意味だからです。表の最下行で、確かめておきましょう。
この記号の書き方は、試験の問題によって少し変わります。論理積を「∧」、論理和を「∨」、否定を「¬」と書く問題や、AND・OR・NOTという英語で書く問題もあります。どれも同じ意味です。
論理式と真理値表
変数と演算記号を組み合わせた式を、「論理式」と言います。1つの式にいくつもの演算が入っているときは、「NOT、AND、ORの順」に計算します。算数で掛け算が足し算より先なのと同じで、ANDがORより先です。たとえば は、 の意味です。ORを先に計算したいときは、 のように、かっこを付けます。
論理式の値を調べるには、真理値表を作ります。変数が3個(A、B、C)なら、組合せは2×2×2=8通りです。行を000、001、010、……、111と、2進数の順に並べると、漏れも重複も防げます。1つの式を一度に計算しようとせず、途中の列を作って少しずつ進めるのがコツです。 で試してみましょう。
| A | B | C | F | ||
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 |
Fが1になるのは、「AがONでBがOFF」のときか、「CがON」のときです。1行ごとに、表の列の意味を言葉に直してみると、式の読み方が身に付きます。
排他的論理和と否定の演算
基本の3つのほかに、試験によく出る演算がいくつかあります。どれも、AND・OR・NOTの組合せで作れる演算です。
排他的論理和(XOR)
「排他的論理和」(XOR)は、2つの入力が異なるときに1になる演算です。記号は です。「どちらか一方だけが1」と言い換えられます。ふつうの論理和(OR)との違いは、両方が1のときです。ORは1になりますが、XORは0になります。
XORを、基本の3つの演算で書くと、次のようになります。「Aが1でBが0」か、「Aが0でBが1」のどちらかなので、異なる場合だけが残ります。
別の見方もできます。「少なくとも一方が1(OR)で、しかも、両方が1ではない(ANDの否定)」ものは、ちょうど一方だけが1のものです。つまり、ORの結果とANDの否定の結果のANDをとると、XORになります。
3つ以上のビットをXORでつなぐと、「1の個数が奇数なら1、偶数なら0」になります。たとえば1⊕1⊕1は、1の個数が3個(奇数)なので1です。この性質は、後で出てくるパリティビットの話につながります。
NAND・NOR・XNOR
ANDやOR、XORの結果を、そのまま否定した演算にも名前が付いています。
- 「否定論理積」(NAND)は、ANDの結果を否定したものです。両方が1のときだけ0になり、あとは1です。
- 「否定論理和」(NOR)は、ORの結果を否定したものです。両方が0のときだけ1になり、あとは0です。
- 「XNOR」は、XORの結果を否定したものです。2つの入力が同じときに1になります。
ある演算に対して、すべての入力で結果が否定になる演算を、その演算の「相補演算」と呼ぶことがあります。ANDの相補演算はNAND、ORの相補演算はNOR、XORの相補演算はXNORです。表で、ANDとNAND、XORとXNORの列を見比べると、0と1が入れ替わっているのが分かります。
XNORを論理式で書くと、「両方1」か「両方0」なので、次のとおりです。また、片方だけを否定したXORと同じ結果になります(片方を否定すると、「異なる」が「同じ」に入れ替わるからです)。
排他的論理和の性質
XORには、ビット列を扱うときに役立つ性質がいくつもあります。
特に大切なのは、「同じ値を2回XORすると元に戻る」ことと、「順序を入れ替えてよい」ことです。この2つを組み合わせると、長いXORの式の中から、同じ値が2つ出てくる部分を、まとめて消せます。使い方は、後の節で見ます。
論理式の法則と変形
数の計算に交換法則や分配法則があるように、論理式にも、いつでも成り立つ法則があります。式を簡単にしたり、2つの式が同じ意味かを調べたりするときに使います。実は、前のページで学んだ集合の法則と、形がそっくりです。前のページの和集合・積集合・補集合・全体集合・空集合を、ここでは「+」「・」、上線、1、0に置き換えると、同じ法則がそのまま使えます。
基本の法則
法則の名前を丸暗記する必要はありません。式の形を見て、迷ったら0と1を代入して確かめれば、確実に判断できます。表の右の列に、確かめ方の例を1つずつ付けました。
| 法則 | 式 | 0と1で確かめる例 |
|---|---|---|
| 交換法則 | A=1、B=0なら、1+0=1、0+1=1 1・0=0、0・1=0 | |
| 結合法則 | A=1、B=0、C=1なら、 (1+0)+1=1、1+(0+1)=1 | |
| 分配法則 | A=1、B=0、C=1なら、 1・(0+1)=1、1・0+1・1=1 A=B=C=1なら、1+1・1=1、 (1+1)・(1+1)=1(1+1=1なので、数の計算とは違う) | |
| べき等法則 | A=1なら、1+1=1、1・1=1 A=0なら、0+0=0、0・0=0 | |
| 0・1との演算 | 、 、 | A=1なら、1+0=1、1+1=1、 1・0=0、1・1=1 |
| 補元の法則 | A=0ならAの否定は1なので、 0+1=1、0・1=0 | |
| 二重否定 | A=1なら、1の否定は0、 その否定は1で、元に戻る | |
| 吸収法則 | A=1、B=0なら、1+1・0=1、1・(1+0)=1 A=0、B=1なら、0+0・1=0、0・(0+1)=0 | |
| ド・モルガンの法則 | 次の節で、数値を入れて確かめます |
数の計算と大きく違うのは、分配法則が2通りあることです。数では「掛け算が足し算に分配される」だけですが、論理式では、ANDがORに分配される形(上の行)のほかに、ORがANDに分配される形(下の行)も成り立ちます。後者は、数の感覚では間違いに見えるので、注意しましょう。0と1を代入して、確かめることができます。たとえばA=1なら、左辺は1+B・C=1、右辺は(1+B)・(1+C)=1・1=1です。A=0なら、左辺はB・C、右辺はB・Cで、やはり一致します。
この表で、特によく使うのは、「吸収法則」と「補元の法則」と「ド・モルガンの法則」です。次の節から、使い方を見ていきましょう。
ド・モルガンの法則
「全体にかかった否定を、内側に入れると、ANDとORが入れ替わり、それぞれの変数が否定になる」というのが、ド・モルガンの法則です。逆向きに、バラバラの否定をまとめて外に出すときにも使えます。
数値を入れて確かめましょう。A=1、B=0とします。 は、 = =0です。一方、 は、0・1=0で、一致します。 は、 = =1で、 は、0+1=1です。こちらも一致します。
この法則から、NANDとNORを、否定を使った式で書き直せます。
「NANDは、否定を内側に入れるとOR」「NORは、否定を内側に入れるとAND」と覚えておくと、後で出てくる、NANDだけで回路を作る話が分かりやすくなります。
式を簡単にする
基本の法則を使うと、長い式を短くできます。よく出る3つのパターンを見てみましょう。どの変形も、式の下に「使った法則」を書き添えます。
1つめは、同じ変数でくくって、補元の法則を使う形です。Bが0でも1でも結果が変わらないので、Bは式に関係がなくなります。
使った法則は、1行目が分配法則(Aでくくる)、2行目が補元の法則、3行目が1との演算です。数値で確かめるなら、A=1、B=0を代入します。左辺は 1・0+1・1=1、右辺はA=1で、一致します。
2つめは、 という形です。分配法則(ORがANDに分配される形)を使います。「Aが1ならそれで十分で、Aが0のときだけBを見る」ので、結局はA+Bになります。
使った法則は、1行目が分配法則(ORがANDに分配される形)、2行目が補元の法則、3行目が1との演算です。数値で確かめるなら、A=0、B=1を代入します。左辺は 0+1・1=1、右辺は 0+1=1で、一致します。
3つめは、かっこを展開してから整理する形です。
使った法則は、1行目が分配法則(かっこの展開)、2行目が補元の法則(A・Aの否定=0)と0との演算、そして交換法則(B・Aの否定を、Aの否定・Bに並べ替え)です。ここまでは、法則のとおりに機械的に進められます。
難しいのは、最後に残った B・C を消してよい理由です。次のように、B・C が0の場合と1の場合に分けて考えます。
- B・Cが0のとき(BかCの少なくとも一方が0): B・Cを足しても、0を足すだけなので、式の値は変わりません。
- B・Cが1のとき(B=C=1): 残りの は、A・1+Aの否定・1=A+Aの否定=1で、すでに1になっています。1にB・C(=1)を足しても、1のままです。
どちらの場合も、B・Cの有無で式の値が変わらないので、消せます。A=0、B=1、C=1で確かめると、消す前は 0+1+1=1、消した後は 0+1=1で、一致します。そこで、次のようになります。
試験では、「論理式と等しいものはどれか」という形で、このような変形の結果が選択肢に並びます。その場合に、一番確実なのが、次の方法です。
代入して確かめる
変数に具体的な0と1を代入して、選択肢の式の値を求め、元の式と食い違うものを消していく方法です。たとえば、 と等しいのは、次のア、イのどちらかを調べます。
- ア:
- イ:
A=1、B=1、C=0を代入します。元の式は、 =1・(0+0)=0です。アは、1・1+0・0=1となり、食い違います。イは、1・0+0・1=0で、一致します。したがって、アは消えて、イが残ります。
ここで注意したいのは、食い違う例が1つ見つかれば「等しくない」と言い切れるのに対し、一致する例がいくつあっても、「等しい」とは言い切れないことです。選択肢が複数残ったときは、別の代入の組合せで、さらに絞り込みましょう。変数が3つでも、全部で8通りしかないので、最後は全部の組合せを調べることもできます。
真理値表から論理式を作る
逆に、真理値表から論理式を作る方法を見ましょう。考え方は、「結果が1になる行を1つずつ式にして、ORでつなぐ」です。次の表の関数Fで試します。
Fが1になるのは、ABCが011、110、111の3行です。まず、011の行だけを取り上げて、1行分の式の作り方を見ます。この行でだけ1になる式を作るには、A、B、Cのそれぞれについて、「この行の値のときに1になる部品」を用意して、全部をANDでつなぎます。
- Aは0なので、Aが0のときに1になる部品、つまりAの否定を使います。
- Bは1なので、Bをそのまま使います。
- Cは1なので、Cをそのまま使います。
ANDでつなぐと です。011を代入すると 1・1・1=1、別の組合せ(たとえば010)を代入すると 1・1・0=0になります。部品が1つでも合わないと0になるので、この式は011の行でだけ1になります。「1ならそのまま、0なら否定を付ける」とは、この部品選びのことです。
同じようにして、110の行は 、111の行は です。これらをORでつなぐと、「3つの行のどれかに当てはまれば1」になるので、次の式になります。
このままでも正しいのですが、簡単にできます。1つめ(011の行の項)と3つめ(111の行の項)はAだけが違い、2つめ(110の行の項)と3つめはCだけが違います。違う変数を補元の法則で消したいので、 を2回使って、それぞれと組にします。同じ項を何回足しても結果が変わらない(べき等法則)ので、こうしてかまいません。
この変形では、1行目がべき等法則( を2回に増やす)、2行目が分配法則(B・Cでくくる、A・Bでくくる)、3行目が補元の法則と1との演算、4行目が分配法則(Bでくくる)です。
答えは、「Bが1で、しかも、AかCの少なくとも一方が1」です。表のFが1の行と、一致していることを確かめてみてください。
結果から演算を逆算する
「ある演算 □ の結果は分からないが、それを使った演算の結果の表だけが分かっている」という問題が出ることがあります。「□」は、「どんな演算か分からない」ことを表す記号です。たとえば、中身の見えない箱にXとYを入れると、結果 X□Y が出てくるとします。箱の中身は分かりませんが、その結果を使った別の演算の答えは見えている、という状況です。
問題では、「X AND (X□Y)」と「X OR (X□Y)」の2つの結果が表で与えられ、そこから X□Y が何かを推理します。ANDとORの2つが与えられるのは、次の事実のとおり、片方では分からない行を、もう片方が補ってくれるからです。
- X=0のとき、「X AND何か」は必ず0になり、「X OR何か」は、その「何か」と同じ値になる。
- X=1のとき、「X OR何か」は必ず1になり、「X AND何か」は、その「何か」と同じ値になる。
つまり、X=0の行ではORの列を、X=1の行ではANDの列を見れば、「何か」の値が読み取れます。例で試してみましょう。X□Yが分からないとして、次の表が得られたとします。
| X | Y | X AND (X□Y) | X OR (X□Y) | X□Y |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
行ごとに見てみましょう。X=0の2行では、「X OR 何か」は「何か」そのものなので、ORの列の0と1が、そのままX□Yです。X=1の2行では、「X AND 何か」が「何か」そのものなので、ANDの列の0と1がX□Yです。出てきた4つの値(0、1、0、1)は、どの行もYと同じです。したがって、この □ は、「Yをそのまま返す演算」だったことになります。
半加算器
論理演算は、足し算にも使えます。1ビットどうしの足し算は、答えが2ビットになることがあります。0+0=00、0+1=01、1+0=01、1+1=10(2進数)です。上位のビットを桁上がりC、下位のビットを和Sとして、真理値表にしてみましょう。
Cの列は、ANDの列と同じです。Sの列は、XORの列と同じです。つまり、次の式で、1ビットの足し算ができます。
この組合せを、「半加算器」と言います。「桁上がりはAND、和はXOR」と覚えておけば、式の形から、すぐに見分けられます。
ビット列に対する論理演算
ここまでは1ビットどうしの演算でした。8ビットなどの「ビット列」に対しては、桁(ビット)ごとに、独立に論理演算をします。上のビットから下のビットへの影響はありません。たとえば、次のようになります。
マスクの考え方
ビット列の一部だけを取り出したり、1や0にしたり、反転したりするとき、「マスク」を使います。塗装のときに、塗らない場所をマスキングテープで覆うのと同じ発想で、「操作したいビット」と「そのままにしたいビット」を、もう1つのビット列(マスク)の0と1で区別します。元の値とマスクの間で、ビットごとに論理演算をすると、マスクが1か0かによって、そのビットの扱いが決まります。演算ごとの働きは、次のとおりです。
覚え方は、「ANDは0で消す、ORは1で立てる、XORは1で反転する」です。残したいビットのところに、何の値を置くかを覚えておくと、迷いません。ANDなら1、OR・XORなら0を置きます。
16進数のマスクは、4ビットずつ区切って考えます。0Fは0000 1111、F0は1111 0000、C0は1100 0000です。次の図で、B4(10110100)にマスクをかけた結果を見てみましょう。
図のように、ANDの0Fは「上位4ビットを消して、下位4ビットを残す」、ORのF0は「上位4ビットを1にして、下位4ビットを残す」、XORのC0は「上位2ビットを反転して、残りを残す」操作になります。
B4(1011 0100)にマスクをかける様子を、1ビットずつ追ってみましょう。結果の太字は、元の値から変化したビットです。
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |
|---|---|---|---|---|---|---|---|---|
| 元の値 B4 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| AND のマスク 0F | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 結果 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| OR のマスク F0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 結果 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
| XOR のマスク C0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 結果 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
ANDの0Fでは、上位4ビット(1011)は、マスクが0000なので、元が1のビットも0にされて、0000になります。下位4ビット(0100)は、マスクが1111なので、そのまま残ります。結果は0000 0100(04)です。ORのF0では、上位4ビットはマスクが1なので全部1になり、下位4ビットはマスクが0なのでそのままで、1111 0100(F4)です。XORのC0では、上位2ビットだけマスクが1なので、「10」が「01」に反転し、残りの6ビットはそのままで、0111 0100(74)になります。
「下位4ビットが変化しない操作はどれか」のような問題では、選択肢の演算とマスクを見て、「下位4ビットに置かれているマスクの値が、残す値になっているか」を調べます。0F(0000 1111)は、下位4ビットが1なので、ANDなら残ります。ORやXORで残すには、下位4ビットが0のF0が必要です。0FとのORは、下位4ビットを全部1にしてしまい、0FとのXORは、下位4ビットを反転してしまいます。
次のツールで、AとBのビットを自由に切り替えて、演算の結果を確かめてみましょう。Bにマスクを設定して、ANDやORの働きを試せます。
ビットの反転
8ビットのすべてのビットを反転する操作は、「FF(1111 1111)とのXOR」です。XORは、マスクが1のビットを反転するので、全ビットが1のマスクを使えば、全ビットが反転します。上の表で見たNOTと同じ結果になります。
ORやANDでは、反転できません。ORでは、元が0のビットを1にはできますが、元が1のビットを0にはできないからです。ANDも、逆の理由で反転できません。「反転は、XORだけが得意」と覚えましょう。
ビットの一部だけを反転したいときは、反転したいところだけを1にしたマスクを使います。たとえば、上位6ビットだけを反転して、下位2ビットを残すなら、マスクは1111 1100(FC)です。下位2ビットのマスクは0なので、XORでは残ります。
倍数の判定とビットの取り出し
2の倍数を2進数で見ると、規則があります。2の倍数は最下位ビットが0、4の倍数は下位2ビットが00、8の倍数は下位3ビット、16の倍数は下位4ビットが、すべて0です。なぜそうなるのかは、2進数の各桁の「重み」を見ると分かります。8ビットなら、重みは右から順に、1、2、4、8、16、32、64、128です。
10進数で、100の倍数かどうかを調べるときは、下2桁が00かを見ますね。100の位より上の桁の重みは、1000、10000、……と、すべて100の倍数だからです。2進数でも同じです。重み8の桁から上(8、16、32、……)は、どれも8の倍数なので、そこにいくつ1があっても、合計は必ず8の倍数になります。つまり、全体が8の倍数かどうかは、残りの下位3ビット(重み4、2、1)の値で決まります。下位3ビットの値は0〜7なので、そこが8の倍数になるのは0のとき、つまり000のときだけです。16の倍数なら、重み16より上が16の倍数なので、下位4ビットが0000かどうかを見ます。
たとえば、40は0010 1000で、下位3ビットが000なので、8の倍数です。42は0010 1010で、下位3ビットが010(=2)なので、8の倍数ではありません。
この規則を使うと、「8ビットの値xが16の倍数か」は、「下位4ビットが全部0か」を調べれば分かります。下位4ビットだけを取り出すには、下位4ビットが1のマスクとANDをとります。その結果が0なら、下位4ビットはすべて0です。
一方、上位4ビットを取り出すマスク(1111 0000)とのANDは、倍数の判定には使えません。上位4ビットだけを見ても、下位4ビットが分からないからです。
もう1つ、パリティビットの例を見ましょう。パリティビットは、通信や記録でのビットの誤りを見つけるための検査用のビットです。たとえば、「最上位をパリティビットとする8ビットの符号」では、下位7ビットがデータです。データだけを取り出すには、7F(0111 1111)とANDをとります。パリティビットだけを取り出すなら、80(1000 0000)とのANDです。
パリティビットの値は、XORで求められます。「偶数パリティ」は、全体で1の個数が偶数になるように、パリティビットを決める方式です。データの7ビットを全部XORすると、「1の個数が奇数なら1」になるので、その値をパリティビットにすれば、全体の1の個数が偶数になります。たとえば、データ1011001は1が4個(偶数)なので、パリティビットは0です。データ1011101は1が5個(奇数)なので、パリティビットは1になります。
排他的論理和の活用
「同じ値を2回XORすると元に戻る」性質は、データの暗号化に使われます。データ(平文)に鍵をXORすると暗号文になり、その暗号文に同じ鍵をXORすると、元の平文に戻ります。
まず、1ビットで確かめておきます。元のビットをA、鍵のビットをKとします。K=1のとき、A=0なら 0⊕1=1、そこにもう一度1をXORすると 1⊕1=0で、元の0に戻ります。A=1なら 1⊕1=0、0⊕1=1で、元の1に戻ります。K=0なら、XORしても値が変わらないので、何回やっても元のままです。XORはビットごとの演算なので、1ビットで成り立つことは、8ビットでもそのまま成り立ちます。8ビットの例を見てみましょう。
XORでつないだ式を解くときは、「順序を入れ替えられる」性質と、「同じ値を2回で消える」性質を使います。たとえば、次の式のaを求めてみます。
順序を入れ替えて、2回出てくる0110を並べると、0110⊕0110=0000となって消えます。残るのは、1010⊕a=0011です。両辺に1010をXORすると、a=0011⊕1010=1001になります。
鍵が複数ある装置も、同じように考えます。入力に、鍵A、鍵B、鍵Cを順にXORして出力を得る装置があるとします。XORは順序を入れ替えられるので、出力は「入力⊕鍵A⊕鍵B⊕鍵C」です。ここで、鍵Bだけを新しい鍵に変えたとき、出力がどう変わるかを考えます。
古い出力と新しい出力を並べてXORすると、入力、鍵A、鍵Cは両方に入っていて、2回ずつ出てくるので消えます。残るのは「旧鍵B⊕新鍵B」だけです。つまり、新しい出力は、古い出力に「旧鍵B⊕新鍵B」をXORした値になります。
入力が1010、鍵Aが0110、旧鍵Bが0011、鍵Cが1100のとき、出力は0011です。鍵Bを0101に変えると、旧鍵B⊕新鍵B=0011⊕0101=0110なので、新しい出力は 0011⊕0110=0101です。実際に 1010⊕0110⊕0101⊕1100 を計算しても0101になり、一致します。
最も右の1だけを残す
ビット列の「最も右にある1」だけを残して、ほかを全部0にする操作は、ビット演算の組合せでできます。手順は3つです。
A=0110 1000で、各段階のビットを並べてみましょう。太字は、注目するビットです。
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |
|---|---|---|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| B=A−1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
| C=A XOR B | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| A AND C | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
1段階目のA−1では、Aの最も右の1(右から4番目)が0になり、その右側の000が111に変わります。それより左の0110は変わりません。10進数で1000から1を引くと999になるのと同じ理屈で、「1つ借りて、右側が全部繰り上がらずに残る」形です。太字の4ビットが、AからBで変化した部分です。
2段階目のAとBのXORでは、異なるビットが1になるので、変化した右の4ビットだけが1になり、左の4ビットは0になります。これがCです。
3段階目では、Cが1の右の4ビットのうち、Aも1のところだけが残ります。Aの右の4ビットは1000で、1なのは最も右の1だけ(それより右は、もともと0)なので、答えは0000 1000になります。
最後の手順では、XORやORではなく、ANDを使うことに注意しましょう。XORやORでは、最も右の1より左側にあるAの1が、そのまま残ってしまうからです。
2の補数との関係
負の数を表す「2の補数」も、論理演算で作れます。2の補数は、「全ビットを反転して、1を足す」ことで求められます。8ビットの正の数nの、負の数−nは、「nとFFのXOR(全ビット反転)」に、1を足した値です。
たとえば、n=22(0001 0110)なら、反転して1110 1001、1を足して1110 1010となります。これは−22を表す8ビットの2の補数です。
論理関数とNAND・NORの万能性
論理関数
入力の0と1の組合せに対して、出力の0か1を決める対応のことを、「論理関数」と言います。AND、OR、XORなどは、どれも論理関数の例です。
論理関数が全部で何種類あるかを数えてみましょう。入力が2つなら、組合せは00、01、10、11の4通りです。この4通りのそれぞれについて、出力を0にするか1にするかを自由に決められるので、決め方は 2×2×2×2=16通り、つまり論理関数は16種類です。入力が3つなら、組合せは8通りで、それぞれに0か1を割り当てるので、2を8回掛けた 2の8乗=256種類になります。
2つの入力の関数を、入力が00、01、10、11のときの出力を左から順に並べた4桁の0と1で表すと、次のようになります。0000から1111までの4桁の並びが16通りあり、それが16種類の関数に対応します。次の表には、そのうちの主なものを載せています。
| 出力の並び | 関数 |
|---|---|
| 0000 | 常に0 |
| 0001 | AND |
| 0110 | XOR |
| 0111 | OR |
| 1000 | NOR |
| 1001 | XNOR |
| 1101 | 「AならばB」() |
| 1110 | NAND |
| 1111 | 常に1 |
NORは「1000」で、00のときだけ1になります。先ほどの表と見比べて、確かめてみましょう。
NANDだけでほかの演算を作る
実は、NANDという演算が1種類あれば、NOT、AND、ORのどれも作れます。コンピュータの回路を作るときは、同じ部品だけで全部を組み立てられるので、とても便利です。作り方を見ていきましょう。
- NOT: 同じ値どうしのNANDは、 なので、否定になります。つまり は、X NAND Xです。
- AND:NANDの結果を、さらに否定すれば、元のANDに戻ります。否定は、上で作った「同じ値のNAND」でできるので、(X NAND Y) NAND (X NAND Y)となります。
- OR: ド・モルガンの法則から、 です。これは「 と のNAND」なので、(X NAND X) NAND (Y NAND Y)となります。
ORの構成が正しいか、真理値表で確かめてみます。
右から2つめと、右端の列が一致しています。「X OR YをNANDだけで表した式はどれか」という問題では、選択肢の式に、X=1、Y=0など具体的な値を代入して、NANDを内側から順に計算し、X OR Yの値と食い違うものを消す方法が、確実です。たとえば、X=1、Y=0のとき、X OR Yは1です。上の構成を代入すると、(1 NAND 1)=0、(0 NAND 0)=1となり、0 NAND 1=1と一致します。
NORにも、同じ性質があります。NORだけで、NOTは「X NOR X」、ORは「(X NOR Y) NOR (X NOR Y)」、ANDは「(X NOR X) NOR (Y NOR Y)」と作れます。NANDの構成の、ANDとORを入れ替えた形になっています。
まとめ
| 項目 | 要点 | 例 |
|---|---|---|
| AND | 両方が1のときだけ1 | 1010 AND 0110 = 0010 |
| OR | 1つでも1なら1 | 1010 OR 0110 = 1110 |
| XOR | 2つが異なるときだけ1 | 1010 XOR 0110 = 1100 |
| NAND・NOR | それぞれAND・ORの否定 | NAND は両方1のときだけ0 |
| AND のマスク(0F) | 下位4ビットを残し、上位4ビットを0にする | B4(1011 0100)→ 04 |
| OR のマスク(F0) | 上位4ビットを1にし、下位4ビットを残す | B4 → F4 |
| XOR のマスク(C0) | 上位2ビットを反転し、残りはそのまま | B4 → 74 |
| XOR の暗号化 | 同じ鍵を2回XORすると元に戻る | 01101001 XOR 10101010 = 11000011(もう一度XORすると01101001) |
練習問題
手順1 与えられたビット列Aを符号なしの2進数と見なし,Aから1を引き,結果をBとする。
手順2 AとBの排他的論理和(XOR)を求め,結果をCとする。
手順3 AとCの [ a ] を求め,結果をAとする。
| ア | 排他的論理和(XOR) |
|---|---|
| イ | 否定論理積(NAND) |
| ウ | 論理積(AND) |
| エ | 論理和(OR) |
解説
「ビット列」とは、0と1を並べたものです。この問題の手順は、「2進数から1を引くと、どのビットが変化するか」を知っていると理解しやすくなります。
10進数で考えてみましょう。1000から1を引くと999になり、右端の0が連続している部分がすべて9に変わって、その左の桁が1つ減ります。2進数でも同じことが起こります。1を引くと、最も右にある1が0になり、その右側に連続していた0がすべて1に変わります(これを「繰り下がり」と言います)。例えば、00101000から1を引くと、00100111になります。
この考え方を使って、例の00101000に手順を当てはめてみます。
| 手順 | 内容 | ビット列 |
|---|---|---|
| 与えられたビット列A | 00101000 | |
| 手順1 B | Aから1を引く | 00100111 |
| 手順2 C | AとBの排他的論理和(XOR) | 00001111 |
| 手順3 A | AとCの [ a ] | 00001000 |
手順2の「排他的論理和(XOR)」は、2つのビットが異なるときだけ1になる演算です。AとBは、最も右の1の位置とその右側のビットだけが異なっているので、Cは「Aの最も右の1の位置から右側がすべて1、それより左はすべて0」というビット列になります。
手順3では、このCを使ってAの「最も右の1」だけを取り出したいので、「どちらも1のときだけ1になる」論理積(AND)を使います。Cで1になっているのは右側の範囲だけで、その範囲でAも1なのは、最も右の1の位置だけです。ほかのビットはすべて0になり、00001000が残ります。
| × ア | AとCの排他的論理和は00100111になり、これは手順1で求めたBと同じ値です。最も右の1だけが残るわけではありません。 |
| × イ | NANDは論理積(AND)の結果を反転させる演算です。ANDの結果の00001000を反転すると11110111になり、ほとんどのビットが1になります。 |
| ○ ウ | AとCの論理積は00001000になり、最も右の1だけが残ります。 |
| × エ | AとCの論理和は00101111になり、Aの1がそのまま残るうえに、Cの1も加わってしまいます。 |
用語リスト
「⭐」は過去に1回出題、「⭐」は2~3回出題、「🌟」は4回以上出題されています。右下の数字「2012」はシラバス初登場年です。「[外]」はシラバス外から出題された用語です。
解説
論理式の否定を扱うときは、ド・モルガンの法則を使います。ド・モルガンの法則とは、「全体の否定をとると、論理積(AND)は論理和(OR)に、論理和は論理積に変わり、それぞれの項が否定される」という規則です。
この問題の式は、2つの括弧の論理積の全体に否定がかかっています。これに上の1つ目の法則を使って分解します。
続いて、それぞれの項に2つ目の法則を使います。否定の否定は元に戻る(二重否定)ことにも注意します。
したがって、元の式は と等しくなります。
念のため、A=1、B=0、C=0の場合で確かめます。元の式は、括弧の中が(0+0)・(1+1)=0・1=0で、その否定は1です。「ア」の式は 1・1+0・0=1 となり、一致します。