치환 실례

1. 개요

치환 실례는 명제 논리, 1차 논리, 수학 등 다양한 분야에서 사용되는 개념으로, 특정 표현식 내의 변수를 다른 표현식으로 대체하는 것을 의미한다. 명제 논리에서는 명제 형식의 원자 명제에 다른 명제 형식을 대입하는 것을, 1차 논리에서는 변수를 항으로 대체하는 것을, 수학에서는 변수를 상수나 다른 표현식으로 치환하는 것을 의미한다. 치환은 항진 명제 형식과 모순 명제 형식의 성질을 보존하며, 1차 논리에서는 다양한 종류의 치환(기저, 선형, 평탄, 이름 변경 등)이 정의된다. 수학에서 치환은 등식의 치환 속성(라이프니츠의 법칙)과 관련되며, 함수 합성 및 대수 구조의 보존과도 연관된다.

2. 명제 논리

명제 논리에서 치환 실례는 어떤 명제 형식 φ가 주어졌을 때, φ에 포함된 명제 변수들을 각각 다른 명제 형식으로 일관되게 대체하여 새로운 명제 형식 ψ를 얻는 것을 말한다. 이렇게 얻어진 ψ를 φ의 치환 실례라고 한다.

일부 추론 시스템에서는 유도 과정 중 이전 단계에 나타난 명제의 치환 실례를 새로운 단계로 도입할 수 있다. 이는 공리적 시스템에서 새로운 행을 추가하거나, 추론 규칙을 사용하는 시스템에서 특정 변수를 도입하는 방법으로 사용될 수 있다.

2.1. 정의

명제 논리에서, 명제 형식 $P$의 치환 실례는 $P$에 포함된 각 명제 변수를 특정한 명제 형식으로 바꾸어 얻는 새로운 명제 형식을 말한다.

더 구체적으로, 원자 명제 $p\_1,\; \backslash dots,\; p\_n$과 명제 형식 $Q\_1,\; \backslash dots,\; Q\_n$이 주어졌을 때, $P$의 치환 실례 $P[Q\_1/p\_1,\; \backslash dots,\; Q\_n/p\_n]$는 $P$ 안의 모든 $p\_i$를 각각 $Q\_i$로 대체하여 얻는다. 이는 다음과 같이 재귀적으로 정의할 수 있다:

* 원자 명제 $p$에 대하여,
* $p$가 치환 대상 변수 $p\_i$ 중 하나가 아니라면 ($p\; \backslash ne\; p\_i$), $p[Q\_1/p\_1,\; \backslash dots,\; Q\_n/p\_n]\; =\; p$이다.
* $p$가 치환 대상 변수 $p\_i$와 같다면 ($p\; =\; p\_i$), $p[Q\_1/p\_1,\; \backslash dots,\; Q\_n/p\_n]\; =\; Q\_i$이다.
* 명제 형식 $P$에 대하여, $(\backslash lnot\; P)[Q\_1/p\_1,\; \backslash dots,\; Q\_n/p\_n]\; =\; \backslash lnot\; (P[Q\_1/p\_1,\; \backslash dots,\; Q\_n/p\_n])$이다.
* 명제 형식 $P,\; Q$에 대하여, $(P\; \backslash land\; Q)[Q\_1/p\_1,\; \backslash dots,\; Q\_n/p\_n]\; =\; P[Q\_1/p\_1,\; \backslash dots,\; Q\_n/p\_n]\; \backslash land\; Q[Q\_1/p\_1,\; \backslash dots,\; Q\_n/p\_n]$이다. (다른 논리 연산자에 대해서도 유사하게 정의된다.)

예를 들어, 명제 형식 ψ와 φ가 명제 논리의 잘 정의된 공식일 때, φ에 있는 명제 변수들을 다른 공식으로 바꾸어 ψ를 얻을 수 있다면, ψ는 φ의 치환 실례가 된다. 이때 같은 변수는 항상 같은 공식으로 바꾸어야 한다.

다음은 치환 실례의 예시이다:

:ψ: $(R\; \backslash to\; S)\; \backslash land\; (T\; \backslash to\; S)$
:는 다음 명제 형식의 치환 실례이다.
:φ: $P\; \backslash land\; Q$
:여기서 ψ는 φ의 변수 $P$를 $(R\; \backslash to\; S)$로, 변수 $Q$를 $(T\; \backslash to\; S)$로 각각 치환하여 얻을 수 있다.

또 다른 예시는 다음과 같다:

:ψ: $(A\; \backslash leftrightarrow\; A)\; \backslash leftrightarrow\; (A\; \backslash leftrightarrow\; A)$
:는 다음 명제 형식의 치환 실례이다.
:φ: $(A\; \backslash leftrightarrow\; A)$
:여기서 ψ는 φ의 변수 $A$를 $(A\; \backslash leftrightarrow\; A)$로 치환하여 얻을 수 있다.

2.2. 성질

만약 P가 항진 명제 형식이라면, 모든 치환 실례 P[Q₁/p₁,...,Q_n/p_n] 역시 항진 명제 형식이다. 마찬가지로, 명제 공식이 모든 평가 (또는 해석)에서 참일 때 항진명제라고 하는데, 어떤 명제 형식 Φ가 항진명제이면 그것의 치환 실례 Θ 역시 항진명제가 된다.

만약 P가 모순 명제 형식이라면, 모든 치환 실례 P[Q₁/p₁,...,Q_n/p_n] 역시 모순 명제 형식이다.

또한, 만약 모든 i=1,...,n에 대하여 Q_i와 R_i가 서로 동치라면, 치환된 결과인 P[Q₁/p₁,...,Q_n/p_n]와 P[R₁/p₁,...,R_n/p_n] 역시 서로 동치이다.

2.3. 예시

명제 $p\backslash lor\; q\backslash lor\; r$를 예로 들어보자. 이 명제에 포함된 원자 명제 $p,\; q,\; r$ 각각을 새로운 명제인 $p\backslash land\; q$, $\backslash lnot\; p\backslash land\; q$, $p\backslash land\backslash lnot\; q$로 치환하면 다음과 같은 명제를 얻는다.
: $(p\backslash land\; q)\backslash lor(\backslash lnot\; p\backslash land\; q)\backslash lor(p\backslash land\backslash lnot\; q)$
이렇게 얻어진 명제는 원래 명제 $p\backslash lor\; q\backslash lor\; r$의 치환 실례라고 한다.

명제 논리에서, ψ와 φ가 잘 정의된 공식일 때, ψ는 φ의 치환 실례이다. 이는 φ에 있는 명제 변수들을 특정 공식들로 일관되게 치환하여(즉, 같은 변수는 항상 같은 공식으로 치환하여) ψ를 얻을 수 있을 때 성립한다.

다른 예를 살펴보자.
* ψ: (R → S) & (T → S)
는 아래 명제 φ의 치환 실례이다.
* φ: P & Q

이는 φ의 명제 변수 P를 (R → S)로, Q를 (T → S)로 치환하면 ψ가 되기 때문이다.

또 다른 예시는 다음과 같다.
* ψ: (A ↔ A) ↔ (A ↔ A)
는 아래 명제 φ의 치환 실례이다.
* φ: (A ↔ A)

이 경우, φ에 있는 모든 변수 A를 (A ↔ A)라는 공식으로 치환하면 ψ를 얻을 수 있다.

일부 추론 시스템에서는 어떤 명제의 치환 실례를 논증 과정에서 새로운 단계로 도입하기도 한다.

3. 1차 논리

일차 논리에서 치환(substitution)은 변수를 항으로 대응시키는 매핑 σ: V → T를 의미한다. 일반적으로 치환은 { x₁ ↦ t₁, …, x_k ↦ t_k } 형태로 표기한다. 이는 각 변수 x_i를 해당 항 t_i로 매핑하고 (여기서 i=1,…,k), 명시되지 않은 다른 모든 변수는 자기 자신으로 매핑함을 나타낸다. 이때 각 x_i는 서로 다른 변수여야 한다.

항 t에 치환을 적용하는 것은 후위 표기법으로 t { x₁ ↦ t₁, ..., x_k ↦ t_k }와 같이 쓰며, 이는 항 t 안에 있는 각 변수 x_i를 동시에 해당 항 t_i로 바꾸는 것을 의미한다. 치환 σ를 항 t에 적용한 결과인 tσ는 항 t의 인스턴스(instance)라고 부른다.

예를 들어, 항 f(z, a, g(x), y)에 치환 { x ↦ z, z ↦ h(a,y) }를 적용하면 다음과 같은 결과가 나온다.

3.1. 정의

1차 논리에서, 항 $t$의, 변수 $x\_1,\backslash dots,x\_n$ 및 항 $u\_1,\backslash dots,u\_n$에 대한 치환 실례 $t[u\_1/x\_1,\backslash dots,u\_n/x\_n]$는 $t$ 속의 각 $x\_i$에 $u\_i$를 넣어 얻는 항이다. 즉, 다음과 같이 재귀적으로 정의된다.
* 연산 $\backslash mathsf\; f$ 및 항 $t\_1,\backslash dots,t\_\{m\_\backslash mathsf\; f\}$에 대하여, (여기서 $m\_\backslash mathsf\; f$는 항수)
*: $\backslash mathsf\; f(t\_1,\backslash dots,t\_\{m\_\backslash mathsf\; f\})[u\_1/x\_1,\backslash dots,u\_n/x\_n]=\backslash mathsf\; f(t\_1[u\_1/x\_1,\backslash dots,u\_n/x\_n],\backslash dots,t\_\{m\_\backslash mathsf\; f\}[u\_1/x\_1,\backslash dots,u\_n/x\_n])$

논리식 $\backslash phi$의, 변수 $x\_1,\backslash dots,x\_n$ 및 항 $t\_1,\backslash dots,t\_n$에 대한 치환 실례 $\backslash phi[t\_1/x\_1,\backslash dots,t\_n/x\_n]$는 $\backslash phi$ 속의 각 자유 변수 $x\_i$에 $t\_i$를 넣어 얻는 논리식이다. 즉, 다음과 같이 재귀적으로 정의된다.
* 항 $t,u$에 대하여, $(t=u)[t\_1/x\_1,\backslash dots,t\_n/x\_n]=(t[t\_1/x\_1,\backslash dots,t\_n/x\_n]=u[t\_1/x\_1,\backslash dots,t\_n/x\_n])$
* 관계 $\backslash mathsf\; R$ 및 항 $u\_1,\backslash dots,u\_\{n\_\backslash mathsf\; R\}$에 대하여, (여기서 $n\_\backslash mathsf\; R$는 항수)
*: $\backslash mathsf\; R(u\_1,\backslash dots,u\_\{n\_\backslash mathsf\; R\})[t\_1/x\_1,\backslash dots,t\_n/x\_n]=\backslash mathsf\; R(u\_1[t\_1/x\_1,\backslash dots,t\_n/x\_n],\backslash dots,u\_\{n\_\backslash mathsf\; R\}[t\_1/x\_1,\backslash dots,t\_n/x\_n])$
* 논리식 $\backslash phi$에 대하여, $(\backslash lnot\backslash phi)[t\_1/x\_1,\backslash dots,t\_n/x\_n]=\backslash lnot(\backslash phi[t\_1/x\_1,\backslash dots,t\_n/x\_n])$
* 논리식 $\backslash phi,\backslash psi$에 대하여, $(\backslash phi\backslash land\backslash psi)[t\_1/x\_1,\backslash dots,t\_n/x\_n]=\backslash phi[t\_1/x\_1,\backslash dots,t\_n/x\_n]\backslash land\backslash psi[t\_1/x\_1,\backslash dots,t\_n/x\_n]$
* 논리식 $\backslash phi$ 및 변수 $x$에 대하여,
$x\backslash ne\; x\_i$라면, $(\backslash forall\; x\backslash phi)[t\_1/x\_1,\backslash dots,t\_n/x\_n]=\backslash forall\; x(\backslash phi[t\_1/x\_1,\backslash dots,t\_n/x\_n])$
$x=x\_i$라면, $(\backslash forall\; x\backslash phi)[t\_1/x\_1,\backslash dots,t\_n/x\_n]=\backslash forall\; x(\backslash phi[t\_1/x\_1,\backslash dots,t\_\{i-1\}/x\_\{i-1\},t\_\{i+1\}/x\_\{i+1\},\backslash dots,t\_n/x\_n])$

논리식 $\backslash phi$ 위의, 변수 $x$의 치환 가능 항(substitutable/free term for $x$^영어)은 다음 조건을 만족시키는 항 $t$이다.
* 만약 $t$가 변수 $y$를 포함하며, $\backslash phi$가 논리식 $\backslash forall\; y\backslash psi$를 포함한다면, $x$는 $\backslash psi$의 자유 변수가 아니다.
즉, 다음과 같이 재귀적으로 정의된다.
* 항 $u,v$에 대하여, $t$는 $u=v$ 위의 $x$의 치환 가능 항이다.
* 관계 $\backslash mathsf\; R$ 및 항 $t\_1,\backslash dots,t\_\{n\_\backslash mathsf\; R\}$에 대하여, $t$는 $\backslash mathsf\; R(t\_1,\backslash dots,t\_\{n\_\backslash mathsf\; R\})$ 위의 $x$의 치환 가능 항이다.
* $t$가 $\backslash phi$ 위의 $x$의 치환 가능 항이라면, $t$는 $\backslash lnot\backslash phi$ 위의 $x$의 치환 가능 항이다.
* $t$가 $\backslash phi,\backslash psi$ 위의 $x$의 치환 가능 항이라면, $t$는 $\backslash phi\backslash land\backslash psi$ 위의 $x$의 치환 가능 항이다.
* $t$가 변수 $y$를 포함하지 않거나, $x$가 $\backslash phi$의 자유 변수가 아니라면, $t$는 $\backslash forall\; y\backslash phi$ 위의 $x$의 치환 가능 항이다.

3.2. 기저 치환, 선형 치환, 평탄 치환, 이름 변경 치환

치환 σ의 영역(domain) dom(σ)은 일반적으로 실제로 대체된 변수의 집합, 즉 dom(σ) = { x ∈ V | xσ ≠ x }으로 정의된다. 특정 속성을 갖는 치환들은 다음과 같이 분류할 수 있다.

* 기저 치환(ground substitution): 치환의 영역에 있는 모든 변수를 기저 항(변수가 없는 항)으로 매핑하는 치환이다. 예를 들어, `{ x ↦ 2, y ↦ 3+4 }`는 기저 치환이다. 기저 치환 σ를 항 t에 적용한 결과인 tσ는, 만약 t의 모든 변수가 σ의 영역에 포함된다면(vars(t) ⊆ dom(σ)), 기저 항이 된다.

* 선형 치환(linear substitution): 치환 σ를 일부 (따라서 모든) 선형 항 t에 적용한 결과 항 tσ가 선형 항(각 변수가 최대 한 번 나타나는 항)이 되는 경우, 해당 치환 σ를 선형 치환이라고 한다. 이는 치환 σ의 영역 변수만 포함하는 항, 즉 vars(t) = dom(σ)인 항 t에 대해 tσ가 선형일 때 성립한다. 예를 들어, `{ x ↦ x<sub>1</sub>, y ↦ y<sub>2</sub>+4 }`는 선형 치환이다 (비기저, 비평탄). 반면, `{ x ↦ y<sub>2</sub>, y ↦ y<sub>2</sub>+4 }`는 결과 항 `y<sub>2</sub>`와 `y<sub>2</sub>+4`가 변수 `y<sub>2</sub>`를 공유하므로 선형 치환이 아니다.

* 평탄 치환(flat substitution): 치환 σ가 모든 변수 x에 대해 xσ를 변수로 매핑하는 경우, 즉 변수를 다른 변수로만 대체하는 치환이다. 예를 들어, `{ x ↦ y<sub>2</sub>, y ↦ y<sub>2</sub> }`는 평탄 치환이다 (비선형). `{ x ↦ x<sub>1</sub>, y ↦ y<sub>2</sub> }`는 선형이면서 평탄한 치환이다.

* 이름 변경 치환(renaming substitution): 변수 집합에 대한 순열로서, 단순히 변수의 이름을 다른 변수 이름으로 일대일로 바꾸는 치환이다. 예를 들어, `{ x ↦ x<sub>1</sub>, x<sub>1</sub> ↦ y, y ↦ y<sub>2</sub>, y<sub>2</sub> ↦ x }`는 이름 변경 치환이다. `{ x ↦ x<sub>1</sub>, y ↦ y<sub>2</sub> }`는 선형이고 평탄하지만, 모든 변수에 대한 순열이 아니므로 이름 변경 치환은 아니다 (만약 변수 집합이 {x, y, x₁, y₂} 보다 크다면).

역 치환:
모든 이름 변경 치환은 항상 역(inverse) 치환 σ⁻¹을 가지며, 모든 항 t에 대해 tσσ⁻¹ = t = tσ⁻¹σ를 만족한다. 위의 이름 변경 치환 예시에서 역은 `{ x ↦ y<sub>2</sub>, y<sub>2</sub> ↦ y, y ↦ x<sub>1</sub>, x<sub>1</sub> ↦ x }`이다. 그러나 임의의 치환에 대해 역을 정의하는 것은 일반적으로 불가능하다. 정보 손실이 발생할 수 있기 때문이다. 예를 들어, 평탄 치환 `{ x ↦ z, y ↦ z }`를 항 (x+y)에 적용하면 (x+y) { x ↦ z, y ↦ z } = z+z가 된다. 결과 항 z+z만으로는 원래 항이 x+y였는지 알 수 없으므로 역 치환을 정의할 수 없다. 마찬가지로 기저 치환 `{ x ↦ 2 }`를 항 (x+2)에 적용하면 (x+2) { x ↦ 2 } = 2+2가 되는데, 이 역시 원래 변수 x에 대한 정보가 손실되어 역을 정의할 수 없다.

3.3. 치환의 합성

두 치환 σ = { x₁ ↦ t₁, …, x_k ↦ t_k }와 τ = { y₁ ↦ u₁, …, y_l ↦ u_l }의 합성(composition)은 στ로 표기한다. 이는 치환 { x₁ ↦ t₁τ, …, x_k ↦ t_kτ, y₁ ↦ u₁, …, y_l ↦ u_l }에서 y_i ∈ { x₁, …, x_k }인 쌍 y_i ↦ u_i를 제거하여 얻는다.

치환 합성은 결합 법칙을 만족한다. 즉, 모든 치환 ρ, σ, τ와 모든 항 t에 대해 다음이 성립한다.
* (ρσ)τ = ρ(στ)
* (tσ)τ = t(στ)

모든 변수를 자기 자신에 매핑하는 [[항등 치환]](identity substitution)은 치환 합성의 중립 원소이다.

치환 σ가 σσ = σ를 만족할 때, 즉 자신과 합성했을 때 자기 자신이 될 때 이를 [[멱등]](idempotent) 치환이라고 한다. 모든 i = 1, ..., k에 대해 x_i ≠ t_i인 치환 { x₁ ↦ t₁, …, x_k ↦ t_k }는, 어떠한 항 t_j에도 변수 x_i가 포함되지 않는 경우에만 멱등이다.
* 멱등 치환 예시: { x ↦ y+y }는 멱등이다. ((x+y) {x↦y+y}) {x↦y+y} = ((y+y)+y) {x↦y+y} = (y+y)+y 이며, 이는 (x+y) {x↦y+y} 와 결과가 같기 때문이다.
* 비멱등 치환 예시: { x ↦ x+y }는 멱등이 아니다. ((x+y) {x↦x+y}) {x↦x+y} = ((x+y)+y) {x↦x+y} = ((x+y)+y)+y 이며, 이는 ((x+y)+y)와 다르므로, (x+y) {x↦x+y} {x↦x+y} ≠ (x+y) {x↦x+y} 이다.

치환 합성은 일반적으로 교환 법칙이 성립하지 않는다. 즉, στ는 τσ와 다를 수 있다.
* 비가환적 합성 예시: { x ↦ y } { y ↦ z } = { x ↦ z, y ↦ z } 이지만, { y ↦ z} { x ↦ y} = { x ↦ y, y ↦ z } 이므로 결과가 다르다.

4. 수학

수학에서 치환은 주로 두 가지 방식으로 사용된다. 첫째는 변수를 상수로 바꾸는 것(변수에 값을 할당하는 것과 유사하다)이고, 둘째는 '[[등식(수학)|등식]]의 치환 속성' 또는 라이프니츠가 제시한 '라이프니츠의 법칙'이라고 불리는 원리를 이용하는 것이다.

수학을 형식 언어로 본다면, 변수는 x, y, z와 같은 기호로 표현되며, 이 기호들은 특정 값의 범위를 나타낸다. 어떤 식이나 공식에서 변수가 자유 변수일 경우, 그 변수가 나타내는 범위 안의 어떤 값으로든 대체될 수 있다. 매개변수(예: 다항식의 계수)나 함수의 인수와 같은 특정 종류의 속박 변수도 치환될 수 있다. 또한, 전칭 양화된 변수는 해당 범위 내의 모든 값으로 대체될 수 있으며, 그 결과는 항상 참인 명제가 된다. 이를 전칭 인스턴스화라고 한다.

그러나 수학적 논리 바깥의 일반적인 수학 텍스트에서는 어떤 변수가 자유 변수이고 어떤 변수가 속박 변수인지 명확하게 구분하기 어려운 경우가 있다. 예를 들어, 라는 식에서 문맥에 따라 변수 $i$가 자유 변수이고 $k$가 속박 변수일 수도 있고, 그 반대일 수도 있다(둘 다 자유 변수일 수는 없다). 어떤 변수를 자유 변수로 간주할지는 주어진 문맥과 의미론에 따라 결정된다.

'등식의 치환 속성' 또는 '라이프니츠의 법칙'(후자는 주로 철학적 맥락에서 사용됨)은 일반적으로 두 대상이 같다면, 하나의 대상이 가진 속성은 다른 대상도 반드시 가져야 한다는 원리이다. 이를 논리 기호를 사용하여 다음과 같이 표현할 수 있다.
$(a=b)\; \backslash implies\; \backslash bigl[\; \backslash phi(a)\; \backslash Rightarrow\; \backslash phi(b)\; \backslash bigr]$
이는 모든 $a$와 $b$, 그리고 자유 변수 $x$를 포함하는 모든 잘 정의된 공식 $\backslash phi(x)$에 대해 성립한다. 예를 들어, 모든 실수 a와 b에 대해, 만약 a = b 이면, a ≥ 0 이라는 사실은 b ≥ 0 이라는 사실을 함의한다(여기서 $\backslash phi(x)$는 x ≥ 0 이다). 이 속성은 특히 연립 방정식을 풀 때 대수학에서 자주 사용되지만, 등식을 사용하는 거의 모든 수학 분야에서 기본적인 원리로 적용된다. 이 속성은 등식의 반사율과 함께 1차 논리에서 등식의 공리를 구성한다.

치환은 함수 합성과 관련이 있지만 동일한 개념은 아니며, 람다 대수에서의 β-축약과도 밀접한 관련이 있다.

4.1. 대수학

치환은 특히 컴퓨터 대수학에서 대수학의 기본 연산 중 하나이다.

치환의 일반적인 예는 다항식과 관련된다. 단변수 다항식의 미지수에 특정 숫자 값이나 다른 표현식을 대입하는 것은 해당 값에서 다항식의 값을 계산하는 것과 같다. 이 연산은 매우 자주 사용되므로, 다항식을 나타내는 표기법도 이에 맞춰진 경우가 많다. 예를 들어, 다항식을 단순히 P라고 이름 붙이는 대신 다음과 같이 변수 X를 포함하여 정의할 수 있다.
:$P(X)=X^5-3X^2+5X-17$
이렇게 정의하면, X 자리에 특정 값이나 식을 넣는 치환을 P(X) 형태로 간단히 나타낼 수 있다. 예를 들면 다음과 같다.
:$P(2)\; =\; 2^5\; -\; 3(2^2)\; +\; 5(2)\; -\; 17\; =\; 32\; -\; 12\; +\; 10\; -\; 17\; =\; 13$
:$P(X+1)\; =\; (X+1)^5\; -\; 3(X+1)^2\; +\; 5(X+1)\; -\; 17\; =\; X^5\; +\; 5X^4\; +\; 10X^3\; +\; 7X^2\; +\; 4X\; -\; 14.$

치환은 다항식뿐만 아니라, 기호로 구성된 다른 종류의 형식적 객체, 예를 들어 자유군의 원소 등에도 적용될 수 있다. 치환을 수학적으로 엄밀하게 정의하기 위해서는, 미지수를 특정 값으로 대응시키는 유일한 준동형 사상이 존재함을 보장하는 보편 성질을 가진 대수적 구조가 필요하다. 이러한 관점에서 보면, 치환은 주어진 준동형 사상에 따라 원소가 어떻게 변환되는지(즉, 그 이미지(image)를 찾는 것)를 확인하는 과정과 같다.