コンピュータの世界では0と1だけで構成されています。でも不思議だと思いませんか？たった0と1だけでエロゲもできるコンピュータが動くなんて! ここではその不思議の入り口を紹介します。もちろんプログラミングにも役立ちますよ。
プログラム上での表記は言語による部分もあり、またif文などの条件式とビット演算とで混乱しやすいので勝手ながら消させていただきました。
George Bool という英国の数学者がいました。彼は論理代数学を作ったので、そこから真偽値の事をブール代数（boolean）など呼びます。電気廻路で論理代数を遣う系を論理廻路と云いますが、コンピュータが0,1のみを扱うのは偶然の産物です。
コンピュータの祖と云えば、かつては亡命ハンガリー系米国人 John von Neumann の Neumann（ノイマン）型Computer とされていました。しかし最近ではそれより早く開発されていた、英国の若き数学者 Alan Turing が第二次大戦中にドイツ軍のエニグマを解読するために考案した、Turing Machine がコンピュータの祖とされます。エニグマの解読機は BOM と呼ばれていたそうですが、文字通りの所謂総当たり式の解読法、つまり逐次命令を実行させていたわけです。Turing Machine は最近になった公表されたため、長らくコンピュータの祖はNeumannとされたわけですが、往々にして技術や発見は来るべき時、同時に多数の研究者によって開発・発見されるのです。
現在のコンピュータは多く CPU を有してます。この CPU は電卓を開発する過程で開発されました。マイクロプロセッサ（Microprocessor）の誕生です。その開発者が嶋正利という日本人なのですね。彼はもともとマイコン（Microcomputer）の生産を依頼する形で渡米してました。ところが米国に技術者が居ない、仕方が無いので彼が開発する運びになった。論理廻路については既に知られてましたが、論理廻路で「計算」を実装するのが一苦労。嶋氏は十進法で実装を行っていたそうですが、なかなか上手く行かないよと悩んでいると、ある日二進数はどうかと云われて、二進数でやると上手く行った。これがマイクロプロセッサと呼ばれるようになった。今のコンピュータが0,1のみを扱う、というのは実はこういう経緯があったわけです。今の Intel のマイクロプロセッサはこの系譜に連なる物ですね。ちなみにこの発明も同時期に多数開発されたました。
なお最近では IBM の POWER（Performance Optimization With Enhanced RISC）なんかが十進数で計算できる廻路を積んでるそうです。ここではその初歩の初歩、論理代数の考え方から始めましょう。
論理代数の世界は0と1だけで構成されます。プログラミングではtrue(真)やfalse(偽)と表現もされます。
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は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は反転とも呼ばれ0なら1、1なら0になります。記号は上にバーを書きます。たとえば&mimetex(a);のNOTは&mimetex(\overline a);や&mimetex(\neg a);と書きます
| 真理値表 | |
| A | Q |
| 0 | 1 |
| 1 | 0 |
ORよりもANDの方が結合の優先度が強いです。&mimetex(a + b \cdot c);は&mimetex(a + \left( b \cdot c \right));ということです。
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);
というものです。真理値表を作って確認してみて下さい
論理代数にも一般の計算と同様交換法則や分配法則が存在します。
意味を考えれば当然ですね
式によっては表現を簡略化することができます。これができずにif文の条件式がえらいことになっちゃってる人が結構います
#mimetex(a \cdot b + a = a);
aが真または、aが真かつbが真。結局aが真なら真ということになります。
#mimetex(a + \overline a = 1);
aが真またはaが偽。aが真でないときは結局偽なのでこれは結局常に真です。この状態では非常に分かりやすいですが、他の変数が絡んで来るとこの考え方が頭から抜けてしまうことがよくあります。例えば
#mimetex(a + \overline {a + b} = a + \overline b);
aが真または、aまたはbが偽(⇔aが偽かつbが偽)。これは&mimetex(a + \overline 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演算について考えてみましょう
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
C言語ではORのbit演算は以下のようにして行います
z = x | y;
これは xとyのbitごとの論理和をとったものです。表で見てみましょう
| x | 11110000 |
| y | 11001010 |
| z | 11111010 |
xとyの少なくとも一方が1の所だけzが1になっていることが分かります。 これも||とは挙動が異なりますので間違わないように気を付けてください
C言語ではNOTのbit演算は以下のようにして行います
y = ~x;
これは xのbitを反転したものです。表で見てみましょう
| x | 11110000 |
| y | 00001111 |
これも!と間違わないように気を付けましょう
C言語ではXORのbit演算は以下のようにして行います
z = x ^ y;
これは xとyのbitごとの排他的論理和をとったものです。表で見てみましょう
| x | 11110000 |
| y | 11001010 |
| z | 00111010 |
xとyのbitの値の異なる部分だけzで1となっていることが分かります
論理廻路には限界があります。電気廻路は論理代数と相性がいいのですが、所謂量子コンピュータは相性がよくありません。NTTが量子コンピュータのAND・OR廻路の開発に成功した、何てのがニュースになったのはいかに開発がむづかしいかを物語る物です。
散々論理代数を扱いましたが、実際に工学的な開発をすすめるにつれ、上手くいかなくなります。Micro と Macro の違いです。日本の物理学者江崎玲於奈がトンネル効果（Quantum tunnelling）をひき起こす物質を発見し、ダイオードは大いに発展することになりました（負性抵抗の発見）。ちなみに高校物理で扱うと思いますがダイオードにもいろいろ方式があり、一般にはPN接合ダイオードと呼ばれます（註：P型半導体とN型半導体があって、半導体に不純物を加えると自由電子が増えたり足りなくなったりする。この二種の半導体を接合する事により、自由電子の多寡で電位差が生じ、さまざまな工学的特性を有するようになる。ダイオードはこの組合せや素材で特性が変わる）。
トンネル効果はQuantum（量子）、正確に訳すと量子トンネル効果です。ここでいう Quantum とは、所謂量子コンピュータを開発する上で問題になる粒子が量子的振る舞いをすること、これを理解することが重要になります。CPU が細分化してゆくにつれ、「漏電」することがわかっています。トンネル効果によれば、ごくごく薄い遮蔽物を光子や電子は透過します。だから絶縁体が原子一列程度だと「漏電」することがあるわけ。量子コンピュータが高速であるといわれる所以は、この透過する性質、不確定性原理により齎される自然法則を論理に応用するからです。従来の論理廻路が高速化されるというよりは、抜け道が見つかったので早く到達できますよ程度の発想です。
論理廻路はあくまで現象を論理に応用した物にすぎません。MacroからMicroへと現象が変われば、論理も変わる事になります。プログラムの論理も、そのうち古典的論理だとか呼ばれる日がくるのかもしれません。