跳至內容

波蘭表示法

維基百科,自由的百科全書
前綴表示法 (+ 3 4 )
中綴表示法 (3 + 4)
後綴表示法 (3 4 + )

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

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

阿隆佐·邱奇在他的經典著作《數理邏輯》中提出該表達方法是一種值得被關注的記法系統,甚至將它與阿弗烈·諾夫·懷海德伯特蘭·羅素在《數學原理》中的邏輯表達式相提並論。[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的乘積)都完成時才會處理。在任何表示法中,最裡面的表達式最先運算,而在波蘭表達式中,決定「最裡面」的是順序而不是括號。

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

計算機編程

[編輯]

LISPS-表達式中廣泛地使用了前綴記法,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年代演變成下表的記法。

概念 普遍記法 波蘭記法
邏輯非 φ
邏輯與 φψ Kφψ
邏輯或 φψ Aφψ
邏輯條件 φψ Cφψ
邏輯雙條件 φψ Eφψ
謝費爾豎線 Dφψ
可能性 φ
必然性 φ
全稱量化 φ Πφ
存在量化 φ Σφ

注釋

[編輯]
  1. ^ from 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. ..."

參見

[編輯]

延伸閱讀

[編輯]
  • Ł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).