Префіксна форма запису

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

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

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

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

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

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

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

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

Попри те, що польська нотація більше активно не використовується в логіці, вона широко застосовується в інформатиці.

Арифметика

У префіксній нотації додавання чисел 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»).

Програмування

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

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

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

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

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

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

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

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

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

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

Поняття	Умовна нотація	Польська нотація	Польське слово
Заперечення	${\displaystyle \neg }$φ	Nφ	negacja
Кон'юнкція	φ${\displaystyle \wedge }$ψ	Kφψ	koniunkcja
Диз'юнкція	φ${\displaystyle \lor }$ψ	Aφψ	alternatywa
Імплікація	φ${\displaystyle \rightarrow }$ψ	Cφψ
Еквівалентність	φ${\displaystyle \leftrightarrow }$ψ	Eφψ	ekwiwalencja
Штрих Шефера	${\displaystyle \phi |\psi }$	Dφψ	dysjunkcja
Можливість	${\displaystyle \Diamond }$φ	Mφ	możliwość
Необхідність	${\displaystyle \Box }$φ	Lφ
Квантор загальності	${\displaystyle \forall }$φ	Πφ
Квантор існування	${\displaystyle \exists }$φ	Σφ

Див. також

• Польський інверсний запис
• Лямбда-числення
• Польська математична школа
• Угорська нотація

Примітки

1. Jorke, Günter; Lampe, Bernhard; Wengel, Norbert (1989). Arithmetische Algorithmen der Mikrorechentechnik [Arithmetic algorithms in microcomputers] (German) (вид. 1). Berlin, Germany: ^[de]. ISBN . EAN:9783341005156, MPN:5539165, License:201.370/4/89. Процитовано 1 грудня 2015.
2. Łukasiewicz, Jan (1957). Aristotle's Syllogistic from the Standpoint of Modern Formal Logic. Oxford University Press. (Reprinted by Garland Publishing in 1987. )
3. (1962). Translation to and from Polish notation (PDF). . 5 (3): 210—213. doi:10.1093/comjnl/5.3.210.
4. Ball, John A. (1978). Algorithms for RPN calculators (вид. 1). Cambridge, Massachusetts, USA: Wiley-Interscience, ISBN .
5. Michael Main (2006). Data structures and other objects using Java (вид. 3rd). Pearson Addison-Wesley. с. 334. ISBN .
6. Łukasiewicz, Jan, Remarks on Nicod's Axiom and on «Generalizing Deduction», page 180.
7. 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.
8. 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. …»
9. 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 і далі.
10. Ł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.
11. Martínez Nava, Xóchitl (1 червня 2011), Mhy bib I fail logic? Dyslexia in the teaching of logic, у Blackburn, Patrick; van Ditmarsch, Hans; ; Soler-Toscano, Fernando (ред.), Tools for Teaching Logic: Third International Congress, TICTTL 2011, Salamanca, Spain, June 1-4, 2011, Proceedings, Lecture Notes in Artificial Intelligence, т. 6680, Springer Nature, с. 162—169, doi:10.1007/978-3-642-21350-2_19, ISBN , […] Polish or prefix notation has come to disuse given the difficulty that using it implies. […]

Література

• Ł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. Pratten, Devid. About Devid R Pratten.