離散数学の集合・論理・数値表現

要点と定義

集合では、全体集合を定めてから補集合を考えます。補集合は全体集合のうち対象の集合に属さない要素、和集合は少なくとも一方に属する要素、積集合は両方に属する要素です。差集合 A−B は「Aに属し、Bには属さない」要素なので、A∩B̅ と表せます。二つの集合のどちらにも属さない要素は A̅∩B̅ で、全体集合から A∪B を除いたものと同じです。補集合の和 A̅∪B̅ は「少なくとも一方に属さない」要素も含むため、両方に属さない集合とは区別します。

論理演算は、真偽値の組合せから結果を決めます。論理積は両方が真のとき真、論理和は少なくとも一方が真のとき真です。排他的論理和は入力が異なるとき真、等価演算は入力が同じとき真になります。否定論理積（NAND）は論理積の否定、否定論理和（NOR）は論理和の否定です。ド・モルガンの法則では、和全体の否定を否定同士の積に、積全体の否定を否定同士の和に変換します。真理値表で全ての入力組合せを確かめると、演算や回路の出力を取り違えにくくなります。

カルノー図は、論理関数が真となるセルを隣接関係に沿ってまとめ、簡単な論理式にする方法です。まとめた範囲で値が変わらない変数を項に残し、変化する変数を省きます。行や列の並びによっては、図の左右端も隣り合うセルとして扱います。

数値表現では、基数、桁ごとの重み、ビット幅、符号表現を確認します。十進数を二進数に直すときは、二で繰り返し割った余りを最後から並べます。例えば十進数の二十六は、二進数で一一〇一〇です。固定ビット幅の符号付き二進数では表現可能な範囲が決まっており、その範囲を外れる演算結果は表せません。過去の出題で扱った補足として、16ビット符号付き2の補数の範囲は−32,768から32,767です。この範囲内の異符号の二数を加えると、和は二数の間に収まるため範囲外になりません。

ビットごとのANDは、対応する桁が両方1のときだけ1を残します。下位八ビットが全て1のマスクとANDを取ると、上位の桁を除いて下位八ビットを取り出せます。例えば十進数の二百五十六を二進数で表すと一〇〇〇〇〇〇〇〇で、これを二進数の一一一一一一一一とANDするとゼロになります。この性質は、八ビットの値を一つ進め、上限を超えたらゼロに戻す計算にも使えます。

適用条件と例

利用者全体をS、貸出中の人をA、予約中の人をBとすると、貸出も予約もしていない人は A̅∩B̅ です。A̅∪B̅ には、貸出中だが予約中ではない人なども含まれます。問題文で「両方に該当しない」のか「少なくとも一方に該当しない」のかを読み分けて、積集合か和集合かを決めます。

論理式や回路を調べるときは、入力の組合せごとに途中の出力も追います。例えばNAND素子に同じ信号を二つ入力すると、その信号の否定が得られます。段ごとの値を書けば、回路全体がどの論理演算になるか確かめられます。カルノー図では、まとめたセルが全て真であること、隣接セルの共通条件だけを式に残していることを確認します。図の端をまたぐまとめができる配置かどうかも見ます。