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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Польська нотація (також відома як префіксна нотація, PN)[1] — вид запису алгебраїчних та логічних виразів, при якому група символів операції записується ліворуч від групи операндів. Якщо арність операторів фіксована, то отримуємо синтаксис без використання будь-яких дужок і без двозначності. Польську нотацію запропонував у 1924 році польський логік Ян Лукасевич з метою спрощення логіки висловлень.

Інколи поняття Польської нотації включає (як протилежність інфіксної нотації[en]) Польську постфіксну нотацію або зворотній Польський запис (англ. Reverse Polish notation, RPN), у якому оператори розташовані після операндів.[2]

Коли польська нотація використовується синтаксисом математичних виразів трансляторів мов програмування, вона легко розкладається у абстрактні синтаксичні дерева та фактично має взаємно однозначне відношення з інфіксною нотацією. Тому Лісп та споріднені йому мови програмування визначають їх синтаксис у визначеннях префіксної нотації (тоді як інші використовують постфіксну)

Нижче приведена цитата з статті Яна Лукасевича, Зауваження щодо аксіоми Нікода та про «Узагальнення дедукції», сторінка 180.[3]

Я несподівано натрапив на ідею бездужкової нотації у 1924 році. Я вперше використав її в виносці до моєї статті Łukasiewicz(1), сторінка 610.

Посилання, цитоване Лукасевичем, певно літографічна доповідь польською мовою. Його стаття Зауваження щодо аксіоми Нікода та про «Узагальнення дедукції» була розглянута Ґ. А. Погожельським в Journal of Symbolic Logic у 1965 році.[4]

Алонзо Черч згадував цю нотацію в своїй книзі з математичної логіки, як гідну уваги систему нотації і навіть протиставляв логічним нотаціям Альфреда Уайтхеда і Бертрана Рассела в праці «Principia Mathematica».[5]

В книзі Лукасевича Силогістика Арістотеля з точки зору сучасної формальної логіки, що була опублікована 1951 року, він згадував, що принцип його нотації полягає у запису функторів до аргументів для уникнення дужок та те, що він застосовував цю нотацію у статтях з логіки починаючи з 1929 року.[6] Потім він починає цитувати, як приклад, статтю 1930 року, яку він написав разом з Альфредом Тарським про сентентенціонне обчислення.[7]

Незважаючи на те, що польська нотація не використовується в математиці, вона широко застосовується в інформатиці.

Арифметика[ред.ред. код]

У префіксній нотації додавання чисел 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). Як і в будь-який інший нотації, вирази, що знаходяться в глибше, обчислюються першими, але в польському записі глибина виразу визначається порядком, а не дужками.

Префіксний запис в простій арифметиці представляє собою в значній мірі академічний інтерес. Як і постфіксний запис, префіксна нотація була використана для деяких комерційних обчислювальних машин (HP-11С). Вивчення префіксної нотації часто є першим кроком в області конструювання компіляторів.

Програмування[ред.ред. код]

Префіксний запис широко застосовується в s-виразах в мові програмування Лісп (LISP), де дужки необхідні, оскільки арифметичні оператори мають різну арність. Мова програмування Ambi використовує польську нотацію для арифметичних операцій і структури програми. Постфіксний запис використовується в багатьох стекових мовах, як PostScript, так і є основою для багатьох обчислювальних машин (калькуляторів), особливо для обчислювальних машин Hewlett-Packard.

Синтаксис мови програмування CoffeeScript дозволяє викликати функції, використовуючи префіксну нотацію, у той же час підтримуючи поширений для мов програмування унарний постфіксний синтаксис.

Також важливо відзначити, що кількість операндів у виразі має бути на один більше ніж кількість операцій, інакше вираз не має сенсу (враховуючи, що в вираженні використовуються тільки бінарні операції). Цьому можна легко не надавати значення при роботі з довгими, складними виразами, що спричинить за собою помилки. Тому необхідно звертати увагу на кількість операцій і операндів при використанні префіксної нотації.

Порядок операцій[ред.ред. код]

Порядок операцій визначається структурою префіксної нотації і може бути легко визначений. Головне, потрібно пам'ятати, що при обчисленні виразу порядок операндів потрібно зберігати. Це не важливо для операцій, які мають властивість комутативності, але для не комутативних операцій, таких як віднімання і ділення, цей факт є ключовим для аналізу виразу. Наприклад, такий вираз:

/ 10 5 = 2 (префіксний запис)

потрібно прочитати, як «10 ділити на 5». Тому результатом обчислення буде 2, а не ½, що було б результатом неправильного аналізу виразу.

Префіксний запис особливо популярний в стекових мовах програмування[en] завдяки властивій їм можливості легко розрізняти порядок операцій без використання дужок. Для виявлення порядку обчислення операторів в префіксній нотації немає необхідності запам'ятовувати всю операційну ієрархію, як при інфіксній нотації[en]. Замість того, щоб аналізувати вираз для виявлення оператора, який потрібно обчислити першим, потрібно зчитувати вираз зліва направо, розглядаючи оператор і найближчі до нього два операнда. Якщо серед цих операндів знаходиться ще один оператор, то обчислення першого оператора відкладається, до тих пір, поки не буде обчислений новий оператор. Ітерації цього процесу повторюються до тих пір, поки оператор не буде обчислено, що має в кінцевому рахунку статися, якщо вираз коректний. Як тільки оператор обчислений, він і його два операнда замінюються отриманим значенням (операндом). Оскільки оператор і два операнда замінюються на обчислений операнд, то стає на один оператор і один операнд менше. Після в вираженні цього також залишається N операторів і N + 1 операнд, що дозволяє ітеративно продовжувати процес.

У наведеному нижче прикладі можна побачити, що складне на перший погляд вираз в префіксній нотації, насправді виявляється не такою вже складною для розуміння (праворуч від знака рівності відповідний вираз в інфіксному записі):

 - * / 15 - 7 + 1 1 3 + 2 + 1 1  =  15 / (7 - (1 + 1)) * 3 - (2 + (1 + 1))
 - * / 15 - 7   2   3 + 2 + 1 1  =  15 / (7 - 2) * 3 - (2 + (1 + 1))
 - * / 15     5     3 + 2 + 1 1  =  15 / 5 * 3 - (2 + (1 + 1))
 - *        3       3 + 2 + 1 1  =  3 * 3 - (2 + (1 + 1))
 -          9         + 2 + 1 1  =  9 - (2 + (1 + 1))
 -          9         + 2   2    =  9 - (2 + 2)
 -          9         4          =  9 - 4
                5                =  5

Польська нотація в логіці[ред.ред. код]

Таблиця, наведена нижче, демонструє ядро запису запропонованої Яном Лукашевичем для числення висловлень. Деякі букви Польського запису означають конкретні слова на польській мові:

Поняття Умовна
нотація
Польська
нотація
Польське
слово
Заперечення φ negacja
Кон'юнкція φψ Kφψ koniunkcja
Диз'юнкція φψ Aφψ alternatywa
Імплікація φψ Cφψ
Еквівалентність φψ Eφψ ekwiwalencja
Штрих Шефера Dφψ dysjunkcja
Можливість φ możliwość
Необхідність φ
Квантор загальності φ Πφ
Квантор існування φ Σφ

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. Jorke, Günter; Lampe, Bernhard; Wengel, Norbert (1989). Arithmetische Algorithmen der Mikrorechentechnik [Arithmetic algorithms in microcomputers] (German) (вид. 1). Berlin, Germany: VEB Verlag Technik. ISBN 3341005153. EAN:9783341005156, MPN:5539165, License:201.370/4/89. Процитовано 2015-12-01. 
  2. Michael Main (2006). Data structures and other objects using Java (вид. 3rd). Pearson Addison-Wesley. с. 334. ISBN 978-0-321-37525-4. 
  3. Łukasiewicz, Jan, Remarks on Nicod's Axiom and on «Generalizing Deduction», page 180.
  4. Pogorzelski, H. A., «Reviewed work(s): Remarks on Nicod's Axiom and on „Generalizing Deduction“ by Jan Łukasiewicz; Jerzy Słupecki; Państwowe Wydawnictwo Naukowe», The Journal of Symbolic Logic, Vol. 30, No. 3 (Sep. 1965), pp. 376—377. The original paper by Jan Łukasiewicz was published in Warsaw in 1961 in a volume edited by Jerzy Słupecki.
  5. Church Alonzo. Introduction to Mathematical Logic. — Princeton, New Jersey: Princeton University Press, 1944. — p.38: «Worthy of remark is the parenthesis-free notation of Jan Łukasiewicz. In this the letters N, A, C, E, K are used in the roles of negation, disjunction, implication, equivalence, conjunction respectively. …»
  6. Cf. Łukasiewicz, (1951) Aristotle's Syllogistic from the Standpoint of Modern Formal Logic, Chapter IV «Aristotle's System in Symbolic Form» (секція «Explanation of the Symbolism»), сторінка 78 і далі.
  7. Łukasiewicz, Jan; Tarski, Alfred, «Untersuchungen über den Aussagenkalkül» ["Investigations into the sentential calculus"], Comptes Rendus des séances de la Société des Sciences et des Lettres de Varsovie, Розділ 23 (1930) Cl. III, сторінки 31–32.

Література[ред.ред. код]

  • Łukasiewicz, Jan (1957). Aristotle’s Syllogistic from the Standpoint of Modern Formal Logic. Oxford University Press. 
  • Łukasiewicz, Jan, «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 (1930). Translated by H. Weber as «Philosophical Remarks on Many-Valued Systems of Propositional Logics», in Storrs McCall, Polish Logic 1920—1939, Clarendon Press: Oxford (1967).

Посилання[ред.ред. код]

  • Ambi — розширюваний браузерний калькулятор ПІЗ Девіда Пратена.[1]