Asociativní vlastnost - Associative property

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Asociativní vlastnost“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Červen 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v matematika, asociativní majetek^[1] je majetkem některých binární operace, což znamená, že změna uspořádání závorek ve výrazu nezmění výsledek. v výroková logika, asociativita je platný pravidlo nahrazení pro výrazy v logické důkazy.

Ve výrazu obsahujícím dva nebo více výskytů v řádku stejného asociativního operátoru, pořadí, ve kterém operace jsou prováděny, nezáleží na tom, jak dlouho po sekvenci operandy se nezmění. To znamená (po přepsání výrazu v závorkách a v případě potřeby v infixové notaci) přeskupení závorky v takovém výrazu se nezmění jeho hodnota. Zvažte následující rovnice:

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

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

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

Asociativita není stejná jako komutativita, který řeší pořadí dvou operandy změní výsledek. Například na pořadí nezáleží při násobení reálných čísel, tj. A × b = b × A, takže říkáme, že násobení reálných čísel je komutativní operací.

Asociativní operace jsou v matematice hojné; ve skutečnosti mnoho algebraické struktury (jako poloskupiny a Kategorie ) výslovně vyžadují, aby jejich binární operace byly asociativní.

Mnoho důležitých a zajímavých operací však není asociativních; některé příklady zahrnují odčítání, umocňování a vektor křížový produkt. Na rozdíl od teoretických vlastností reálných čísel, přidání plovoucí bod čísla v informatice nejsou asociativní a volba způsobu přidružení výrazu může mít významný vliv na zaokrouhlovací chybu.

Definice

Binární operace ∗ na přístroji S je asociativní, když tento diagram dojíždí. To znamená, že když obě cesty z S×S×S na S komponovat na stejnou funkci od S×S×S na S.

Formálně, a binární operace ∗ na a soubor S je nazýván asociativní pokud vyhovuje asociační právo:

(X ∗ y) ∗ z = X ∗ (y ∗ z) pro všechny X, y, z v S.

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

(xy)z = X(yz) = xyz pro všechny X, y, z v S.

Asociativní zákon lze vyjádřit také funkční notací takto: F(F(X, y), z) = F(X, F(y, z)).

Zobecněné asociační právo

Při absenci asociativního majetku pět faktorů a, b, c, d, e mít za následek Tamari mříž objednávky čtyři, případně různé produkty.

Pokud je binární operace asociativní, opakovaná aplikace operace vytvoří stejný výsledek bez ohledu na to, jak jsou do výrazu vloženy platné dvojice závorek.^[2] Tomu se říká zobecněné asociační právo. Například lze napsat produkt čtyř prvků, 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 produktu asociativní, zobecněný asociativní zákon říká, že všechny tyto vzorce přinesou stejný výsledek. Takže pokud vzorec s vynechanými závorkami již nemá jiný význam (viz níže), lze závorky považovat za zbytečné a produkt „“ lze jednoznačně zapsat jako

${displaystyle abcd.}$

Jak se počet prvků zvyšuje, počet možných způsobů vložení závorek rychle roste, ale pro disambiguaci zůstávají zbytečné.

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

Příklady

V asociativních operacích je ${displaystyle (xcirc y) circle z = xcirc (ycirc z)}$.

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

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

• The zřetězení ze tří strun "Ahoj", " ", "svět" lze vypočítat zřetězením prvních dvou řetězců (dává "Ahoj ") a připojení třetího řetězce ("svět"), nebo spojením druhého a třetího řetězce (dává "svět") a zřetězení prvního řetězce ("Ahoj") s výsledkem. Tyto dvě metody produkují stejný výsledek; zřetězení řetězců je asociativní (ale nikoli komutativní).
• v aritmetický, přidání a násobení z reálná čísla jsou asociativní; tj.,

${displaystyle left. {egin {matrix} (x + y) + z = x + (y + z) = x + y + zquad (x, y) z = x (y, z) = x, y, zqquad qquad qquad quad, end {matrix}} ight} {mbox {for all}} x, y, zin mathbb {R}.}$

Z důvodu asociativity lze seskupovací závorky bez dvojznačnosti vynechat.

• 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 nikoli komutativní. Stejně tak 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 nikoli komutativní.
• Sčítání a násobení komplexní čísla a čtveřice jsou asociativní. Přidání octonions je také asociativní, ale násobení oktonionů je neasociativní.
• The největší společný dělitel a nejmenší společný násobek funkce působí asociativně.

${displaystyle left. {egin {matrix} operatorname {gcd} (operatorname {gcd} (x, y), z) = operatorname {gcd} (x, operatorname {gcd} (y, z)) = operatorname {gcd} ( x, y, z) quad operatorname {lcm} (operatorname {lcm} (x, y), z) = operatorname {lcm} (x, operatorname {lcm} (y, z)) = operatorname {lcm} (x , y, z) quad end {matrix}} ight} {mbox {pro všechny}} x, y, zin mathbb {Z}.}$

• Užívání průsečík nebo svaz z sady:

${displaystyle left. {egin {matrix} (Acap B) cap C = Acap (Bcap C) = Acap Bcap Cquad (Acup B) cup C = Acup (Bcup C) = Acup Bcup Cquad end {matrix}} ight} { mbox {pro všechny sady}} A, B, C.}$

• Li M je nějaká sada a S označuje sadu všech funkcí z M na M, pak provoz složení funkce na S je asociativní:

${displaystyle (fcirc g) circle h = fcirc (gcirc h) = fcirc gcirc hqquad {mbox {pro všechny}} f, g, hin S.}$

• Mírně obecněji, vzhledem ke čtyřem sadám M, N, P a Q, s h: M na N, G: N na P, a F: P na Q, pak

${displaystyle (fcirc g) circle h = fcirc (gcirc h) = fcirc gcirc h}$

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

• Zvažte sadu 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í. Tak například A (BC) = (AB) C = A. Tato operace není komutativní.

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

Výroková logika

Pravidlo výměny

Ve standardní pravdivě funkční výrokové logice sdružení,^[4][5] nebo asociativita^[6] jsou dva platný pravidla nahrazení. Pravidla umožňují přesouvat závorky logické výrazy v logické důkazy. Pravidla (pomocí logické spojky notace) jsou:

${displaystyle (Plor (Qlor R)) Leftrightarrow ((Plor Q) lor R)}$

a

${displaystyle (Pland (Qland R)) Leftrightarrow ((Pland Q) land R),}$

kde "${displaystyle Leftrightarrow}$" je metalogické symbol představující "lze nahradit v a důkaz s."

Pravda funkční spojky

Asociativita je majetkem některých logické spojky pravdivě funkční výroková logika. Následující logické ekvivalence prokázat, že asociativita je vlastnost konkrétních spojek. Následující jsou pravdivě funkční tautologie.^[7]

Asociativita disjunkce:

${displaystyle ((Plor Q) lor R) leftrightarrow (Plor (Qlor R))}$

${displaystyle (Plor (Qlor R)) leftrightarrow ((Plor Q) lor R)}$

Asociativita spojení:

${displaystyle ((Pland Q) land R) leftrightarrow (Pland (Qland R))}$

${displaystyle (Pland (Qland R)) leftrightarrow ((Pland Q) land R)}$

Asociativita rovnocennosti:

${displaystyle ((Pleftrightarrow Q) leftrightarrow R) leftrightarrow (Pleftrightarrow (Qleftrightarrow R))}$

${displaystyle (Pleftrightarrow (Qleftrightarrow R)) leftrightarrow ((Pleftrightarrow Q) leftrightarrow R)}$

Společné popření je příkladem funkčního pojiva pravdivosti ne asociativní.

Neasociativní operace

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

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

U takové operace pořadí hodnocení dělá hmota. Například:

• Odčítání

${displaystyle (5-3) -2, ekv., 5- (3-2)}$

• Divize

${displaystyle (4/2) / 2, ekv., 4 / (2/2)}$

• Umocňování

${displaystyle 2 ^ {(1 ^ {2})}, ekv, (2 ^ {1}) ^ {2}}$

Všimněte si také, že nekonečné částky nejsou obecně asociativní, 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}$

Studium neasociativních struktur vychází z důvodů poněkud odlišných od hlavního proudu klasické algebry. Jedna oblast uvnitř neasociativní algebra který se velmi rozrostl, je Lež algebry. Tam je asociativní zákon nahrazen Jacobi identita. Algebry lži abstraktní podstatu nekonečně malé transformace, a stali se všudypřítomnými v matematice.

Existují další specifické typy neasociativních struktur, které byly podrobně studovány; tyto mají tendenci pocházet z některých konkrétních aplikací nebo oblastí, jako je kombinatorická matematika. Další příklady jsou kvazigroup, quasifield, neasociativní prsten, neasociativní algebra a komutativní neasociativní magma.

Neasociativita výpočtu s plovoucí desetinnou čárkou

V matematice je sčítání a násobení reálných čísel asociativní. Naproti tomu v počítačové vědě sčítání a množení plovoucí bod čísla jsou ne asociativní, protože chyby zaokrouhlování jsou zavedeny, když jsou hodnoty odlišné velikosti spojeny dohromady.^[8]

Pro ilustraci zvažte 4-bitovou reprezentaci s plovoucí desetinnou čárkou mantisa:
(1.000₂×2⁰ +1.000₂×2⁰) +1.000₂×2⁴ =1.000₂×2¹ +1.000₂×2⁴ =1.001₂×2⁴
1.000₂×2⁰ +(1.000₂×2⁰ +1.000₂×2⁴) =1.000₂×2⁰ +1.000₂×2⁴ =1.000₂×2⁴

Přestože většina počítačů počítá s 24 nebo 53 bity mantisy,^[9] toto je důležitý zdroj chyby zaokrouhlování a přístupy jako Kahanův součtový algoritmus jsou způsoby, jak chyby minimalizovat. To může být obzvláště problematické v paralelních výpočtech.^[10][11]

Zápis pro neasociativní operace

Obecně se k označení musí použít závorky pořadí hodnocení pokud se neasociativní operace objeví více než jednou ve výrazu (pokud notace neurčí pořadí jiným způsobem, jako ${displaystyle {dfrac {2} {3/4}}}$). Nicméně, matematici dohodnout se na konkrétním pořadí vyhodnocení několika běžných neasociativních operací. Jedná se jednoduše o notační konvenci, aby se zabránilo závorkám.

A levo-asociativní operace je neasociativní operace, která se konvenčně vyhodnocuje zleva doprava, tj.

${displaystyle left. {egin {matrix} x * y * z = (x * y) * zqquad qquad quad, w * x * y * z = ((w * x) * y) * zquad {mbox {atd .}} qquad qquad qquad qquad qquad qquad, end {matrix}} ight} {mbox {pro všechny}} w, x, y, zin S}$

zatímco a pravo-asociativní operace se konvenčně vyhodnocuje zprava doleva:

${displaystyle left. {egin {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, konec {matrix}} ight} {mbox {pro všechny}} w, x, y, zin S}$

Vyskytují se jak asociativní operace, tak asociativní operace. Levé asociativní operace zahrnují následující:

• Odečítání a dělení reálných čísel:^{[12][13][14][15][16]}

${displaystyle x-y-z = (x-y) -z}$

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

• Aplikace funkcí:

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

Tuto notaci lze motivovat pomocí kari izomorfismus.

Pravo-asociativní operace zahrnují následující:

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

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

Exponentiace se běžně používá v závorkách nebo vpravo asociativně, protože opakovaná operace levé asociativní umocňování je málo užitečná. Opakované síly by byly většinou přepsány násobením:

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

Správně naformátovaný horní index se ve své podstatě chová jako sada závorek; např. ve výrazu ${displaystyle 2 ^ {x + 3}}$ přidání se provede před umocňování, přestože neexistují žádné výslovné závorky ${displaystyle 2 ^ {(x + 3)}}$ omotané kolem toho. Tak daný výraz jako ${displaystyle x ^ {y ^ {z}}}$, plný exponent ${displaystyle y ^ {z}}$ základny ${displaystyle x}$ je vyhodnocen jako první. V některých kontextech, zejména v rukopisu, je však rozdíl mezi ${displaystyle {x ^ {y}} ^ {z} = (x ^ {y}) ^ {z}}$, ${displaystyle x ^ {yz} = x ^ {(yz)}}$ a ${displaystyle x ^ {y ^ {z}} = x ^ {(y ^ {z})}}$ může být těžké vidět. V takovém případě je pravá asociativita obvykle implikována.

• Definice funkce

${displaystyle mathbb {Z} ightarrow mathbb {Z} ightarrow mathbb {Z} = mathbb {Z} ightarrow (mathbb {Z} ightarrow mathbb {Z})}$

${displaystyle xmapsto ymapsto x-y = xmapsto (ymapsto x-y)}$

Použití pravo-asociativního zápisu pro tyto operace může být motivováno Curry – Howardova korespondence a podle kari izomorfismus.

Mezi neasociativní operace, pro které není definováno žádné konvenční hodnocení, patří následující.

• Umocňování reálných čísel v infixové notaci:^[17]

${displaystyle (x ^ {wedge} y) ^ {wedge} zeq x ^ {wedge} (y ^ {wedge} z)}$

• Knuthovi operátoři se šipkou nahoru:

${displaystyle auparrow uparrow (buparrow uparrow c) eq (auparrow uparrow b) uparrow uparrow c}$

${displaystyle auparrow uparrow uparrow (buparrow uparrow uparrow c) eq (auparrow uparrow uparrow b) uparrow uparrow uparrow c}$

• Užívání křížový produkt tří vektorů:

${displaystyle {vec {a}} imes ({vec {b}} imes {vec {c}}) eq ({vec {a}} imes {vec {b}}) imes {vec {c}} qquad {mbox {for some}} {vec {a}}, {vec {b}}, {vec {c}} in mathbb {R} ^ {3}}$

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

${displaystyle {(x + y) / 2 + z nad 2} eq {x + (y + z) / 2 nad 2} qquad {mbox {pro všechny}} x, y, zin mathbb {R} {mbox {with} } xeq z.}$

• Užívání relativní doplněk sad ${displaystyle (Ackslash B) ackslash C}$ není totéž jako ${displaystyle Ackslash (B ackslash C)}$. (Srovnej nezjednodušení materiálu logicky.)

Viz také

• Lightův test asociativity
• Teleskopická řada, použití asociativity přidávání pro rušení termínů v nekonečnu série
• A poloskupina je množina s asociativní binární operací.
• Komutativita a distribučnost jsou dvě další často diskutované vlastnosti binárních operací.
• Asociativita síly, alternativita, flexibilita a N-ary asociativita jsou slabé formy asociativity.
• Mufangské identity také poskytují slabou formu asociativity.

Reference