ITの基礎知識|ITパスポート・基本情報

【離散数学】の記事一覧

論理演算

2017.08.31

この記事での学習内容 ITパスポート  基本情報  応用情報

論理式の表現,論理演算,ド・モルガンの法則などの基本法則,真理値表,カルノー図の 手法を理解する。

用語例: 否定,論理和,論理積,排他的論理和,否定論理和,否定論理積,論理関数,分 配則

論理演算

命題の真偽によって演算結果を表すことを論理演算といいます。
基本となるものに「否定(NOT)」「論理積(AND)」「論理和(OR)」があります。

演算意 味
否定1つの命題が「~ではない」と逆になる(NOT)
論理積2つの命題が「~かつ~」の関係(AND)
論理和2つの命題が「~または~」の関係(OR)

論理演算はコンピュータと縁の深いモデル化の技法です。
AND、OR、NOTで複数の命題を組み合わせれば、どんな複雑な論理回路も作ることが出来ます。
また、データ間の関係も論理式に置き換えると整理できるので、プログラミングやデータベースの構築に欠かせない理論です。

否定(NOT) 、論理積(AND)、論理和(OR)

集合の論理演算は、リレーもしくは半導体回路を使った電子回路で実現することが出来ます。
真理値表のAとBを入力に見立てて、その真、偽の状態によって論理和の真理値表と同じ結果を出力する回路をOR回路、論理積と同じ結果を出力するものをAND回路、入力の否定を出力するものをNOT回路といいます。

 MIL記号ベン図真理値表
Aの否定
AとBの論理積
AとBの論理和

それぞれの回路は回路図上で以下の図のような記号(MIL記号)を使って表します。
NAND回路とNOR回路は、それぞれAND回路、OR回路にNOT回路を繋いだものとなります。

これらの回路を組み合わせることで、非常に複雑な論理式や機能を電子回路で実現することが出来ます。実際、コンピュータ内部で足し算やシフト演算を行うALU、命令デコーダ、タイミング制御回路、レジスタやメモリ(DRAMを除く)なども全て論理回路で構成されています。

また、基本となる論理演算を組み合わせたものもよく利用されます。代表的なものは、「否定論理和(NOR)」「否定論理積(NAND)」「排他的論理和(XOR)」です。

論理演算の一般的な法則

2つの命題を使った論理演算には、幾つかの法則が成り立ちます。

交換の法則:

結合の法則:

分配の法則:

復元の法則:

ド・モルガンの法則:

ド・モルガンの法則を始めとする、論理演算の各種の法則は、複雑な論理式を簡略化したり、別の式に変換したりする時に利用できます。

これは、プログラムの開発において、判定条件が複雑になった時、評価する式を簡略化したり、デジタル回路を設計する時に、同じロジックの回路を少ない部品点数で設計し直したり、と言った場面で役立ちます。

カルノー図法

カルノー図法は真理値表でパターン数が増えて見づらいときなど、論理式を簡略化するための図法。下記のような変数が3つ以上の式で、論理積の項を論理和した形(積和形)の場合に使いやすいとされている。

上記の式をカルノー図で表した例

 

集合と命題

2017.08.31
この記事での学習内容 ITパスポート  基本情報  応用情報集合,命題,ベン図の手法と考え方を理解する。用語例: 和集合,積集合,補集合,部分集合,真,偽,命題論理集合集合とは、同じ属性を持つ要素の集まりのことです。集合はよく「ベン図」で表されます。要素全体の集まりを四角で表し、そのうち集合に含まれる要素を色付きの円で示します。この時、集合に含まれない円の外側のことを補集合とい...

Read more...

この記事での学習内容 基本情報 応用情報加減乗除,表現可能な数値の範囲,シフト演算,演算精度(誤差とその対策)など,コ ンピュータでの算術演算を理解する。用語例: 論理シフト,算術シフト,桁落ち,情報落ち,丸め,打切り,オーバフロー(あ ふれ),アンダフロー,単精度,倍精度シフト演算引き算は2の補数を使うと足し算で同じ計算が出来ましたが、掛け算や割り算の場合はどうでしょうか。例...

Read more...

この記事での学習内容 ITパスポート 基本情報 応用情報小数の表現を理解する。用語例: 固定小数点数,単精度浮動小数点数,倍精度浮動小数点数,仮数,指数小数の表現方法の種類小数の表現方法には固定小数点数と浮動小数点数があります。また、浮動小数点数には、単精度浮動小数点数と倍精度浮動小数点数などがあります。固定小数点数コンピュータで負の数を含む整数の数値データを扱うときは、固...

Read more...

この記事での学習内容 ITパスポート 基本情報 応用情報負の数の表現(補数表現)を理解する。用語例: BCD (Binary Coded Decimal:2 進化 10 進),パック 10 進数2進数における表現の問題点整数の場合は桁数が多くなる程度ですが、小数の場合はそもそも表現できる数が少ないため、どうしても「誤差」が生じてしまいます。例えば、10進数の 0.75 は、2進...

Read more...

基数

2017.08.21
この記事での学習内容 ITパスポート 基本情報 応用情報2 進数,8 進数,10 進数,16 進数,n 進数の表現,2 進数と 10 進数などの基数の変換手法 を理解する。記数法私たちが一般的に数値を扱うときには0~9までの数字を使う、「10進法」を用いています。 一方で通信やコンピュータの分野では「2進法」「8進法」「16進法」などが使われます。10進法では0~9までの数字を...

Read more...

離散数学とは

2017.08.08
離散数学とは離散数学(りさんすうがく、英語:discrete mathematics)とは、原則として離散的な(言い換えると連続でない、とびとびの)対象をあつかう数学のことである。有限数学あるいは離散数理と呼ばれることもある。 グラフ理論、組み合わせ理論、最適化問題、計算幾何学、プログラミング、アルゴリズム論が絡む[1]応用分野で、その領域を包括的・抽象的に表現する際に用いられることが...

Read more...