Notație prefixată
Notația prefixată[1] sau notația poloneză prefixată (în engleză Normal Polish notation – NPN[2][3]) este o notație pentru o operație matematică și logică în care operatorii sunt plasați înainte de operanzi, cum ar fi semnul plus în expresia + 3 4.
Avantajul acestei notații este că nu are nevoie de paranteze cât timp fiecare operator are un număr de operanzi fix. Descrierea „poloneză” se referă la naționalitatea logicianului Jan Łukasiewicz,[4][5] care a inventat această notație în 1924.[6]
Termenul de „notație poloneză” este folosit în opoziție cu „notație infixată” și cuprinde atât notația poloneză prefixată, cât și pe cea postfixată.[7]
Când notația poloneză este folosită ca sintaxă pentru expresiile matematice de către interpretoarele limbajelor de programare, este prelucrată ușor în arbori sintactici abstracți(d) și de fapt poate defini o bijecție între acestea. Din această cauză, LISP și limbajele de programare înrudite își definesc întreaga sintaxă în notația prefixată (folosită și de alte limbaje).
Istoric
modificareUn citat dintr-o lucrare a lui Jan Łukasiewicz, Observații asupra axiomei lui Nicod și asupra „deducției generalizate”, pagina 180, arată cum a fost inventată notația:
„Am pornit la ideea unei notații fără paranteze în 1924. Am folosit această notație pentru prima dată în articolul meu Łukasiewicz(1), p. 610, notă de subsol.”
Referința citată de Łukasiewicz este aparent o raportare litografiată în limba poloneză. Lucrarea de referință a lui Łukasiewicz Observații asupra axiomei lui Nicod și asupra „deducției generalizate” a fost revizuită de Henry A. Pogorzelski în Journal of Symbolic Logic în 1965.[8] Heinrich Behmann, editor în 1924 al unui articol de Moses Schönfinkel,[9] avea deja ideea de a elimina parantezele din formulele logice. Într-una dintre lucrările sale, Łukasiewicz a afirmat că notația sa este cea mai compactă și este o notație scrisă liniar fără paranteze, dar nu prima, deoarece Gottlob Frege propusese deja notația sa fără paranteze în Begriffsschrift în 1879.[10]
Alonzo Church menționează această notație în cartea sa clasică despre logica matematică ca fiind demnă de remarcat în sistemele de notație, în contrast cu cele afirmate în lucrarea Principia Mathematica de Alfred North Whitehead și Bertrand Russell.[11]
În cartea lui Łukasiewicz din 1951, Silogistica lui Aristotel din punctul de vedere al logicii formale moderne, el menționează că principiul notației sale a fost acela de a scrie operatorul înainte de argumente pentru a evita parantezele și că și-a folosit notația în lucrările sale de logică din 1929.[12] Apoi citează, ca exemplu, o lucrare din 1930 pe care a scris-o împreună cu Alfred Tarski despre logica propozițională(d).[13]
Deși nu se mai folosește prea mult în logică,[14] notația prefixată este folosită în informatică.
Exemple de cum funcționează
modificareExpresia pentru adunarea numerelor 1 și 2 este scrisă în notația prefixată drept + 1 2 în loc de 1 + 2, cum este în notația infixată. În expresii, chiar complexe, operatorii preced operanzii lor, dar operanzii pot fi ei înșiși expresii care includ din nou operatori și operanzii lor. De exemplu, expresia care ar fi scrisă în notația infixată convențională ca
- (5 − 6) × 7
poate fi exprimată în notația prefixată ca
- × (− 5 6) 7
Presupunând o aritate dată a tuturor operatorilor implicați (aici "−" denotă operația binară de scădere, nu funcția unară de schimbare a semnului), orice reprezentare prefixată bine formată este lipsită de ambiguitate, iar parantezele în expresia prefixată sunt inutile. Ca atare, expresia de mai sus poate fi simplificată în continuare la
- × − 5 6 7
Efectuarea produsului este amânată până când cei doi operanzi ai săi sunt disponibili (adică 5 minus 6, și 7). Ca și în cazul oricărei notații, sunt evaluate mai întâi expresiile cele mai interioare, dar în notația poloneză această „interioritate” poate fi transmisă prin succesiunea de operatori și operanzi, fără paranteze.
În notația convențională, infixată, parantezele sunt necesare pentru a depăși regulile standard de prioritate. În exemplul de mai sus, mutarea parantezelor
- 5 − (6 × 7)
sau îndepărtarea lor
- 5 − 6 × 7
schimbă sensul expresiei și rezultatul. Această expresie este scrisă în notație prefixată ca
- − 5 × 6 7.
Când apar operații necomutative, cum ar fi împărțirea sau scăderea, este necesar să se coordoneze aranjarea în secvență a operanzilor cu definirea modului în care operatorul își ia argumentele, adică de la stânga la dreapta (se poate și invers). De exemplu, : 10 5, cu 10 la stânga lui 5, are semnificația 10 : 5 (se înțelege „împarte 10 la 5”) sau prin − 7 6, cu 7 la stânga lui 6, are semnificația 7 − 6 (se înțelege „scade din 7 operandul 6”).
Implementare
modificareNotația prefixată a fost aplicată pe scară largă în LISP, Tcl/TK și LDAP.
Note
modificare- ^ Ioan Ivan, Marius Popa, Paul Pocatilu, Structuri de date, București, Editura ASE, 2008, ISBN: 978-606-505-031-0
- ^ en „The Implementation and Power of Programming Languages”. Accesat în .
- ^ de Jorke, Günter; Lampe, Bernhard; Wengel, Norbert (). Arithmetische Algorithmen der Mikrorechentechnik [Arithmetic algorithms in microcomputers] (ed. 1). Berlin, Germany: VEB Verlag Technik. ISBN 3-34100515-3. ISBN: 978-3-34100515-6. MPN 5539165. License 201.370/4/89. Accesat în .
- ^ en Łukasiewicz, Jan (). „Chapter IV. Aristotle's System in Symbolic Form (section on "Explanation of the Symbolism")”. Aristotle's Syllogistic from the Standpoint of Modern Formal Logic (ed. 1). p. 78.
- ^ en Łukasiewicz, Jan (). Aristotle's Syllogistic from the Standpoint of Modern Formal Logic (ed. 2). Oxford University Press. (Reprinted by Garland Publishing in 1987 ISBN: 0-8240-6924-2.)
- ^ pl Łukasiewicz, Jan (februarie 1929). Elementy logiki matematycznej (ed. 1). Warsaw, Poland: Państwowe Wydawnictwo Naukowe
- ^ en Main, Michael (). Data structures and other objects using Java (ed. 3rd). Pearson PLC Addison-Wesley. p. 334. ISBN 978-0-321-37525-4.
- ^ en Pogorzelski, Henry Andrew (septembrie 1965). „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 (Review). Association for Symbolic Logic. 30 (3): 376–377. JSTOR 2269644. (NB. The original 1931 paper "Uwagi o aksjomacie Nicoda i 'dedukcji uogólniającej" by Jan Łukasiewicz was re-published at Państwowe Wydawnictwo Naukowe, Warsaw, Poland in 1961 in a volume edited by Jerzy Słupecki.)
- ^ de Schönfinkel, Moses (). „Über die Bausteine der mathematischen Logik”. Mathematische Annalen. 92 (3–4): 305–316. doi:10.1007/BF01448013
- ^ de Gottschall, Christian (). Logische Notationen und deren Verarbeitung auf elektronischen Rechenanlagen aus theoretischer, praktischer und historischer Sicht (Diploma thesis). Vienna, Austria. p. 88.
Die ältesten Texte in den 'Selected Works', in denen Łukasiewicz polnische Notation verwendet, datieren relativ spät, sind aber Präsentationen vorangehender Arbeiten, die 'in the course of the years 1920–1930' (S. 131) stattgefunden haben, also auch keine genauere Zeitangabe geben.
- ^ en Church, Alonzo (). Introduction to Mathematical Logic. Princeton, New Jersey, USA: Princeton University Press. 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. […]
- ^ en Łukasiewicz, Jan (). „Chapter IV. Aristotle's System in Symbolic Form (section on "Explanation of the Symbolism")”. Aristotle's Syllogistic from the Standpoint of Modern Formal Logic (ed. 1). p. 78.
- ^ de Łukasiewicz, Jan; Tarski, Alfred (). „Untersuchungen über den Aussagenkalkül”. Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie. 23 (Cl. III): 31–32.
- ^ en Martínez Nava, Xóchitl (), „Mhy bib I fail logic? Dyslexia in the teaching of logic”, În Blackburn, Patrick; van Ditmarsch, Hans; Manzano, Maria; 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, pp. 162–169, doi:10.1007/978-3-642-21350-2_19, ISBN 978-3-64221349-6,
[…] Polish or prefix notation has come to disuse given the difficulty that using it implies. […]
Vezi și
modificareLegături externe
modificare
Materiale media legate de notație prefixată la Wikimedia Commons
