수학(mathematics)에서, 결합 속성(associative property)은 일부 이항 연산(binary operation)의 속성입니다. 명제 논리(propositional logic)에서, 결합성(associativity)은 논리적 증명(logical proofs)의 표현(expressions)에 대해 유효한(valid) 대체의 규칙(rule of replacement)입니다.
같은 결합적 연산자의 행에서 둘 이상의 발생을 포함하는 표현 안에서, 연산(operations)의 수열이 변경되지 않는 한 연산(operations)이 수행되는 순서는 중요하지 않습니다. 즉, (괄호와 함께 및 필요하다면 중위 표기법에서 표현을 다시 쓴 후) 그러한 표현에서 괄호(parentheses)를 다시-배열하는 것은 값을 변경하지 않을 것입니다. 다음 방정식을 생각해 보십시오:
\(\quad\)\((2 + 3) + 4 = 2 + (3 + 4) = 9 \,\)
\(\quad\)\(2 \times (3 \times 4) = (2 \times 3) \times 4 = 24 .\)
심지어 괄호가 각 줄에서 다시-배치될지라도, 표현의 값은 변경되지 않았습니다. 이것은 임의의 실수(real number)에 대한 덧셈과 곱셈을 수행할 때 참을 유지하므로, "실수의 덧셈과 곱셈은 결합적 연산"이라고 말할 수 있습니다.
결합성(Associativity)은, 두 피연산자(operand)의 순서가 결과를 변경하는지 여부를 나타내는 교환성(commutativity)과 같지 않습니다. 예를 들어, 그 순서는 실수의 곱셈에서 중요하지 않습니다; 즉, a × b = b × a이므로, 우리는 실수 곱셈은 교환적 연산이라고 말합니다.
결합 연산은 수학에 매우 자주 나옵니다; 실제로, (세미-그룹(semigroups) 및 카테고리(categories)와 같은) 많은 대수적 구조(algebraic structure)는 명시적으로 이항 연산에서 결합적이 되는 것을 요구합니다.
어쨌든, 많은 중요하고 흥미로운 연산은 비-결합적입니다; 일부 예제는 뺄셈(subtraction), 지수(exponentiation) 및 벡터 교차 곱(vector cross product)을 포함합니다. 실수의 이론적 속성과는 다르게, 컴퓨터 과학에서 부동-점(floating poing) 숫자의 덧셈은 결합적이 아니고, 표현식을 결합하기 위한 방법의 선택은 반올림 오차에 큰 영향을 미칠 수 있습니다.
Definition
공식적으로, 집합(set) S 위에 이항 연산이 만약 결합 법칙(associative law)을 만족시키면, 결합적(associative)이라고 불립니다:
\(\quad\)(x ∗ y) ∗ z = x ∗ (y ∗ z) S에서 모든 x, y, z에 대해.
여기서, *는 연산의 기호를 대체하기 위해 사용되며, 이것은 임의의 기호, 심지어 곱셈(multiplication)에 대해서 처럼 기호의 부재(병치(juxtaposition))일 수 있습니다.
\(\quad\)(xy)z = x(yz) = xyz S에서 모든 x, y, z에 대해.
교환 법칙은 함수 표기법에서 역시 표현될 수 있습니다. 따라서:
\(\quad\)f(f(x, y), z) = f(x, f(y, z)).
Generalized associative law
만약 이항 연산이 결합적이면, 연산의 반복된 적용은 유효한 괄호 쌍이 표현에 삽입되는 방법과 관계없이 같은 결과를 생성합니다. 이것은 일반화된 교환 법칙(generalized associative law)이라고 불립니다. 예를 들어, 네 가지 인수의 곱은, 인수의 순서의 변경 없이, 다섯 가지 방법에서 쓰일 수 있습니다:
\(\quad\)\(((ab)c)d\)
\(\quad\)\((ab)(cd)\)
\(\quad\)\((a(bc))d\)
\(\quad\)\(a((bc)d)\)
\(\quad\)\(a(b(cd))\)
만약 곱 연산이 결합적이면, 일반화된 결합 법칙은 모든 이들 수식이 같은 결과를 산출할 것이라고 말합니다. 따라서 만약 생략된 괄호를 가진 수식이 다른 의미를 갖지 않으면 (아래를 참조하십시오), 괄호는 불필요한 것으로 여겨지고 "그" 곱은 다음으로 명백하게 쓰일 수 있습니다:
\(\quad\)\(abcd.\)
인수의 숫자가 증가함에 따라, 괄호를 삽입할 수 있는 가능한 방법의 숫자는 빠르게 증가하지만, 그들은 명확성에 대해 불필요하게 남아 있습니다.
이것이 작동하지 않는 예제는 논리적 쌍조건부(logical biconditional) \(\leftrightarrow\)입니다. 그것은 결합적이며, 따라서 A\(\leftrightarrow\)(B\(\leftrightarrow\)C)는 (A\(\leftrightarrow\)B)\(\leftrightarrow\)C와 동등하지만, A\(\leftrightarrow\)B\(\leftrightarrow\)C가 (A\(\leftrightarrow\)B and B\(\leftrightarrow\)C)를 가장 공통적으로 의미하며, 이것은 동등하지 않습니다.
Examples
결합적 연산의 일부 예제는 다음을 포함합니다:
i) 세 문자열 "hello", " ", "world"의 연쇄(concatenation)는 처음 두 문자열을 연쇄하고("hello "로 주어짐), 여기에 세 번째 문자열("world")을 덧 붙이거나, 또는 두번째와 세번째 문자열을 결합하고(" world"로 주어짐) 앞의 결과물에 첫 번째 문자열("hello") 연쇄할 수 있습니다. 두 가지 방법은 같은 결과를 생산합니다; 문자열 연쇄는 결합적입니다(그러나 교환적은 아닙니다).
ii) 산술(arithmetic)에서, 실수의 덧셈(addition) 및 곱셈(multiplication)은 결합적입니다; 즉,
\(\quad\)\(
\left.
\begin{matrix}
(x+y)+z=x+(y+z)=x+y+z
\\
(x\,y)z=x(y\,z)=x\,y\,z
\end{matrix}
\right\}
\forall x,y,z\in\mathbb{R}.
\)
결합성 때문에, 그룹화 괄호는 모호성 없이 생략될 수 있습니다.
iii) 자명한 연산 x ∗ y = x (즉, 그 결과는 두 번째 인수가 무엇인지 상관없이, 첫 번째 인수입니다)은 결합적이지만 교환적은 아닙니다.
마찬가지로, 자명한 연산 x ∘ y = y (즉, 그 결과는 첫 번째 인수가 무엇인지 상관없이, 두 번째 인수입니다)은 결합적이지만 교환적은 아닙니다.
i) 복소수(complex number)와 쿼터니언(quaternion)의 덧셈과 곱셈은 결합적입니다. 옥토니언(octonions)의 덧셈은 역시 결합적이지만, 옥토니언(octonions)의 곱셈은 비-결합적입니다.
ii) 최대 공통 약수(greatest common divisor)와 최소 공통 배수(least common multiple) 함수는 결합적으로 작동합니다.
\(\quad\)\(
\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\}\forall x,y,z\in\mathbb{Z}.
\)
iii) 집합(Sets)의 교집합(intersection) 또는 합집합(union)을 취하는 것:
\(\quad\)\(
\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\}\forall\mathrm{sets}\; A,B,C.
\)
iv) 만약 M 이 어떤 집합이고 S 가 M 에서 M 으로의 모든 함수의 집합을 나타내면, S 위에 함수 합성(functional composition)의 연산은 결합적입니다.
\(\quad\)\((f\circ g)\circ h=f\circ(g\circ h)=f\circ g\circ h\qquad\forall f,g,h\in S.\)
v) 조금 더 일반적으로, 네 집합 \(M\), \(N\), \(P\) 및 \(Q\)과 함께 세 함수 \(h: M \to N\), \(g: N \to P\), 및 \(f: P \to Q\)가 주어지면,
\(\quad\)\((f\circ g)\circ h=f\circ(g\circ h)=f\circ g\circ h\).
앞에서 처럼. 짧게 말해서, 맵핑의 합성은 항상 결합적입니다.
vi) 세 원소, A, B, C를 갖는 집합을 생각해 보십시오. 다음 연산은 결합적입니다:
| X | A | B | C |
| A | A | A | A |
| B | A | B | C |
| C | A | A | A |
따라서, 예를 들어, A(BC)=(AB)C = A. 이 연산은 교환적이 아닙니다.
vii) 행렬(matrices)은 선형 함수(linear function)를 나타내고, 행렬 곱셈(matrix multiplication)이 함수형 합성을 나타내기 때문에, 우리는 행렬 곱셈이 결합적이라는 결론을 쉽게 내릴 수 있습니다.
Propositional logic
Rule of replacement
표준 진리-함수형 명제 논리에서, 결합(association), 또는 결합성(associativity)은 두 가지 유효한(valid) 대체의 규칙(rules of replacement)입니다. 그 규칙은 논리적 증명(logical proofs)에서 논리적 표현(logical expressions)에서 괄호를 이동하는 것을 허용합니다. 그 규칙(논리적 연결(logical connectives) 표기법을 사용함)은 다음입니다:
\(\quad\)\((P \vee (Q \vee R)) \Leftrightarrow ((P \vee Q) \vee R)\)
및
\(\quad\)\((P \wedge (Q \wedge R)) \Leftrightarrow ((P \wedge Q) \wedge R),\)
여기서 " \(\Leftrightarrow\)"는 "증명(proof)에서 대체될 수 있음"을 나타내는 메타-논리(metalogic)적 기호(symbol)입니다.
Truth functional connectives
결합성(Associativity)은 진리-함수형 명제 논리(propositional logic)의 일부 논리 연결자(logical connective)의 속성입니다. 다음의 논리적 동치(logical equivalence)는 결합성이 특정 연결자의 속성임을 시연합니다. 다음은 진리-함수형 동의어-반복(tautologies)입니다.
논리합의 교환성:
\(\quad\)\(((P \vee Q) \vee R) \leftrightarrow (P \vee (Q \vee R))\)
\(\quad\)\((P \vee (Q \vee R)) \leftrightarrow ((P \vee Q) \vee R)\)
논리곱의 교환성:
\(\quad\)\(((P \wedge Q) \wedge R) \leftrightarrow (P \wedge (Q \wedge R))\)
\(\quad\)\((P \wedge (Q \wedge R)) \leftrightarrow ((P \wedge Q) \wedge R)\)
동치의 교환성:
\(\quad\)\(((P \leftrightarrow Q) \leftrightarrow R) \leftrightarrow (P \leftrightarrow (Q \leftrightarrow R))\)
\(\quad\)\((P \leftrightarrow (Q \leftrightarrow R)) \leftrightarrow ((P \leftrightarrow Q) \leftrightarrow R)\)
Non-associative operation
결합 법칙을 만족시키지 않는 집합 S에서 이항 연산 \(*\)은 비-결합적(non-associative)이라고 불립니다. 기호적으로,
\(\quad\)\((x*y)*z\ne x*(y*z)\qquad\mbox{for some }x,y,z\in S.\)
그런한 연산에 대해, 평가의 순서가 중요합니다. 예를 들어:
\(\quad\)\(
(5-3)-2 \, \ne \, 5-(3-2)
\)
ii) 나눗셈(Division)
\(\quad\)\(
(4/2)/2 \, \ne \, 4/(2/2)
\)
iii) 지수(Exponentiation)
\(\quad\)\(
2^{(1^2)} \, \ne \, (2^1)^2
\)
역시 무한 합은 일반적으로 결합적이 아님을 주목하십시오. 예를 들어:
\(\quad\)\(
(1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+(1+-1)+\dots \, = \, 0
\)
반면에,
\(\quad\)\(
1+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+(-1+1)+\dots \, = \, 1
\)
비-결합적 구조의 연구는 고전적인 대수의 주류와는 다소 다른 이유로 발생합니다. 매우 크게 성장한 비-결합적 대수(non-associative algebra) 안에서 한 영역은 리 대수(Lie algebra)의 그것입니다. 거기에서 결합 법칙은 야코비 항등(Jacobi identity)에 의해 대체됩니다. 리 대수는 무한소 변환(infinitesimal transformation)의 필수 본질을 추상화하고, 수학에서 유비쿼터스(ubuquitous) 되었습니다.
심도 있게 연구되어 온 비-결합적 구조의 다른 특정 유형이 있습니다; 이것들은 조합론적 수학(combinatorial mathematics)과 같은 특정 응용 또는 영역에서 오는 경향입니다. 다른 예제는 준-그룹(Quasigroup), 준-필드(Quasifield), 비-결합적 링(Non-associative ring), 비-결합적 대수(Non-associative algebra) 및 교환 비-결합 마그마(Commutative non-associative magmas)가 있습니다.
Nonassociativity of floating point calculation
수학에서, 실수의 덧셈 및 곱셈은 결합적입니다. 대조적으로, 컴퓨터 과학에서, 부동-점 숫자의 덧셈 및 곱셈은 결합적이 아닌데, 왜냐하면 크기가 다른 값을 함께 결합할 때 반올림 오차가 발생하기 때문입니다.
이것을 설명하기 위해, 4-비트 가수(유효 숫자)를 갖는 부동-점 표현을 생각해 보십시오:
(1.0002×20 + 1.0002×20) + 1.0002×24 = 1.0002×21 + 1.0002×24 = 1.0012×24
1.0002×20 + (1.0002×20 + 1.0002×24) = 1.0002×20 + 1.0002×24 = 1.0002×24
심지어 대부분의 컴퓨터가 24 또는 53 비트의 가수로 계산될지라도, 이것이 반올림 오차의 중요한 원천이고, 카한 합 알고리듬(Kahan summation algorithm)과 같은 접근법은 오류를 최소화하는 방법입니다. 그것은 병렬 컴퓨팅에서 특히 문제가 될 수 있습니다.
Notation for non-associative operations
일반적으로, 괄호는 만약 비-결합적 연산이 표현에서 한 번보다 많이 나타나면 (만약 표기법이 또 다른 방법에서, \(\dfrac{2}{3/4}\)처럼, 순서를 지정하지 않으면), 평가의 순서(order of evaluation)를 나타내기 위해서 반드시 사용되어야 합니다. 어쨌든, 수학자들은 여러 공통 비-결합적 연산에 대해 특정 평가의 순서에 동의합니다. 이것은 단순히 괄호를 피하기 위한 표기법의 규칙입니다.
왼쪽-결합적 연산은 전통적으로 왼쪽에서 오른쪽으로로 평가되는 비-결합적 연산입니다. 즉,
\(\quad\)\(
\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
\)
반면에 오른쪽-결합적 연산은 전통적으로 오른쪽에서 왼쪽으로 평가합니다:
\(\quad\)\(
\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
\)
왼쪽-결합적 및 오른쪽-결합적 둘 다가 발생합니다. 왼쪽-결합 연산은 다음을 포함합니다:
i) 실수의 뺄셈과 나눗셈:
\(\quad\)\(x-y-z=(x-y)-z\)
\(\quad\)\(x/y/z=(x/y)/z\)
ii) 함수 적용:
\(\quad\)\((f \, x \, y) = ((f \, x) \, y)\)
이 표기법은 커링(curring) 동형-사상(isomorphism)에 의해 동기-부여될 수 있습니다.
오른쪽-결합적 연산은 다음을 포함합니다:
i) 위첨자 표기법에서 실수의 지수(exponentiation):
\(\quad\)\(x^{y^z}=x^{(y^z)}\)
지수는 괄호 또는 오른쪽 결합적으로 공통적으로 사용되는데 왜냐하면 번복된 왼쪽-결합적 지수 연산이 덜 사용되기 때문입니다. 반복된 거듭제곱은 대개 곱셈으로 다시-표현될 것입니다:
\(\quad\)\((x^y)^z=x^{(yz)}\)
올바르게 형식회된, 위첨자는 본질적으로 일련의 괄호로 작동합니다; 예를 들어, 표현 \(2^{x+3}\)에서, 명시적으로 괄호가 감싼 식 \(2^{(x+3)}\)이 아님에도 불구하고 지수 계산 전에(before) 덧셈을 계산합니다. 따라서 \(x^{y^z}\)와 같은 표현이 주어지면, 밑 \(x\)의 전체 지수 \(y^z\)를 먼저 평가됩니다. 어쨌든, 일부 문맥에서, 특히 손으로 쓸 때, \({x^y}^z=(x^y)^z\), \(x^{yz}=x^{(yz)}\) 및 \(x^{y^z}=x^{(y^z)}\) 사이의 차이는 구별하기 어려울 수 있습니다. 그러한 경우에서, 오른쪽-결합성은 보통 의미됩니다.
iii) 함수 정의(function definition)
\(\quad\)\(\mathbb{Z} \to \mathbb{Z} \to \mathbb{Z} = \mathbb{Z} \to (\mathbb{Z} \to \mathbb{Z})\)
\(\quad\)\(x \mapsto y \mapsto x - y = x \mapsto (y \mapsto x - y)\)
이들 연산에 오른쪽-결합적 표기법을 사용하는 것은 커리-하워드 대응(Curry-Howard correspondence)와 커링(currying) 동형-사상(isomorphism)에 의해 동기-부여될 수 있습니다.
전통적으로 평가 순서가 정의되지 않은 비-결합적 연산은 다음을 포함합니다.
i) 중위 표기법에서 실수의 지수화:
\(\quad\)\((x^\wedge y)^\wedge z\ne x^\wedge(y^\wedge z)\)
ii) 커누스의 윗-화살표 연산자(Knuth's up-arrow operators):
\(\quad\)\( a \uparrow \uparrow (b \uparrow \uparrow c) \ne (a \uparrow \uparrow b) \uparrow \uparrow c\)
\(\quad\)\( a \uparrow \uparrow \uparrow (b \uparrow \uparrow \uparrow c) \ne (a \uparrow \uparrow \uparrow b) \uparrow \uparrow \uparrow c\)
iii) 세 벡터의 교차 곱(cross product)을 취하는 것:
\(\quad\)\(\vec a \times (\vec b \times \vec c) \neq (\vec a \times \vec b ) \times \vec c \qquad \exists \vec a,\vec b,\vec c \in \mathbb{R}^3\)
iv) 실수의 쌍 평균(average)을 취하는 것:
\(\quad\)\(\displaystyle {(x+y)/2+z\over2}\ne{x+(y+z)/2\over2} \qquad \forall x,y,z\in\mathbb{R} \text{ with }x\ne z.\)
v) 집합 \((A\backslash B)\backslash C\)의 상대적인 여집합(relative complement)을 취하는 것은 \(A\backslash (B\backslash C)\)와 같지 않습니다. (논리에서 물질 비-복제(material nonimplication)와 비교하십시오.)
Antiassociativity
S 위에 이항 연산이 역-결합적 연산(antiassociative operation)인 것과 다음인 것은 필요충분 조건입니다:
\(\quad\)∀x,y,z∈S:(x∘y)∘z≠x∘(y∘z)
(S,∘)를 대수적 구조로 놓습니다.
그런-다음 (S,∘)는 역-결합적 구조(antiassociative structure)인 것과 ∘이 역-결합적 연산인 것은 필요충분 조건입니다.
즉, 다음과 필요충분 조건입니다:
\(\quad\)∀x,y,z∈S:(x∘y)∘z≠x∘(y∘z)
