Notation polonaise - Polish notation

Notation suffixe ("Reverse Polish") Notation infixe Notation de préfixe ("Polonais")

v t e

Notation polonaise ( PN ), également connu sous le nom de notation normale polonaise ( NPN ), Lukasiewicz notation , la notation de Varsovie , la notation préfixe polonais ou simplement notation préfixe , est une notation mathématique dans laquelle les opérateurs précèdent leurs opérandes , contrairement à la plus commune notation infixe , dans laquelle les opérateurs sont placés entre les opérandes, ainsi que la notation polonaise inverse (RPN), dans laquelle les opérateurs suivent leurs opérandes. Il n'a pas besoin de parenthèses tant que chaque opérateur a un nombre fixe d'opérandes . La description « polonaise » fait référence à la nationalité du logicien Jan Łukasiewicz , qui a inventé la notation polonaise en 1924.

Le terme notation polonaise est parfois pris (comme l'opposé de la notation infixe ) pour inclure également la notation polonaise inversée.

Lorsque la notation polonaise est utilisée comme syntaxe pour des expressions mathématiques par des interpréteurs de langage de programmation , elle est facilement analysée en arbres de syntaxe abstraite et peut, en fait, définir une représentation un-à-un pour le même. Pour cette raison, Lisp ( voir ci-dessous ) et les langages de programmation associés définissent l'intégralité de leur syntaxe en notation préfixe (et d'autres utilisent la notation postfixe).

Histoire

Une citation d'un article de Jan Łukasiewicz , Remarks on Nicod's Axiom and on "Generalizing Deduction" , page 180, explique comment la notation a été inventée :

J'ai eu l'idée d'une notation sans parenthèses en 1924. J'ai utilisé cette notation pour la première fois dans mon article Łukasiewicz(1), p. 610, note de bas de page.

La référence citée par Łukasiewicz est apparemment un rapport lithographié en polonais . L'article de référence de Łukasiewicz Remarks on Nicod's Axiom and on "Generalizing Deduction" a été revu par Henry A. Pogorzelski dans le Journal of Symbolic Logic en 1965. Heinrich Behmann , éditeur en 1924 de l'article de Moses Schönfinkel , avait déjà l'idée d'éliminer parenthèses dans les formules logiques.

Alonzo Church mentionne cette notation dans son livre classique sur la logique mathématique comme digne de remarque dans les systèmes de notation même en contraste avec l' exposition et le travail de notation logique d' Alfred Whitehead et Bertrand Russell dans Principia Mathematica .

Dans le livre de 1951 de Łukasiewicz, Aristotle's Syllogistic from the Standpoint of Modern Formal Logic , il mentionne que le principe de sa notation était d'écrire les foncteurs avant les arguments pour éviter les parenthèses et qu'il avait utilisé sa notation dans ses papiers logiques depuis 1929. Il a ensuite poursuit en citant, à titre d'exemple, un article de 1930 qu'il a écrit avec Alfred Tarski sur le calcul des phrases .

Alors qu'elle n'est plus beaucoup utilisée en logique, la notation polonaise a depuis trouvé une place en informatique .

Explication

L'expression pour additionner les nombres 1 et 2 est écrite en notation polonaise comme + 1 2 (préfixe), plutôt que comme 1 + 2 (in-fixe). Dans les expressions plus complexes, les opérateurs précèdent toujours leurs opérandes, mais les opérandes peuvent eux-mêmes être des expressions comprenant à nouveau des opérateurs et leurs opérandes. Par exemple, l'expression qui serait écrite en notation infixe conventionnelle comme

(5 − 6) × 7

peut être écrit en notation polonaise comme

× (− 5 6) 7

En supposant une arité donnée de tous les opérateurs impliqués (ici le "-" désigne l'opération binaire de soustraction, pas la fonction unaire de changement de signe), toute représentation de préfixe bien formée de celle-ci est sans ambiguïté et les crochets dans l'expression du préfixe sont inutiles. En tant que telle, l'expression ci-dessus peut être encore simplifiée en

× − 5 6 7

Le traitement du produit est différé jusqu'à ce que ses deux opérandes soient disponibles (c'est-à-dire 5 moins 6 et 7). Comme pour toute notation, les expressions les plus intimes sont évaluées en premier, mais dans la notation polonaise, cette « intimité » peut être transmise par la séquence d'opérateurs et d'opérandes plutôt que par des crochets.

Dans la notation infixe conventionnelle, les parenthèses sont nécessaires pour remplacer les règles de priorité standard , car, en se référant à l'exemple ci-dessus, les déplacer

5 − (6 × 7)

ou les supprimer

5 − 6 × 7

change le sens et le résultat de l'expression. Cette version est écrite en notation polonaise comme

− 5 × 6 7 .

Lorsqu'il s'agit d'opérations non commutatives, comme la division ou la soustraction, il est nécessaire de coordonner l'arrangement séquentiel des opérandes avec la définition de la façon dont l'opérateur prend ses arguments, c'est-à-dire de gauche à droite. Par exemple, ÷ 10 5 , avec 10 à gauche à 5, a la signification de 10 ÷ 5 (lire comme "diviser 10 par 5"), ou - 7 6 , avec 7 à gauche à 6, a la signification de 7 - 6 ( lire comme "soustraire de 7 l'opérande 6").

Algorithme d'évaluation

La notation préfixe/postfixe est particulièrement populaire pour sa capacité innée à exprimer l'ordre prévu des opérations sans avoir besoin de parenthèses et d'autres règles de priorité, comme elles sont généralement utilisées avec la notation infixe . Au lieu de cela, la notation indique de manière unique quel opérateur évaluer en premier. Les opérateurs sont supposés avoir chacun une arité fixe , et tous les opérandes nécessaires sont supposés être explicitement donnés. Une expression de préfixe valide commence toujours par un opérateur et se termine par un opérande. L'évaluation peut procéder soit de gauche à droite, soit en sens inverse. En commençant par la gauche, la chaîne d'entrée, constituée de jetons désignant des opérateurs ou des opérandes, est poussée jeton par jeton sur une pile , jusqu'à ce que les entrées supérieures de la pile contiennent le nombre d'opérandes qui correspond à l'opérateur le plus haut (immédiatement en dessous). Ce groupe de jetons au sommet de la pile (le dernier opérateur empilé et le nombre d'opérandes correspondant) est remplacé par le résultat de l'exécution de l'opérateur sur ce/ces opérandes. Ensuite, le traitement de l'entrée se poursuit de cette manière. L'opérande le plus à droite dans une expression de préfixe valide vide donc la pile, à l'exception du résultat de l'évaluation de l'expression entière. En commençant par la droite, la poussée des jetons est effectuée de la même manière, seule l'évaluation est déclenchée par un opérateur, trouvant le nombre approprié d'opérandes qui correspond à son arité déjà au sommet de la pile. Maintenant, le jeton le plus à gauche d'une expression de préfixe valide doit être un opérateur, adapté au nombre d'opérandes dans la pile, ce qui donne à nouveau le résultat. Comme on peut le voir à partir de la description, un magasin déroulant sans capacité d'inspection de pile arbitraire suffit pour implémenter cette analyse .

La manipulation de la pile esquissée ci-dessus fonctionne - avec une entrée en miroir - également pour les expressions en notation polonaise inversée .

Notation polonaise pour la logique

Le tableau ci-dessous montre le noyau de la notation de Jan Łukasiewicz pour la logique phrastique . Certaines lettres de la table de notation polonaise représentent des mots particuliers en polonais , comme indiqué :

Concept	Notation conventionnelle	notation polonaise	terme polonais
Négation	${\displaystyle \neg \varphi }$	${\displaystyle \mathrm {N} \varphi }$	negacja
Conjonction	${\displaystyle \varphi \land \psi }$	${\displaystyle \mathrm {K} \varphi \psi }$	koniunkcja
Disjonction	${\displaystyle \varphi \lor \psi }$	${\displaystyle \mathrm {A} \varphi \psi }$	alternatywa
Matériel conditionnel	${\displaystyle \varphi \to \psi }$	${\displaystyle \mathrm {C} \varphi \psi }$	implicacja
Biconditionnel	${\displaystyle \varphi \leftrightarrow \psi }$	${\displaystyle \mathrm {E} \varphi \psi }$	ekwiwalencja
Falsum	${\displaystyle \bot }$	${\displaystyle \mathrm {O} }$	fałsz
AVC Sheffer	${\displaystyle \varphi \mid \psi }$	${\displaystyle \mathrm {D} \varphi \psi }$	dysjunkja
Possibilité	${\displaystyle \Diamant \varphi }$	${\displaystyle \mathrm {M} \varphi }$	możliwość
Nécessité	${\displaystyle \Box \varphi }$	${\displaystyle \mathrm {L} \varphi }$	konieczność
Quantificateur universel	${\displaystyle \forall p\,\varphi }$	${\displaystyle \Pi p\,\varphi }$	kwantyfikator ogólny
Quantificateur existentiel	${\displaystyle \exists p\,\varphi }$	${\displaystyle \Sigma p\,\varphi }$	kwantyfikator szczegółowy

Notez que les quantificateurs variaient sur des valeurs propositionnelles dans les travaux de ukasiewicz sur les logiques à plusieurs valeurs.

Bocheński a introduit un système de notation polonaise qui nomme les 16 connecteurs binaires de la logique propositionnelle classique . Pour la logique propositionnelle classique, c'est une extension compatible de la notation de Łukasiewicz. Mais les notations sont incompatibles dans le sens où Bocheński utilise L et M (pour la non-implication et la non-implication inverse) en logique propositionnelle et Łukasiewicz utilise L et M en logique modale.

Implémentations

La notation par préfixe a été largement appliquée dans les expressions S Lisp , où les crochets sont requis car les opérateurs du langage sont eux-mêmes des données ( fonctions de première classe ). Les fonctions Lisp peuvent également être variadiques . Le langage de programmation Tcl , tout comme Lisp, utilise également la notation polonaise via la bibliothèque mathop. Le langage de programmation Ambi utilise la notation polonaise pour les opérations arithmétiques et la construction de programmes. La syntaxe du filtre LDAP utilise la notation de préfixe polonaise.

La notation Postfix est utilisée dans de nombreux langages de programmation orientés pile comme PostScript et Forth . La syntaxe CoffeeScript permet également d'appeler des fonctions en utilisant la notation de préfixe, tout en prenant en charge la syntaxe de suffixe unaire commune dans d'autres langages.

Le nombre de valeurs de retour d'une expression est égal à la différence entre le nombre d'opérandes dans une expression et l'arité totale des opérateurs moins le nombre total de valeurs de retour des opérateurs.

La notation polonaise, généralement sous forme de suffixe, est la notation choisie par certaines calculatrices , notamment de Hewlett-Packard . À un niveau inférieur, les opérateurs postfix sont utilisés par certaines machines à pile telles que les grands systèmes de Burroughs .

Voir également

• Notation polonaise inversée
• Application de fonction
• Calcul lambda
• Curry
• Lisp (langage de programmation)
  • S-expression
• École polonaise de mathématiques
• notation hongroise
• Verbe-sujet-objet (VSO)
• Verbe-objet-sujet (VOS)

Les références

Lectures complémentaires

• ukasiewicz, janvier (1957). La syllogistique d'Aristote du point de vue de la logique formelle moderne . Presse de l'Université d'Oxford .
• ukasiewicz, janvier (1930). "Philosophische Bemerkungen zu mehrwertigen Systemen des Aussagenkalküls" [Remarques philosophiques sur les systèmes à plusieurs valeurs de logique propositionnelle]. Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie (en allemand). 23 : 51-77.Traduit par H. Weber dans Storrs McCall, Polish Logic 1920-1939 , Clarendon Press : Oxford (1967).

Liens externes

• Médias liés à la notation polonaise (mathématiques) sur Wikimedia Commons