Łączność -Associative property

W matematyce własność asocjacyjna jest własnością niektórych operacji binarnych , co oznacza, że ​​zmiana kolejności nawiasów w wyrażeniu nie zmieni wyniku. W logice zdań asocjacyjność jest obowiązującą regułą zastępowania wyrażeń w dowodach logicznych .

W wyrażeniu zawierającym co najmniej dwa wystąpienia w wierszu tego samego operatora asocjacyjnego kolejność wykonywania operacji nie ma znaczenia, o ile sekwencja argumentów nie ulega zmianie. To znaczy (po przepisaniu wyrażenia z nawiasami i w razie potrzeby w notacji infiksowej), zmiana kolejności nawiasów w takim wyrażeniu nie zmieni jego wartości. Rozważ następujące równania:

${\displaystyle (2+3)+4=2+(3+4)=9\,}$

${\displaystyle 2\razy (3\razy 4)=(2\razy 3)\razy 4=24.}$

Mimo że w każdym wierszu zmieniono nawiasy, wartości wyrażeń nie uległy zmianie. Ponieważ dotyczy to wykonywania dodawania i mnożenia na dowolnych liczbach rzeczywistych , można powiedzieć, że „dodawanie i mnożenie liczb rzeczywistych są operacjami asocjacyjnymi”.

Asocjatywność to nie to samo co przemienność , która określa, czy kolejność dwóch argumentów wpływa na wynik. Na przykład kolejność nie ma znaczenia w mnożeniu liczb rzeczywistych, to znaczy a × b = b × a , więc mówimy, że mnożenie liczb rzeczywistych jest operacją przemienną. Jednak operacje takie jak składanie funkcji i mnożenie macierzy są asocjacyjne, ale (na ogół) nie są przemienne.

Operacje asocjacyjne są obfite w matematykę; w rzeczywistości wiele struktur algebraicznych (takich jak półgrupy i kategorie ) wyraźnie wymaga, aby ich operacje binarne były asocjacyjne.

Jednak wiele ważnych i interesujących operacji nie jest asocjacyjnych; niektóre przykłady obejmują odejmowanie , potęgowanie i iloczyn wektorowy . W przeciwieństwie do teoretycznych własności liczb rzeczywistych, dodawanie liczb zmiennoprzecinkowych w informatyce nie jest asocjacyjne, a wybór sposobu powiązania wyrażenia może mieć istotny wpływ na błąd zaokrąglania.

Definicja

Operacja binarna ∗ na zbiorze S jest asocjacyjna, gdy ten diagram komutuje . To znaczy, gdy dwie ścieżki od S × S × S do S składają się na tę samą funkcję od S × S × S do S .

Formalnie operacja binarna ∗ na zbiorze S nazywana jest asocjatywną , jeśli spełnia prawo asocjacji :

( x ∗ y ) ∗ z = x ∗ ( y ∗ z ) dla wszystkich x , y , z w S .

W tym przypadku ∗ służy do zastąpienia symbolu operacji, którym może być dowolny symbol, a nawet brak symbolu ( zestawienie ) jak w przypadku mnożenia .

( xy ) z = x ( yz ) = xyz dla wszystkich x , y , z w S .

Prawo asocjacji można również wyrazić w notacji funkcyjnej w następujący sposób: f ( f ( x , y ), z ) = f ( x , f ( y , z )) .

Uogólnione prawo stowarzyszeniowe

W przypadku braku własności asocjacyjnej, pięć czynników a, b, c, d, e daje w wyniku siatkę Tamari rzędu czwartego, być może różnych iloczynów.

Jeśli operacja binarna jest asocjacyjna, wielokrotne zastosowanie operacji daje ten sam wynik, niezależnie od tego, jak prawidłowe pary nawiasów są wstawiane do wyrażenia. Nazywa się to uogólnionym prawem asocjacyjnym . Na przykład iloczyn czterech elementów można zapisać bez zmiany kolejności czynników na pięć możliwych sposobów:

${\ Displaystyle ((ab) c) d}$

${\displaystyle (ab)(cd)}$

${\displaystyle (a(bc))d}$

${\displaystyle a((bc)d)}$

${\displaystyle a(b(cd))}$

Jeśli operacja iloczynowa jest asocjacyjna, to uogólnione prawo asocjacyjne mówi, że wszystkie te formuły dadzą ten sam wynik. Tak więc, o ile formuła z pominiętymi nawiasami nie ma już innego znaczenia (patrz poniżej), nawiasy można uznać za niepotrzebne, a „produkt” można zapisać jednoznacznie jako

${\displaystyle abcd.}$

Wraz ze wzrostem liczby elementów liczba możliwych sposobów wstawiania nawiasów szybko rośnie, ale pozostają one niepotrzebne do uściślania.

Przykładem, w którym to nie działa, jest logiczny dwuwarunkowy . Jest asocjacyjne, więc A (BC ) jest równoważne ( AB) C, ale A B C najczęściej oznacza ( AB i BC ), co nie jest równoważne. ${\displaystyle \leftrightarrow}$${\displaystyle \leftrightarrow}$${\displaystyle \leftrightarrow}$${\displaystyle \leftrightarrow}$${\displaystyle \leftrightarrow}$${\displaystyle \leftrightarrow}$${\displaystyle \leftrightarrow}$${\displaystyle \leftrightarrow}$${\displaystyle \leftrightarrow}$

Przykłady

W operacjach asocjacyjnych jest .${\displaystyle (x\circ y)\circ z=x\circ (y\circ z)}$

Dodawanie liczb rzeczywistych jest asocjacyjne.

Oto kilka przykładów operacji asocjacyjnych.

• Konkatenację trzech ciągów ,"hello" , " "można "world"obliczyć, łącząc dwa pierwsze ciągi (dając "hello ") i dołączając trzeci ciąg ( "world") lub łącząc drugi i trzeci ciąg (dając " world") i łącząc pierwszy ciąg ( "hello") z wynikiem. Te dwie metody dają ten sam wynik; łączenie ciągów jest skojarzone (ale nie przemienne).
• W arytmetyce dodawanie i mnożenie liczb rzeczywistych są asocjacyjne; tj,

${\ Displaystyle \ lewo. {\ zacząć {macierz} (x + y) + z = x + (y + z) = x + y + z \ quad \ \ (x \ y) z = x (y \ z )=x\,y\,z\qquad \qquad \qquad \quad \ \ \,\end{macierz}}\right\}{\mbox{dla wszystkich }}x,y,z\in \mathbb {R } .}$

Ze względu na asocjatywność nawiasy grupujące można pominąć bez dwuznaczności.

• Trywialna operacja x ∗ y = x (to znaczy, że wynikiem jest pierwszy argument, bez względu na to, jaki jest drugi argument) jest asocjacyjna, ale nie przemienna. Podobnie trywialna operacja x ∘ y = y (to znaczy, że wynikiem jest drugi argument, bez względu na to, jaki jest pierwszy argument) jest asocjacyjna, ale nie przemienna.
• Dodawanie i mnożenie liczb zespolonych i kwaternionów są asocjacyjne. Dodawanie oktonów jest również asocjacyjne, ale mnożenie oktonów nie jest asocjacyjne.
• Największy wspólny dzielnik i najmniej wspólne funkcje wielokrotne działają asocjacyjnie.

${\ Displaystyle \ lewo. {\ zacznij {macierz} \ nazwa operatora {gcd} (\ nazwa operatora {gcd} (x, y), z) = \ nazwa operatora {gcd} (x, \ nazwa operatora {gcd} (y, z) )=\nazwa operatora {gcd} (x,y,z)\ \quad \\\nazwa operatora {lcm} (\nazwa operatora {lcm} (x,y),z)=\nazwa operatora {lcm} (x,\nazwa operatora { lcm} (y,z))=\operatorname {lcm} (x,y,z)\quad \end{matrix}}\right\}{\mbox{ dla wszystkich }}x,y,z\in \mathbb {Z}.}$

• Biorąc przecięcie lub sumę zbiorów : _

${\ Displaystyle \ lewo. {\ zacząć {macierz} (A \ czapka B) \ czapka C = A \ czapka (B \ czapka C) = A \ czapka B \ czapka C \ quad \ \ (A \ kubek B) \ cup C=A\cup (B\cup C)=A\cup B\cup C\quad \end{matrix}}\right\}{\mbox{dla wszystkich zbiorów }}A,B,C.}$

• Jeżeli M jest jakimś zbiorem, a S oznacza zbiór wszystkich funkcji od M do M , to operacja złożenia funkcji na S jest asocjacyjna:

${\ Displaystyle (f \ circ g) \ circ h = f \ circ (g \ circ h) = f \ circ g \ circ h \ qquad {\ mbox {dla wszystkich}} f, g, h \ w S.}$

• Nieco ogólniej, biorąc pod uwagę cztery zbiory M , N , P i Q , z h : M do N , g : N do P i f : P do Q , to

${\displaystyle (f\circ g)\circ h=f\circ (g\circ h)=f\circ g\circ h}$

jak wcześniej. Krótko mówiąc, kompozycja map jest zawsze skojarzona.

• Rozważ zestaw z trzema elementami, A, B i C. Poniższa operacja:

×	A	b	C
A	A	A	A
b	A	b	C
C	A	A	A

jest skojarzeniowa. Na przykład A(BC)=(AB)C = A. Ta operacja nie jest przemienna.

• Ponieważ macierze reprezentują funkcje liniowe , a mnożenie macierzy reprezentuje złożenie funkcji, można od razu stwierdzić, że mnożenie macierzy jest asocjacyjne.

Logika zdań

Zasada wymiany

W standardowej logice prawdziwościowo-funkcjonalnej zdań, asocjacja lub asocjatywność to dwie ważne reguły zastępowania . Reguły pozwalają przesuwać nawiasy w wyrażeniach logicznych w dowodach logicznych . Zasady (przy użyciu notacji spójników logicznych ) to:

${\ Displaystyle (P\lor (Q\lorR))\Leftrightarrow ((P\lor Q)\lorR)}$

oraz

${\ Displaystyle (P \ ziemia (Q \ ziemia R)) \ Leftrightarrow ((P \ ziemia Q) \ ziemia R)}$

gdzie " " jest symbolem metalicznym reprezentującym "może być zastąpiony w dowodzie na". ${\ Displaystyle \ Leftrightarrow}$

Prawda funkcjonalne spójniki

Asocjatywność jest właściwością niektórych spójników logicznych logiki prawdziwościowo- zdaniowej . Poniższe logiczne równoważności pokazują, że asocjatywność jest właściwością poszczególnych spójników. Poniżej przedstawiono tautologie prawdziwościowo-funkcjonalne .

Asocjatywność alternatywy :

${\ Displaystyle ((p \ lor Q) \ lor R) \ leftrightarrow (p \ lor (Q \ lor R))}$

${\ Displaystyle (p \ lor (Q \ lor R)) \ leftrightarrow ((p \ lor Q) \ lor R)}$

Łączność koniunkcji :

${\ Displaystyle ((P \ ziemia Q) \ ziemia R) \ leftrightarrow (P \ ziemia (Q \ ziemia R))}$

${\ Displaystyle (P \ ziemia (Q \ ziemia R)) \ leftrightarrow ((p \ ziemia Q) \ ziemia R)}$

Asocjatywność równoważności :

${\ Displaystyle ((P\leftrightarrow Q)\leftrightarrow R)\leftrightarrow (P\leftrightarrow (Q\leftrightarrow R))}$

${\displaystyle (p\leftrightarrow (Q\leftrightarrow R))\leftrightarrow ((p\leftrightarrow Q)\leftrightarrow R)}$

Wspólne zaprzeczanie jest przykładem spójnika funkcjonalnego prawdy, który nie jest asocjacyjny.

Operacja bez asocjacji

Operacja binarna na zbiorze S , która nie spełnia prawa asocjacyjnego, nazywana jest nieskojarzeniową . Symbolicznie, ${\styl wyświetlania *}$

${\ Displaystyle (x * y) * z \ neq x * (y * z) \ qquad {\ mbox {dla niektórych}} x, y, z \ w S.}$

Dla takiej operacji kolejność oceny ma znaczenie. Na przykład:

• Odejmowanie

${\displaystyle (5-3)-2\,\neq \,5-(3-2)}$

• Podział

${\displaystyle (4/2)/2\,\neq \,4/(2/2)}$

• Potęgowanie

${\ Displaystyle 2 ^ {(1 ^ {2})} \ \ neq \ (2 ^ {1}) ^ {2}}$

• Wektor krzyżowy produkt

${\ Displaystyle {\ zacząć {wyrównany} \ mathbf {i} \ razy (\ mathbf {i} \ razy \ mathbf {j}) & = \ mathbf {i} \ razy \ mathbf {k} =- \ mathbf {j } \\(\mathbf {i} \times \mathbf {i} )\times \mathbf {j} &=\mathbf {0} \times \mathbf {j} =\mathbf {0} \end{aligned}} }$

Również chociaż dodawanie jest asocjacyjne dla sum skończonych, nie jest asocjacyjne wewnątrz sum nieskończonych ( szeregów ). Na przykład,

${\ Displaystyle (1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+\kropki =0}$

mając na uwadze, że

${\ Displaystyle 1 + (-1 + 1) + (-1 + 1) + (-1 + 1) + (-1 + 1) + (-1 + 1) + (-1 + 1) + \ kropki = 1.}$

Niektóre operacje nieskojarzone mają fundamentalne znaczenie w matematyce. Pojawiają się one często jako mnożenie w strukturach zwanych algebrami nieasocjacyjnymi , które mają również dodawanie i mnożenie przez skalar . Przykładami są oktoniony i algebry Liego . W algebrach Liego mnożenie spełnia tożsamość Jacobiego zamiast prawa skojarzeń; pozwala to wyabstrahować algebraiczną naturę nieskończenie małych przekształceń .

Inne przykłady to quasigroup , quasifield , pierścień nieasocjacyjny i przemienne magmy nieasocjacyjne .

Niełączność obliczeń zmiennoprzecinkowych

W matematyce dodawanie i mnożenie liczb rzeczywistych ma charakter asocjacyjny. Natomiast w informatyce dodawanie i mnożenie liczb zmiennoprzecinkowych nie jest asocjacyjne, ponieważ błędy zaokrąglania są wprowadzane, gdy łączone są ze sobą wartości o różnej wielkości.

Aby to zilustrować, rozważmy reprezentację zmiennoprzecinkową z 4-bitową mantysą :
(1.000 ₂ ×2 ⁰ + 1.000 ₂ ×2 ⁰ ) + 1.000 ₂ ×2 ⁴ = 1.000 ₂ ×2 ¹ + 1.000 ₂ ×2 ⁴ = 1,00 1 ₂ ×2 ⁴
1,000 ₂ ×2 ⁰ + (1.000 ₂ ×2 ⁰ + 1,000 ₂ ×2 ⁴ ) = 1,000 ₂ ×2 ⁰ + 1,000 ₂ ×2 ⁴ = 1,00 0 ₂ ×2 ⁴

Mimo że większość komputerów oblicza z 24 lub 53 bitami mantysy, jest to ważne źródło błędu zaokrąglania, a podejścia, takie jak algorytm sumowania Kahana, pozwalają zminimalizować błędy. Może to być szczególnie problematyczne w przypadku obliczeń równoległych.

Notacja dla operacji nieskojarzeniowych

Ogólnie rzecz biorąc, nawiasy muszą być używane do wskazania kolejności oceny , jeśli operacja nieskojarzona występuje w wyrażeniu więcej niż raz (chyba że notacja określa kolejność w inny sposób, na przykład ). Jednak matematycy zgadzają się na określoną kolejność oceny dla kilku typowych operacji nieskojarzeniowych. Jest to po prostu konwencja notacji, aby uniknąć nawiasów. ${\displaystyle {\dfrac {2}{3/4}}}$

Operacja lewostronnie asocjacyjna jest operacją nieskojarzeniową, która jest konwencjonalnie oceniana od lewej do prawej, tj.

${\ Displaystyle \ lewo. {\ zacząć {macierz} x * y * z = (x * y) * z \ qquad \ qquad \ quad \ \ \ w * x * y * z = ((w * x) * y)*z\quad \\{\mbox{etc.}}\qquad \qquad \qquad \qquad \qquad \qquad \ \ \,\end{matrix}}\right\}{\mbox{dla wszystkich }} w,x,y,z\w S}$

podczas gdy prawostronna operacja skojarzona jest konwencjonalnie oceniana od prawej do lewej:

${\ Displaystyle \ lewo. {\ zacząć {macierz} x * y * z = x * (y * z) \ qquad \ qquad \ quad \ \ \ w * x * y * z = w * (x * (y *z))\quad \\{\mbox{etc.}}\qquad \qquad \qquad \qquad \qquad \qquad \ \ \,\end{matrix}}\right\}{\mbox{dla wszystkich }} w,x,y,z\w S}$

Występują zarówno operacje lewostronne, jak i prawostronne. Operacje lewostronnie asocjacyjne obejmują:

• Odejmowanie i dzielenie liczb rzeczywistych:

${\displaystyle xyz=(xy)-z}$

${\ Displaystyle x/y/z = (x/y)/z}$

• Aplikacja funkcji:

${\displaystyle (f\,x\,y)=((f\,x)\,y)}$

Ta notacja może być motywowana izomorfizmem curryingu .

Operacje prawostronnie asocjacyjne obejmują:

• Potęgowanie liczb rzeczywistych w notacji w indeksie górnym:

${\ Displaystyle x ^ {y ^ {z}} = x ^ {(y ^ {z})}}$

Potęgowanie jest powszechnie używane z nawiasami lub prawostronnie skojarzone, ponieważ powtarzana operacja potęgowania lewostronnie skojarzona jest mało przydatna. Powtarzające się uprawnienia w większości byłyby przepisywane przez mnożenie:

${\ Displaystyle (x ^ {y}) ^ {z} = x ^ {(yz)}}$

Prawidłowo sformatowany indeks górny z natury zachowuje się jak zestaw nawiasów; np. w wyrażeniu dodawanie jest wykonywane przed potęgowaniem, mimo że nie ma wokół niego wyraźnych nawiasów . W ten sposób dane wyrażenie takie jak , pełny wykładnik podstawy jest obliczany jako pierwszy. Jednak w niektórych kontekstach, zwłaszcza w pismach odręcznych, różnica między , a może być trudna do zauważenia. W takim przypadku zwykle zakłada się prawostronną asocjatywność.${\ Displaystyle 2 ^ {x + 3}}$${\ Displaystyle 2 ^ {(x + 3)}}$${\ Displaystyle x ^ {y ^ {z}}}$${\ Displaystyle y ^ {z}}$${\displaystyle x}$${\ Displaystyle {x ^ {y}} ^ {z} = (x ^ {y}) ^ {z}}$${\ Displaystyle x ^ {yz} = x ^ {(yz)}}$${\ Displaystyle x ^ {y ^ {z}} = x ^ {(y ^ {z})}}$

• Definicja funkcji

${\ Displaystyle \ mathbb {Z} \ rightarrow \ mathbb {Z} \ rightarrow \ mathbb {Z} = \ mathbb {Z} \ rightarrow (\ mathbb {Z} \ rightarrow \ mathbb {Z})}$

${\ Displaystyle x \ mapsto y \ mapsto xy = x \ mapsto (y \ mapsto xy)}$

Stosowanie notacji prawostronnie asocjacyjnej dla tych operacji może być motywowane korespondencją Curry-Howarda i izomorfizmem curryingu .

Operacje nieskojarzone, dla których nie zdefiniowano konwencjonalnej kolejności oceny, obejmują następujące elementy.

• Potęgowanie liczb rzeczywistych w notacji infiksowej:

${\ Displaystyle (x ^ {\ klin} y) ^ {\ klin} z \ neq x ^ {\ klin} (y ^ {\ klin} z)}$

• Operatory strzałek w górę Knutha :

${\ Displaystyle a \ uparrow \ uparrow (b \ uparrow \ uparrow c) \ neq (a \ uparrow \ uparrow b) \ uparrow \ uparrow c}$

${\ Displaystyle a \ uparrow \ uparrow \ uparrow (b \ uparrow \ uparrow \ uparrow c) \ neq (a \ uparrow \ uparrow \ uparrow b) \ uparrow \ uparrow \ uparrow c}$

• Biorąc iloczyn krzyżowy trzech wektorów:

${\ Displaystyle {\ vec {a}} \ razy ({\ vec {b}} \ razy {\ vec {c}}) \ neq ({\ vec {a}} \ razy {\ vec {b}}) \times {\vec {c}}\qquad {\mbox{ dla niektórych }}{\vec {a}},{\vec {b}},{\vec {c}}\in \mathbb {R} ^ {3}}$

• Biorąc średnią par liczb rzeczywistych:

${\ Displaystyle {(x + y) / 2 + z \ ponad 2} \ neq {x + (y + z) / 2 \ ponad 2} \ qquad {\ mbox {dla wszystkich}} x, y, z \ w \ mathbb {R} {\mbox{ z }}x\neq z.}$

• Względne uzupełnienie zbiorów to nie to samo co . (Porównaj brak implikacji materialnej w logice.)${\displaystyle (A\backslash B)\backslash C}$${\ Displaystyle A \ ukośnik odwrotny (B \ ukośnik odwrotny C)}$

Historia

Wydaje się, że William Rowan Hamilton ukuł termin „własność skojarzeniowa” około 1844 roku, kiedy rozważał nieskojarzoną algebrę Oktonionów , o której dowiedział się od Johna T. Gravesa .

Zobacz też

• Test asocjacji światła
• Szeregi teleskopowe , wykorzystanie asocjatywności dodawania do anulowania wyrazów w szeregu nieskończonym
• Półgrupa jest zbiorem z asocjacyjną operacją binarną.
• Przemienność i dystrybucyjność to dwie inne często omawiane właściwości operacji binarnych.
• Asocjatywność mocy , alternatywność , elastyczność i asocjatywność N-argumentowa są słabymi formami asocjatywności.
• Tożsamości Moufang zapewniają również słabą formę asocjacji.

Bibliografia