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

Постфиксная нотация («обратная польская») Обозначение инфиксов Обозначение префикса («польский»)

v т е

Польское обозначение ( PN ), также известные как нормальная польская запись ( NPN ), ^[1] Лукасевич обозначение , Варшава обозначение , польский префикс обозначение или просто префикс обозначения , является математической записью , в которой операторы предшествуют их операнды , в отличии от более общего инфиксная нотация , в которой операторы помещаются между операндами, а также обратная польская нотация (RPN), в которой операторы следуютих операнды. Скобки не нужны, если каждый оператор имеет фиксированное количество операндов . Описание «Польский» относится к национальности из логик Яна Лукасевичем , ^[2] , который изобрел польское обозначение в 1924 году ^{[3] [4]}

Термин « польская нотация» иногда используется (как противоположность инфиксной нотации ), чтобы также включить обратную польскую нотацию. ^[5]

Когда польская нотация используется в качестве синтаксиса для математических выражений интерпретаторами языков программирования , она легко разбирается на абстрактные синтаксические деревья и фактически может определять однозначное представление для них. Из-за этого Лисп ( см. Ниже ) и родственные языки программирования определяют весь свой синтаксис в префиксной нотации (а другие используют постфиксную нотацию).

История [ править ]

Цитата из статьи Яна Лукасевич , Заметки о Axiom Nicod и на «Обобщая дедукцию» , стр 180, говорится , как было изобретено обозначение:

Я пришел к идее обозначения без скобок в 1924 году. Я впервые использовал это обозначение в своей статье Лукасевич (1), с. 610, сноска.

Ссылка, процитированная Лукасевичем, по-видимому, представляет собой литографированный отчет на польском языке . Статья Лукасевича « Замечания об аксиоме Никода и об« обобщающей дедукции »» была рассмотрена Генри А. Погорзельским в « Журнале символической логики» в 1965 году. ^[6] Генрих Беманн , редактор статьи Моисея Шенфинкеля в 1924 году , ^[7] уже была идея убрать круглые скобки в логических формулах.

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

В книге Лукасевича 1951 года «Силлогистика Аристотеля с точки зрения современной формальной логики» он упоминает, что принцип его обозначений состоял в том, чтобы писать функторы перед аргументами, чтобы избежать скобок, и что он использовал свои обозначения в своих логических работах с 1929 года ^{[9]. ]} Затем он цитирует, в качестве примера, статью 1930 года, которую он написал вместе с Альфредом Тарски о сентенциальном исчислении . ^[10]

Хотя польская нотация больше не используется в логике, ^{[11] с} тех пор она нашла место в информатике .

Объяснение [ править ]

Выражение для сложения чисел 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 .

При работе с некоммутативными операциями, такими как деление или вычитание, необходимо согласовывать последовательное расположение операндов с определением того, как оператор принимает свои аргументы, т. Е. Слева направо. Например, ÷ 10 5 , где 10 слева до 5, имеет значение 10 ÷ 5 (читается как «разделить 10 на 5»), или - 7 6 , где 7 слева до 6, имеет значение 7 - 6 ( читается как «вычесть из 7 операнд 6»).

Алгоритм оценки [ править ]

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

Приведенная выше схема манипуляции со стеком работает - с зеркальным вводом - также для выражений в обратной польской нотации .

Польское обозначение логики [ править ]

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

Концепция	Условные обозначения	Польская нотация	Польский термин
Отрицание	${\ displaystyle \ neg \ varphi}$	${\ Displaystyle \ mathrm {N} \ varphi}$	Негачья
Соединение	${\ displaystyle \ varphi \ land \ psi}$	${\ Displaystyle \ mathrm {K} \ varphi \ psi}$	Koniunkcja
Дизъюнкция	${\ displaystyle \ varphi \ lor \ psi}$	${\ displaystyle \ mathrm {A} \ varphi \ psi}$	альтернатива
Материал условный	${\ displaystyle \ varphi \ to \ psi}$	${\ Displaystyle \ mathrm {C} \ varphi \ psi}$	импликация
Двусмысленный	${\ displaystyle \ varphi \ leftrightarrow \ psi}$	${\ displaystyle \ mathrm {E} \ varphi \ psi}$	Ekwiwalencja
Ложь	${\ displaystyle \ bot}$	${\ displaystyle \ mathrm {O}}$	fałsz
Инсульт Шеффера	${\ displaystyle \ varphi \ mid \ psi}$	${\ Displaystyle \ mathrm {D} \ varphi \ psi}$	dysjunkcja
Возможность	${\displaystyle \Diamond \varphi }$	${\displaystyle \mathrm {M} \varphi }$	Możliwość
Необходимость	${\displaystyle \Box \varphi }$	${\displaystyle \mathrm {L} \varphi }$	Konieczność
Универсальный квантификатор	${\displaystyle \forall p\,\varphi }$	${\displaystyle \Pi p\,\varphi }$	kwantyfikator ogólny
Экзистенциальный квантификатор	${\displaystyle \exists p\,\varphi }$	${\displaystyle \Sigma p\,\varphi }$	kwantyfikator szczegółowy

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

Бохенский ввел систему польской записи, которая называет все 16 бинарных связок классической логики высказываний. Для классической логики высказываний это совместимое расширение обозначений Лукасевича. Но обозначения несовместимы в том смысле, что Бохенский использует L и M (для неимпликации и обратного неимпликации) в логике высказываний, а Лукасевич использует L и M в модальной логике. ^[13]

Реализации [ править ]

Префиксная нотация нашла широкое применение в S-выражениях Лиспа , где скобки необходимы, поскольку операторы в языке сами являются данными (функции первого класса ). Функции Лиспа также могут быть вариативными . Язык программирования Tcl , как и Lisp, также использует польскую нотацию через библиотеку mathop. В языке программирования Ambi ^[14] для арифметических операций и построения программ используется польская нотация. Синтаксис фильтра LDAP использует польскую префиксную нотацию. ^[15]

Обозначение Postfix используется во многих языках программирования, ориентированных на стек, таких как PostScript и Forth . Синтаксис CoffeeScript также позволяет вызывать функции с использованием префиксной нотации, при этом поддерживая унарный постфиксный синтаксис, распространенный в других языках.

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

Польская нотация, обычно в виде постфикса, является выбранной нотацией некоторых калькуляторов , особенно Hewlett-Packard . ^[16] На более низком уровне постфиксные операторы используются некоторыми стековыми машинами, такими как большие системы Берроуза .

См. Также [ править ]

• Обратная польская запись
• Приложение функции
• Лямбда-исчисление
• Каррирование
• Лисп (язык программирования)
  • S-выражение
• Польская математическая школа
• Венгерская нотация
• Глагол – субъект – объект (VSO)
• Глагол – объект – субъект (ГОС)

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Лукасевич, Ян (1957). Силлогистика Аристотеля с точки зрения современной формальной логики . Издательство Оксфордского университета .
• Лукасевич, Ян (1930). "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.Переведено Х. Вебером в Storrs McCall, Polish Logic 1920-1939 , Clarendon Press : Oxford (1967).

Внешние ссылки [ править ]

• СМИ, связанные с польской нотацией (математикой) на Викискладе?