離散数学の基礎

要点と定義

離散数学は、コンピュータが扱う数や論理の基礎を扱います。この節では、選べる状態の数え方、論理演算と論理回路、2進表現の読み方を結び付けます。

組合せの数え方と容量

互いに独立した選択を順に行うとき、全体の数は各段階の選択数を掛けて求めます。たとえば、各桁に26種類の文字を使い、桁数が3桁なら、コードは最大で26×26×26＝17,576通りです。必要な人数以上の異なるコードを用意できる桁数を選びます。顧客数が毎年一定の割合で増えるなら、年ごとの増加率を掛けて将来の人数を見積もります。8,000人が毎年20％増える例では、3年後は8,000×1.2³＝13,824人です。2桁の676通りでは足りず、3桁の17,576通りなら足ります。

最短経路のように、途中の点を経由する経路を数える場合、経由点までの経路と、そこから目的地までの経路をそれぞれ数えて掛け合わせます。たとえば、一方の区間で右に2回、上に2回進むなら、4歩のうち上に進む2歩の位置を選ぶので6通りです。次の区間が右3回、上2回なら、5歩のうち上2歩の位置を選ぶので10通りです。経由点を通る全経路は6×10＝60通りです。これは、各区間の動きが組み合わさって一つの経路になるためです。

論理演算と真理値表

命題や論理回路の入力は、真偽を表す0と1で扱えます。AND（論理積）は両方が1のときだけ1、OR（論理和）は少なくとも一方が1なら1です。NOT（否定）は0と1を反転します。NANDはANDの結果を反転したもの、NORはORの結果を反転したものです。XOR（排他的論理和）は入力が異なるときに1、同じときに0になります。これらの規則を入力の全組合せに当てはめた一覧が真理値表です。

NANDだけでもNOTやORなどを構成できます。X NAND XはNOT Xです。したがって、(X NAND X) NAND (Y NAND Y)は、NOT XとNOT YのANDを反転した形で、ド・モルガンの法則によりX OR Yになります。式の見た目だけで判断せず、各段の出力を真理値表で確かめるのが確実です。

3入力の多数決回路は、入力のうち2つ以上が1なら出力が1です。これは「AとBがともに1」「BとCがともに1」「CとAがともに1」のいずれかが成り立つことと同じです。各組のANDを取り、その結果をORでまとめれば条件を表せます。

1桁の2進数を足す半加算器は、和の下位桁と桁上がりを別々に出力します。下位桁は入力が異なる場合に1なのでXOR、桁上がりは両方が1の場合にだけ生じるのでANDです。たとえば1＋1は2進数で10となり、下位桁は0、桁上がりは1です。

一つの論理回路を複数のゲートで組むときは、中間出力も含めて各入力の結果を追います。NANDと別のゲートの出力を最後にANDへ入れる回路では、別のゲートをORにすると、入力00、01、10、11に対して出力は順に0、1、1、0となり、XORを実現できます。

論理演算は、重み付きの和としきい値でも表せます。入力X、Yに重みWx、Wyを掛けて足し、合計がしきい値T以上なら1、未満なら0を出す方式です。重みがそれぞれ0.5の場合、ANDには入力11の合計1だけが届くようにTを0.5より大きく1以下にします。NANDには入力00、01、10では届き、入力11では届かないしきい値を選びます。重みが負なら、入力が増えるほど合計が小さくなる場合もあります。全入力を代入して条件を確かめることが必要です。

2の補数と下位ビット

負数を2の補数で表す固定幅の2進数では、下位ビットは値を一定数で割った余りに関係します。下位2ビットが11なら、表現された整数は4で割ると3と同じ剰余類に属します。ただし、負数の余りをどう定義するかは除算規則に依存します。商を絶対値の小数点以下切捨てで求める規則では、たとえば−5を4で割る商は−1、余りは−1です。したがって「余りが常に3」とは言えず、正負と指定された除算規則を確認します。

適用条件と例

コードの容量を計算するときは、各桁で使える記号の種類数を基数として、桁数分だけ掛けます。各桁で26種類を使う3桁コードなら26³通りです。ここでは桁ごとの選択を独立に行え、同じコードを複数人に割り当てない前提です。利用可能なコードの一部を予約する場合や、先頭に使えない文字がある場合は、その制約を反映して容量を数え直します。必要数を超える最小の桁数を選びます。