波兰表示法 - 维基百科,自由的百科全书
![]() |
前缀表示法 (+ 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年代演变成下表的记法。
概念 | 普遍记法 | 波兰记法 |
---|---|---|
逻辑非 | φ | 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).