波蘭表示法

	前綴表示法（+ 3 4 ）
	中綴表示法（3 + 4）
	後綴表示法（3 4 + ）

波蘭表示法（英語：Polish notation，或波蘭記法）是一種邏輯、算術和代數表示方法，其特點是操作符置於操作數的前面，因此也稱做前綴表示法。如果操作符的元數（arity）是固定的，則語法上不需要括號仍然能被無歧義地解析。波蘭記法是波蘭數學家揚·武卡謝維奇於1920年代引入的，用於簡化命題邏輯。

揚·武卡謝維奇本人提到：^[1]

“

我在1924年突然有了一個無需括號的表達方法，我在文章第一次使用了這種表示法。

”

——Łukasiewicz(1), p. 610, footnote.

阿隆佐·邱奇在他的經典著作《數理邏輯》中提出該表達方法是一種值得被關注的記法系統，甚至將它與阿弗烈·諾夫·懷海德和伯特蘭·羅素在《數學原理》中的邏輯表達式相提並論。^[2]

算術形式[編輯]

表達「三加四」時，前綴記法寫作「+ 3 4 」，而不是「3 + 4」。在複雜的表達式中，操作符仍然在操作數的前面，但操作數可能是包含操作符的平凡表達式。例如，中綴運算式(5 - 6) * 7 ，在前綴表達式中可以表示為：

*(− 5 6) 7

或省略括號：

* - 5 6 7

由於簡單的算術運算符都是二元的，該前綴表達式無需括號，且表述是無歧義的。在前面的例子裡，中綴形式的括號是必需的，如果將括號移動到：

5 - (6 * 7)

即：

5 - 6 * 7

則會改變整個表達式的值。而其正確的前綴形式是：

- 5 * 6 7

減法運算要等它的兩個操作數（5；6和7的乘積）都完成時才會處理。在任何表示法中，最裡面的表達式最先運算，而在波蘭表達式中，決定「最裡面」的是順序而不是括號。

簡單算術的前綴表達式主要是用於學術研究方面。與逆波蘭表示法不同，前綴表達式基本沒有在商業計算器中使用過，但是其體系經常在編譯器構造的概念教學中首先使用。

計算機編程[編輯]

LISP的S-表達式中廣泛地使用了前綴記法，S-表達式中使用了括號是因為它的算術操作符有可變的元數（arity）。逆波蘭表示法在許多基於堆疊的程序語言（如PostScript）中使用，以及是一些計算器（特別是惠普）的運算原理。

假定只有二元運算時，操作數的個數必然為操作符的個數加一，否則表達式就無意義。這樣在計算更複雜，更長的表達式時，可以簡單地忽略某些錯誤表達式，因此在使用前綴記法時必須小心仔細檢查其表達意義。

運算順序[編輯]

前綴表達式的運算順序很容易檢測。需注意的是，當運算時，操作符是作用在第一個操作數上，特別是需注意不滿足交換律的運算，如除法、減法。例如，下列式子：

 / 10 5 = 2  (前缀记法)

表示10/5，結果是2，而不是½。

基於堆疊的操作符由於其本身的特性，無需括號也很容易區分運算的順序，因此大量使用波蘭記法。運算波蘭表達式時，無需記住運算的層次，只需要直接尋找第一個運算的操作符。以二元運算為例，從左至右讀入表達式，遇到一個操作符後跟隨兩個操作數時，則計算之，然後將結果作為操作數替換這個操作符和兩個操作數；重複此步驟，直至所有操作符處理完畢。因為在正確的前綴表達式中，操作數必然比操作符多一個，所以必然能找到一個操作符符合運算條件；而替換時，兩個操作數和一個操作符替換為一個操作數，所以減少了各一個操作符和操作數，仍然可以迭代運算直至計算整個式子。多元運算也類似，遇到足夠的操作數即產生運算，迭代直至完成。迭代結束的條件由表達式的正確性來保證。下面是一個例子，演示了每一步的運算順序：

 - * / 15 - 7 + 1 1 3 + 2 + 1 1 =
 - * / 15 - 7   2   3 + 2 + 1 1 =
 - * / 15     5     3 + 2 + 1 1 =
 - *        3       3 + 2 + 1 1 =
 -          9         + 2 + 1 1 =
 -          9         + 2   2   =
 -          9         4         =
                5

邏輯運算的波蘭記法[編輯]

下面的表格顯示了命題邏輯的揚·武卡謝維奇記法，波蘭記法中的某些字母代表特定的波蘭語單詞。普遍記法在1970和1980年代演變成下表的記法。

概念	普遍記法	波蘭記法
邏輯非	$\neg$ φ	Nφ
邏輯與	φ $\wedge$ ψ	Kφψ
邏輯或	φ $\lor$ ψ	Aφψ
邏輯條件	φ $\rightarrow$ ψ	Cφψ
邏輯雙條件	φ $\leftrightarrow$ ψ	Eφψ
謝費爾豎線	$\phi \|\psi$	Dφψ
可能性	$\Diamond$ φ	Mφ
必然性	$\Box$ φ	Lφ
全稱量化	$\forall$ φ	Πφ
存在量化	$\exists$ φ	Σφ

注釋[編輯]

^ from Nicod's Axiom and Generalizing Deduction, page 180. 原文用波蘭語寫在一個平版報告上。
^ Church, Alonzo. Introduction to Mathematical Logic. Princeton, New Jersey: Princeton University Press. 1944. - p.38: "Worthy of remark is the parenthesis-free notation of Jan Łukasiewicz. In this the letters N, A, C, E, K are used in the roles of negation, disjunction, implication, equivalence, conjunction respectively. ..."

參見[編輯]

延伸閱讀[編輯]

Łukasiewicz, Jan. Aristotle’s Syllogistic from the Standpoint of Modern Formal Logic. Oxford University Press. 1957.
Łukasiewicz, Jan, "Philosophische Bemerkungen zu mehrwertigen Systemen des Aussagenkalküls", Comptes rendus des séances de la Société des Sciences et des Lettres de Varsovie, 23:51-77 (1930). Translated by H. Weber as "Philosophical Remarks on Many-Valued Systems of Propositional Logics", in Storrs McCall, Polish Logic 1920-1939, Clarendon Press: Oxford (1967).

[1] rom Nicod's Axiom and Generalizing Deduction, page 180. 原文用波蘭語寫在一個平版報告上。

[2] Church, Alonzo. Introduction to Mathematical Logic. Princeton, New Jersey: Princeton University Press. 1944. - p.38: "Worthy of remark is the parenthesis-free notation of Jan Łukasiewicz. In this the letters N, A, C, E, K are used in the roles of negation, disjunction, implication, equivalence, conjunction respectively. ..."

[1]

[2]