Инфиксная запись Постфиксная запись

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

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

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

Арифметика

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

${\displaystyle (5-6)*7}$

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

${\displaystyle *\ (-\ 5\ 6)\ 7}$

(или просто)

${\displaystyle *\ -\ 5\ 6\ 7}$

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

${\displaystyle 5-(6*7)}$

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

${\displaystyle 5-6*7}$ .

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

${\displaystyle -\ 5*6\ 7}$

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

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

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

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

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

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

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

${\displaystyle /\ 10\ 5=2}$ (префиксная запись)

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

Префиксная запись особенно популярна в стековых языках благодаря свойственной им возможности легко различать порядок операций без использования скобок. Для выявления порядка вычисления операторов в префиксной нотации даже нет необходимости запоминать всю операционную иерархию, как при инфиксной нотации . Вместо того, чтобы анализировать выражение для обнаружения оператора, который нужно вычислить первым, нужно считывать выражение слева направо, рассматривая оператор и ближайшие к нему два операнда. Если среди этих операндов находится ещё один оператор, то вычисление первого оператора откладывается , до тех пор, пока не будет вычислен новый оператор. Итерации этого процесса повторяются до тех пор, пока оператор не будет вычислен, что должно в конечном счёте произойти, если в выражении количество операндов на один больше, чем количество операций (в случае бинарных операций). Как только оператор вычислен, он и его два операнда заменяются полученным значением (операндом). Поскольку оператор и два операнда заменяются на вычисленный операнд, то становится на один оператор и один операнд меньше. После этого в выражении также остаётся ${\displaystyle N}$ операторов и ${\displaystyle 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

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

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

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

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

См. также

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

Примечания

Литература

• Ł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).

Ссылки

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