Asociativní vlastnost -Associative property

V matematice je asociativní vlastnost vlastností některých binárních operací , což znamená, že přeuspořádání závorek ve výrazu nezmění výsledek. Ve výrokové logice je asociativita platným pravidlem nahrazení výrazů v logických důkazech .

Ve výrazu obsahujícím dva nebo více výskytů stejného asociativního operátoru v řadě nezáleží na pořadí, ve kterém jsou operace prováděny, pokud se nezmění sekvence operandů . To znamená (po přepsání výrazu se závorkami a v případě potřeby v infixové notaci) změna uspořádání závorek v takovém výrazu nezmění jeho hodnotu. Zvažte následující rovnice:

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

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

I když byly závorky na každém řádku přeskupeny, hodnoty výrazů se nezměnily. Protože toto platí při provádění sčítání a násobení na libovolných reálných číslech , lze říci, že „sčítání a násobení reálných čísel jsou asociativní operace“.

Asociativita není totéž jako komutativnost , která řeší, zda pořadí dvou operandů ovlivňuje výsledek. Například při násobení reálných čísel nezáleží na pořadí, tedy a × b = b × a , takže říkáme, že násobení reálných čísel je komutativní operace. Operace jako skládání funkcí a násobení matic jsou však asociativní, ale (obecně) ne komutativní.

Asociativní operace jsou v matematice hojné; ve skutečnosti mnoho algebraických struktur (jako jsou pologrupy a kategorie ) výslovně vyžaduje, aby jejich binární operace byly asociativní.

Mnoho důležitých a zajímavých operací je však neasociativních; některé příklady zahrnují odčítání , umocňování a vektorový křížový součin . Na rozdíl od teoretických vlastností reálných čísel není sčítání čísel s pohyblivou řádovou čárkou v informatice asociativní a volba způsobu asociace výrazu může mít významný vliv na zaokrouhlovací chybu.

Definice

Binární operace ∗ na množině S je asociativní, když tento diagram komutuje . To znamená, že když se dvě cesty od S × S × S k S složí do stejné funkce od S × S × S k S .

Formálně se binární operace ∗ na množině S nazývá asociativní , pokud splňuje asociativní zákon :

( x ∗ y ) ∗ z = x ∗ ( y ∗ z ) pro všechna x , y , z v S .

Zde se ∗ používá k nahrazení symbolu operace, což může být jakýkoli symbol, a dokonce i absence symbolu ( juxtapozice ) jako u násobení .

( xy ) z = x ( yz ) = xyz pro všechna x , y , z v S .

Asociativní zákon lze také vyjádřit ve funkčním zápisu takto: f ( f ( x , y ), z ) = f ( x , f ( y , z )) .

Zobecněné asociační právo

Při absenci asociativní vlastnosti má pět faktorů a, b, c, d, e za následek Tamariho mřížku řádu čtyři, případně různé produkty.

Pokud je binární operace asociativní, opakovaná aplikace operace poskytuje stejný výsledek bez ohledu na to, jak jsou do výrazu vloženy platné dvojice závorek. Toto se nazývá zobecněné asociativní právo . Například součin čtyř prvků může být zapsán, aniž by se měnilo pořadí faktorů, pěti možnými způsoby:

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

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

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

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

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

Pokud je operace součinu asociativní, zobecněný asociativní zákon říká, že všechny tyto vzorce dají stejný výsledek. Pokud tedy vzorec s vynechanými závorkami již nemá jiný význam (viz níže), lze závorky považovat za zbytečné a „ten“ součin lze zapsat jednoznačně jako

${\displaystyle abcd.}$

Se zvyšujícím se počtem prvků rychle roste počet možných způsobů vkládání závorek , které však zůstávají zbytečné pro jednoznačnost.

Příkladem, kde to nefunguje, je logická bipodmínka . Je asociativní, takže A (B C) je ekvivalentní (A B) C, ale A B C nejčastěji znamená (A B a B C), což není ekvivalentní. ${\displaystyle \leftrightarrow }$${\displaystyle \leftrightarrow }$${\displaystyle \leftrightarrow }$${\displaystyle \leftrightarrow }$${\displaystyle \leftrightarrow }$${\displaystyle \leftrightarrow }$${\displaystyle \leftrightarrow }$${\displaystyle \leftrightarrow }$${\displaystyle \leftrightarrow }$

Příklady

V asociativních operacích je .${\displaystyle (x\circ y)\circ z=x\circ (y\circ z)}$

Sčítání reálných čísel je asociativní.

Některé příklady asociativních operací zahrnují následující.

• Zřetězení tří řetězců , , lze vypočítat zřetězením prvních dvou řetězců (giving ) a připojením třetího řetězce ( ), nebo spojením druhého a třetího řetězce (giving ) a zřetězením prvního řetězce ( ) s výsledkem. Tyto dvě metody poskytují stejný výsledek; zřetězení řetězců je asociativní (ale ne komutativní)."hello"" ""world""hello ""world"" world""hello"
• V aritmetice , sčítání a násobení reálných čísel jsou asociativní; tj,

${\displaystyle \left.{\begin{matrix}(x+y)+z=x+(y+z)=x+y+z\quad \\(x\,y)z=x(y\,z )=x\,y\,z\qquad \qquad \qquad \quad \ \ \,\end{matice}}\right\}{\mbox{pro všechny }}x,y,z\in \mathbb {R } .}$

Kvůli asociativitě mohou být závorky seskupení vynechány bez dvojznačnosti.

• Triviální operace x ∗ y = x (to znamená, že výsledkem je první argument, bez ohledu na to, jaký je druhý argument) je asociativní, ale ne komutativní. Podobně triviální operace x ∘ y = y (to znamená, že výsledkem je druhý argument, bez ohledu na to, jaký je první argument) je asociativní, ale ne komutativní.
• Sčítání a násobení komplexních čísel a čtveřic jsou asociativní. Sčítání oktonionů je také asociativní, ale násobení oktonionů je neasociativní.
• Největší společný dělitel a nejmenší společný násobek funkcí působí asociativně.

${\displaystyle \left.{\begin{matrix}\operatorname {gcd} (\operatorname {gcd} (x,y),z)=\operatorname {gcd} (x,\operatorname {gcd} (y,z) )=\název operátora {gcd} (x,y,z)\ \quad \\\název operátora {lcm} (\název operátora {lcm} (x,y),z)=\název operátora {lcm} (x,\název operátora { lcm} (y,z))=\jméno operátora {lcm} (x,y,z)\quad \end{matrix}}\right\}{\mbox{ pro všechna }}x,y,z\in \mathbb {Z} .}$

• Využití křižovatky nebo spojení množin : _

${\displaystyle \left.{\begin{matrix} (A\cap B)\cap C=A\cap (B\cap C)=A\cap B\cap C\quad \\(A\cup B)\ šálek C=A\pohár (B\pohár C)=A\pohár B\pohár C\čtyřkolka \end{matice}}\vpravo\}{\mbox{pro všechny sady }}A,B,C.}$

• Jestliže M je nějaká množina a S označuje množinu všech funkcí od M do M , pak je operace skládání funkcí na S asociativní:

${\displaystyle (f\circ g)\circ h=f\circ (g\circ h)=f\circ g\circ h\qquad {\mbox{for all }}f,g,h\in S.}$

• Trochu obecněji, dáme-li čtyři množiny M , N , P a Q , s h : M na N , g : N na P af : P na Q , pak

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

jako dříve. Stručně řečeno, kompozice map je vždy asociativní.

• Uvažujme množinu se třemi prvky, A, B a C. Následující operace:

×	A	B	C
A	A	A	A
B	A	B	C
C	A	A	A

je asociativní. Tedy například A(BC)=(AB)C = A. Tato operace není komutativní.

• Protože matice reprezentují lineární funkce a násobení matic představuje složení funkcí, lze okamžitě dojít k závěru, že násobení matic je asociativní.

Výroková logika

Pravidlo výměny

Ve standardní pravdivostně funkční výrokové logice jsou asociace nebo asociativita dvě platná pravidla nahrazení . Pravidla umožňují přesouvat závorky v logických výrazech v logických důkazech . Pravidla (pomocí zápisu logických spojovacích prvků) jsou:

${\displaystyle (P\lor (Q\lor R))\Leftrightarrow ((P\lor Q)\lor R)}$

a

${\displaystyle (P\land (Q\land R))\Leftrightarrow ((P\land Q)\land R),}$

kde " " je metalogický symbol představující "lze nahradit v nátisku s". ${\displaystyle \Leftrightarrow }$

Pravda funkční spojky

Asociativita je vlastnost některých logických spojek pravdivostně-funkční výrokové logiky . Následující logické ekvivalence demonstrují, že asociativita je vlastností konkrétních spojovacích výrazů. Následují pravdivě funkční tautologie .

Asociativita disjunkce :

${\displaystyle ((P\lor Q)\lor R)\leftrightarrow (P\lor (Q\lor R))}$

${\displaystyle (P\lor (Q\lor R))\leftrightarrow ((P\lor Q)\lor R)}$

Asociativita konjunkce :

${\displaystyle ((P\land Q)\land R)\leftrightarrow (P\land (Q\land R))}$

${\displaystyle (P\land (Q\land R))\leftrightarrow ((P\land Q)\land R)}$

Asociativita ekvivalence :

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

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

Společné popření je příkladem funkčního spojovacího výrazu, který není asociativní.

Neasociativní operace

Binární operace na množině S , která nesplňuje asociativní zákon, se nazývá neasociativní . Symbolicky, ${\displaystyle *}$

${\displaystyle (x*y)*z\neq x*(y*z)\qquad {\mbox{pro některé }}x,y,z\in S.}$

U takové operace na pořadí hodnocení záleží . Například:

• Odčítání

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

• Divize

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

• Umocňování

${\displaystyle 2^{(1^{2})}\,\neq \,(2^{1})^{2}}$

• Vektorový křížový produkt

${\displaystyle {\begin{aligned}\mathbf {i} \times (\mathbf {i} \times \mathbf {j} )&=\mathbf {i} \times \mathbf {k} =-\mathbf {j } \\(\mathbf {i} \times \mathbf {i} )\times \mathbf {j} &=\mathbf {0} \times \mathbf {j} =\mathbf {0} \end{aligned}} }$

Také ačkoli je sčítání asociativní pro konečné součty, není asociativní uvnitř nekonečných součtů ( řad ). Například,

${\displaystyle (1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+\tečky =0}$

zatímco

${\displaystyle 1+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+\tečky = 1.}$

Některé neasociativní operace jsou v matematice zásadní. Často se objevují jako násobení ve strukturách nazývaných neasociativní algebry , které mají také sčítání a skalární násobení . Příklady jsou oktoniony a Lieovy algebry . V Lieových algebrách násobení uspokojuje Jacobiho identitu místo asociativního zákona; toto umožňuje abstrahovat algebraickou povahu infinitezimálních transformací .

Jiné příklady jsou kvazigrupa , kvazipole , neasociativní kruh a komutativní neasociativní magmata .

Neasociativita výpočtu s pohyblivou řádovou čárkou

V matematice je sčítání a násobení reálných čísel asociativní. Naproti tomu v informatice není sčítání a násobení čísel s plovoucí desetinnou čárkou asociativní, protože při spojení hodnot rozdílných velikostí dochází k zaokrouhlovacím chybám.

Pro ilustraci uvažujme reprezentaci s plovoucí desetinnou čárkou se 4bitovou mantisou :
(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 ⁴

Přestože většina počítačů počítá s 24 nebo 53 bity mantisy, je to důležitý zdroj zaokrouhlovacích chyb a přístupy, jako je Kahanův sumační algoritmus, jsou způsoby, jak chyby minimalizovat. Obzvláště problematické to může být při paralelním počítání.

Zápis pro neasociativní operace

Obecně platí, že závorky musí být použity k označení pořadí vyhodnocení , pokud se neasociativní operace objeví ve výrazu více než jednou (pokud zápis neurčuje pořadí jiným způsobem, například ). Matematici se však shodují na konkrétním pořadí hodnocení pro několik běžných neasociativních operací. Toto je prostě konvence zápisu, aby se zabránilo závorkám. ${\displaystyle {\dfrac {2}{3{/4}}}$

Levá asociativní operace je neasociativní operace, která se konvenčně vyhodnocuje zleva doprava, tzn.

${\displaystyle \left.{\begin{matrix}x*y*z=(x*y)*z\qquad \qquad \quad \,\\w*x*y*z=((w*x)* y)*z\quad \\{\mbox{atd.}}\qquad \qquad \qquad \qquad \qquad \qquad \ \ \,\end{matrix}}\right\}{\mbox{pro všechny }} w,x,y,z\in S}$

zatímco pravá asociativní operace se konvenčně vyhodnocuje zprava doleva:

${\displaystyle \left.{\begin{matrix}x*y*z=x*(y*z)\qquad \qquad \quad \,\\w*x*y*z=w*(x*(y *z))\quad \\{\mbox{atd.}}\qquad \qquad \qquad \qquad \qquad \qquad \ \ \,\end{matrix}}\right\}{\mbox{pro všechny }} w,x,y,z\in S}$

Vyskytují se levo-asociativní i pravé asociativní operace. Levé asociativní operace zahrnují následující:

• Odčítání a dělení reálných čísel:

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

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

• Aplikace funkcí:

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

Tento zápis může být motivován curryingovým izomorfismem.

Mezi pravoasociativní operace patří následující:

• Umocňování reálných čísel v zápisu horního indexu:

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

Umocňování se běžně používá se závorkami nebo asociativně vpravo, protože opakovaná operace umocňování vlevo je málo použitelná. Opakované mocniny by byly většinou přepsány násobením:

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

Správně naformátovaný horní index se přirozeně chová jako sada závorek; např. ve výrazu se sčítání provádí před umocněním, přestože kolem něj nejsou žádné explicitní závorky. Tedy daný výraz, jako je , je nejprve vyhodnocen úplný exponent základu . V některých kontextech, zejména v rukopisu, však může být rozdíl mezi , a těžko viditelný. V takovém případě je obvykle implikována pravá asociativita.${\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})}}$

• Definice funkce

${\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)}$

Použití pravé asociativní notace pro tyto operace může být motivováno Curry-Howardovou korespondencí a curryingovým izomorfismem.

Neasociativní operace, pro které není definován konvenční vyhodnocovací příkaz, zahrnují následující.

• Umocňování reálných čísel v infixovém zápisu:

${\displaystyle (x^{\wedge }y)^{\wedge }z\neq x^{\wedge }(y^{\wedge }z)}$

• Knuthovy operátory šipky nahoru :

${\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}$

• Vezmeme křížový součin tří vektorů:

${\displaystyle {\vec {a}}\times ({\vec {b}}\times {\vec {c}})\neq ({\vec {a}}\times {\vec {b}}) \times {\vec {c}}\qquad {\mbox{ pro některé }}{\vec {a}},{\vec {b}},{\vec {c}}\in \mathbb {R} ^ {3}}$

• Vezmeme-li párový průměr reálných čísel:

${\displaystyle {(x+y)/2+z \over 2}\neq {x+(y+z)/2 \over 2}\qquad {\mbox{pro všechna }}x,y,z\in \ mathbb {R} {\mbox{ s }}x\neq z.}$

• Vzít relativní doplněk množin není totéž jako . (Porovnejte věcnou neimplikaci v logice.)${\displaystyle (A\obrácené lomítko B)\obrácené lomítko C}$${\displaystyle A\obrácené lomítko (B\obrácené lomítko C)}$

Dějiny

Zdá se, že William Rowan Hamilton vytvořil termín „asociativní vlastnost“ kolem roku 1844, v době, kdy uvažoval o neasociativní algebře Octonionů , o které se dozvěděl od Johna T. Gravese.

Viz také

• Lightův test asociativity
• Telescoping series , použití asociativity sčítání pro zrušení členů v nekonečné řadě
• Pologrupa je množina s asociativní binární operací.
• Komutativnost a distributivita jsou dvě další často diskutované vlastnosti binárních operací.
• Mocninná asociativita , alternativnost , flexibilita a N-ární asociativita jsou slabé formy asociativnosti.
• Identity muufangů také poskytují slabou formu asociativnosti.

Reference