ブール代数 | rpn入門(初級編) [講座] | 逆ポーランド電卓の実践ウェブ rpn hacks!

逆ポーランド電卓の実践ウェブ rpn hacks!

逆ポーランド電卓rpnの実践ウェブ   
rpn hacks! アールピーエヌ・ハックスサイトマップ

rpn | 講座 | rpn入門 | rpnの使い方を基本から応用まできちんと学習。

HOME > 講座 > rpn入門 > 初級編 > ブール代数 hatena yahoo buzzurl livedoor del.icio.us nifty newsing twitter facebook rss ソーシャルブックマーク

ブール代数

コンピュータ的な考え方

 ブール(1815~1864)は論理学を数学のように全て記号で表わしました。自然言語の「そして」「または」「でない」をそれぞれ「AND」「OR」「NOT」と表わしたのですが、これはとても画期的なことでした。

論理学における真を1、偽を0と表現し、AND, OR, NOTで表現します。例えば、ブレーキを踏んでキーを回さないとエンジンスタートしない仕組みは、以下のように簡単明瞭に表現できます。

ブレーキを踏んでいる/いないをPで表わし、キーを回す/回さないをQで表わします。すると、P AND Qが1の時、エンジンがかかることになります。これら論理演算の真理値表を以下に示します(後の説明のためにXORも示す)。なお、rpnではANDは&、ORは:、XORは;、NOTは~と表記します。

  P Q|P & Q  P Q| P : Q  P Q| P ; Q  P | ~P
  ---+-----  ---+------  ---+------  --+---
  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進として、それぞれ計算してみましょう。

  >rpn 1011b 1fh &     --> 1011bと1fhのAND(論理積)
  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進で得てみましょう。

  >rpn 1011b 11111b ; b
  10100b


これは、以下のようにそれぞれの桁の論理和を計算していることに等しいのです。

             0 1 0 1 1
          ;) 1 1 1 1 1
           ------------
             1 0 1 0 0


結果、10100bが10進では20になるわけです。

4番目の例のNOTに関しては説明が難しくなりますが、rpnでは2進数を最大で、「11111111111111111111111111111111」まで表現できます。そして、2の補数表現では、この値は-1になります。例題の演算で得られた値は、1の補数だから1と0がきれいに以下のように反転するわけです。

          ~) 0 .. 0 1 0 1 1
           ----------------
             1 .. 1 0 1 0 0


これは10進では-12になります(10進へは2の補数表現として変換することに注意)。この講座はコンピュータにおける数値表現の説明を行なうわけではないので、これ以上の説明は省きますが、詳しく知りたい人は情報科学の書籍で勉強してみてください。

シフトは右に左に

 さて、最後の論理演算について説明しましょう。それは、算術右シフト「]」と算術左シフト「[」です。これは数値を2進数で考えて、右や左に指定された数だけシフトするものです。

  >rpn 1010b 2 ]    ⇒ 1010bを右に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にする式。
…………………………………………………………………………………………

答えはこちらLinkIcon

警告文字で作られた図表や式が崩れることがあります。ブラウザによっては固定幅フォントをMSゴシックにするときれいに表示されます。それでも崩れる場合は図表や式をメモ帳にコピー後、閲覧下さい。

警告rpn試用版と標準版(2kリビジョン)はダブルクォートで囲ってください。

rpn 1 2 + ⇒ rpn "1 2 +"
rpn 1 -c foo ⇒ rpn "1" -c "foo"

ダブルクォートは省略できることが多いのですが、慣れない間は囲んだほうが無難です。なお、本ウェブサイトの記事ではrpn標準版(98リビジョン)を使用しているため囲っていません。詳しくは技術サポートの「rpn TIPS参照ください。

注意rpnの障害情報はこちら

警告rpn試用版の場合、複雑なプログラムや処理時間のかかるプログラムの一部には動作しないものがあるかもしれません。あくまで無料提供であることを勘案・了承ください。rpn標準版は、すべてのプログラムが動作します。