ブール代数
コンピュータ的な考え方
ブール(1815～1864)は論理学を数学のように全て記号で表わしました。自然言語の「そして」「または」「でない」をそれぞれ「AND」「OR」「NOT」と表わしたのですが、これはとても画期的なことでした。
論理学における真を1、偽を0と表現し、AND, OR, NOTで表現します。例えば、ブレーキを踏んでキーを回さないとエンジンスタートしない仕組みは、以下のように簡単明瞭に表現できます。
ブレーキを踏んでいる/いないをPで表わし、キーを回す/回さないをQで表わします。すると、P AND Qが1の時、エンジンがかかることになります。これら論理演算の真理値表を以下に示します(後の説明のためにXORも示す)。なお、rpnではANDは&、ORは:、XORは;、NOTは~と表記します。
---+----- ---+------ ---+------ --+---
0 0| 0 0 0| 0 0 0| 0 0 | 1
0 1| 0 0 1| 1 0 1| 1 1 | 0
1 0| 0 1 0| 1 1 0| 1
1 1| 1 1 1| 1 1 1| 0
このような、0と1で表現するブール代数はコンピュータ技術には欠かせないものです。論理学だけでなく、デジタルのハードウェア回路もブール代数で表現できます。
rpnでブール代数を扱う
rpnでは、この論理演算を2進、8進、10進、16進の数値に対して適用することができます。例えば、以下のように2進の1011bと16進の1fhを論理演算することができます(NOTは1011bを演算)。結果を10進として、それぞれ計算してみましょう。
11
>rpn 1011b 1fh : --> 1011bと1fhのOR(論理和)
31
>rpn 1011b 1fh ; --> 1011bと1fhのXOR(論理差)
20
>rpn 1011b ~ --> 1011bのNOT(1の補数)
-12
このように、ブール代数も逆ポーランド記法で書くので、論理演算子は数値の後に配置されます。
さて、上記の式で何故、結果が11、31、20、-12のようになるのでしょうか。答えは簡単です。例えば3番目の例のrpn 1011b 1fh ;と等価な式を、全て2進で表現して、結果も2進で得てみましょう。
10100b
これは、以下のようにそれぞれの桁の論理和を計算していることに等しいのです。
;) 1 1 1 1 1
------------
1 0 1 0 0
結果、10100bが10進では20になるわけです。
4番目の例のNOTに関しては説明が難しくなりますが、rpnでは2進数を最大で、「11111111111111111111111111111111」まで表現できます。そして、2の補数表現では、この値は-1になります。例題の演算で得られた値は、1の補数だから1と0がきれいに以下のように反転するわけです。
----------------
1 .. 1 0 1 0 0
これは10進では-12になります(10進へは2の補数表現として変換することに注意)。この講座はコンピュータにおける数値表現の説明を行なうわけではないので、これ以上の説明は省きますが、詳しく知りたい人は情報科学の書籍で勉強してみてください。
シフトは右に左に
さて、最後の論理演算について説明しましょう。それは、算術右シフト「]」と算術左シフト「[」です。これは数値を2進数で考えて、右や左に指定された数だけシフトするものです。
2
>rpn 1010b 2 [ ⇒ 1010bを左に2つシフト
40
最初の例で説明すると、1010bを右に1つシフトすると101b、もう1つシフトして10b。10bは10進で2です。次の例も1010bを左に1つシフトすると10100b、もう1つシフトして101000b。101000bは10進で40となります。ちなみに、「rpn 100 2 *」と「rpn 100 1 [」は同じ値になりますね。
コンピュータは数字、文字、絵、音…全てを0と1のバイナリで表現します。それらをAND/OR/XOR/NOTといった論理演算で処理、加工しています。コンピュータの画面に表示される文字、絵、コンピュータから流れる音楽、これら全てが実は0と1の集まりであり、論理演算の結果と言えます。
以下を逆ポーランド式に変換せよ。
(1) 論理演算子で10進数の数値「123」を2倍する式。
(2) 論理演算子で10進数の数値「123」を4分の1にする式。
…………………………………………………………………………………………
/