Loading article…
ポーランド記法（PN ）は、通常のポーランド記法（NPN）[1] とも呼ばれ、ウカシェヴィチ記法、ワルシャワ記法、ポーランド接頭辞記法、または単に接頭辞記法とも呼ばれ、演算子が 被演算子の前に来る数学記法であり、より一般的な中置記法（演算子が被演算子の間に置かれる）や逆ポーランド記法（RPN）（演算子が被演算子の後に来る）とは対照的である。各演算子が固定数の被演算子を持つ限り、括弧は不要である。「ポーランド」という記述は、1924年にポーランド記法を発明した論理学者ヤン・ウカシェヴィチ[2] ：24 [3] ：78 [4]の国籍を指している。 [5] ：367、脚注3 [6] ：180、脚注3
ポーランド記法という用語は、（中置記法の反対として）逆ポーランド記法も含むと解釈されることがある。[7]
ポーランド記法はプログラミング言語 インタープリタによって数式の構文として使用される場合、抽象構文木に簡単に解析され、実際に同じものの1 対 1 表現を定義できます。このため、Lisp (以下を参照) および関連するプログラミング言語では、構文全体をプレフィックス記法で定義します (他の言語ではポストフィックス記法を使用します)。
歴史
1931年のヤン・ルカシェヴィチの論文[5] :367、脚注3 [6] :180、脚注3 からの引用では、この記法がどのようにして発明されたかが述べられている。
私は1924年に括弧を使わない表記法のアイデアを思いつきました。その表記法を初めて使用したのは、Łukasiewicz (1)の論文、610ページの脚注です。
Łukasiewicz が引用した文献、すなわち Łukasiewicz (1) [8]は、明らかにポーランド語で石版印刷された報告書である。Łukasiewicz の参照論文[5]は、 1965 年にHenry A. PogorzelskiによってJournal of Symbolic Logicでレビューされた。[9] 1924 年に Moses Schönfinkelの論文の編集者であったHeinrich Behmann [10]は、論理式から括弧をなくすというアイデアをすでに持っていた。彼の論文の 1 つで、Łukasiewicz は、彼の表記法が最もコンパクトで、線形に記述された最初の括弧なしの表記法であるが、ゴットロープ・フレーゲが1879 年にすでに括弧なしのBegriffsschrift表記法を提案していたため、最初のものではないと述べている。[11]
アロンゾ・チャーチは、数理論理学に関する古典的な著書の中で、この記法は、アルフレッド・ホワイトヘッドやバートランド・ラッセルの『プリンキピア・マテマティカ』における論理記法の解説や研究と比べても、記法システムの中で注目に値するものであると述べています。[12]
ウカシェヴィチの1951年の著書『現代形式論理学から見たアリストテレスの三段論法』では、彼の記法の原則は括弧を避けるために関数を引数の前に書くことであり、1929年以来論理学の論文でその記法を使用していたと述べています。 [3] : 78 そして、例として、アルフレッド・タルスキと共著した1930年の文法計算に関する論文を挙げています。[13]
ポーランド記法は論理学ではあまり使われなくなったが、[14]その後コンピュータサイエンスの分野で使われるようになった。
説明
1と2を足す式は、ポーランド記法では1 + 2 （中置）ではなく、+ 1 2（前置）と書きます。より複雑な式では、演算子はオペランドの前にありますが、オペランド自体が再び演算子とそのオペランドを含む式である場合があります。たとえば、従来の中置記法では次のように書かれる式は、
（５ − ６） × ７
ポーランド語表記では次のように書ける。
× (− 5 6) 7
関係するすべての演算子の引数が与えられたと仮定すると（ここで「-」は減算の二項演算を表し、符号変更の単項関数を表しません）、適切なプレフィックス表現はどれも曖昧さがなく、プレフィックス式内の括弧は不要です。したがって、上記の式はさらに次のように簡略化できます。
× − 5 6 7
積の処理は、2 つのオペランド (つまり、5 から 6 を引いた値と 7) が使用可能になるまで延期されます。他の表記法と同様に、最も内側の式が最初に評価されますが、ポーランド表記法では、この「最も内側であること」は括弧ではなく、演算子とオペランドのシーケンスによって伝えられます。
従来の中置記法では、括弧は標準的な優先順位規則を無視する必要がある。上記の例を参考にすると、括弧を移動すると
5 − (6 × 7)
または削除する
5 − 6 × 7
式の意味と結果が変わります。このバージョンはポーランド語表記で次のように書かれています。
− 5 × 6 7.
除算や減算などの非可換演算を扱う場合、演算子が引数を取る方法、つまり左から右への方法の定義とオペランドの順序の配置を調整する必要があります。たとえば、÷ 10 5では、 10 が 5 の左側にあるため、 10 ÷ 5 の意味を持ちます (「10 を 5 で割る」と読みます)。また、− 7 6では、 7 が 6 の左側にあるため、 7 − 6 の意味を持ちます (「7 からオペランド 6 を引く」と読みます)。
評価アルゴリズム
プレフィックス/ポストフィックス表記法は、インフィックス表記法で通常使用される括弧やその他の優先順位規則を必要とせずに、意図した演算順序を表現できるという本来の能力があるため、特に人気があります。代わりに、この表記法は、どの演算子を最初に評価するかを一意に示します。演算子はそれぞれ固定の引数を持つものと想定され、必要なオペランドはすべて明示的に指定されているものと想定されます。有効なプレフィックス式は常に演算子で始まり、オペランドで終わります。評価は、左から右、またはその逆の方向に進めることができます。左から始めて、演算子またはオペランドを表すトークンで構成される入力文字列が、スタックの一番上のエントリに最上位の演算子 (すぐ下) に収まる数のオペランドが含まれるまで、トークンごとにスタックにプッシュされます。スタック上部のこのトークンのグループ (最後にスタックされた演算子とそれに対応するオペランドの数) は、これらのオペランドに対して演算子を実行した結果に置き換えられます。その後、入力の処理がこのように続行されます。したがって、有効なプレフィックス式の右端のオペランドは、式全体の評価結果を除いて、スタックを空にします。右から開始する場合、トークンのプッシュは同様に実行されますが、評価は演算子によってトリガーされ、スタックトップにすでにあるそのアリティに適合する適切な数のオペランドが検索されます。ここで、有効なプレフィックス式の左端のトークンは、スタック内のオペランドの数に適合する演算子である必要があり、これにより再び結果が得られます。説明からわかるように、任意のスタック検査機能のないプッシュダウンストアで、この解析を実装するのに十分です。
上で説明したスタック操作は、ミラー化された入力を使用して、逆ポーランド記法の式でも機能します。
論理のポーランド記法
以下の表は、現代論理におけるヤン・ウカシェヴィチの表記法の中核を示しています。ポーランド語表記表の一部の文字は、次に示すように、ポーランド語の特定の単語を表しています。
Łukasiewicz の多値論理に関する研究では、 量指定子が命題値の範囲に及んでいたことに注意してください。
Bocheńskiは、古典的な命題論理の16個の二項接続詞すべてに名前を付けるポーランド記法のシステムを導入した。[18] : 16 古典的な命題論理にとって、これはŁukasiewiczの記法の互換性のある拡張である。しかし、Bocheńskiは命題論理で（非含意と逆非含意に対して）およびを使用し、Łukasiewiczは様相論理で およびを使用するという意味で、これらの記法は互換性がない。
実装
プレフィックス表記法はLispの S式で広く使われており、言語内の演算子自体がデータ（第一級関数）であるため括弧が必要となる。Lisp関数は可変長の場合もある。Tclプログラミング言語もLispと同様にmathopライブラリを通じてポーランド記法を使用する。Ambi [19]プログラミング言語は算術演算とプログラム構築にポーランド記法を使用する。LDAPフィルタ構文はポーランドプレフィックス表記法を使用する。[20]
ポストフィックス表記は、 PostScriptやForthなどの多くのスタック指向プログラミング言語で使用されます。CoffeeScript構文では、他の言語で一般的な単項ポストフィックス構文をサポートしながら、プレフィックス表記を使用して関数を呼び出すこともできます。
式の戻り値の数は、式内のオペランドの数と演算子の合計引数の数との差から演算子の戻り値の合計数を引いた数に等しくなります。
ポーランド記法は、通常は後置形式で、ヒューレット・パッカードなどの特定の計算機で選択された記法です。[21]より低いレベルでは、後置演算子はバローズの大規模システムなどの一部のスタックマシンで使用されます。
参照
参考文献
- ^ ヨーク、ギュンター;ランペ、ベルンハルト。ノルベルト・ウェンゲル (1989)。 Arithmetische Algorithmen der Mikrorechentechnik [マイクロコンピュータの算術アルゴリズム] (ドイツ語) (第 1 版)。ベルリン、ドイツ: VEB Verlag Technik。ISBN 3-34100515-3. EAN 978-3-34100515-6. MPN 5539165. ライセンス 201.370/4/89 . 2015-12-01に取得。
- ^ abcdefghi Łukasiewicz、1 月(1929 年)。Elementy logiki matematycznej (ポーランド語) (1 版)。ワルシャワ、ポーランド: パンストワヴェ・ヴィダウニクトゥ・ナウコヴェ;ウカシェヴィチ、ヤン（1963年）。数理論理学の要素。 Wojtasiewicz、Olgierd Adrian [ポーランド語]翻訳。米国ニューヨーク州:マクミラン カンパニー。
- ^ abcde Łukasiewicz, Jan (1957) [1951].アリストテレスの三段論法 - 現代形式論理学の観点から(第2版). Oxford University Press .(1987 年にGarland Publishingより再版、ISBN 0-8240-6924-2 )
- ^ Kennedy, John (1982年8月). 「RPN Perspective」. PPC Calculator Journal . 9 (5). サンタモニカカレッジ数学部、サンタモニカ、カリフォルニア州、米国：26–29。CiteSeerX 10.1.1.90.6448 . 2022年7月1日時点のオリジナルよりアーカイブ。2022年7月2日閲覧。 （12ページ）
- ^ abc Łukasiewicz、1 月(1931 年)。 「Uwagi o aksjomacie Nicoda i 'dedukcji uogólniającej'」 [ニコッドの公理と「一般化演繹」についてのコメント]。Księga pamiątkowa Polskiego Towarzystwa Filozoficznego We Lwowie、12. II。 1904 ～ 1912 年。 II. 1929年（ポーランド語）。 Lwów: Wydawnictwo Polskie Towarzystwo Filozoficzne。 366–383ページ。
- ^ ab Łukasiewicz, Jan (1970). 「ニコドの公理と『演繹の一般化』に関するコメント」「Borkowski, L. (編)。選集。アムステルダムおよびロンドン/ワルシャワ: North-Holland Publishing Company/Polish Scientific Publishers。pp. 179–196。」
- ^ メイン、マイケル (2006)。Java を使用したデータ構造とその他のオブジェクト (第 3 版)。ピアソン PLCアディソン ウェズリー。p . 334。ISBN 978-0-321-37525-4。
- ^ Łukasiewicz、1 月(1929)。 「ああ、ズナツェニウ・イ・ポトゼバッハ・ロジキ・マテマティチュネー」。ナウカ・ポルスカ（ポーランド語）。10 : 604–620。
- ^ ポゴゼルスキー、ヘンリー・アンドリュー(1965 年 9 月)。 「レビュー対象作品: ニコッドの公理と「一般化演繹」についての考察、ヤン・ウカシェヴィチ、イェジ・スウペツキ、パンストヴェヴェ・ヴィダウニクトゥ・ナウコヴェ著」。記号論理ジャーナル(レビュー)。30 (3)。記号論理学会: 376–377。JSTOR 2269644。(注意。Jan Łukasiewiczによる 1931 年のオリジナル論文「Uwagi o aksjomacie Nicoda i 'dedukcji uogólniającej」は、1961 年にポーランド、ワルシャワのPaństwowe Wydawnictwo Naukowe (National Scientific Publishers)で、 Jerzy Słupeckiが編集した一冊として再出版されました。)
- ^ シェーンフィンケル、モーセ(1924)。 「Über die Bausteine der mathematischen Logik」[数学的論理の構成要素について]。Mathematische Annalen (ドイツ語)。92 (3-4): 305-316。土井：10.1007/BF01448013。S2CID 118507515; van Heijenoort, Jean編 (1967)。「数理論理学の構成要素について」。数理論理学の資料集、1879-1931。Bauer -Mengelberg, Stefan 訳[オランダ語]。ハーバード大学出版局。pp. 355-366。
- ^ クリスチャン・ゴットシャル (2005)。Logische Notationen und deren Verarbeitung auf elektronischen Rechenanlagen aus theoretischer, praktischer und historischer Sicht (卒業論文) (ドイツ語)。ウィーン、オーストリア。 p. 88:
Die ältesten Texte in den 'Selected Works', in denen Łukasiewicz polnische Notation verwendet, datieren relativ spät, sind aber Präsentationen vorangehender Arbeiten, die 'in the course of the years 1920–1930' (S. 131) stattgefunden haben, alsoああケイネ・ゲナウエレ・ゼイタンガベ・ゲベン。
{{cite book}}: CS1 メンテナンス: 場所が見つかりません 発行者 (リンク) - ^ Church, Alonzo (1944). Introduction to Mathematical Logic . Princeton, New Jersey, USA: Princeton University Press . p. 38.
[…] 特筆すべきは、Jan Łukasiewicz の括弧なしの表記法です。この表記法では、N、A、C、E、K の文字がそれぞれ否定、選言、含意、同値、連言の役割で使用されています。 […]
- ^ ジャン・ウカシェヴィチ;アルフレッド、タルスキ(1930)。 「Untersuhungen über den Aussagenkalküls」[感覚微積分の調査]。Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie (ドイツ語)。23 (Cl. III): 30–50。
- ^ Martínez Nava, Xóchitl (2011-06-01)、「論理が苦手なのはなぜ？論理教育における失読症」、Blackburn, Patrick、van Ditmarsch, Hans、Manzano, Maria、Soler-Toscano, Fernando (編)、Tools for Teaching Logic: Third International Congress、TICTTL 2011、Salamanca、Spain、2011 年 6 月 1 日～4 日、Proceedings、Lecture Notes in Artificial Intelligence、vol. 6680、Springer Nature、pp. 162～169、doi :10.1007/978-3-642-21350-2_19、ISBN 978-3-64221349-6,
[…] ポーランド語表記法や接頭辞表記法は、使用の難しさから使用されなくなっています。 […]
- ^ ab Łukasiewicz、1 月(1939 年)。 「デア・エキヴァレンゼンカルキュル」。Collectanea Logica (ドイツ語)。1：145-169。
- ^ Łukasiewicz、1 月(1930)。 「Untersuhungen über den Aussagenkalküls」[感覚微積分の調査]。Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie (ドイツ語)。23 (Cl. III): 51–77。
- ^ ab Łukasiewicz, Jan (1953). 「様相論理のシステム」.コンピューティングシステムジャーナル. 3 (1): 111–149.
- ^ ボチェンスキー、ユゼフ・マリア(1949)。フリブールで書かれた。論理数学の精度(PDF)。コレクション Synthese (フランス語)。 Vol. 2. オランダ、ペイバ、ブッスム：FG クルーンダー。2023-08-03 にオリジナルからアーカイブ(PDF)されました。2023 年 11 月 12 日に取得。Bocheński, Józef Maria (1959)として翻訳。A Precis of Mathematical Logic 。Bird, Otto A. [at Wikidata]により翻訳。ドルドレヒト、オランダ: D. Reidel Publishing Company。
- ^ 「Google Code アーカイブ - Google Code プロジェクト ホスティング用の長期ストレージ」。2017 年 9 月 28 日時点のオリジナルよりアーカイブ。2022 年 11 月 14 日閲覧。
- ^ 「LDAP フィルター構文」。2022 年 10 月 14 日時点のオリジナルよりアーカイブ。2022 年 11 月 14 日閲覧。
- ^ 「HP 電卓 - HP 35s RPN モード」(PDF)。Hewlett-Packard 。 2022 年 1 月 21 日時点のオリジナルよりアーカイブ(PDF) 。 2022 年 11 月 14 日閲覧。
さらに読む
- フォテ、マイケル。トーマス・ウィルク編。 (2015) [2014-11-14]。ドイツのイエナで書かれました。 Keller、Stack und automatisches Gedächtnis – eine Struktur mit Potenzial [セラー、スタック、および自動メモリ - 可能性のある構造] (PDF) (Tagungsband zum Kolloquium 14. 2014 年 11 月、イエナ)。 GI シリーズ: 情報学講義ノート (LNI) – テーマ (ドイツ語)。 Vol. T-7。ボン、ドイツ: Gesellschaft für Informatik (GI) / Köllen Druck + Verlag GmbH。ISBN 978-3-88579-426-4. ISSN 1614-3213. 2020年4月12日時点のオリジナルよりアーカイブ（PDF） . 2020年4月12日閲覧。[1] (77ページ)
- ラングマック、ハンス[ドイツ語] (2015) [2014-11-14]。ドイツのキールで書かれました。 Friedrich L. Bauers und Klaus Samelsons Arbeiten in den 1950er-Jahren zur Einführung der Begriffe Kellerprinzip und Kellerautomat [セラー原理とセラーオートマトンという用語の導入に関する 1950 年代のフリードリヒ L. バウアーとクラウス サメルソンの著作] (PDF) (ドイツ語) ）。ドイツ、イエナ: Institut für Informatik、Christian-Albrechts-Universität zu Kiel。 19～29ページ。2022-11-14 にオリジナルからアーカイブ(PDF)されました。2022 年 11 月 14 日に取得。(11 ページ) (注: Fothe & Wilke に掲載)
- グース、ゲルハルト[ドイツ語] (2017-08-07)。 Geschichte der deutschsprachigen Informatik - Programmiersprachen und Übersetzerbau [ドイツ語圏における情報学の歴史 - プログラミング言語とコンパイラー設計] (PDF) (ドイツ語)。カールスルーエ、ドイツ: Fakultät für Informatik、カールスルーエ工科大学(KIT)。2022-05-19 にオリジナルからアーカイブ(PDF)されました。2022 年 11 月 14 日に取得。（11ページ）
外部リンク
ウィキメディア・コモンズのポーランド記法（数学）に関連するメディア