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 года . ] : 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»).

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

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

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

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

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

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

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

Реализации

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

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

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

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

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

Рекомендации

  1. ^ Йорке, Гюнтер; Лампе, Бернхард; Венгель, Норберт (1989). Arithmetische Algorithmen der Mikrorechentechnik [ Арифметические алгоритмы в микрокомпьютерах ] (на немецком языке) (1-е изд.). Берлин, Германия: VEB Verlag Technik . ISBN 3-34100515-3. ЕАН  978-3-34100515-6. МПН 5539165. Лицензия 201.370/4/89 . Проверено 1 декабря 2015 г.
  2. ^ abcdefghi Лукасевич, январь (1929). Elementy logiki matematycznej (на польском языке) (1-е изд.). Варшава, Польша: Państwowe Wydawnictwo Naukowe; Лукасевич, Ян (1963). Элементы математической логики . Перевод Войтасевича, Ольгерда Адриана [на польском языке] . Нью-Йорк, США: Компания MacMillan .
  3. ^ abcde Лукасевич, Ян (1957) [1951]. Силлогистика Аристотеля с точки зрения современной формальной логики (2-е изд.). Издательство Оксфордского университета .(Перепечатано издательством Garland Publishing в 1987 году, ISBN 0-8240-6924-2 .) 
  4. ^ Кеннеди, Джон (август 1982 г.). «РПН Перспектива». Журнал калькулятора PPC . Математический факультет Колледжа Санта-Моники, Санта-Моника, Калифорния, США. 9 (5): 26–29. CiteSeerX 10.1.1.90.6448 . Архивировано из оригинала 1 июля 2022 г. Проверено 2 июля 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). «Комментарии к аксиоме Никода и к «обобщающей дедукции»". Борковский, Л. (ред.). Избранные произведения . Амстердам и Лондон / Варшава: Издательство Северной Голландии / Польское научное издательство. Стр. 179–196.
  7. ^ Мейн, Майкл (2006). Структуры данных и другие объекты с использованием Java (3-е изд.). Pearson PLC Аддисон-Уэсли . п. 334. ИСБН  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). Введение в математическую логику . Принстон, Нью-Джерси, США: Издательство Принстонского университета . п. 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), «Почему я не справляюсь с логикой? Дислексия в преподавании логики», в Блэкберне, Патрик; ван Дитмарш, Ганс; Мансано, Мария ; Солер-Тоскано, Фернандо (ред.), Инструменты для преподавания логики: Третий международный конгресс, TICTTL 2011, Саламанка, Испания, 1–4 июня 2011 г., Материалы, конспекты лекций по искусственному интеллекту, том. 6680, Springer Nature , стр. 162–169, номер документа : 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. ^ Аб Лукасевич, Январь (1953). «Система модальной логики». Журнал вычислительных систем . 3 (1): 111–149.
  18. ^ Боченский, Юзеф Мария (1949). Написано во Фрибуре. Краткое изложение математической логики (PDF) . Коллекция Synthese (на французском языке). Том. 2. Буссум, Пайс-Бас, Нидерланды: Ф.Г. Крундер. Архивировано (PDF) из оригинала 3 августа 2023 г. Проверено 12 ноября 2023 г.В переводе Боченский, Юзеф Мария (1959). Краткое изложение математической логики . Перевод Берда, Отто А. [в Викиданных] . Дордрехт, Нидерланды: Издательство Д. Рейделя.
  19. ^ «Архив кода Google — долгосрочное хранилище для хостинга проектов Google Code» . Архивировано из оригинала 28 сентября 2017 г. Проверено 14 ноября 2022 г.
  20. ^ «Синтаксис фильтра LDAP» . Архивировано из оригинала 14 октября 2022 г. Проверено 14 ноября 2022 г.
  21. ^ «Калькуляторы HP — режим HP 35s RPN» (PDF) . Hewlett Packard . Архивировано (PDF) из оригинала 21 января 2022 г. Проверено 14 ноября 2022 г.

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

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