離散数学の基礎

要点と定義

IPAシラバスVer.7.2の「離散数学」では、基数と数値表現、算術演算と精度、集合と命題、論理演算の基本法則を扱います。基数は数を表す位取りの基準で、2進数・8進数・10進数・16進数などがあります。数値表現には補数表現や固定小数点数・浮動小数点数があり、演算では表現可能な範囲や誤差にも注意します。

2進数の加算は、各桁を足し、2以上になった分を次の桁へ繰り上げます。例えば、1011₂＋0110₂は、右端から計算すると10001₂です。2進数から10進数への変換では、各桁にその位の重みを掛けて合計します。シフト演算や丸め・打切り、オーバーフローなども、コンピュータ上の算術演算を考える基本です。

集合では、和集合はどちらかに属する要素、積集合は両方に属する要素、補集合は全体集合Sのうち対象集合に属さない要素を表します。差集合X−YはX∩Ȳと等しいため、Ā−BはĀ∩B̄です。補集合は、どの全体集合を基準にするかを明らかにして扱います。過去の出題で扱った補集合と差集合の関係を判断する際も、この定義を順に適用します。

論理演算では、論理積は両方が真のとき真、論理和は少なくとも一方が真のとき真、否定は真偽を反転します。排他的論理和（XOR）は入力が異なるとき真で、片方の入力を反転すると、もう片方の状態によらず出力も反転します。入力A・Bの順を00、01、10、11とすると、XORの出力は0、1、1、0です。これは過去の出題で階段スイッチの動作条件を論理演算に対応させた補足です。

XORの相補演算は等価演算（XNOR）です。各入力の組で結果を否定するので、入力が等しいとき真、異なるとき偽になります。XORとXNORの真理値は各行で互いに否定です。この関係を用いると、候補の演算が相補かどうかを真理値で確かめられます。

論理式は真理値表やカルノー図で確認・簡約できます。論理積を「・」、論理和を「＋」、否定を上線で表すと、回路の各段を式に置き換えてからまとめられます。過去の出題で扱った回路では、上段が¬A・B、下段がA・B、出力が(¬A・B)＋(A・B)となり、分配則でBに簡約できます。

カルノー図では、隣り合うセルをまとめ、グループ内で変化する変数を項から消します。行・列をグレイコード順に並べると、左右端も隣接します。過去の出題で扱った図では、AB=00かつD=0の端の2セルがĀ・B̄・D̄、B=1かつD=1の2行×2列がB・Dにまとまり、その和が図の1の配置を表します。

適用条件と例

位取り表現の変換では、各位の重みと基数を取り違えないようにします。ビット単位のANDで特定のビットだけを残す方法は、マスクの各桁が何を選ぶかを確認してから使います。過去の出題で扱った補足では、nが0から255の範囲にあり、n+1を255とのANDで下位8ビットに制限すると、nが255未満ならn+1、nが255なら0になります。これは特定の範囲とマスクに基づく処理例で、任意の値にそのまま使えるとは限りません。

要素数を数えるときは、条件を満たす相手の個数を一方の添字ごとに数え、最後に合計します。例えばiごとにjが0からi−1までなら、jはi個あります。過去の出題の範囲では、i=0から99までの個数を合計して0+1+…+99=99×100÷2=4,950となります。端点と順序を条件どおりに数えることが大切です。この三角形領域の個数計算自体がシラバスに個別列挙されているとは限らず、離散数学の基礎的な数の扱いに関連する応用例です。