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
Un 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ă
Expresia 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
Notația prefixată a fost aplicată pe scară largă în LISP, Tcl/TK și LDAP.
Note
Vezi și
Legături externe
Materiale media legate de notație prefixată la Wikimedia Commons
