Sifat asosiatif

Dalam matematika, sifat asosiatif adalah sebuah sifat dari beberapa operasi biner, yang berarti mengubah posisi tanda kurung dalam sebuah ekspresi tidak akan mengubah hasilnya, Dalam logika proposisional, asosiatif adalah sebuah aturan pengganti yang sah untuk ekspresi-ekspresi dalam bukti logis.

Dalam sebuah ekspresi mengandung dua kejadian atau lebih dalam sebuah baris dari operator asosiatif yang sama, urutan pelaksanaan operasi-operasi tidak menjadi masalah selama barisan dari operan tidak berubah. Artinya, (setelah menulis ulang ekspresinya dengan tanda kurung dan dalam notasi infiks jika diperlukan) mengubah posisi tanda kurung dalam ekspresi seperti itu tidak akan mengubah nilainya. Tinjaulah persamaan berikutː

$(2+3)+4=2+(3+4)=9\,$

$2\times (3\times 4)=(2\times 3)\times 4=24.$

Meskipun tanda kurung mengubah posisi pada setiap garis, nilainya pada ekspresi tidak berubah. Karena ini benar ketika tampil sebagai penjumlahan dan perkalian pada setiap bilangan real, ini bisa dikatakan "penjumlahan dan perkalian dari bilangna real adalah merupakan operasi asosiatif".

Asosiatif tidak sama dengan komutatif, yang membahas apakah urutan dari dua operan mengubah hasil atau tidak . Sebagai contoh, urutan tidak masalah dalam perkalian bilangan real, yaitu, $a\times b=b\times a$, jadi kita katakan bahwa perkalian bilangan real adalah operasi komutatif.

Operasi asosiatif berlimpah dalam matematika; faktanya, banyak struktur aljabar (seperti semigrup dan kategori) secara eksplisit membutuhkan operasi binernya menjadi asosiatif.

Bagaimanapun, banyak yang penting dan operasi-operasi yang menarik merupakan non-asosiatif, beberapa contoh termasuk pengurangan, eksponensiasi, dan produk cross vektor. Berlawanan dengan sifat-sifat teoretis dari bilangan real, penjumlahan dan bilangan titik mengambang dalam ilmu komputer tidak asosiatif, dan pilihan bagaiamana untuk mengasosiasikan sebuah ekspresi bisa memiliki sebuah hasil yang penting pada kesalahan pembulatan.

Definisi

Sebuah operasi biner ∗ pada himpunan $S$ asosiatif ketika diagram ini komutatif. Artinya, ketika dua jalur dari $S\times S\times S$ ke komposisi $S$ menadi fungsi yang sama dari $S\times S\times S$ ke $S$.

Secara formal, sebuah operasi biner $*$ pada sebuah himpunan $S$ disebut asosiatif jika memenuhi hukum asosiatif.

$(x*y)*z=x*(y*z)$, untuk semua $x,y,z$ dalam $S$

Disini $*$ digunakan untuk menggantikan simbol operasi, yang mungkin merupakan simbol apapun, dan meskipun ketiadaan dari simbol (penjajaran) sebagai untuk perkalian.

$(xy)z=x(yz)=xyz$, untuk semua $x,y,z$ dalam $S$.

Hukum asosiatif bisa juga diekspresikan dalam notasi fungsional jadiː $f(f(x,y),z)=f(x,f(y,z))$.

Hukum asosiatif yang digeneralisasikan

Dalam ketiadaan dari sifat asosiatif, kelima faktor $a,b,c,d,e$ menghasilkan sebuah kisi Tamari urutan keempat, produk yang mungkin berbeda.

Jika sebuah operasi biner adalah asosiatif, penerapan berulang dari operasi menghasilkan hasil yang sama terlepas dan bagaimana pasangan tanda kurung yang sah disisipkan dalam ekspresi. Ini disebut hukum asosiatif yang digeneralisasi. Misalnya, sebuah porduk fari empat anggota bisa ditulis bisa ditulis, tanpa menggantikan urutan dari faktor-faktor, dalam lima kemungkinanː

$((ab)c)d$

$(ab)(cd)$

$(a(bc))d$

$a((bc)d)$

$a(b(cd))$

Jika operasi produk adalah asosiatif, hukum asosiatif yang digeneralisasi mengatakan bahwa semua rumus-rumus ini akan menghasilkan hasil yang sama. Jadi kecuali rumus dengan tanda kurung yang dihilangkan sudah memiliki sebuah arti yang berbeda (lihat bawah), tanda kurung bisa dianggap tidak perlu dan produk"nya" bisa ditulis dengan jelas sebagaiː

$abcd.$

Sebagai bilangan dari anggota-anggota meningkat, bilangan dari kemungkinan cara untuk memasukkan tanda kurung tumbuh dengan cepat, tetapi tidak perlu untuk disambiguasi.

Sebuah contoh di mana tidak bekerja adalah bikondisional logis $\leftrightarrow$. Ini adalah asosiatif, demikian $A\leftrightarrow (B\leftrightarrow C)$ ekuivalen dengan $(A\leftrightarrow B)\leftrightarrow C$, namun $A\leftrightarrow B\leftrightarrow C$ paling umum mengartikan ($A\leftrightarrow B$ dan $B\leftrightarrow C$), yang tidak ekuivalen

Contoh

Dalam operasi-operasi asosiatif adalah $(x\circ y)\circ z=x\circ (y\circ z)$.

Penjumlahan dari bilangan real adalah asosiatif.

Beberapa contoh dari operasi-operasi asosiatif termasuk yang berikut ini.

• Penggabungan dari tiga rangkaian "hello", " ", "world" bisa dihitung oleh penggabungan dua rangkaian pertama (diberikan "hello ") dan menambhakan rangkaian ketiga ("world"), atau dengan menggabungkan rangkaian kedua atau ketiga (diberikan " world") dan menggabungkan rangkaian pertama ("hello") dengan hasilnya. Keuda metodenya menghasilkan hasil yang sama, penggabungan rangkaian adalah asosiatig (tetapi bukan komutatif).
• Dalam aritmetika, penjumlahan dan perkalian dari bilangan real adalah asosiatif, yaitu,

$\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{matrix}}\right\}{\mbox{untuk semua }}x,y,z\in \mathbb {R} .$

Karena asosiatif, pengelompokan tanda kurung bisa dihilangkan tanpa kemenduaan.

• Operasi biasa $x*y=x$ (artinya, hasilnya adalah argumen pertama, tidak peduli apa argumen keduanya) adalah asosiatif, tetapi bukan komutatif. Demikian juga, operasi trivial $x\circ y=y$ (artinya, hasilnya adalah argumen kedua, tidak peduli apa argumen kepertamanya) adalah asosiatif, tetapi bukan komutatif.
• Penjumlahan dan peralian dari bilangan kompleks dan kuaternion adalah asosiatif. Penjumlahan dari oktonion juga asosiatif, tetapi perkalian dari oktonion adalah tidak asosiatif.
• Fungsi faktor persekutuan terbesar dan kelipatan persekutuan terkecil bersifat secara asosiatif.

$\left.{\begin{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}}\right\}{\mbox{ for all }}x,y,z\in \mathbb {Z} .$

• Mengambil irisan atau gabungan dari himpunan-himpunanː

$\left.{\begin{matrix}(A\cap B)\cap C=A\cap (B\cap C)=A\cap B\cap C\quad \\(A\cup B)\cup C=A\cup (B\cup C)=A\cup B\cup C\quad \end{matrix}}\right\}{\mbox{for all sets }}A,B,C.$

• Jika $M$ adalah beberapa himpunan dan $S$ melambangkan himpunan dari semua fungsi dari $M$ ke $M$, maka operasi dari komposisi fungsi pada $S$ adalah asosiatifː

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

• Sedikit lebih umum, diberikan empat himpunan $M$, $N$, $P$, dan $Q$, dengan $h$ː $M$ ke $N$,$g$ː $N$ ke $P$, dan $f$ː $P$ ke $Q$, makaː

$(f\circ g)\circ h=f\circ (g\circ h)=f\circ g\circ h$

seperti sebelumnya. Pendeknya, komposisi dari peta selalu asosiatif.

• Tinjaulah sebuah himpunan dengan tiga anggota, $A$, $B$, dan $C$. Operasi berikut iniː

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

asosiatif. Demikian, sebagai contoh, $A(BC)=(AB)C=A$. Operasi ini tidak komutatif.

• Karena matriks mewakili fungsi linear, dan perkalian matriks mewakili komposisi fungsi, salah satunya bisa secepatnya menyimpulkan bahwa perkalian matriks adalah asosiatif.

Logika proposisional

Aturan penggantian

Dalam logika proposisional kebenaran fungsional standar, asosiasi, atau asosiatif adalah dua aturan penggantian yang sah. Peraturannya memungkinkan salah satunya untuk memindahkan tanda kurung dalam ekspresi logis dalam bukti logis. Aturan (menggunakan notasi penghubung logis adalahː

$(P\lor (Q\lor R))\Leftrightarrow ((P\lor Q)\lor R)$

dan

$(P\land (Q\land R))\Leftrightarrow ((P\land Q)\land R),$

dimana "$\Leftrightarrow$" adalah simbol metalogis mewakili "bisa menggantikan dalam sebuah bukti dengan."

Penghubung fungsional kebenaran

Asosiatif adalah sebuah sifat dari beberapa penghubung logis. Kesetaraan logis berikut mendemonstrasikan bahwa asosiatif adalah sebuah sifat dari penghubung tertentu. Berikut ini adalah tautologi fungsional kebenaran.

Asosiatif dari disjungsi

$((P\lor Q)\lor R)\leftrightarrow (P\lor (Q\lor R))$

$(P\lor (Q\lor R))\leftrightarrow ((P\lor Q)\lor R)$

Asosatif dari konjungsi

$((P\land Q)\land R)\leftrightarrow (P\land (Q\land R))$

$(P\land (Q\land R))\leftrightarrow ((P\land Q)\land R)$

Asosatif dari kesetaraan

$((P\leftrightarrow Q)\leftrightarrow R)\leftrightarrow (P\leftrightarrow (Q\leftrightarrow R))$

$(P\leftrightarrow (Q\leftrightarrow R))\leftrightarrow ((P\leftrightarrow Q)\leftrightarrow R)$

Penolakan bersama adalah sebuah contoh dari sebuah penghubung fungsional kebenaran yang bukan asosiatif.

Operasi non-asosiatif

Sebuah operasi biner $*$ pada sebuah himpunan $S$ yang tidak memenuhi hukum asosiatif disebut non-asosiatif. Secara simbolis,

Untuk sebuah operasi, urutan dari evaluasi itu penting. Sebagai contohː

• Pengurangan

$(5-3)-2\,\neq \,5-(3-2)$

• Pembagian

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

Juga perhatikan bahwa penjumlahan tak terbatas umumnya tidak asosatif, sebagai contohː

dimana

Studi tentang struktur-struktur non-asosiatif muncul dari alasan-alasan agak berbeda dari arus utama dari aljabar klasik. Satu area dalam aljabar non-asosiatif yang tumbuh sangat besar adalah aljabar Lie. Disana hukum asosiatif dignatikan oleh identitas Jacobi. Aljabar Lie meringkaskan alami esensial dari transformasi infinitesimal, dan telah menjadi di mana-mana dalam matematika.

Terdapat jenis-jenis tertentu lainnya yang telah dipelajari secara mendalam; ini cenderung berasal dari beberapa penerapan yang spesifik atau bidang-bidang seperti matematika kombinatorial. Contoh lainnya adalah grup kuasi, bidang kuasi, gelanggang non-asosiatif, aljabar non-asosiatif dan magma non-asosiatif komutatif.

Nonasosiatif dari perhitungan titik mengambang

Dalam matematika, penjumlahan dan perkalian dari bilangan real adalah asosiatif. Sebaliknya, dalam ilmu komputer, penjumlahan dan perkalian dari bilangan titik mengambang tidak asosiatif, sebagai galat pembulatan diperkenalkan ketika nilai-nilai berukuran berbeda digabungkan berbeda.

Untuk mengilustrasikan ini, tinjaulah sebuah representasi titik mengambang dengan sebuah mantissa 4-bit.

(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⁴

Meskipun sebagian besar komputer-komputer menghitung dengan 24 atau 53 bit mantissa, ini adalah sumber yang penting dari galat pembulatan, dan mendekati seperti algoritma penjumlahan Kahan adalah cara untuk memperkecil galat-galatnya. Itu bisa sangat berpengalaman dlam komputer paralel.

Notasi untuk operasi-operasi non-asosiastif

Secara umum, tanda kurung pasti digunakan untuk menunjukkan urutan evaluasi jika sebuah operasi non-asosiatif muncul lebih dari satu dalam sebuah ekspresi (kecuali notasinya menentukan urutannya dengan cara lain, seperti ${\frac {2}{3/4}}$). Namun, matematikawan setuju pada sebuah urutan evaluasi tertentu untuk beberapa umum operasi non-asosiatif. Ini meyederhanakan sebuah konvensi notasi untuk menghindari tanda kurung.

Sebuah operasi asosiatif kiri adalah operasi non-asosiatif yang secara konvensional dievaluasikan dari kiri ke kanan, yaitu,

$\left.{\begin{matrix}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{for all }}w,x,y,z\in S$

sedangkan sebuah operasi asosiatif kanan secara konvensional dievaluasikan dari kanan ke kiri.

$\left.{\begin{matrix}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{for all }}w,x,y,z\in S$

Kedua operasi asosiatif kiri dan asosiatif kanan terjadi. Operasi asosiatif kiri termasuk yang berikut ini.

• Pengurangan dan pembagian dari bilangan realː
• Penerapanː fungsi

$(f\,x\,y)=((f\,x)\,y)$

Notasi ini bisa dimotivasi dengan currying isomorfisme.

Operasi asosiatif kanan termasuk yang berikut ini.

• Eksponensiasi atau bilangan real dalam notasi superskripː

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

Eksponensiasi biasanya digunakan dengan tanda kurung atau asosatif kanan karena sebuah operasi eksponensiasi asosiatif kiri yang berulang tidak banyak digunakan. Pangkat berulang sering ditulis ulang dengan perkalian

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

Diformat dengan benar, supeskrip secara inheren berperilaku sebagai sebuah himpunan dari tanda kurung; misalnya, dalam ekspresi $2^{x+3}$, penjumlahan dilkaukan sebelum eksponensiasi meskipun tidak ada tanda kurung eksplisit $2^{(x+3)}$ melilitnya. Demikian diberikan sebuah ekspresi seperti $x^{y^{z}}$, eksponen penuh $y^{z}$ dari dasar $x$ dievaluasikan pertama. Namun, dalam beberapa konteks, termasuk tulis tangan, perbedaan antara ${x^{y}}^{z}=(x^{y})^{z}$, $x^{yz}=x^{(yz)}$ dan $x^{y^{z}}=x^{(y^{z})}$ bisa jadi sulit untuk dilihat. Dalam kasus seperti itu, asosiatif kanan biasanya tersirat.

• Definisi fungsi

Menggunakan notasi asosiatif kanan untuk operasi-operasi ini bisa dimotivasi oleh korespondensi Curry-Howard dan dengan currying isomorfisme.

Operasi non-asosiatif untuk yang urutan evaluasi yang tidak konvensional didefinisikan termasuk sebagai berikut.

• Eksponensiasi dari bilangan real dalam notasi infiks.

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

• Operator panah atas Knuth

$a\uparrow \uparrow (b\uparrow \uparrow c)\neq (a\uparrow \uparrow b)\uparrow \uparrow c$

$a\uparrow \uparrow \uparrow (b\uparrow \uparrow \uparrow c)\neq (a\uparrow \uparrow \uparrow b)\uparrow \uparrow \uparrow c$

• Mengambil produk silang
• Mengambil rata-rata berpasangan dari bilangan realː

${(x+y)/2+z \over 2}\neq {x+(y+z)/2 \over 2}\qquad {\mbox{for all }}x,y,z\in \mathbb {R} {\mbox{ with }}x\neq z.$

• Mengambil komplemen relatif dari himpunan $(A\backslash B)\backslash C$ tidak sama dengan $A\backslash (B\backslash C)$. (Membandingkan nonimplikasi material dalam logika.)

Lihat pula

• Tes asosiatif Light
• Deret teleskopik, penggunaan dari asosatif penjumlahan untuk membatalkan istilah dalam sebuah deret tak terhingga
• Sebuah semigrup adalah sebuah himpunan dengan operasi biner asosiatif.
• Komutatif dan distributif adalah dua lainnya yang sering dibahas sifat-sifat dari operasi-operasi biner.
• Asosiatif pangkat, alternatif, fleksibilitas, dan asosiatif N-ari adalah bentuk-bentuk yang lemah dari asosiatif.
• Identitas Moufang juga memberikan bentuk yang lemah dari asosiatif.