stringtranslate.com

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

Польская нотация ( PN ), также известная как нормальная польская нотация ( NPN ), [1] нотация Лукасевича , Варшавская нотация , Польская префиксная нотация или просто префиксная нотация — это математическая нотация, в которой операторы предшествуют своим операндам , в отличие от более распространенной инфиксной нотации , в которой операторы размещаются между операндами, а также обратной польской нотации (RPN), в которой операторы следуют за своими операндами. Она не нуждается в скобках, пока каждый оператор имеет фиксированное количество операндов . Описание «польская» относится к национальности логика Яна Лукасевича , [2] : 24  [3] : 78  [ 4], который изобрел польскую нотацию в 1924 году. [5] : 367, сноска 3  [6] : 180, сноска 3 

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

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

История

Цитата из статьи Яна Лукасевича 1931 года [5] : 367, сноска 3  [6] : 180, сноска 3  описывает, как была изобретена эта нотация:

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

Ссылка, цитируемая Лукасевичем, т. е. Лукасевич (1), [8], по-видимому, является литографированным отчетом на польском языке . Ссылающаяся статья [5] Лукасевича была рассмотрена Генри А. Погожельским в журнале символической логики в 1965 году. [9] Генрих Бехманн , редактор в 1924 году статьи Моисея Шёнфинкеля , [10] уже имел идею устранения скобок в логических формулах. В одной из своих статей Лукасевич заявил, что его нотация является наиболее компактной и первой линейно записанной безскобочной нотацией, но не первой, поскольку Готтлоб Фреге предложил свою безскобочную нотацию Begriffsschrift еще в 1879 году. [11]

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

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

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

Объяснение

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

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

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

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

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

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

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

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

Реализации

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

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

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

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

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

Ссылки

  1. ^ Йорке, Гюнтер; Лампе, Бернхард; Венгель, Норберт (1989). Arithmetische Algorithmen der Mikrorechentechnik [ Арифметические алгоритмы в микрокомпьютерах ] (на немецком языке) (1-е изд.). Берлин, Германия: VEB Verlag Technik . ISBN 3-34100515-3. EAN  978-3-34100515-6. MPN 5539165. Лицензия 201.370/4/89 . Получено 01.12.2015 .
  2. ^ abcdefghi Лукасевич, январь (1929). Elementy logiki matematycznej (на польском языке) (1-е изд.). Варшава, Польша: Państwowe Wydawnictwo Naukowe; Лукасевич, Ян (1963). Элементы математической логики . Перевод Войтасевича, Ольгерда Адриана [на польском языке] . Нью-Йорк, США: Компания MacMillan .
  3. ^ abcde Лукасевич, Ян (1957) [1951]. Силлогистика Аристотеля с точки зрения современной формальной логики (2-е изд.). Oxford University Press .(Переиздано Garland Publishing в 1987 году, ISBN 0-8240-6924-2 .) 
  4. ^ Кеннеди, Джон (август 1982 г.). «RPN Perspective». PPC Calculator Journal . 9 (5). Математический факультет, Колледж Санта-Моники, Санта-Моника, Калифорния, США: 26–29. CiteSeerX 10.1.1.90.6448 . Архивировано из оригинала 01.07.2022 . Получено 02.07.2022 . (12 страниц)
  5. ^ abc Лукасевич, Январь (1931). «Uwagi o aksjomacie Nicoda i 'dedukcji uogólniającej'» [Комментарии к аксиоме Никода и к «обобщающей дедукции»). Księga pamiątkowa Polskiego Towarzystwa Filozoficznego We Lwowie, 12. II. 1904–1912. II. 1929 г. (на польском языке). Львов: Wydawnictwo Polskie Towarzystwo Filozoficzne. стр. 366–383.
  6. ^ Лукасевич, Ян (1970). «Комментарии к аксиоме Никода и к «Обобщающей дедукции»". В Борковски, Л. (ред.). Избранные труды . Амстердам и Лондон/Варшава: North-Holland Publishing Company/Polish Scientific Publishers. С. 179–196.
  7. ^ Main, Michael (2006). Структуры данных и другие объекты с использованием Java (3-е изд.). Pearson PLC Addison-Wesley . стр. 334. ISBN  978-0-321-37525-4.
  8. ^ Лукасевич, Ян (1929). «О значении и математической логике». Наука Польска (на польском языке). 10 : 604–620.
  9. ^ Погожельски, Генри Эндрю (сентябрь 1965 г.). «Рецензируемые работы: Замечания об аксиоме Никода и об «обобщающей дедукции» Яна Лукасевича, Ежи Слупецкого, Państwowe Wydawnictwo Naukowe». Журнал символической логики (обзор). 30 (3). Ассоциация символической логики : 376–377. JSTOR  2269644.(Примечание. Оригинальная статья Яна Лукасевича «Uwagi o aksjomacie Nicoda i 'dedukcji uogólniającej» 1931 года была переиздана в Państwowe Wydawnictwo Naukowe (Национальное научное издательство), Варшава , Польша, в 1961 году в томе под редакцией Ежи Слупецкого .)
  10. ^ Шенфинкель, Моисей (1924). «Über die Bausteine ​​der mathematischen Logik» [О строительных блоках математической логики]. Mathematische Annalen (на немецком языке). 92 (3–4): 305–316. дои : 10.1007/BF01448013. S2CID  118507515; ван Хейеноорт, Жан , ред. (1967). «О строительных блоках математической логики». Источниковая книга по математической логике, 1879–1931 . Перевод Бауэра-Менгельберга, Стефана [на голландском языке] . Издательство Гарвардского университета . стр. 355–366.
  11. ^ Готшалл, Кристиан (2005). Logische Notationen und deren Verarbeitung auf elektronischen Rechenanlagen aus theoretischer, praktischer und historischer Sicht (Дипломная работа) (на немецком языке). Вена, Австрия. п. 88: Die ältesten Texte in den «Избранные произведения», in denen Łukasiewicz polnische Notation verwendet, datieren relativ spät, sind aber Präsentationen vorangehender Arbeiten, die «в течение 1920–1930 годов» (S. 131) stattgefunden haben, также auch keine genauere Zeitangabe geben.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
  12. ^ Чёрч, Алонзо (1944). Введение в математическую логику . Принстон, Нью-Джерси, США: Princeton University Press . стр. 38. […] Достойна упоминания бесскобочная запись Яна Лукасевича. В ней буквы N, A, C, E, K используются в ролях отрицания, дизъюнкции, импликации, эквивалентности, конъюнкции соответственно. […]
  13. ^ Лукасевич, Ян ; Тарский, Альфред (1930). «Untersuchungen über den Aussagenkalküls» [Исследования по исчислению предложений]. Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie (на немецком языке). 23 (кл. III): 30–50.
  14. ↑ Мартинес Нава, Ксочитль (01.06.2011), «Mhy bib I fail logic? Dyslexia in the teaching of logic», в Blackburn, Patrick; van Ditmarsch, Hans; Manzano, Maria ; Soler-Toscano, Fernando (ред.), Tools for Teaching Logic: Third International Congress, TICTTL 2011, Salamanca, Spain, 1–4 июня 2011 г., Proceedings, Lecture Notes in Artificial Intelligence, vol. 6680, Springer Nature , стр. 162–169, doi :10.1007/978-3-642-21350-2_19, ISBN 978-3-64221349-6, […] Польская или префиксная запись вышла из употребления из-за трудностей, которые влечет за собой ее использование. […]
  15. ^ аб Лукасевич, Январь (1939). «Дер Эквивалензенкалькюль». Collectanea Logica (на немецком языке). 1 : 145–169.
  16. ^ Лукасевич, Ян (1930). «Untersuchungen über den Aussagenkalküls» [Исследования по исчислению предложений]. Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie (на немецком языке). 23 (кл. III): 51–77.
  17. ^ ab Лукасевич, Ян (1953). «Система модальной логики». Журнал вычислительных систем . 3 (1): 111–149.
  18. ^ Боченский, Юзеф Мария (1949). Написано во Фрибуре. Краткое изложение математической логики (PDF) . Коллекция Synthese (на французском языке). Том. 2. Буссум, Пайс-Бас, Нидерланды: Ф.Г. Крундер. Архивировано (PDF) из оригинала 3 августа 2023 г. Проверено 12 ноября 2023 г.Перевод: Bocheński, Józef Maria (1959). A Precis of Mathematical Logic . Перевод: Bird, Otto A. [на Wikidata] . Дордрехт, Нидерланды: D. Reidel Publishing Company.
  19. ^ "Архив Google Code - Долгосрочное хранилище для хостинга проектов Google Code". Архивировано из оригинала 2017-09-28 . Получено 2022-11-14 .
  20. ^ "LDAP Filter Syntax". Архивировано из оригинала 2022-10-14 . Получено 2022-11-14 .
  21. ^ "Калькуляторы HP - HP 35s RPN Mode" (PDF) . Hewlett-Packard . Архивировано (PDF) из оригинала 2022-01-21 . Получено 2022-11-14 .

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

Внешние ссылки