波蘭表示法
波蘭表示法（英語：Polish notation，或波蘭記法）是一種邏輯、算術和代數表示方法，其特點是操作符置於操作數的前面，因此也稱做前綴表示法。如果操作符的元數（arity）是固定的，則語法上不需要括號仍然能被無歧義地解析。波蘭記法是波蘭數學家揚·武卡謝維奇於1920年代引入的，用於簡化命題邏輯。
|
| 前綴表示法 （+ 3 4 ） |
| 中綴表示法 （3 + 4） |
| 後綴表示法 （3 4 + ） |
揚·武卡謝維奇本人提到：[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年代演變成下表的記法。
| 概念 | 普遍記法 | 波蘭記法 |
|---|---|---|
| 邏輯非 | φ | Nφ |
| 邏輯與 | φ ψ | Kφψ |
| 邏輯或 | φ ψ | Aφψ |
| 邏輯條件 | φ ψ | Cφψ |
| 邏輯雙條件 | φ ψ | Eφψ |
| 謝費爾豎線 | Dφψ | |
| 可能性 | φ | Mφ |
| 必然性 | φ | Lφ |
| 全稱量化 | φ | Πφ |
| 存在量化 | φ | Σφ |
註釋
編輯- ^ 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).