【離散数学】2進数、基数、数値表現、演算精度、集合、ベン図、論理演算、命題

離散数学(2進数、基数、数値表現、演算精度、集合、ベン図、論理演算、命題など)について解説します。

【進数】2進数、10進数、16進数

用語 2進数
MSB Most Significant Bit(上位ビット)。「1000 0110 1101 0110」の上位4ビットというと「1000」を指します。
LSB Least Significant Bit(下位ビット)。「1000 0110 1101 0110」の下位4ビットというと「0110」を指します。
ビットシフト ビットシフト演算とは、桁を左右にシフトさせる演算です。左に移動する場合を「左シフト演算」、右は「右シフト演算」といいます。
カルノー図法 表を使って論理式を簡単化する方法です。
BCDコード 10進数(0~9)に対応した4ビットの2進数(0000~1001)で10進数の各桁を表現する方法です.(Binary Coded Decimal code:2進化10進コード)
ゾーン10進数 BCDコードでは、4ビットで10進数の1桁を表現していましたが、これを8ビットにしたものです。
パック10進数 10進数2桁を1バイトで表したものです。数値部はBCDコードを使って表し、最下部に符号部を追加します。偶数桁の場合符号部を足すと2桁にならないので先頭に0を追加します。

【ブール代数】

性質 式1 式2 性質の解説
単位元 A+1=1 A·1=A ブール代数では1が単位元です。命題変数と1との論理和(OR)は1であり、論理積(AND)はその命題変数と同一です。
零元 A+0=A A·0=0 ブール代数では0が零元です。命題変数と0との論理和(OR)はその命題変数と同一であり、論理積(AND)は0です。
補元 A+A=1 A·A=0 命題変数とその否定の命題変数は補元の関係にあるという。命題変数とその補元との論理和(OR)は1であり、論理積(AND)は0です。
交換律 A+B=B+A A·B=B·A 論理和(OR)の演算または論理積(AND)の演算において、それぞれの命題変数を交換しても同じです。
分配律 A+(B·C)=(A+B)·(A+C) A·(B+C)=(A·B)+(A·C) 複数の命題変数の項からなる論理演算の組み合わせにより、項を分配することができます。
結合律 A+(B+C)=(A+B)+C A·(B·C)=(A·B)·C 論理和(OR)の演算または論理積(AND)の演算において、それぞれの命題変数の計算の優先順位(結合)を変えても同じです。
吸収律 A+(A·B)=A A·(A+B)=A 複数の命題変数の項からなる論理演算の組み合わせにより、項を吸収することができます。
ド・モルガンの法則 A+B=A·B A·B=A+B 複数の命題変数の論理積(AND)全体の否定(NOT)は命題変数それぞれの否定(NOT)の論理和(OR)と等しく、複数の命題変数の論理和(OR)全体の否定(NOT)は命題変数それぞれの否定(NOT)の論理積(AND)と等しい。このことは否定(NOT)と組み合わせることで論理和(OR)と論理積(AND)が変換可能ですことを示している。
二重否定 A=A 命題変数の否定(NOT)の否定(NOT)は、元に戻ってその命題変数と同一です。
べき等 A+A=A A·A=A 同じ命題変数同士の論理和(OR)あるいは論理積(AND)は、その命題変数と同一です。

(1)   \begin{eqnarray*} \overline{(A\land B)} = \overline{A}\lor \overline{B}\\ \overline{(A\lor B)} = \overline{A}\land \overline{B}\\ \end{eqnarray*}

【基数】

変換 概要
小数(16進数)→分数(10進数) 16進数の小数を10進数で表すと小数第1位が1/16、小数第2位が(1/16^2=)1/256というように桁が小さくなるごとに1/16ずつ小さくなる

【数値表現】

負の整数表現には主に以下の3種類があります。

種別 概要
1の補数による表現 ●1の補数:全ビットを反転
2の補数による表現 ●2の補数:全ビット反転し、さらに1を加算(桁上がりさせる)
●減算処理を負数の作成と加算処理で行える
●nビットで表現できる整数の範囲は -2^{n-1} ~ 2^{n-1}-1
絶対値に符号を付けた表現 左端ビットが0の場合は正、1の場合は負

【演算精度】桁落ち, 丸め誤差, 情報落ち, 打ち切り誤差

種別 概要
桁落ち 絶対値の差が非常に小さい2つの値の差を求めたとき、仮数部の大半が打ち消しあい、計算結果の有効桁数が少なくなることによって生じる誤差。
丸め誤差 指定された有効桁数で演算するために切捨て、切上げ、四捨五入などで下位の桁を削除するときに発生する誤差。
情報落ち 絶対値の非常に大きな数値と小さな数値の加算や減算を行ったとき、小さい数値が計算結果に反映されないことによる誤差。
打ち切り誤差 無限級数で表される数値の計算処理を有限項で打ち切ったことによって発生する誤差。

【集合】

【ベン図】

【論理演算】

XOR回路

XOR回路には、特定のビットと1でXORをとると、そのビットを反転できます。

X Y 出力
0 0 0
0 1 1
1 0 1
1 1 0

【命題】

【情報処理入門】テクノロジ系、マネジメント系、ストラテジ系、資格試験
情報処理の基礎知識(テクノロジ系、マネジメント系、ストラテジ系)や資格試験についてまとめました。なお、情報処理技術者試験の出題分野別(テクノロジ系、マネージメント系、ストラテジ系)に各項目を整理しています。そのため、ITパスポート、基本情...

コメント

タイトルとURLをコピーしました