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

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

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

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

История

Цитата из статьи Ян Лукасевич, Замечания об аксиоме Никода и об «обобщающей дедукции», стр. 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»).

Алгоритм оценки

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

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

Польское обозначение логики

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

Концепция	Общепринятый обозначение	Польский обозначение	Польский срок
Отрицание	${displaystyle, например, 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 o psi}$	${displaystyle mathrm {C} varphi psi}$	импликация
Двусмысленный	${displaystyle varphi leftrightarrow psi}$	${displaystyle mathrm {E} varphi psi}$	Эквиваленча
Ложь	${displaystyle ot}$	${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 существует p, varphi}$	${displaystyle Sigma p, varphi}$	kwantyfikator szczegółowy

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

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

Реализации

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

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

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

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

Смотрите также

дальнейшее чтение

Лукасевич, Ян (1957). Силлогистика Аристотеля с точки зрения современной формальной логики. Oxford University Press.
Лукасевич, Ян (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, Польская логика 1920-1939, Clarendon Press: Оксфорд (1967).

внешняя ссылка

СМИ, связанные с Польская нотация (математика) в Wikimedia Commons

[Jorke_1989-1] Йорке, Гюнтер; Лампе, Бернхард; Венгель, Норберт (1989). Arithmetische Algorithmen der Mikrorechentechnik [Арифметические алгоритмы в микрокомпьютерах] (на немецком языке) (1-е изд.). Берлин, Германия: ВЭБ Верлаг Техник. ISBN 3341005153. EAN 9783341005156. MPN 5539165. Лицензия 201.370 / 4/89.. Получено 2015-12-01.

[Łukasiewicz_1957-2] Лукасевич, Ян (1957). Силлогистика Аристотеля с точки зрения современной формальной логики. Oxford University Press. (Перепечатано издательством Garland Publishing в 1987 г. ISBN 0-8240-6924-2)

[Hamblin_1962-3] Хэмблин, Чарльз Леонард (1962). «Перевод в польскую нотацию и обратно» (PDF). Компьютерный журнал. 5 (3): 210–213. Дои:10.1093 / comjnl / 5.3.210.

[Ball_1978-4] Болл, Джон А. (1978). Алгоритмы для калькуляторов RPN (1-е изд.). Кембридж, Массачусетс, США: Wiley-Interscience, John Wiley & Sons, Inc. ISBN 0-471-03070-8.

[Main_2006-5] Мэйн, Майкл (2006). Структуры данных и другие объекты с использованием Java (3-е изд.). Pearson PLC Эддисон-Уэсли. п. 334. ISBN 978-0-321-37525-4.

[Pogorzelski_1965-6] Погожельский, Генри А., "Рецензируемые работы: Замечания об Аксиоме Никода и" Обобщающей дедукции "Яна Лукасевича; Ежи Слупецкого; Państwowe Wydawnictwo Naukowe", Журнал символической логики, Vol. 30, № 3 (сентябрь 1965 г.), стр. 376–377. Оригинальная статья Лукасевича была опубликована в Варшава в 1961 году в томе под редакцией Ежи Слупецкого.

[Mengelberg-7] "Über die Bausteine der Mathematischen Logik", Mathematische Annalen 92, страницы 305-316. Перевод Стефана Бауэра-Менгельберга как «О строительных блоках математической логики» в Жан ван Хейеноорт, 1967. Справочник по математической логике, 1879-1931 гг.. Издательство Гарвардского университета: 355-66.

[Church_1944-8] Церковь, Алонсо (1944). Введение в математическую логику. Принстон, Нью-Джерси, США: Princeton University Press. п. 38. […] Заслуживает внимания запись Яна Лукасевича без скобок. Здесь буквы N, A, C, E, K используются в ролях отрицания, дизъюнкции, импликации, эквивалентности, соединения соответственно. […]

[Łukasiewicz_1951-9] Лукасевич, (1951) Силлогистика Аристотеля с точки зрения современной формальной логики, Глава IV «Система Аристотеля в символической форме» (раздел «Объяснение символизма»), с. 78 и далее.

[Łukasiewicz_1930-10] Лукасевич, Ян; Тарский, Альфред, «Untersuchungen über den Aussagenkalkül» [«Исследования исчисления предложений»], Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie, Vol. 23 (1930) Кл. III, стр. 31–32.

[Martínez_2011-11] Мартинес Нава, Ксочитл (2011-06-01), «Mhy bib I fail logic? Дислексия в преподавании логики», в Блэкберне, Патрик; ван Дитмарш, Ганс; Манзано, Мария; Солер-Тоскано, Фернандо (ред.), Инструменты для обучения логике: Третий международный конгресс, TICTTL 2011, Саламанка, Испания, 1-4 июня 2011 г., Материалы, Конспект лекций по искусственному интеллекту, 6680, Springer Nature, стр. 162–169, Дои:10.1007/978-3-642-21350-2_19, ISBN 9783642213496, […] Польская или префиксная нотация вышла из употребления, учитывая сложность ее использования. […]

[Craig_1998-12] Крейг, Эдвард (1998), Энциклопедия философии Рутледж, том 8, Тейлор и Фрэнсис, п. 496, г. ISBN 9780415073103.

[Bocheński_1959-13] Бохенский, Юзеф Мария (1959). A Precis of Mathematical Logic, переведенный Отто Бердом из французского и немецкого изданий, D. Reidel: Dordrecht, Holland.

[Ambi-14] ttps://code.google.com/p/ambi/

[LDAPSyntax-15] ttp://www.ldapexplorer.com/en/manual/109010000-ldap-filter-syntax.htm

[RPN_HP35S-16] "Калькуляторы HP | HP 35s RPN Mode » (PDF). Hewlett Packard.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]