Worldlex Wiki Dans une expression contenant deux occurrences ou plus du même opérateur associatif, l'ordre des opérations est indifférent tant que la séquence des opérandes reste inchangée. Autrement dit (après avoir réécrit l'expression avec des parenthèses et en notation infixe si nécessaire), réorganiser les parenthèses dans une telle expression ne modifiera pas sa valeur. Prenons les équations suivantes :
Bien que les parenthèses aient été réorganisées sur chaque ligne, les valeurs des expressions sont restées inchangées. Cela est toujours vrai lors des additions et multiplications de nombres réels , car ces opérations sont associatives.
L'associativité est différente de la commutativité , qui détermine si l'ordre des opérandes influe sur le résultat. Par exemple, l'ordre n'a pas d'importance dans la multiplication des nombres réels ( la composition de fonctions et la multiplication matricielle sont associatives, mais généralement pas commutatives.
Les opérations associatives sont omniprésentes en mathématiques ; de fait, de nombreuses structures algébriques (telles que les semi-groupes et les catégories ) imposent explicitement l’associativité de leurs opérations binaires. Cependant, de nombreuses opérations importantes et intéressantes ne sont pas associatives ; on peut citer, par exemple, la soustraction , l’exponentiation et le produit vectoriel . Contrairement aux propriétés théoriques des nombres réels, l’addition de nombres à virgule flottante en informatique n’est pas associative, et le choix de l’association d’une expression peut avoir un impact significatif sur les erreurs d’arrondi.
Loi associative généralisée
Si une opération binaire est associative, l'application répétée de l'opération produit le même résultat quelle que soit la manière dont les paires de parenthèses valides sont insérées dans l'expression. C'est ce qu'on appelle la loi d'associativité généralisée .
Le nombre de combinaisons possibles est simplement le nombre de Catalan , , pour n opérations sur n + 1 valeurs. Par exemple, un produit de 3 opérations sur 4 éléments peut s'écrire (en ignorant les permutations des arguments) de plusieurs manières possibles :
Si l'opération de produit est associative, la loi d'associativité généralisée stipule que toutes ces expressions donneront le même résultat. Par conséquent, à moins que l'expression sans parenthèses n'ait déjà une signification différente (voir ci-dessous), les parenthèses peuvent être considérées comme superflues et « le » produit peut s'écrire sans ambiguïté comme suit :
À mesure que le nombre d'éléments augmente, le nombre de façons possibles d'insérer des parenthèses croît rapidement, mais elles restent inutiles pour lever l'ambiguïté.
Un exemple où cela ne fonctionne pas est la biconditionnelle logique Voici quelques exemples d'opérations associatives."hello"peut être "world"calculée soit en concaténant les deux premières (on obtient "hello ") et en ajoutant la troisième ( "world"), soit en joignant la deuxième et la troisième (on obtient " world") et en concaténant la première ( "hello") avec le résultat. Les deux méthodes produisent le même résultat ; la concaténation de chaînes est associative (mais non commutative).
L' opération est associative. Ainsi, par exemple, A ( BC ) = ( AB ) C = A. Cette opération n'est pas commutative.× UN B C UN UN UN UN B UN B C C UN UN UN
Logique propositionnelle
et
où " " est un symbole métaphysique représentant " peut être remplacé dans une preuve par".
connecteurs fonctionnels de vérité
L'associativité est une propriété de certains connecteurs logiques de la logique propositionnelle vérifonctionnelle . Les équivalences logiques suivantes démontrent que l'associativité est une propriété de connecteurs particuliers. Les propositions suivantes (et leurs réciproques, puisque des tautologies vérifonctionnelles . La négation conjointe est un exemple de connecteur fonctionnel de vérité qui n'est pas associatif.
Opération non associative
Une opération binaire sur un ensemble S qui ne satisfait pas la loi d'associativité est dite non associative . Symboliquement,
Pour une telle opération, l'ordre d'évaluation a son importance. Par exemple :
De plus, bien que l'addition soit associative pour les sommes finies, elle ne l'est pas à l'intérieur des sommes infinies ( séries ). Par exemple, alors que
Certaines opérations non associatives sont fondamentales en mathématiques. Elles apparaissent fréquemment sous la forme de la multiplication dans des structures appelées algèbres non associatives , qui possèdent également une addition et une multiplication par un scalaire . Les octonions et les algèbres de Lie en sont des exemples . Dans les algèbres de Lie, la multiplication satisfait l'identité de Jacobi au lieu de la loi d'associativité ; ceci permet d'abstraire la nature algébrique des transformations infinitésimales .
D'autres exemples sont le quasigroupe , le quasichamp , l'anneau non associatif et les magmas non associatifs commutatifs .
Non-associativité du calcul en virgule flottante
En mathématiques, l'addition et la multiplication des nombres réels sont associatives. En revanche, en informatique, l'addition et la multiplication des nombres à virgule flottante ne le sont pas , car des erreurs d'arrondi différentes peuvent survenir lorsque des valeurs de tailles différentes sont combinées dans un ordre différent.
Pour illustrer cela, prenons l'exemple d'une représentation en virgule flottante avec une mantisse de 4 bits :
algorithme de sommation de Kahan permettent de minimiser ces erreurs. Ce problème peut s'avérer particulièrement préoccupant en calcul parallèle.Notation pour les opérations non associatives
Histoire
William Rowan Hamilton semble avoir inventé le terme « propriété associative » vers 1844, à une époque où il contemplait l'algèbre non associative des octonions qu'il avait apprise de John T. Graves .
Relation avec la commutativité dans certains cas particuliers
En général, les opérations associatives ne sont pas commutatives. Cependant, sous certaines conditions particulières, l'associativité peut impliquer la commutativité. Les opérateurs associatifs définis sur un intervalle de la droite réelle sont commutatifs s'ils sont continus et injectifs par rapport à leurs deux arguments. Il en résulte que tout opérateur associatif continu à deux entrées réelles, strictement croissant par rapport à chacune de ses entrées, est commutatif.