論理代数の履歴(No.3)

概要†

コンピュータの世界では0と1だけで構成されています。でも不思議だと思いませんか？たった0と1だけでエロゲもできるコンピュータが動くなんて!　ここではその不思議の入り口を紹介します。もちろんプログラミングにも役立ちますよ。

プログラム上での表記は言語による部分もあり、またif文などの条件式とビット演算とで混乱しやすいので勝手ながら消させていただきました。

↑

実践†

↑

論理代数（ブール代数）の世界†

論理代数の世界は0と1だけで構成されます。プログラミングではtrue(真)やfalse(偽)と表現もされます。

↑

AND（論理積）†

ANDとは日本語でかつといい、与えられた数がすべて1のとき答えは1になります。ANDの記号は&mimetex(\cdot);で表され、&mimetex(A \cdot B);と書きます。&やandと書いたりもしますし、論理学では&mimetex(A \cap B);と書いたりもします。

AとBのすべての組み合わせと&mimetex(A \cdot B);の答えQを表にしたものを真理値表といいます。

真理値表
A	B	Q
0	0	0
0	1	0
1	0	0
1	1	1

↑

OR（論理和）†

ORは1であれば答えが1になります。記号は+ですが、足し算ではありません。1+1=2ではなく、1+1=1です。C言語などでは|と書きます。注意、よく日本語のまたはと例えられます。（日本語のまたははどちらか一方という意味を含む場合もありますが、ORは両方真でも真です。）

真理値表
A	B	Q
0	0	0
0	1	1
1	0	1
1	1	1

↑

NOT（否定）†

NOTは反転とも呼ばれ0なら1、1なら0になります。記号は上にバーを書きます。たとえば&mimetex(a);のNOTは&mimetex(\overline a);や&mimetex(\neg a);と書きます

真理値表
A	Q
0	1
1	0

↑

ANDとORの結合性†

ORよりもANDの方が結合の優先度が強いです。&mimetex(a + b \cdot c);は&mimetex(a + \left( b \cdot c \right));ということです。

↑

XOR（排他的論理和）†

aとbのうちどちらか一方のみが真のとき真となるものをaとbの排他的論理和と言います。記号としては&mimetex(\oplus);で表されます。また、xor ^ を演算子として使ったりもします。

XORはANDとORで表現できます。aとbの排他的論理和の場合は以下のようになります。

&mimetex(a \oplus b = a \cdot \overline{b} + \overline{a} \cdot b);

真理値表
A	B	Q
0	0	0
0	1	1
1	0	1
1	1	0

↑

ド・モルガンの法則†

ド・モルガンの法則というものがあります

#mimetex(\overline{a \cdot b} = \overline a + \overline b)

#mimetex(\overline{a + b} = \overline a \cdot \overline b)

というものです。真理値表を作って確認してみて下さい

↑

交換法則と分配法則†

論理代数にも一般の計算と同様交換法則や分配法則が存在します。

a･b+a･c = a･(b+c)
(a+b)･(c+d) = a･c+b･c+a･d+b･d
a+b+c = (a+b)+c = a+(b+c)
a+b = b+a
a･b = b･a

意味を考えれば当然ですね

↑

式の簡略化†

式によっては表現を簡略化することができます。これができずにif文の条件式がえらいことになっちゃってる人が結構います

&mimetex(a \cdot b + a = a);

aが真または、aが真かつbが真。結局aが真なら真ということになります。

&mimetex(a + \overline a = 1);

aが真またはaが偽。aが真でないときは結局偽なのでこれは結局常に真です。この状態では非常に分かりやすいですが、他の変数が絡んで来るとこの考え方が頭から抜けてしまうことがよくあります。例えば

&mimetex(a + \overline{a \cdot b} = a + b);

aが真または、aが偽かつbが真。これはa+bと同じです。複雑化すればするほど見逃してしまいがちです

&mimetex(a \cdot {\overline b} + a \cdot b + \overline{a} \cdot b = a + b);

&mimetex(\overline{a} \cdot b \cdot c + a \cdot \overline{b} + a \cdot b + \overline{a} \cdot \overline{b} = a + \overline{b} + c);

↑

プログラミングにおける論理代数の扱い†

プログラミングにおいて論理代数は大きく分けて2通りの扱いかたがあります。C言語を例に紹介します

↑

条件式†

if文などの条件式は論理代数で表すことができます。

if (a < b && c == d || !e && f) {
     /* 条件を満たしたときに処理する内容を書く */
}

C言語においては0以外の整数値を真、0を偽として扱います。&&は論理代数のANDの意味を表します。||は論理代数のORで、!はNOTです。少なくともC言語には条件式としてXORはありません
C言語では結合性は&&の方が優先的です。恐らく他の言語も基本的にそのような仕様になっていると思います
条件としては a < b (aがbより小さい)などの条件を書き込むことができます。この演算の結果は真ならば0以外、偽ならば0です。また、eやfのように直接真偽を表すような変数を書き込むこともできます
Javaではif文の条件はboolean型で表されるなど、言語によって何を真とし、何を偽とするかは異なる場合があります

↑

ビット演算†

コンピュータでは全ての値は実際は2進法によっておこなわれています。ここでは8bit同士のbit演算について考えてみましょう

↑

AND†

C言語ではANDのbit演算は以下のようにして行います

z = x & y;

これはxとyのbitごとの論理積をとったものです。表で見てみましょう

x	11110000
y	11001010
z	11000000

xとyが共に1の所だけzが1になっていることが分かります
これは条件式の&&とは違うので注意して下さい。試しに11110000と00001111の論理積をとってみましょう。前者をx, 後者をyとします

x && y x, yは共に0では無いので0以外の何らかの値
x & y  x, yをビットごとに論理積をとると0

↑

OR†

C言語ではORのbit演算は以下のようにして行います

z = x | y;

これは xとyのbitごとの論理和をとったものです。表で見てみましょう

x	11110000
y	11001010
z	11111010

xとyの少なくとも一方が1の所だけzが1になっていることが分かります。これも||とは挙動が異なりますので間違わないように気を付けてください

↑

NOT†

C言語ではNOTのbit演算は以下のようにして行います

y = ~x;

これは xのbitを反転したものです。表で見てみましょう

x	11110000
y	00001111

これも!と間違わないように気を付けましょう

↑

XOR†

C言語ではXORのbit演算は以下のようにして行います

z = x ^ y;

これは xとyのbitごとの排他的論理和をとったものです。表で見てみましょう

x	11110000
y	11001010
z	00111010

xとyのbitの値の異なる部分だけzで1となっていることが分かります

論理代数 の履歴(No.3)

概要†

実践†