결합법칙

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 일반화된 결합 법칙
4. 예시
5. 명제 논리
6. 비결합적 연산
- 6.1. 부동 소수점 연산의 비결합성
- 6.2. 비결합적 연산의 표기법
7. 프로그래밍 언어
8. 역사
참조

1. 개요

결합법칙은 집합 S에 정의된 이항 연산 *에 대해 (x * y) * z = x * (y * z)가 성립하는 것을 의미하며, 연산 순서에 관계없이 결과가 같음을 나타낸다. 덧셈과 곱셈, 행렬 곱셈, 집합의 교집합과 합집합, 논리 연산 등 다양한 수학적 연산에서 결합법칙이 성립한다. 일반화된 결합법칙은 괄호의 위치에 관계없이 연산의 결과가 같음을 의미하며, 프로그래밍 언어에서는 연산자 결합성이 연산 순서를 결정하는 중요한 요소로 작용한다. 결합법칙을 만족하지 않는 연산은 비결합적이며, 뺄셈, 나눗셈, 거듭제곱, 벡터 외적 등이 이에 해당한다. 윌리엄 로완 해밀턴은 옥토니언의 비결합 대수를 연구하면서 처음으로 "결합법칙"이라는 용어를 사용했다.

더 읽어볼만한 페이지

초등대수학 - 이차 방정식
이차 방정식은 최고차항이 2차인 대수 방정식으로, $ax^2 + bx + c = 0$ 형태로 표현되며 근의 공식으로 해를 구하고 판별식에 따라 실근 또는 허근을 가지며 여러 분야에 응용된다.
초등대수학 - 방정식
방정식은 수학에서 두 식이 등호로 연결된 형태로, 미지수의 값을 구하는 것을 목표로 하며, 다양한 종류로 분류되어 여러 수학 및 과학 분야에서 활용된다.
이항연산 - 뺄셈
뺄셈은 두 수의 관계를 나타내는 연산으로, 덧셈의 역연산이며, 피감수에서 감수를 빼는 연산으로 차를 구하고, 반교환법칙과 결합 법칙은 성립하지 않으며, 다양한 계산 방법과 함께 여러 분야에서 활용된다.
이항연산 - 나눗셈
나눗셈은 하나의 수를 다른 수로 나누어 몫과 나머지를 구하는 기본적인 산술 연산이다.
추상대수학 - 직교
직교는 수학에서 수직으로 만나는 기하학적 개념에서 시작하여 내적 공간의 벡터 내적이 0이거나 가군과 쌍대 가군의 원소가 특정 조건을 만족할 때 성립하며, 직교 집합, 직교 기저, 직교 여공간 등의 구조를 정의하고 푸리에 급수, 상대성이론, 양자역학 등 다양한 분야에서 활용될 뿐 아니라 컴퓨터 과학, 통계학, 법률, 예술 등에서도 독립적인 요소나 개념을 나타내는 데 사용된다.
추상대수학 - 코시 열
코시 열은 무한수열에서 항들이 뒤로 갈수록 서로 가까워지는 수열로, 수렴열은 항상 코시 열이지만 그 역은 성립하지 않을 수 있으며, 실수의 완비성 정의 및 무한급수 수렴성 판정에 중요한 역할을 하는 개념이다.

결합법칙
개요
정의	집합 S의 모든 원소 x, y, z에 대해 (x * y) * z = x * (y * z)를 만족하는 연산 *
관련 개념	교환 법칙, 분배 법칙, 항등원, 멱등원
대수 구조
반군	결합 법칙을 만족하는 닫힌 이항 연산을 갖는 집합
모노이드	항등원을 갖는 반군
군	역원을 갖는 모노이드
환	덧셈에 대해 아벨 군을 이루고, 곱셈에 대해 반군을 이루며, 분배 법칙을 만족하는 대수적 구조
체	0이 아닌 모든 원소가 곱셈에 대해 역원을 갖는 환
명제 논리
논리곱	(P ∧ (Q ∧ R)) ↔ ((P ∧ Q) ∧ R)
논리합	(P ∨ (Q ∨ R)) ↔ ((P ∨ Q) ∨ R)
예시
일반적인 예	덧셈: (2 + 3) + 4 = 2 + (3 + 4) = 9 곱셈: (2 × 3) × 4 = 2 × (3 × 4) = 24
비결합적인 연산	뺄셈: (5 - 3) - 1 ≠ 5 - (3 - 1) 나눗셈: (8 ÷ 4) ÷ 2 ≠ 8 ÷ (4 ÷ 2) 지수: (2^3)^4 ≠ 2^(3^4) 함수 합성: (f ∘ g) ∘ h ≠ f ∘ (g ∘ h) 벡터곱: (i × j) × j ≠ i × (j × j)
같이 보기
관련 문서	결합성 (언어학)

2. 정의

집합 ''S''에 대해 정의된 이항 연산 $*$ 이 결합법칙을 만족하면 다음 식이 성립한다.

: $(x*y)*z = x*(y*z)\qquad\forall x,y,z \in S$

이때 좌변과 우변의 값은 연산을 수행하는 순서에 영향을 받지 않는다. 이 법칙은 $*$ 연산이 세 번 이상 나타날 때에도 확장해서 적용할 수 있으며, 따라서 $*$ 가 결합법칙을 만족하면 연산 순서를 따로 지정하지 않아도 모호함 없이 수식의 값이 결정된다. 따라서 보통 위의 수식을 괄호 없이 다음과 같이 쓴다.

: $x*y*z$

결합 법칙은 함수 표기법으로도 표현할 수 있는데, $(f \circ (g \circ h))(x) = ((f \circ g) \circ h)(x)$ 와 같이 표현할 수 있다.

3. 일반화된 결합 법칙

이항 연산이 결합 법칙을 만족하면, 연산을 반복적으로 적용할 때 괄호를 어떻게 묶어도 결과가 같다.^[2] 이를 '''일반화된 결합 법칙'''이라고 한다.

괄호를 묶는 가능한 방법의 수는 카탈랑 수로 주어지며, ''n+1''개의 값에 대한 ''n''개의 연산에 해당한다. 예를 들어, 4개의 요소에 대한 3개의 연산의 곱은 (인수의 순열을 무시하고) 다음 5가지 방법으로 쓸 수 있다.

$((ab)c)d$
$(a(bc))d$
$a((bc)d$
$(a(b(cd))$
$(ab)(cd)$

곱 연산이 결합적이라면, 일반화된 결합 법칙은 이러한 모든 표현식이 동일한 결과를 생성한다는 것을 의미한다. 따라서 괄호가 생략된 표현식이 이미 다른 의미를 가지지 않는 한, 괄호는 불필요한 것으로 간주될 수 있으며, 곱은 다음과 같이 모호하지 않게 쓸 수 있다.

:

abcd

요소의 수가 증가함에 따라 괄호를 삽입할 수 있는 가능한 방법의 수는 빠르게 증가하지만, 이러한 방법은 모호성을 제거하는 데 불필요하다.

이것이 작동하지 않는 예는 논리적 쌍조건문이다. 논리적 쌍조건문은 결합적이다. 따라서,

A \leftrightarrow (B \leftrightarrow C)

는

(A \leftrightarrow B) \leftrightarrow C

와 동일하지만,

A \leftrightarrow B \leftrightarrow C

는 가장 일반적으로

(A \leftrightarrow B)

및

(B \leftrightarrow C)

를 의미하며, 이는 동일하지 않다.

4. 예시

자연수, 정수, 유리수, 실수, 복소수, 사원수의 덧셈과 곱셈은 결합법칙이 성립한다. 팔원수의 덧셈도 결합법칙이 성립하지만, 곱셈은 성립하지 않는다.^[3]
최대공약수와 최소공배수 함수는 결합법칙을 만족한다.^[3]
행렬 곱셈은 결합법칙을 만족한다.^[3]
선형 변환은 행렬의 곱셈으로 표현되므로, 선형 변환 역시 결합법칙을 만족한다.^[3]
집합의 교집합과 합집합 연산은 각각 결합법칙이 성립한다.^[3]
진릿값의 논리곱, 논리합, 배타적 논리합 등 논리 연산은 각각 결합법칙이 성립한다.
각 함수의 정의역과 치역이 올바르게 정의된 합성함수도 결합법칙을 만족한다. 즉, $h: M \to N, \ g: N \to P, \ f: P \to Q$ 인 세 함수가 있을 때,

:

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

이다.

5. 명제 논리

표준 진리 함수 명제 논리에서, 결합^[4]^[5] 또는 결합성^[6]은 두 개의 타당한 치환 규칙이다. 이 규칙은 논리식의 괄호를 논리 증명에서 이동할 수 있게 한다. 이 규칙은 (논리 연산자 표기법을 사용하여) 다음과 같다.

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

여기서 "

\Leftrightarrow

"는 "증명에서 다음으로 대체될 수 있다"를 나타내는 메타논리적 기호이다.

결합법칙은 진리 함수 명제 논리의 일부 논리 연결사의 속성이다. 다음의 논리적 동치는 결합법칙이 특정 연결사의 속성임을 보여준다.

;선언의 결합법칙

:

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

;접합의 결합법칙

:

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

;동치의 결합법칙

:

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

공통 부정은 결합법칙이 아닌 진리 함수 연결사의 한 예이다.

6. 비결합적 연산

집합 ''S''에 대한 이항 연산 *가 결합법칙을 만족하지 않으면 비결합적이라고 한다. 즉, 어떤 ''x'', ''y'', ''z'' ∈ ''S''에 대해 (''x'' * ''y'') * ''z'' ≠ ''x'' * (''y'' * ''z'')가 성립한다.

이러한 연산에서는 연산 순서가 ''중요''하다. 비결합적 연산의 예시는 다음과 같다.

뺄셈: (5 - 3) - 2 ≠ 5 - (3 - 2)
나눗셈: (4 / 2) / 2 ≠ 4 / (2 / 2)
거듭제곱: 2^(1²) ≠ (2¹)²
벡터 외적:
'''i''' × ('''i''' × '''j''') = '''i''' × '''k''' = -'''j'''
('''i''' × '''i''') × '''j''' = '''0''' × '''j''' = '''0'''

덧셈은 유한한 합에 대해서는 결합적이지만, 무한한 합(급수)에서는 일반적으로 결합적이지 않다. 예를 들어, (1 + -1) + (1 + -1) + (1 + -1) + ... = 0 이지만, 1 + (-1 + 1) + (-1 + 1) + (-1 + 1) + ... = 1 이다.

팔원수와 리 대수는 비결합 대수의 대표적인 예시이다. 리 대수는 결합 법칙 대신 야코비 항등식을 만족시키며, 무한소 변환의 대수적 성질을 추상화한다.

이 외에도 준군, 준체, 비결합 링, 가환 비결합 마그마 등이 비결합적 연산의 예시이다.

6. 1. 부동 소수점 연산의 비결합성

수학에서 실수의 덧셈과 곱셈은 결합법칙을 따른다. 반면에 컴퓨터 과학에서 부동 소수점 숫자의 덧셈과 곱셈은 결합 법칙을 ''따르지 않는데'', 크기가 다른 값들을 다른 순서로 더할 때 다른 반올림 오차가 발생할 수 있기 때문이다.^[7]

이를 설명하기 위해 4비트 가수를 갖는 부동 소수점 표현을 고려해 보자.

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

대부분의 컴퓨터는 24 또는 53비트의 가수로 계산하지만,^[8] 이는 여전히 중요한 반올림 오차의 원인이며, 카한 덧셈 알고리즘과 같은 접근 방식은 오차를 최소화하는 방법이다. 이는 병렬 컴퓨팅에서 특히 문제가 될 수 있다.^[9]^[10]

6. 2. 비결합적 연산의 표기법

일반적으로 비결합 연산이 한 표현식에 여러 번 나타나는 경우, 연산 순서를 명확히 하기 위해 괄호를 사용해야 한다. 하지만, 자주 쓰이는 몇몇 비결합 연산에 대해서는 괄호를 피하기 위해 특정 연산 순서를 따르는 것이 관례이다.
좌결합 연산은 왼쪽에서 오른쪽으로 평가하는 비결합 연산이다. 즉,

a * b * c = (a * b) * c
a * b * c * d = ((a * b) * c) * d

와 같이 계산한다.
우결합 연산은 오른쪽에서 왼쪽으로 평가하는 비결합 연산이다. 즉,

x * y * z = x * (y * z)
w * x * y * z = w * (x * (y * z))

와 같이 계산한다.

좌결합 연산의 예는 다음과 같다.

실수의 뺄셈과 나눗셈^[26]^[27]^[28]^[29]^[30]

:* x - y - z = (x - y) - z

:* x / y / z = (x / y) / z

함수의 적용

:* (f x y) = ((f x) y)

우결합 연산의 예는 다음과 같다.

실수의 거듭제곱 (윗 첨자 표기법의 경우)

:* x^{y^z} = x^{(y^z)}

함수 정의

:* ℤ → ℤ → ℤ = ℤ → (ℤ → ℤ)

:* x ↦ y ↦ x - y = x ↦ (y ↦ x - y)

연산 순서가 정의되지 않은 비결합 연산도 있다. 예를 들면 다음과 같다.

실수의 거듭제곱 연산 (중위 표기법)^[31]

:* (x^y)^z ≠ x^{(y^z)}

크누스의 윗화살표 연산자

:* a ↑↑ (b ↑↑ c) ≠ (a ↑↑ b) ↑↑ c

세 벡터의 외적

:* a × (b × c) ≠ (a × b) × c

실수 쌍의 평균

:* (x + y) / 2 + z / 2 ≠ x + (y + z) / 2 / 2

집합의 상대 여집합

:* (A \ B) \ C ≠ A \ (B \ C)

7. 프로그래밍 언어

대부분의 프로그래밍 언어에서 사칙 연산의 연산자 우선순위는 곱셈과 나눗셈이 덧셈과 뺄셈보다 높다. 예를 들어, `a * b + c`는 `(a * b) + c`를 의미하고, `a - b / c`는 `a - (b / c)`를 의미한다.^[26]^[27]^[28]^[29]^[30]

많은 연산자를 가진 C 언어와 같이 우선순위가 많은 언어도 있고, APL처럼 우선순위가 거의 없고 결합성만으로 연산 순서를 결정하는 언어도 있다.

대부분의 프로그래밍 언어에서 덧셈과 뺄셈, 곱셈과 나눗셈 사이에는 우선순위 차이가 없다. `a + b - c + d - e`와 같은 식은 왼쪽부터 순서대로 `(((a + b) - c) + d) - e`와 같이 계산된다. 이러한 결합을 좌 결합(left-associative)이라고 한다. 반대로 우 결합(right-associative)도 존재한다.

C 계열 언어에서 대입 연산자 `=`는 우 결합이다. `a = b = 1;`이라는 식은 `a = (b = 1)`로 해석되어, `b`에 1이 대입되고, 그 결과값 1이 다시 `a`에 대입된다.

거듭제곱 연산자(`**` 또는 `^`)의 결합성은 언어마다 다르다. 루비에서는 우 결합이지만, VB에서는 좌 결합이다.^[32]
비 결합(non-associative)은 좌 결합도 우 결합도 아닌 경우이다. 예를 들어, 비교 연산자 `<`는 `a < b < c`와 같이 사용될 때, `(a < b) < c` 또는 `a < (b < c)`로 해석되지 않는다. 파이썬과 같은 일부 언어에서는 `a < b < c`를 `a < b`이고 `b < c`인지를 검사하는 특별한 의미로 해석하기도 한다.

8. 역사

윌리엄 로완 해밀턴은 1844년경 존 T. 그레이브스에게서 배운 옥토니언의 비결합 대수를 고찰하면서 "결합법칙"이라는 용어를 처음 사용한 것으로 보인다.^[17]^[18]

참조

_[1] 서적 Algebra Springer Science+Business Media
_[2] 서적 Modern Algebra: an Introduction http://www.wiley.com[...] Wiley
_[3] 웹사이트 Matrix product associativity http://www.khanacade[...] Khan Academy 2016-06-05
_[4] 서적 Critical Thinking McGraw-Hill Education 2017
_[5] 서적 Introduction to Logic Pearson Education 2014
_[6] 서적 A Concise Introduction to Logic Cengage Learning 2016
_[7] 문서 The Art of Computer Programming
_[8] 서적 IEEE Standard for Floating-Point Arithmetic 2008-08-29
_[9] 간행물 Effects of Floating-Point non-Associativity on Numerical Computations on Massively Multithreaded Systems http://cass-mt.pnnl.[...] 2014-04-08
_[10] 학술지 What Every Computer Scientist Should Know About Floating-Point Arithmetic http://perso.ens-lyo[...] 2016-01-20
_[11] 웹사이트 Order of arithmetic operations https://math.berkele[...]
_[12] 웹사이트 The Order of Operations http://eduplace.com/[...] Education Place
_[13] Youtube The Order of Operations https://www.khanacad[...] Khan Academy
_[14] 웹사이트 Using Order of Operations and Exploring Properties http://www.doe.virgi[...] Virginia Department of Education 2022-07-16
_[15] 문서 Taschenbuch der Mathematik
_[16] 웹사이트 Exponentiation Associativity and Standard Math Notation https://codeplea.com[...] Codeplea 2016-08-23
_[17] 학술지 On quaternions or a new system of imaginaries in algebra http://www.maths.tcd[...] Trinity College Dublin
_[18] 학술지 The Octonions https://www.ams.org/[...]
_[19] 서적 Algebra Springer Science+Business Media
_[20] 서적 Modern Algebra: an Introduction http://www.wiley.com[...] Wiley
_[21] 웹사이트 Matrix product associativity http://www.khanacade[...] Khan Academy 2016-06-05
_[22] 문서 Moore and Parker 2016-10
_[23] 문서 Copi and Cohen 2016-10
_[24] 문서 Hurley 2016-10
_[25] 웹사이트 https://math.stackex[...]
_[26] 웹사이트 Order of arithmetic operations https://math.berkele[...]
_[27] 웹사이트 The Order of Operations http://eduplace.com/[...] Education Place
_[28] Youtube The Order of Operations https://www.khanacad[...] Khan Academy
_[29] 웹사이트 Using Order of Operations and Exploring Properties http://www.doe.virgi[...] Virginia Department of Education
_[30] 문서 Taschenbuch der Mathematik
_[31] 웹사이트 Exponentiation Associativity and Standard Math Notation https://codeplea.com[...] Codeplea 2016-08-23
_[32] 웹사이트 http://msdn.microsof[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com