~~~~~~~~~~~~~~~~~~~~ Arc.Ask3.Ru ~~~~~~~~~~~~~~~~~~~~~ 
Номер скриншота №:
✰ FF580D4CC79E96684BE4270EF17A3E6B__1712440380 ✰
Заголовок документа оригинал.:
✰ Polish notation - Wikipedia ✰
Заголовок документа перевод.:
✰ Польские обозначения - Википедия ✰
Снимок документа находящегося по адресу (URL):
✰ https://en.wikipedia.org/wiki/Polish_notation ✰
Адрес хранения снимка оригинал (URL):
✰ https://arc.ask3.ru/arc/aa/ff/6b/ff580d4cc79e96684be4270ef17a3e6b.html ✰
Адрес хранения снимка перевод (URL):
✰ https://arc.ask3.ru/arc/aa/ff/6b/ff580d4cc79e96684be4270ef17a3e6b__translat.html ✰
Дата и время сохранения документа:
✰ 12.06.2024 03:28:42 (GMT+3, MSK) ✰
Дата и время изменения документа (по данным источника):
✰ 7 April 2024, at 00:53 (UTC). ✰ 

~~~~~~~~~~~~~~~~~~~~~~ Ask3.Ru ~~~~~~~~~~~~~~~~~~~~~~ 
Сервисы Ask3.ru: 
 Архив документов (Снимки документов, в формате HTML, PDF, PNG - подписанные ЭЦП, доказывающие существование документа в момент подписи. Перевод сохраненных документов на русский язык.)https://arc.ask3.ruОтветы на вопросы (Сервис ответов на вопросы, в основном, научной направленности)https://ask3.ru/answer2questionТоварный сопоставитель (Сервис сравнения и выбора товаров) ✰✰
✰ https://ask3.ru/product2collationПартнерыhttps://comrades.ask3.ru


Совет. Чтобы искать на странице, нажмите Ctrl+F или ⌘-F (для MacOS) и введите запрос в поле поиска.
Arc.Ask3.ru: далее начало оригинального документа

Польские обозначения - Википедия Jump to content

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

Из Википедии, бесплатной энциклопедии

Польская нотация ( 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»).

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

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

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

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

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

Концепция Общепринятый
обозначение
Польский
обозначение
Польский
срок
Отрицание [2] : 27–28  отрицание
Материал условный [2] : 28–31  импликация
Дизъюнкция [2] : 34–35  альтернатива
Соединение [2] : 35–36  соединение
Несоединение [2] : 36  дизъюнкция
двуусловный [2] : 37  или [3] : 108  эквивалентность
Универсальный квантификатор [2] : 154–156  общий квантификатор
Экзистенциальный квантор [2] : 157  подробный квантификатор
Истинный [15] : 275  правда правда
ЛОЖЬ [15] : 275  ложный, ложный
Возможность [16] : 52  [3] : 134  или [17] : 111  возможность
Необходимость [3] : 134  или [17] : 111  необходимость

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

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

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

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

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

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

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

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

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

  1. ^ Йорке, Гюнтер; Лампа, Бернар; Венгель, Норберт (1989). Арифметические алгоритмы микрокомпьютерах ( в на немецком языке) (1-е изд.). Берлин, Германия: VEB Verlag Technik . ISBN  3-34100515-3 . ЕАН   978-3-34100515-6 . МПН 5539165. Лицензия 201.370/4/89 . Проверено 1 декабря 2015 г.
  2. ^ Перейти обратно: а б с д Это ж г час я Лукасевич, Ян (1929). Элементы математической логики (на польском языке) (1-е изд.). Варшава, Польша: Национальное научное издательство ; Лукасевич, Ян (1963). Элементы математической логики . Перевод Войтасевича, Ольгерда Адриана [на польском языке] . Нью-Йорк, США: Компания MacMillan .
  3. ^ Перейти обратно: а б с д Это Лукасевич, Ян (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. ^ Перейти обратно: а б с Лукасевич, Ян (1931). «Комментарии к . аксиоме Никода и к «обобщающей дедукции»] Памятная книга Польского философского общества во Львове, 12 февраля. 1904–1912. II. 1929 г. (на польском языке). Львов: Издательство Польского философского общества. стр. 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 . (Примечание: оригинальная статья Яна Лукасевича «Заметки об аксиоме Никода и обобщающей дедукции» 1931 года была переиздана в Państwowe Wydawnictwo Naukowe (Национальное научное издательство), Варшава , Польша, в 1961 году в томе под редакцией Ежи Слупецкого .)
  10. ^ Шёнфинкель, Моисей (1924). «О составных элементах математической логики». Математические анналы (на немецком языке). 92 (3–4): 305–316. дои : 10.1007/BF01448013 . S2CID   118507515 ; ван Хейеноорт, Жан , изд. (1967). «О составных элементах математической логики». Справочник по математической логике, 1879–1931 гг . Перевод Бауэр-Менгельберга, Стефана [на голландском языке] . Издательство Гарвардского университета . стр. 355–366.
  11. ^ Готшалл, Кристиан (2005). Логические обозначения и их обработка в электронных вычислительных системах с теоретической, практической и исторической точки зрения (дипломная работа) (на немецком языке). Вена, Австрия. п. 88: Самые старые тексты «Избранных сочинений», в которых Лукасевич использует польские обозначения, датируются относительно поздно, но представляют собой изложения предыдущих произведений, которые имели место «в течение 1920–1930 годов» (с. 131), т.е. также не указывайте более точное время. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
  12. ^ Черч, Алонсо (1944). Введение в математическую логику . Принстон, Нью-Джерси, США: Издательство Принстонского университета . п. 38. […] Заслуживают внимания записи без скобок Яна Лукасевича. При этом буквы N, A, C, E, K используются в роли отрицания, дизъюнкции, импликации, эквивалентности и соединения соответственно. […]
  13. ^ Лукасевич, Ян ; Тарский, Альфред (1930). «Untersuchungen über den Aussagenkalküls» [Исследования по исчислению предложений]. Отчеты заседаний Варшавского общества наук и литературы (на немецком языке). 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» [Исследования по исчислению предложений]. Отчеты заседаний Варшавского общества наук и литературы (на немецком языке). 23 (кл. III): 51–77.
  17. ^ Перейти обратно: а б Лукасевич, Ян (1953). «Система модальной логики». Журнал вычислительных систем . 3 (1): 111–149.
  18. ^ Боченский, Иосиф Мэри (1949). Написано во Фрибуре. Точность математической логики (PDF) . Синтез коллекции (на французском языке). Том. 2. Буссум, Нидерланды, Нидерланды: Ф.Г. Крундер. Архивировано (PDF) из оригинала 08.08.2023. Получено 1 ноября 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 г.

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

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

Arc.Ask3.Ru: конец оригинального документа.
Arc.Ask3.Ru
Номер скриншота №: FF580D4CC79E96684BE4270EF17A3E6B__1712440380
URL1:https://en.wikipedia.org/wiki/Polish_notation
Заголовок, (Title) документа по адресу, URL1:
Polish notation - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть, любые претензии не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, денежную единицу можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)