Polsk indgang

Polsk notation ( rekord ), også kendt som præfiksnotation (rekord), er en form for skrivning af logiske , aritmetiske og algebraiske udtryk. Et karakteristisk træk ved en sådan notation er , at operatoren er placeret til venstre for operanderne . Hvis operatøren har en fast aritet , vil en sådan notation ikke have nogen parentes og kan fortolkes uden tvetydighed. Den polske logiker Jan Lukasiewicz opfandt denne notation omkring 1920 for at forenkle propositionel logik .

Alonzo Church nævnte denne notation i sin klassiske bog om matematisk logik som et bemærkelsesværdigt notationssystem, og modsatte endda Alfred Whiteheads og Bertrand Russells udlægninger af logiske notationer i Principia Mathematica . [en]

Selvom den polske notation ikke bruges i matematik, er den meget brugt i datalogi .

Aritmetik

I præfiksnotation vil tilføjelse af tallene 1 og 2 blive skrevet "+ 1 2" i stedet for at skrive "1 + 2". I mere komplekse udtryk går operatorerne forud for operanderne, men selve operanderne kan være ikke-trivielle udtryk, der indeholder deres egne operatorer. For eksempel et udtryk, der er skrevet med traditionel infix-notation

(5 − 6) * 7

i præfiks kan skrives som

*(− 5 6) 7

eller simpelthen

* − 5 6 7

Da enhver simpel aritmetisk operation er binær, kan dens præfiksrepræsentation ikke fortolkes på to måder, så der er ingen grund til at bruge parenteser. I det foregående eksempel var der brug for parenteser i den traditionelle infix-notation, og nu vil vi flytte dem

5 − (6 * 7)

eller bare slette

5 − 6 * 7

dette vil ændre betydningen og resultatet af evalueringen af hele udtrykket. Den tilsvarende præfiksnotation for et sådant udtryk ville se sådan ud:

− 5 * 6 7

Subtraktionsberegningen forsinkes, indtil begge operander (5 og resultatet af at gange 6 og 7) er blevet læst. Som med enhver anden notation evalueres de dybeste udtryk først, men i polsk notation bestemmes dybden af et udtryk af rækkefølgen, ikke parenteserne.

Præfiksnotation i simpel aritmetik er af stort set akademisk interesse. Ligesom postfix-notation er præfiksnotation blevet brugt til nogle kommercielle computere (HP-11C). At lære om præfiksnotation er ofte det første trin i compilerdesign.

Programmering

Præfiksnotation er meget udbredt i s-udtryk i programmeringssproget Lisp , hvor der er behov for parenteser, fordi aritmetiske operatorer har forskellige ariteter. Ambi - programmeringssproget bruger polsk notation til aritmetiske operationer og programstruktur. Postfix-notation bruges i mange stack-sprog , såsom PostScript , og er grundlaget for mange computermaskiner (beregnere), især Hewlett-Packard computere .

Det er også vigtigt at bemærke, at antallet af operander i et udtryk skal være én mere end antallet af operationer, ellers giver udtrykket ikke mening (i betragtning af at der kun bruges binære operationer i udtrykket ). Dette kan let overses, når man arbejder med lange, komplekse udtryk, som vil føre til fejl. Derfor er det nødvendigt at være opmærksom på antallet af operationer og operander, når du bruger præfiksnotation.

Operationsrækkefølge

Rækkefølgen af operationer bestemmes af strukturen af præfiksnotationen og kan let bestemmes. Det vigtigste at huske er, at når man vurderer et udtryk, skal rækkefølgen af operanderne bevares. Dette er ikke vigtigt for operationer, der er kommutative , men for ikke-kommutative operationer såsom subtraktion og division er dette faktum nøglen til at analysere udtrykket. For eksempel følgende udtryk:

/ 10 5 = 2 (præfiksnotation)

skal læses som "at dividere 10 med 5". Derfor vil resultatet af beregningen være 2, ikke ½, hvilket ville være resultatet af en forkert parsing af udtrykket.

Præfiksnotation er især populær i stack-sprog på grund af deres evne til nemt at skelne mellem rækkefølgen af operationer uden at bruge parenteser. For at bestemme rækkefølgen af evaluering af operatorer i præfiksnotation er det ikke engang nødvendigt at huske hele operationshierarkiet, som med infiksnotation . I stedet for at analysere udtrykket for at finde den operator, der skal evalueres først, bør man læse udtrykket fra venstre mod højre, se på operatoren og dens nærmeste to operander. Hvis der er en anden operatør blandt disse operander, forsinkes evalueringen af den første operatør, indtil den nye operatør er evalueret. Gentagelser af denne proces gentages, indtil operatoren evalueres, hvilket til sidst skal ske, hvis antallet af operander i udtrykket er én mere end antallet af operationer (i tilfælde af binære operationer). Når en operator er blevet evalueret, erstattes den og dens to operander med den resulterende værdi (operanden). Da operatoren og to operander erstattes af den beregnede operand, er der en operator og en mindre operand. Derefter forbliver N operatorer og N + 1 operander også i udtrykket, hvilket giver dig mulighed for iterativt at fortsætte processen.

I eksemplet nedenfor kan du se, at et tilsyneladende kompliceret udtryk i præfiksnotation faktisk ikke er så svært at forstå (til højre for lighedstegnet, det tilsvarende udtryk i infiksnotation):

- * / 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

Polsk notation i logik

Tabellen nedenfor viser kernenotationen foreslået af Jan Lukasiewicz til propositionel logik . Nogle bogstaver i den polske notation står for specifikke ord på polsk :

koncept	Betinget notation	polsk notation	polsk ord
Negation	$\neg$ φ	Nφ	negacja
Konjunktion	φ ψ $\kile$	Kφψ	koniunkcja
Disjunktion	φ ψ $\lor$	Aφψ	alternativt
implikation	φ ψ $\højre pil$	Cφψ
Ækvivalens	φ ψ $\venstrehøjrepil$	Eφψ	ekwiwalencja
Schaeffer slagtilfælde	$\phi \|\psi$	Dφψ	dysjunkcja
Mulighed	$\Diamant$ φ	Mφ	możliwość
Brug for	$\Boks$ φ	Lφ
Universal kvantifier	$\for alle$ φ	Πφ
Eksistens kvantifier	$\eksisterer$ φ	Σφ

Bemærk, at i Lukasiewicz' papir om logik med mange værdier, er kvantificerere ordnet efter propositionel værdi.

Se også

Omvendt polsk notation

Noter

↑ Kirke, Alonzo. Introduktion til matematisk logik . - Princeton, New Jersey: Princeton University Press , 1944. - s.38: "Værdig at bemærke er den parentesfrie notation af Jan Łukasiewicz. I denne bruges bogstaverne N, A, C, E, K i rollerne henholdsvis negation, disjunktion, implikation, ækvivalens, konjunktion. ..."

Litteratur

Lukasiewicz , Jan. Aristoteles' syllogistik fra den moderne formelle logiks standpunkt . — Oxford University Press , 1957.
Ł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). Oversat af H. Weber som "Philosophical Remarks on Many-Valued Systems of Propositional Logics", i Storrs McCall, Polish Logic 1920-1939 , Clarendon Press: Oxford (1967).