배타적 논리합

3. 정의

배타적 논리합은 중위 표기법을 사용하여 표현하는 경우가 많다. 연산자로는 $\backslash veebar$ (유니코드: U+22BB ⊻), $\backslash dot\backslash vee$가 주로 사용되며, 혼동의 여지가 없을 때에는 XOR, xor, $\backslash oplus$ (유니코드: U+2295 ⊕), +, ≠ 등이 사용되기도 한다.

논리학에서는 $\backslash veebar$를 사용하여 $P\; \backslash veebar\; Q$와 같이 표현하고, 논리 회로에서는 $\backslash oplus$를 사용하여 $A\; \backslash oplus\; B$와 같이 표현하는 경우가 많다.

3. 1. 진리표

3. 2. 예시

4. 성질

배타적 논리합은 논리곱, 논리합, 부정을 사용하여 다음과 같이 표현할 수 있다.

: $P\; \backslash veebar\; Q\; =\; (P\; \backslash land\; \backslash lnot\; Q)\; \backslash lor\; (\backslash lnot\; P\; \backslash land\; Q)$

: $P\; \backslash veebar\; Q\; =\; (P\; \backslash lor\; Q)\; \backslash land\; (\backslash lnot\; P\; \backslash lor\; \backslash lnot\; Q)$

: $P\; \backslash veebar\; Q\; =\; (P\; \backslash lor\; Q)\; \backslash land\; \backslash lnot\; (P\; \backslash land\; Q)$

배타적 논리합은 다음과 같은 성질을 갖는다.

5. 현대 대수학과의 관계

배타적 논리합 연산($\backslash \{T,\; F\backslash \},\; \backslash oplus$)은 가환군이다. 논리곱($\backslash wedge$)과 배타적 논리합($\backslash oplus$) 연산을 결합하면, 두 원소 체 $\backslash mathbb\{F\}\_2$ (갈루아 체 GF(2))가 된다.^[1]

$F$를 0으로, $T$를 1로 연관시키면, 논리 "AND" 연산은 $\backslash mathbb\{F\}\_2$에서의 곱셈으로, "XOR" 연산은 $\backslash mathbb\{F\}\_2$에서의 덧셈으로 해석할 수 있다.^[1]

:$\backslash begin\{matrix\}$

r = p \land q & \Leftrightarrow & r = p \cdot q \pmod 2 \\[3pt]

r = p \oplus q & \Leftrightarrow & r = p + q \pmod 2 \\

\end{matrix}

이러한 관계를 통해 불 함수를 $\backslash mathbb\{F\}\_2$의 다항식으로 표현할 수 있으며, 이를 함수의 대수적 정규 형식이라고 한다.^[1]

6. 컴퓨터 과학에서의 응용

• 비트 연산: XOR 연산은 비트 연산에 자주 사용되며, 특히 특정 비트를 반전시키는 데 유용하다. 예를 들어, 어떤 수에서 특정 비트를 반전시키려면, 해당 비트를 1로 설정하고 XOR 연산을 수행하면 된다.
• 두 비트 비교: 두 비트가 서로 다른 값을 가지는지 확인하는 데 사용될 수 있다.
• 제어 가능한 비트 반전기: XOR 게이트는 제어 입력에 따라 데이터 입력 값을 반전시킬지 여부를 선택할 수 있는 제어 가능한 비트 반전기로 동작한다.
• 패리티 비트 생성: 홀수 개의 1 비트가 있는지 확인하는 데 사용된다. 이는 패리티 함수에서 반환되는 패리티 비트를 생성하는 데 활용된다.
• 하드웨어 난수 생성: XOR 연산은 하드웨어 난수 생성기에서 엔트로피 풀을 생성하는 데 사용될 수 있다. XOR 연산은 무작위성을 보존하는 특성이 있어, 여러 개의 잠재적 난수 데이터 소스를 XOR 연산으로 결합하면 예측 불가능성이 높은 난수를 얻을 수 있다.^[22]
• RAID: XOR는 RAID 3–6에서 패리티 정보를 생성하는 데 사용된다. 예를 들어, 두 개 이상의 하드 드라이브에서 데이터를 XOR하여 패리티 정보를 생성하고, 이를 별도의 드라이브에 저장함으로써 데이터 손실 시 복구할 수 있도록 한다.^[23]
• 오버플로 감지: XOR는 부호 있는 이진 산술 연산 결과의 오버플로를 감지하는 데 사용될 수 있다.
• XOR 연결 리스트: XOR 연결 리스트는 이중 연결 리스트 데이터 구조를 나타내기 위해 XOR 속성을 활용하여 공간을 절약한다.
• 컴퓨터 그래픽: 컴퓨터 그래픽에서 XOR 기반 그리기 방식은 알파 채널 또는 오버레이 평면이 없는 시스템에서 경계 상자 및 커서와 같은 항목을 관리하는 데 사용된다.
• 프로그래밍 언어: 프로그래밍 언어에서 XOR 연산은 `^`, `@`, `XOR`, `xor` 등의 기호나 키워드로 표현된다. Haskell과 같이 일부 언어에서는 배타적 논리합 연산자가 별도로 존재하지 않고, 같지 않음을 나타내는 비교 연산자(`!=`)가 XOR 연산의 의미를 갖기도 한다.^[24]

6. 1. 비트 연산

앞서 언급했듯이 배타적 논리합은 2를 모듈로 한 덧셈과 동일하므로, 두 개의 ''n''비트 문자열의 비트 단위 배타적 논리합은 벡터 공간 $(\backslash Z/2\backslash Z)^n$에서 표준 벡터 덧셈과 동일하다.

컴퓨터 과학에서 배타적 논리합은 다음과 같은 여러 용도로 사용된다.

• 두 비트가 서로 다른지 알려준다.
• 제어 가능한 비트 반전기이다(제어 입력은 데이터 입력을 반전할지 여부를 선택한다).
• 홀수 개의 1 비트가 있는지 알려준다($A\; \backslash oplus\; B\; \backslash oplus\; C\; \backslash oplus\; D\; \backslash oplus\; E$는 변수의 홀수 개수가 참일 if and only if 때 참이 된다). 이는 패리티 함수에서 반환되는 패리티 비트와 같다.

비트별 배타적 논리합은 자리올림을 무시한 2진수의 덧셈 결과와 같다.

1자리의 2진수의 배타적 논리합은 반가산기의 일부이다.

배타적 논리합과 비트별 배타적 논리합은 다른 경우가 있다. 0 (거짓)과 1 (참)에 대해서는 배타적 논리합과 비트별 배타적 논리합은 같다. 그러나 0이 아닌 값이 모두 참으로 간주되는 환경이나, 0이 아닌 값이 참 (1)으로 묵시적인 형변환되는 환경에서는 0과 1 이외의 값에 대해서도 (비트별이 아닌) 배타적 논리합을 구할 수 있으며, 결과는 일반적으로 비트별 배타적 논리합과는 다르므로 주의해야 한다.

비트별 배타적 논리합은 컴퓨터에서 비트 연산을 수행할 때 특정 비트만 반전시키는 데 자주 사용된다. 어떤 숫자와 그 숫자의 비트를 반전시키고 싶은 부분을 1로 한 숫자와 배타적 논리합을 취하면 지정한 부분이 반전된 숫자를 얻을 수 있다.

:$0011\_\{(2)\}\; \backslash oplus\; 0110\_\{(2)\}\; =\; 0101\_\{(2)\}$

많은 프로세서에서 레지스터를 0으로 만들 때 직접 0을 레지스터로 전송하는 것보다 자기 자신과의 XOR 연산을 통해 0으로 만드는 것이 유리한 경우가 있다.

:$X\; \backslash oplus\; X\; =\; 0$

주로 다음과 같은 조건이 성립하는 경우, 언어 프로세서가 최적화의 일환으로 XOR을 사용한다.

• 즉시 값 0을 생략함으로써 코드 크기를 줄일 수 있다.
• 처리가 레지스터와 ALU만으로 완료되므로 사이클 수나 소비 전력을 줄일 수 있다.
• XOR 연산에 의한 플래그 변화가 그 이후 처리에 불리한 영향을 남기지 않는다.

6. 2. 하드웨어

6. 3. 소프트웨어

• 두 비트가 서로 다른지 알려준다.
• 제어 가능한 비트 반전기이다(제어 입력은 데이터 입력을 반전할지 여부를 선택한다).
• 홀수 개의 1 비트가 있는지 알려준다($A\; \backslash oplus\; B\; \backslash oplus\; C\; \backslash oplus\; D\; \backslash oplus\; E$는 변수의 홀수 개수가 참일 if and only if 때 참이 된다). 이는 패리티 함수에서 반환되는 패리티 비트와 같다.
• 논리 회로에서 간단한 가산기는 숫자를 더하기 위해 XOR 게이트를 사용하고, 올림 출력을 생성하기 위해 일련의 AND, OR 및 NOT 게이트를 사용하여 만들 수 있다.
• 일부 컴퓨터 아키텍처에서는 레지스터를 자체적으로 XOR하여(자체적으로 XOR된 비트는 항상 0) 레지스터에 0을 저장하는 것이 0 값을 로드하고 저장하는 것보다 더 효율적이다.^[22]
• XOR 스왑 알고리즘을 사용하여 컴퓨터에서 두 개의 숫자 변수를 교환하는 데 사용할 수 있다. 그러나 이는 호기심으로 간주되며 실제로 권장되지 않는다.
• XOR 연결 리스트는 이중 연결 리스트 데이터 구조를 나타내기 위해 공간을 절약하기 위해 XOR 속성을 활용한다.
• 부호 있는 이진 산술 연산 결과의 오버플로를 감지하는 데에도 사용된다. 결과의 가장 왼쪽에 유지된 비트가 왼쪽에 있는 무한 개의 자릿수와 같지 않으면 오버플로가 발생했음을 의미한다. 이 두 비트를 XOR하면 오버플로가 있는 경우 "1"이 된다.^[23]
• 많은 프로세서에서 레지스터를 0으로 만들 때 직접 0을 레지스터로 전송하는 것보다 자기 자신과의 XOR 연산을 통해 0으로 만드는 것이 유리한 경우가 있다.

• 주로 다음과 같은 조건이 성립하는 경우, 언어 프로세서가 최적화의 일환으로 XOR을 사용한다.

• 비트별 배타적 논리합에 의해 다수의 입력에서 거짓의 개수의 홀수·짝수 (패리티)를 감지할 수 있으므로 오류 검출에 사용된다. 이 목적으로 배타적 논리합 (논리 게이트)을 나무 가지 모양으로 연결한 회로를 패리티 트리라고 한다.
• 비트별 배타적 논리합은 특정 비트의 반전 연산이므로, 두 번 반복하면 원래대로 돌아온다. 즉,

• 이것은 결합 법칙에 의해 다음과 같이 증명할 수 있다.

• 이 성질은 편리하며, 다양한 응용이 있다. 단순한 것으로는 (현대에는 유용성이 거의 없지만) 두 개의 레지스터의 내용을 다른 자원을 사용하지 않고 교환할 수 있는 "XOR 교환 알고리즘"이 있으며, 데이터 구조에서는 "XOR 연결 리스트"가 있다.

7. 암호학에서의 응용

비트간 배타적 논리합(XOR)은 특정 비트를 반전시키는 특징이 있어, 같은 키로 XOR 연산을 두 번 반복하면 원래 값으로 돌아온다. 즉, \( (P \oplus K) \oplus K = P \) 가 성립한다. 이러한 성질을 이용하여 키 \(K\)를 사용해 \(P\)를 암호화하면 \( P \oplus K \) 가 된다.

예를 들어, 이진수 \(0011_{(2)}\)는 키 \(0110_{(2)}\)를 이용하여 \(0101_{(2)}\)로 암호화되며, 다시 \(0101_{(2)} \oplus 0110_{(2)} = 0011_{(2)}\) 와 같이 같은 키를 사용하여 복호화할 수 있다. 하지만 XOR 연산만으로는 쉽게 해독될 수 있기 때문에, 실제 암호화에는 다른 여러 연산과 함께 사용된다.^[24]

XOR 연산은 버넘 암호에 사용되는 원리이다. 버넘 암호는 평문에 키를 XOR하여 암호문을 생성한다. 이때, 일회용 패드를 사용하면 이론적으로 해독이 불가능한 안전성을 확보할 수 있지만, 원문과 같은 길이의 키를 사전에 안전하게 공유하고 보관해야 하는 현실적인 어려움이 따른다.

8. 자연 언어에서의 배타적 논리합

분리는 흔히 자연 언어에서 배타적으로 이해된다. 영어에서 분리 접속사 "or"는, 특히 "either"와 함께 사용될 때 배타적으로 이해되는 경우가 많다. 아래 영어 예시는 일반적으로 대화에서 메리가 가수이자 시인 둘 다가 아니라는 것을 암시하는 것으로 이해될 것이다.^[4][5]

:1. 메리는 가수이거나 시인이다.

하지만 분리는 "either"와 결합해서도 포괄적으로 이해될 수 있다. 예를 들어 아래의 첫 번째 예시는 "either"가 두 분리절이 모두 참이라는 명백한 진술과 결합하여 유용하게 사용될 수 있음을 보여준다. 두 번째 예시는 하향적 함축 문맥에서 배타적 추론이 사라진다는 것을 보여준다. 이 예시에서 분리가 배타적으로 이해된다면, 어떤 사람들이 쌀과 콩을 모두 먹었을 가능성이 열려 있게 된다.^[4]

:2. 메리는 가수이거나 시인이거나 둘 다이다.

:3. 아무도 쌀이나 콩을 먹지 않았다.

위와 같은 예시들은 배타성 추론을 포괄적인 의미론을 기반으로 계산된 화용론적 대화 함축으로 분석하도록 동기를 부여했다. 함축은 전형적으로 취소 가능하며, 그 계산이 수량의 격률에 의존하는 경우 하향적 함축 문맥에서는 발생하지 않는다. 하지만 일부 연구자들은 배타성을 진정한 의미론적 함의로 취급하고 이를 검증할 비고전 논리를 제안했다.^[4]

영어 "or"의 이러한 특징은 다른 언어에서도 발견된다. 그러나 많은 언어는 프랑스어의 ''soit... soit''와 같이 강력하게 배타적인 분리 구문을 가지고 있다.^[4]

"내 키는 160cm 이상이다"와 "내 몸무게는 52kg 미만이다"라는 두 명제의 배타적 논리합은 이 중 하나만 성립하는 것이므로, "나는 키가 160cm 이상이고 몸무게가 52kg 이상이다. 또는 나는 키가 160cm 미만이고 몸무게가 52kg 미만이다."가 된다.

두 명제 A, B에 대해 교집합 A ∧ B가 공집합이면, 배타적 논리합은 논리합과 같아진다. 예를 들어, A = "내 키는 160cm이다"와 B = "내 키는 170cm이다"는 동시에 성립할 수 없으므로(교집합이 공집합), (A xor B)는 (A ∨ B)와 마찬가지로 "내 키는 160cm 또는 170cm 중 하나이다"가 된다.

9. 기타 응용

• 님 게임(Nim game): 배타적 논리합과 이진 표기법을 사용하여 님 게임의 필승 전략을 분석할 수 있다.^[23]
• RAID: RAID 3–6에서 데이터 손실 시 복구를 위한 패리티 정보를 생성하는 데 XOR 연산이 사용된다. 예를 들어, 두 개 이상의 하드 드라이브에서 및 바이트를 XOR하여 해당 바이트를 "백업"한 다음() 다른 드라이브에 기록할 수 있다. 이 방법을 사용하면 세 개의 하드 드라이브 중 하나라도 손실되면 나머지 드라이브의 바이트를 XOR하여 손실된 바이트를 다시 생성할 수 있다.^[23]
• 컴퓨터 그래픽스: 알파 채널 또는 오버레이 평면이 없는 시스템에서 경계 상자 및 커서와 같은 항목을 관리하는 데 XOR 기반 그리기 방식이 사용될 수 있다.

참조

_[1] 웹사이트 XOR http://mathworld.wol[...] Wolfram Research 2015-06-17
_[2] 서적 Précis de logique mathématique https://burjcdigital[...] F. G. Kroonder, Bussum, Pays-Bas 1949
_[3] 서적 Algorithmic Cryptanalysis CRC Press
_[4] 간행물 Disjunction https://plato.stanfo[...] Metaphysics Research Lab, Stanford University 2020-09-03
_[5] 서적 The Genealogy of Disjunction Oxford University Press 1994
_[6] 서적 The Mathematical Analysis of Logic, Being an Essay Towards a Calculus of Deductive Reasoning https://archive.org/[...] Macmillan, Barclay, & Macmillan/George Bell 1847
_[7] 서적 A Mathematical Introduction to Logic A Harcourt Science and Technology Company 2001
_[8] 서적 A Concise Introduction to Mathematical Logic Springer 2010
_[9] 간행물 On the Algebra of Logic https://archive.org/[...] Little, Brown & Company 1883
_[10] 서적 Vorlesungen über die Algebra der Logik (Exakte Logik), Erster Band Druck und Verlag B. G. Teubner 1890
_[11] 서적 Notations de logique mathématique. Introduction au formulaire de mathématique Fratelli Boccna. 1894
_[12] 서적 ПРЯМАЯ И ОБРАТНАЯ ТЕОРЕМЫ: ЭЛЕМЕНТЫ АЛГЕБРЫ ЛОГИКИ https://www.mathedu.[...] ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО ФИЗИКа-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ 1959
_[13] 간행물 A Symbolic Analysis of Relay and Switching Circuits https://www.cs.virgi[...]
_[14] 간행물 Sets of Independent Postulates for the Algebra of Logic 1904
_[15] 서적 Die philosophischen Schriften, Siebter Band https://archive.org/[...] Weidmann 1890
_[16] 간행물 New Sets of Independent Postulates for the Algebra of Logic, With Special Reference to Whitehead and Russell's Principia Mathematica 1933
_[17] 서적 Introduction to Mathematical Logic Princeton University Press 1996
_[18] 서적 Routledge Encyclopedia of Philosophy, Volume 8 https://books.google[...] Taylor & Francis 1998
_[19] 서적 Elementy logiki matematycznej Państwowe Wydawnictwo Naukowe 1929
_[20] 서적 The C Programming Language Prentice-Hall
_[21] Mathworld Symmetric Difference
_[22] 웹사이트 Exclusive OR (XOR) and hardware random number generators http://www.robertnz.[...] 2002-02-28
_[23] 웹사이트 How RAID 5 actually works http://rickardnobel.[...] 2011-07-26
_[24] 문서 "ビット演算の排他的論理和には専用の演算が必要である（Haskellではxorという関数）。"