결합법칙 (Associative Property)

결합법칙(associative law)은 이항 연산 ∘가 모든 a, b, c에 대해 (a ∘ b) ∘ c = a ∘ (b ∘ c)를 만족하는 성질입니다. 세 개 이상을 연산할 때 앞의 두 개를 먼저 묶든 뒤의 두 개를 먼저 묶든 결과가 같으므로 괄호를 생략하고 a ∘ b ∘ c로 쓸 수 있습니다. 보통의 덧셈과 곱셈은 결합법칙을 만족합니다.

자세히 알아보기

결합법칙은 교환법칙(a ∘ b = b ∘ a)과 다릅니다. 행렬 곱셈과 함수 합성은 결합법칙을 만족하지만 교환법칙은 만족하지 않습니다. 반대로 뺄셈 (8 − 4) − 2 = 2 ≠ 8 − (4 − 2) = 6, 나눗셈, 거듭제곱 (2³)² ≠ 2³²은 결합법칙을 만족하지 않습니다.

결합법칙은 군·모노이드·환·체 같은 대수 구조의 기본 공리입니다. 실용적으로는 계산 순서를 자유롭게 바꿀 수 있게 해 주므로, 큰 계산을 여러 조각으로 나눠 병렬로 처리한 뒤 합치거나(병렬 리덕션), 거듭제곱을 '제곱 후 곱하기'로 빠르게 계산하는 근거가 됩니다.

주의할 예외가 컴퓨터의 부동소수점 덧셈입니다. 반올림 오차 때문에 (a + b) + c와 a + (b + c)가 미세하게 다를 수 있습니다.

블록체인·암호화폐에서는

• 타원곡선 점 덧셈: 곡선 위 점들의 덧셈이 결합법칙을 만족한다는 것은 자명하지 않은 정리이며, 이것이 성립하기 때문에 점들이 군을 이루고 개인 키 d에 대해 dG를 '두 배 후 더하기'로 빠르게 계산할 수 있습니다. 비트코인·이더리움의 모든 서명이 이 성질에 기대고 있습니다.
• 서명·키 집계: BLS 서명 집계와 MuSig2의 공개 키 합산은 결합·교환법칙 덕분에 순서와 묶는 방식에 상관없이 같은 결과를 냅니다.
• 결정론적 합의: 모든 노드가 같은 결과를 내야 하는 블록체인에서는 부동소수점처럼 결합법칙이 깨지는 연산이 위험합니다. EVM이 부동소수점을 지원하지 않고 정수(고정소수점) 산술만 쓰는 이유 중 하나입니다.
• 해시 연쇄는 비결합적: 머클 트리에서 H(H(a‖b)‖c)와 H(a‖H(b‖c))는 다르므로, 트리의 모양(묶는 순서)이 정확히 정의되어야 합니다.

쉽게 말하면

결합법칙은 '어디에 괄호를 쳐도 답이 같다'는 규칙입니다. 덧셈은 되고, 뺄셈은 안 됩니다.

예시

(2 + 3) + 4 = 2 + (3 + 4) = 9, (2 × 3) × 4 = 2 × (3 × 4) = 24. 그러나 (2 − 3) − 4 = −5, 2 − (3 − 4) = 3입니다.