배타적 논리합
배타적 논리합 (exclusive or)은 수리 논리학에서 주어진 2개의 명제 가운데 1개만 참일 경우를 판단하는 논리 연산이다. 약칭으로 XOR, EOR, EXOR라고도 쓴다.
연산자는 <math>\veebar</math> (유니코드: U+22BB ⊻), <math>\dot\vee</math>이다. 혼돈이 되지 않을 경우, XOR, xor <math>\oplus</math> (유니코드: U+2295 ⊕), +、≠ 라고도 쓴다.
추가로 컴퓨터 프로그래밍 등에서 응용 수학으로, 비트간 배타적 논리합(bitwise exclusive or{{#if:| {{#if:Template:Lang/도움말 고리|[[[Template:Lang/도움말 고리|*]]]}}|}}Template:일반 기타)을 간단히 배타적 논리합, XOR이라고 부르는 경우가 있다. 연산자는 XOR, xor, <math>\oplus</math>, ^ 등이 사용된다.
예시
“내 키는 160cm 이상이다.”와 “내 몸무게는 60kg 미만이다.” 이 두 명제의 배타적 논리합은, “내 키는 160cm 이상이고 몸무게는 60kg 이상이다. 혹은, 내 키는 160cm 미만이고 몸무게는 60kg 미만이다.”가 된다.
추가로, 두 명제 A,B 에 대한 교집합 (A ∧ B)가 공집합이면, 배타적 논리합은 논리합과 같게 된다. 예를 들어, A = “내 키는 160cm이다.”와 B = “내 키는 170cm이다.”는 동시에 성립할 수 없기 때문에(교집합이 없음), (A xor B)와 (A ∨ B)는 동일하게 “내 키는 160cm와 170cm 중 하나다.”가 된다.
특징
- <math>P \veebar Q = (P \land \lnot Q) \lor (\lnot P \land Q)</math>
- <math>P \veebar Q = (P \lor Q) \land (\lnot P \lor \lnot Q)</math>
- <math>P \veebar Q = (P \lor Q) \land \lnot (P \land Q)</math>
라고 표현할 수 있다.
2를 몫으로 하는 잉여류체 <math>\mathbb{Z} / [2]</math>의 가감산(이 체에서는 덧셈과 뺄셈이 같다)은 0을 거짓, 1을 참으로 생각하면 배타적 논리합이 된다. 같은 종류(거짓이나 참)를 더하면 거짓이 되고 다른 종류를 더하면 참이 된다.
진리표
| 명제 P | 명제 Q | P ⊻ Q |
|---|---|---|
| 참 | 참 | 거짓 |
| 참 | 거짓 | 참 |
| 거짓 | 참 | 참 |
| 거짓 | 거짓 | 거짓 |
비트간 배타적 논리합
이진법으로 표현한 수의 각 비트에 대한 2진 집합체 <math>\mathbb{Z} / [2]</math> 에 가감산(0은 거짓, 1은 참으로 생각하고 배타적 논리합을 함)의 결과를 비트간 배타적 논리합, 배타적 비트화라고 하며 단순하게 배타적 논리합이라고도 한다.
비트간 배타적 논리합은 이진 유한체 <math>\mathrm{GF}(2^n), n \in \mathbb{N}</math> 로 가감산(덧셈과 뺄셈이 같음)에 동일하다. 추가로, <math>\mathbb{Z} / [2]</math>는, 이진 유한체 <math>\mathrm{GF}(2)\,</math> 이다.
0(거짓)과 1(참)에 대한 배타적 논리합과 비트간 배타적 논리합은 같다. 하지만 0과 1이외 다른 형태의 데이터가 있는 환경에서는 다른 형태의 데이터와 배타적 논리합(비트간 배타적 논리합이 아님)이 되어 결과적으로는 비트간 배타적 논리합과 다른 결과가 나오므로 주의해야 한다.
비트간 배타적 논리합은 비트 연산에서 특정 비트를 반전시키는 데 사용된다. 어느 수에서 반전을 하고 싶은 부분의 비트를 1로이 채워진 수와 배타적 논리합을 하면 지정된 부분이 반전된 수를 얻을 수 있다
- <math>0011_{(2)} \oplus 0110_{(2)} = 0101_{(2)}</math> .
비트간 배타적 논리합으로, 다수의 입력에 대한 오류 짝수 홀수 패리티를 계산하여 오류 검출에 사용된다. 이 목적으로 배타적 논리합(논리 게이트)을 트리 구조로 접속된 회로를 패리티 트리라고 한다.
비트간 배타적 논리합은 특정 비트의 반전이므로, 2회 반복하면 원래대로 된다. 즉
- <math>(P \oplus K) \oplus K = P</math>
이것을 이용하여, <math>K</math>의 키를 사용하여 암호화할 수 있다. <math>P\,</math>를 암호화하면 <math>P \oplus K</math>가 된다.
위의 예시를 들자면, <math>0011_{(2)}</math>는 키 <math>0110_{(2)}</math>를 이용하여 <math>0101_{(2)}</math>로 암호화되며,
- <math>0101_{(2)} \oplus 0110_{(2)} = 0011_{(2)}</math>
라고 키를 이용하여 암호를 복원할 수 있다. 단지 이것만으로 쉽게 풀려버리기 때문에 실제 암호화에는 다른 여러 가지 연산을 같이 사용한다.
