논리 연산

덤프버전 :

분류

논리 연산 관련 틀
[ 펼치기 · 접기 ]






1. 개요
2. 논리 연산의 종류
2.1. 부정 (NOT; ¬)
2.2. 논리곱 (AND; ∧)
2.3. 논리합 (OR; ∨)
2.4. 부정 논리곱 (NAND; ⊼)
2.5. 부정 논리합 (NOR; ⊽)
2.6. 배타적 논리합 (XOR; ⊻)
2.7. 동치 (EQV; ≡)
3. 성질
3.1. 항등원(identity)
3.2. 연산 우선 순위
4. 연산 법칙(law)
4.1. 교환법칙(commutatitve)
4.2. 결합법칙(associative)
4.3. 분배법칙(distributive)
4.4. 동일법칙(idempotent)[1]
4.5. 흡수법칙(absorption)
4.6. 이중부정 법칙(involution)
4.7. 드모르간 법칙(De Morgan's)
4.8. 합의 법칙(Consensus)
4.9. 그 밖의 연산 법칙
5. 관련 문서


1. 개요[편집]

論理演算

불 대수(Boolean algebra)는 19세기 중반 영국의 수학자 조지 불(George Boole, 1815년 11월 2일 ~ 1864년 12월 8일)이 고안하고 형식화한 대수 체계를 의미한다.

논리 연산(logical operation, logical connective)으로도 불린다. 수리논리학이나 컴퓨터과학에서, 두 개의 상태인 참(1, T, True)과 거짓(0, F, False)으로 불 연산(Boolean expression)이라 한다. 불 대수의 출현 이후로 논리학은 기호논리학의 성향이 강해지기 시작한다.

프로그래밍에서는 조건에 의한 분기나 반복을 만드는 데 이용되고, 디지털 논리 회로를 배울 때 유용하게 사용된다. 디지털 회로의 신호는 0과 1로만 구성되어 있기 때문이다. 전자계통에선 논리 연산을 하는 소자를 게이트(Gate)라고 하며 트랜지스터 여러 개를 조합해서 만들 수 있다.

이산수학에서는 속(Lattice) 중 Complementary Lattice이며 Distributive Lattice인 Lattice를 불 속(Boolean Lattice)이라 하며 이를 대수(Algebra)식으로 나타낸 것을 불 대수(Boolean Algebra)라고 한다. 불 속의 원소 개수는 해당 원자(atom) 개수 [math(n)]에 대해 [math(2^n)]개이다. 즉, 불 속의 원소 개수는 2의 제곱수대로 올라간다고 보면 된다.

불 대수는 집합으로 해석할 수 있다. [math(A)], [math(B)], [math(C)] 등 문자를 전체집합 [math(U=\{0, 1\})]의 공집합이 아닌 진부분집합으로 생각할 때, 논리합(or)은 합집합으로, 논리곱(and)는 교집합으로, 부정(not)은 여집합으로 생각할 수 있다.[2][3]

집합 기호는 고안자의 이름을 따서 [math(\mathbb B)]로 표현한다.[4] 아래의 연산과 함께 환을 이룬다.

2. 논리 연산의 종류[편집]

시작하기 앞서, 처음 보는 연산의 경우 진리표(Truth Table)를 사용하면 비교적 단순한 연산의 결과는 직접 확인할 수 있다. 다만 변수의 개수가 늘어나면 확인해야 하는 값이 대폭 증가하기 때문에, 기초적인 이해를 돕는 이상의 활용은 어렵다. 아래의 진리표를 보자.

아래는 [math(A \text{ and } B)]를 나타낸 것으로서, [math(A)]와 [math(B)] 값이 모두 참이면 1(True)을 출력하고 둘 중 하나의 값이라도 거짓이면 0(False)를 출력한다.

[math(A)]
[math(B)]
[math(A\wedge B)] (AND)
0
0
0
0
1
0
1
0
0
1
1
1


2.1. 부정 (NOT; ¬)[편집]

말 그대로 부정(否定)이다. 즉, 참과 거짓을 뒤집는다. C언어의 영향을 받은 프로그래밍 언어에서는 일반적으로 !를 부정 연산자로 사용하며, 그 외에 [math(\sim A)]도 많은 프로그래밍 언어에서 사용되고[5], 필기나 서적 등에서는 [math(A')] [6]또는 [math(A)] 위에 ㅡ를 그려넣은 [math(\bar{A} )] 기호가 주로 쓰인다. 불 보수(Boolean Complement)로도 불린다. 이 연산을 하는 회로는 따로 보수기(inverter)라는 이름으로 불린다.

[math(A)]
[math(\neg \ A)]
0
1
1
0


2.2. 논리곱 (AND; ∧)[편집]

두 명제가 모두 참이어야 참값을 돌려준다. C언어의 영향을 받은 프로그래밍 언어에서는 일반적으로 &를 논리곱 연산자로 사용하며, 불 대수에서는 AND는 곱셈과 동치이다. 불 곱(Boolean Multiplication) 혹은 논리곱이라 부른다. 아래의 연산결과를 보면 왜 곱셈과 동치인지 쉽게 알 수 있을 것이다. [math(AB)] 또는 [math(A\cdot B)][7]로도 표시한다.

[math(A)]
[math(B)]
[math(A \wedge B)]
0
0
0
0
1
0
1
0
0
1
1
1


2.3. 논리합 (OR; ∨)[편집]

두 명제 중 어느 한 명제만 참이어도 참값을 돌려준다. C언어의 영향을 받은 프로그래밍 언어에서는 일반적으로 |를 논리합 연산자로 사용한다. 불 대수에서는 OR는 덧셈과 동치여서, 논리합(Boolean Addition)으로 부른다. 아래에서 보듯 [math(\boldsymbol{1 + 1 = 1})] 임을 주의해야 한다. [math(A+B)][8]로도 표시한다.

[math(A)]
[math(B)]
[math(A \vee B)]
0
0
0
0
1
1
1
0
1
1
1
1


2.4. 부정 논리곱 (NAND; ⊼)[편집]

Not AND. 논리곱의 결과값을 부정한 것이다. 즉, 두 명제가 모두 참이면 거짓값을 돌려주고 그 외에는 참값을 돌려준다. 참고로 NAND만을 통해 다른 논리 연산식을 모조리 구현할 수 있기 때문에[9] 현재 사용되는 플래시 메모리들은 대부분이 NAND 회로로 구성되어 있다.

[math(A)]
[math(B)]
[math(A \barwedge B)]
0
0
1
0
1
1
1
0
1
1
1
0


2.5. 부정 논리합 (NOR; ⊽)[편집]

Not OR. 논리합의 결과값을 부정한 것이다. 즉, 두 명제가 모두 거짓이면 참값을 돌려주고 그 외에는 거짓값을 돌려준다. NAND와 마찬가지로 NOR만으로 다른 논리 연산식을 모조리 구현할수 있기에 초기 플래시 메모리들은 대부분이 NOR 회로로 구성하였다. 근데 NAND 회로가 값이 싸다보니 이쪽은 자연스럽게 도태되었다.

[math(A)]
[math(B)]
[math(A~\overline{\vee}~B)]
0
0
1
0
1
0
1
0
0
1
1
0


2.6. 배타적 논리합 (XOR; ⊻)[편집]

두 명제 중 정확히 하나만 참이어야, 혹은 두 명제의 참거짓 여부가 다를 때 참값을 돌려준다. [math(A'B+AB')][10]와 동치이다. 논리학에서는 기호 [math(\veebar)]를 사용하지만, 공학에서는 [math(\oplus)]를 사용한다.

C언어의 영향을 받은 프로그래밍 언어에서는 
^
를 배타적 논리합 기호로 사용한다. 다만 일반적인 경우에는 
^
가 제곱으로 사용되기 때문에 처음 프로그래밍 언어를 배우는 사람들은 제곱을 하려고 
^
기호를 사용했다가 안드로메다로 가는 경우가 있다.(…)[11][12] 이 방식으로 특정 '키'를 이용해 암호화를 하면 그 '키'로 복호화가 가능해서, 암호화 기법으로도 널리 사용된다. 비교 대상의 비트가 0이든 1이든 상관 없이 같기만 하면 0을 돌려준다는 특성을 이용하여 어셈블리어 등의 언어에서 어떤 레지스터나 변수를 0으로 초기화할 때 사용되기도 한다.[13] 이런 특성때문에 XOR을 이용해 임시 변수 없이 변수를 스왑하는 기법[14]은 메모리 사용량에서야 좀 이득을 보겠지만 실제론 거의 사용되지 않는다. 스왑하는 값이 같은 주소를 참조한다면 엉망이 되기 때문.

결합법칙이 성립하므로 n항연산으로 일반화 가능하다. 이 경우 n개의 입력 중 참의 개수가 홀수이면 출력이 참이 되는 연산으로 정의된다.

[math(A)]
[math(B)]
[math(A\veebar B)]
0
0
0
0
1
1
1
0
1
1
1
0


2.7. 동치 (EQV; ≡)[편집]

두 명제가 다 참이거나 다 거짓이면, 즉 두 명제의 진리값이 같으면 참값을 돌려준다. 배타적 논리합(XOR)의 부정이라고 할 수 있으므로 배타적 부정 논리합 (XNOR) 또는 배타적 논리곱(XAND)이라고도 한다. 논리학에서는 기호 [math(\equiv)]를 사용하나, [math(\underline{\wedge})] 혹은 [math(\overline\veebar)]를 사용하기도 하고, 공학에서는 [math(=)]를 쓰기도 한다.

수학적으로는 크로네커 델타([math(\delta_{ij} = \left\{\begin{matrix} 0 \; \; \; \text{if} \; \; \; i \neq j \\ 1 \; \; \; \text{if} \; \; \; i = j \end{matrix}\right.)])로 정의돼 있다. C언어 및 그 파생 언어에서 '
=
'는 대입(
:=
)을 의미하므로 동치 연산자를 '
==
'로 표기한다. [math((A\underline{\wedge}B)'= AB)]와 동치이다. XOR과 달리 결합법칙이 성립하지 않는다.

[math(A)]
[math(B)]
[math(A\equiv B)]
0
0
1
0
1
0
1
0
0
1
1
1


3. 성질[편집]

공리(axiom)전제(postulation)이라고도 부른다.


3.1. 항등원(identity)[편집]

[math(A\cdot 1 = A = 1\cdot A)]
[math(A+0 = A = 0+A)]


3.2. 연산 우선 순위[편집]

NOT > AND > OR 이다.

  • 부정(NOT) 연산은 AND와 OR보다 연산 우선 순위가 높다.
  • 대수학에서 곱셈 연산이 덧셈 연산보다 우선이듯이, 논리 연산에서도 논리곱(AND)이 논리합(OR) 보다 연산 순위가 높다.

분배법칙의 아래 두 식 중에 첫 번째 식의 우변에는 괄호가 없다. 이는 AND가 OR보다 연산 우선 순위가 높기 때문이다. 괄호가 생략된 것이라 보아도 되는데 [math(A\cdot B)]와 [math(A\cdot C)]에 대한 괄호의 존재 여부는 우변의 결과에 영향을 미치지 않는다.
[math(A\cdot (B+C)=A\cdot B+A\cdot C)]
[math(A+(B\cdot C)=(A+B)\cdot (A+C))]

[math(A\cdot (B+C)=(A\cdot B)+(A\cdot C)=A\cdot B+A\cdot C)]


4. 연산 법칙(law)[편집]

혼동 방지를 위해, 다음 기호만을 사용하여 표기한다.
연산
표기
NOT
[math(')]
AND
[math(\cdot)]
OR
[math(+)]
XOR
[math(\oplus)]


4.1. 교환법칙(commutatitve)[편집]

[math(A+B=B+A)]
[math(A\cdot B=B\cdot A)]
[math(A\oplus B = B\oplus A)]


4.2. 결합법칙(associative)[편집]

[math((A+B)+C=A+(B+C))]
[math((A\cdot B)C=A\cdot (B\cdot C))]
[math((A\oplus B)\oplus C = A\oplus (B\oplus C))]

NXOR을 포함하여 NAND, NOR 등 모든 부정 연산은 결합법칙이 성립하지 않는다.

4.3. 분배법칙(distributive)[편집]

[math(A\cdot (B+C)=A\cdot B+A\cdot C)]
[math(A+(B\cdot C)=(A+B)\cdot (A+C))]
[math(A\cdot (B\oplus C) = A\cdot B\oplus A\cdot C)]

논리연산의 분배법칙 결과는 [math(A+(B\cdot C)=(A+B)\cdot (A+C))]가 된다. 드모르간 법칙 하단의 설명을 보면 쉽게 이해할 수 있다.


4.4. 동일법칙(idempotent)[15][편집]

[math(A\cdot A = A)]
[math(A + A = A)]
계산하려는 두 숫자가 똑같으면 결과도 그 똑같은 값이 나온다는 뜻이다. [math(A)]에 0을 대입했을 때도 성립하고 1을 대입했을 때도 성립하는 것으로 해당 성질을 증명할 수 있다.


4.5. 흡수법칙(absorption)[편집]

[math(A+A\cdot B=A)]
[math(A\cdot (A+B)=A)]
전기 회로에서 곱연산을 직렬로, 합연산을 병렬로 생각해보면 이해가 쉽다. 아래 식에서 [math(B)]는 [math(A)]와 병렬이라서 [math(B)]가 끊어졌어도 [math(A)]가 이어져 있으면 그대로 전기가 흐르기 때문에 사실상 [math(B)]는 없는 것이나 다름없고, [math(A)]를 직렬로 두 개 단 것과 똑같기 때문에 식이 저렇게 [math(A)]로 흡수되는 것이다.

두 흡수법칙 식의 증명은 아래와 같다. 증명의 3행에 흡수법칙의 위쪽 식이 등장한다.


[math(\def\arraystretch{1.5} \begin{array}{clr}
&A \cdot (A+B) &\\
=&A \cdot A + A \cdot B &\because 분배법칙\\
=&A + A\cdot B &\because 동일법칙\ A\cdot A = A\\
=&A\cdot 1 + A\cdot B &\because 항등원\ A\cdot 1 = A\\
=&A\cdot (1 + B) &\because 분배법칙\\
=&A\cdot 1 &\because B + 1 = 1\\
=&A &\because 항등원\ A\cdot 1 = A\\
\end{array})]


4.6. 이중부정 법칙(involution)[편집]

[math((A')' = A)]


4.7. 드모르간 법칙(De Morgan's)[편집]

[math((A \cdot B)'=A'+B')]
[math((A+B)'=A' \cdot B')]
식을 깔끔하게 정리할 때 가장 많이 사용되는데다가 NAND 연산, NOR 연산과 밀접한 연관이 있는 만큼 불 대수에서 상당히 중요하게 다뤄지는 성질이다. 오죽하면 대부분 교재에서 이 법칙 하나만 불 대수 파트에서 분리해서 따로 가르칠 정도.

사실 머리를 좀 굴려보면 AND와 OR은 같은 구조의 함수지만(항등원끼리 연산하면 항등원, 나머지 경우는 항등원이 아닌 것) AND는 항등원이 1(=0')이고 OR은 항등원이 0(=1')일 뿐이라는 걸 알 수 있는데, 다시 말해 NOT은 ({0 || 1}, AND)에서 ({0, 1}, OR)로 가는 Isomorphism이다. 이중 부정규칙을 이용하면 동시에 NOT은 ({0 || 1}, OR)에서 ({0, 1}, AND)로 가는 Isomorphism이므로 결론적으로 NOT은 ({0 || 1}, AND, OR)에서 ({0, 1}, OR, AND)로 가는(연산이 서로 바뀌었다) Isomorphism이다.

이걸 이용해 드모르간 법칙을 쉽게 증명할 수 있을 뿐만 아니라 성질 항목에 나와있는 한쌍의 공식이 서로를 유도할 수 있다는 걸 쉽게 보일 수 있다.


4.8. 합의 법칙(Consensus)[편집]

[math(AB + {\color{red}BC} + CA' = AB + CA')]
[math((A + B){\color{red}(B + C)}(C + A') = (A + B)(C + A'))]
자세히 보면 가운데 마디가 사라진 것을 볼 수 있다.

증명은 아래와 같다.
우선

[math(\def\arraystretch{1.5} \begin{array}{clr}
&BC&\\
=&1\cdot BC &\because 항등원\ A\cdot 1 = A\\
=&(A+A')\cdot BC &\because A+A' = 1\\
=&ABC+ A'BC &\because 분배법칙\\
=&ABC + CA'B &\because 교환법칙\end{array})]

임을 이용한다.

[math(\def\arraystretch{1.5} \begin{array}{clr}
&AB + BC + CA'&\\
=&AB + ABC + CA'B + CA'&\\
=&(AB+AB\cdot C) + (CA'\cdot B + CA') &\because 결합법칙\\
=&(AB + AB\cdot C) + (CA' + CA'\cdot B) &\because 교환법칙\\
=&AB + CA' &\because 흡수법칙\ A+A\cdot B = A\end{array})]
비슷한 방법으로 아래 식도 증명할 수 있다.


4.9. 그 밖의 연산 법칙[편집]

[math(A + A' = 1)]
[math(A\cdot A' = 0)]

[math(A+1=1)]
[math(A\cdot 0 = 0)]

[math((A\oplus B)' = A\oplus B' = A'\oplus B)]
[math(A'\oplus B' = A\oplus B)]

[math(A+A'\cdot B=A+B)]
[math(A\cdot (A'+B)=A\cdot B)]

마지막 식의 증명은 다음과 같다.

[math(\def\arraystretch{1.5} \begin{array}{clr}
&A\cdot (A'+B)&\\
=&A\cdot A' + A\cdot B &\because 분배법칙\\
=&0 + A\cdot B &\because A\cdot A' = 0\\
=&A\cdot B &\because 항등원\ 0 + A = A\end{array})]
그 위의 식도 비슷하다.



5. 관련 문서[편집]



파일:크리에이티브 커먼즈 라이선스__CC.png 이 문서의 내용 중 전체 또는 일부는 2023-11-20 02:01:49에 나무위키 논리 연산 문서에서 가져왔습니다.

[1] 멱등(冪等)법칙이라고도 한다.[2] 단, 0을 원소로 가지는 집합끼리의 교집합은 공집합이므로, 교집합을 논리곱(and)이라고 하려면 공집합 또한 0으로 보아야 한다.[3] 이 방법을 통해 드모르간 법칙이 불 대수에서 성립함을 직접적 증명 없이 이해할 수 있다.[4] 원소가 두 개(Binary)뿐인 집합이라는 의미도 함의하고 있다.[5] ~는 C언어에서도 마찬가지로 부정으로 사용되긴 하나, 논리 연산이 아닌 비트 연산이다.[6] 프라임이라 읽는다. 미분 기호로도 쓰인다.[7] 주의하자면 곱셈이 절대로 아니다! [math(A \boldsymbol{\text{ and }} B)], [math(A)] 논리곱 [math(B)]. 이래도 헷갈린다(...)[8] [math(A \boldsymbol{\text{ or }} B)][9] [math(p\uparrow p=\neg p, (p\uparrow q)\uparrow (p\uparrow q)=p\wedge q,(p\uparrow p)\uparrow (q\uparrow q)=p\vee q)][10] ((not A) and B) or (A and (not B))[11] C언어에서 제곱은 
math.h
라는 헤더 파일을 include(포함)하고(<math.h>), 
pow(밑, 지수)
함수를 사용하면 가능하다.[12] PHP 5.6 이상이나 Python 등의 언어에서는 또 
**
로 지수를 표현하는 것이 가능하다.[13] 예를 들어, AX라는 레지스터를 0으로 초기화 할 땐 
MOV AX,0
을 써도 되지만 
XOR AX,AX
를 해도 된다는 의미이다. AX에 뭔 값이 들어있는지는 알 수 없지만, 같은 것끼지 연산시키면 무조건 0을 반환하는 XOR의 특성 상 해당 연산의 결과는 AX의 원래 값과는 상관 없이 항상 0이 된다.[14] [math(A=A\veebar B)]; [math(B=A\veebar B)]; [math(A=A\veebar B)][15] 멱등(冪等)법칙이라고도 한다.

관련 문서