Польская запись

По́льская нота́ция (за́пись), также известна как пре́фиксная нота́ция (запись), это форма записи логических, арифметических и алгебраических выражений. Характерная черта такой записи — оператор располагается слева от операндов. Если оператор имеет фиксированную арность, то в такой записи будут отсутствовать круглые скобки и она может быть интерпретирована без неоднозначности. Польский логик Ян Лукасевич изобрёл эту запись примерно в 1920, чтобы упростить пропозициональную логику.

Алонзо Чёрч упоминал эту нотацию в своей классической книге по математической логике как достойную внимания систему нотации и даже противопоставлял экспозиции логических нотаций Альфреда Уайтхеда и Бертрана Рассела в Principia Mathematica.^[1]

Несмотря на то, что польская запись не используется в математике, она широко применяется в информатике.

Арифметика

В префиксной нотации сложение чисел 1 и 2 будет записано « $+\ 1\ 2$ » вместо записи « $1+2$ ». В более сложных выражениях операторы предшествуют операндам, но операнды сами могут быть нетривиальными выражениями, содержащими свои собственные операторы. Например, выражение, которое в традиционной инфиксной нотации записывается так:

(5-6)*7

в префиксной может быть записано как:

*\ (-\ 5\ 6)\ 7

(или просто)

*\ -\ 5\ 6\ 7

Так как любая простая арифметическая операция является бинарной, то её префиксное представление не может быть интерпретировано двояко, поэтому нет необходимости использовать скобки. В предыдущем примере в традиционной, инфиксной записи круглые скобки были необходимы, а теперь переместим их:

5-(6*7)

или вовсе удалим:

5-6*7

.

Это изменило смысл и результат вычисления всего выражения. Соответствующая префиксная запись такого выражения будет выглядеть следующим образом:

-\ 5*6\ 7

Вычисление вычитания задерживается до тех пор пока не будут считаны оба операнда (5 и результат перемножения 6 и 7). Как и в любой другой нотации, выражения находящиеся в глубине вычисляются первыми, но в польской записи глубина выражения определяется порядком, а не скобками.

Префиксная запись в простой арифметике представляет в значительной степени академический интерес. Как и постфиксная запись, префиксная нотация была использована для некоторых коммерческих вычислительных машин (HP-11С). Изучение префиксной записи часто является первым шагом в области конструирования компиляторов.

Программирование

Префиксная запись широко применяется в s-выражениях в языке программирования Лисп, где скобки необходимы, поскольку арифметические операторы обладают различной арностью. Язык программирования Ambi использует польскую запись для арифметических операций и структуры программы. Постфиксная запись используется во многих стековых языках, таких как PostScript, и является основой для многих вычислительных машин (калькуляторов), особенно для вычислительных машин Hewlett-Packard.

Также важно отметить, что количество операндов в выражении должно быть на один больше чем количество операций, иначе выражение не имеет смысла (учитывая, что в выражении используются только бинарные операции). Этому можно легко не придавать значения при работе с длинными, сложными выражениями, что повлечёт за собой ошибки. Поэтому необходимо обращать внимание на количество операций и операндов при использовании префиксной нотации.

Порядок операций

Порядок операций определяется структурой префиксной нотации и может быть легко определён. Главное, нужно помнить, что при вычислении выражения порядок операндов нужно сохранять. Это не важно для операций, которые обладают свойством коммутативности, но для некоммутативных операций, таких как вычитание и деление, этот факт является ключевым для анализа выражения. Например, следующее выражение:

/\ 10\ 5=2

(префиксная запись)

нужно прочесть, как «деление 10 на 5». Поэтому результатом вычисления будет 2, а не 0,5, что было бы результатом неправильного анализа выражения.

Префиксная запись особенно популярна в стековых языках благодаря свойственной им возможности легко различать порядок операций без использования скобок. Для выявления порядка вычисления операторов в префиксной нотации даже нет необходимости запоминать всю операционную иерархию, как при инфиксной нотации. Вместо того, чтобы анализировать выражение для обнаружения оператора, который нужно вычислить первым, нужно считывать выражение слева направо, рассматривая оператор и ближайшие к нему два операнда. Если среди этих операндов находится ещё один оператор, то вычисление первого оператора откладывается, до тех пор, пока не будет вычислен новый оператор. Итерации этого процесса повторяются до тех пор, пока оператор не будет вычислен, что должно в конечном счёте произойти, если в выражении количество операндов на один больше, чем количество операций (в случае бинарных операций). Как только оператор вычислен, он и его два операнда заменяются полученным значением (операндом). Поскольку оператор и два операнда заменяются на вычисленный операнд, то становится на один оператор и один операнд меньше. После этого в выражении также остаётся $N$ операторов и $N+1$ операнд, что позволяет итеративно продолжать процесс.

В приведённом ниже примере можно увидеть, что сложное на первый взгляд выражение в префиксной нотации, на самом деле оказывается не таким уж сложным для понимания (справа от знака равенства соответствующее выражение в инфиксной записи):

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

Польская нотация в логике

Таблица, приведённая ниже, демонстрирует ядро записи предложенной Яном Лукасевичем для пропозициональной логики. Некоторые буквы Польской записи означают конкретные слова на польском языке:

Понятие	Условная нотация	Польская нотация	Польское слово
Отрицание	$\neg$ φ	Nφ	negacja
Конъюнкция	φ $\wedge$ ψ	Kφψ	koniunkcja
Дизъюнкция	φ $\lor$ ψ	Aφψ	alternatywa
Импликация	φ $\rightarrow$ ψ	Cφψ
Эквиваленция	φ $\leftrightarrow$ ψ	Eφψ	ekwiwalencja
Штрих Шеффера	$\phi \|\psi$	Dφψ	dysjunkcja
Возможность	$\Diamond$ φ	Mφ	możliwość
Необходимость	$\Box$ φ	Lφ
Квантор всеобщности	$\forall$ φ	Πφ
Квантор существования	$\exists$ φ	Σφ

Заметим, что в работе Лукасевича о многозначной логике кванторы упорядочены по пропозициональной ценности.

См. также

Обратная польская нотация

Примечания

↑ 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).

Ссылки

Ambi — расширяемый браузерный калькулятор ОПЗ Дэвида Праттена.

[1] 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]