このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ
  • 追加された行はこの色です。
  • 削除された行はこの色です。
  • 数式記法 へ行く。

*目次 [#b43e3807]

#contents


*中置記法 [#m004bf3b]

 ''中置記法''とは、2項演算*をx*yのように表す方法のことである。人間が一般的に計算するときはこの手法が使われている。しかしコンピュータにとってみれば、この手法が最善とはいえない。なぜなら中置記法だと数式の表現において括弧を用いないと数式の解釈が曖昧になってしまうからだ。一方、次の紹介する前置記法や後置記法だと括弧がなくても任意の数式が表すことができる。


*前置記法 [#b9cd601f]

 *xyのように書く手法を''前置記法(ポーランド記法)''という。ポーランドの論理学者ルカシェヴェッツによってちなんで名付けられた。



**ポーランド記法が使われる場面 [#p37960ec]

-[[LISP]]


**帰納的定義 [#m32a5f19]

***加法+と乗法・の世界の帰納的定義 [#q7e0bf71]

 加法+と乗法・からなる前置記法の数式の形成規則を帰納的に定義すると次のようになる。ただし変数はすべてxで表すことにする。

+xは数式である。
+X,Yが数式ならば、+XY,・XYはすべて数式である。
+以上の手続きで得られるものだけが数式である。

***ブール形式の帰納的定義 [#m08392fe]

 ブール形式(ブール関数の数式表現)では、演算記号として次の4つが用いられる。

-補: ̄
-和:+
-積:・
-排他的論理和(環和):XOR

 変数はすべてxで表すとする。

 このとき前置記法で表したブール形式の機能的定義は次のようになる。

+xは数式である。
+X,Yが数式ならば、 ̄XY,+XY,・XY,XOR XYはすべて数式である。
+以上の手続きで得られるものだけが数式である。


***命題論理式の帰納的定義 [#u71b1808]

 命題論理式では、演算記号として次の4つが用いられる。

-否定:〜
-選言:∨
-連言:∧
-合意:→

 命題変数はすべてpで表すとする。

 このとき前置記法で表した命題論理式の機能的定義は次のようになる。

+pは数式である。
+p,qが数式ならば、〜pq,∨pq,∧pq,→pqはすべて数式である。
+以上の手続きで得られるものだけが数式である。


*後置記法 [#e68392de]

 xy*のように書く手法を''後置記法(逆ポーランド法)''という。

例:通常の数式「e=(a-b)÷(c+d)」を逆ポーランド記法の数式に変換する場合

+e=(a-b)÷(c+d)
--「a-b」を逆ポーランド記法の数式「ab-」にする。これをXとする。
+e=X÷(c+d)
--「c+d」を逆ポーランド記法の数式「cd+」にする。これをYとする。
+e=X÷Y
--「X÷Y」を逆ポーランド記法の数式「XY÷」にする。これをZとする。
+e=Z
--「e=Z」を逆ポーランド記法の数式「eZ=」にする。
+「eZ=」にZ(,Y,X)を代入していく。すると、「eab-cd+÷=」になる。


**逆ポーランド法が使われる場面 [#e27c62a6]

-一部の電卓
-コンパイラにおける中間言語の数式の表現


**帰納的定義 [#r67d25f1]

***加法+と乗法・の世界の帰納的定義 [#p16fa646]

 加法+と乗法・からなる後置記法の数式の形成規則を帰納的に定義すると次のようになる。ただし変数はすべてxで表すことにする。

+xは数式である。
+X,Yが数式ならば、XY+,XY・はすべて数式である。
+以上の手続きで得られるものだけが数式である。


***ブール形式の帰納的定義 [#y2643682]

 ブール形式(ブール関数の数式表現)では、演算記号として次の4つが用いられる。

-補: ̄
-和:+
-積:・
-排他的論理和(環和):XOR

 変数はすべてxで表すとする。

 このとき後置記法で表したブール形式の機能的定義は次のようになる。

+xは数式である。
+X,Yが数式ならば、XY ̄,XY+,XY・,XY XORはすべて数式である。
+以上の手続きで得られるものだけが数式である。


***命題論理式の帰納的定義 [#xfebf18b]

 命題論理式では、演算記号として次の4つが用いられる。

-否定:〜
-選言:∨
-連言:∧
-合意:→

 命題変数はすべてpで表すとする。

 このとき前置記法で表した命題論理式の機能的定義は次のようになる。

+pは数式である。
+p,qが数式ならば、pq〜,pq∨,pq∧,pq→はすべて数式である。
+以上の手続きで得られるものだけが数式である。


*中置記法 / 前置記法 / 後置記法の計算 [#ia4dab4e]

|中置記法|前置記法|後置記法|
|1+2・3|+1・2 3|1 2 3・+|
|(1+2)・3|・+1 2 3|1 2+3・|
|(1+2・3)・(4+5)|・+1・2 3+4 5|1 2 3・+4 5+・|


*参考文献 [#lccddd34]

-『形式言語と有限オートマトン入門』
-『ソフトウェア開発技術者 午前対策(基礎編) テキスト』