최근 수정 시각 : 2022-07-21 12:04:48

논리 연산

불 대수에서 넘어옴
수학기초론
Foundations of Mathematics
{{{#!wiki style="margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px"
{{{#!wiki style="letter-spacing: -1px" 		다루는 대상과 주요 토픽
수리논리학 논리 · 논증{ 귀납논증 · 연역논증} · 공리 및 공준 · 증명{ 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문( 조각적 정의) · 명제 논리( 명제, 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리( 존재성과 유일성) · 형식문법 · 유형 이론
집합론 집합( 원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계( 동치관계 · 순서 관계) · 순서쌍( 튜플) · 서수( 하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC( 선택공리) · 기수( 초한기수) · 절대적 무한
범주론 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성
계산가능성 이론 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수 · 계산
정리
드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 불완전성 정리 · 힐베르트의 호텔 · 연속체 가설
기타
예비사항( 약어 및 기호) · 벤 다이어그램 · 수학철학 · 이산수학·수리논리학 둘러보기 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 }}}}}}}}}}}}


전자기학
Electromagnetism
{{{#!wiki style="margin:0 -10px -5px; min-height:2em; word-break:keep-all"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px; letter-spacing: -1px" 		기초 개념
관련 수학 이론 <colbgcolor=#fff,#191919> [math(boldsymbol{nabla})] · 디랙 델타 함수 · 연속방정식 · 분리 벡터
전기와 자기 전자기력 · 전자기 유도 ( 패러데이 법칙) · 맥스웰 방정식 · 전자기파 · 포인팅 벡터 · 전자기학의 경계치 문제 · 전자기파 방사
정전기학 <colbgcolor=#fff,#191919> 전하 · 전기장 · 전기 변위장 · 전기 퍼텐셜 · 가우스 법칙 · 전기 쌍극자 모멘트 · 유전율 · 대전현상 · 정전용량 · 시정수 · 정전기 방전
정자기학 자성 · 자기장 · 자기장 세기 · 자기 퍼텐셜 · 자기 쌍극자 모멘트 · 로런츠 힘 · 홀 효과 · 비오-사바르 법칙 · 앙페르 법칙 · 투자율
구현체 자석( 전자석) · 발전기 · 전동기
'''[[회로이론|{{{#fff 전압 · 전류 · 전기 저항 ( 띠틈 ) · 전력 ( 전력량 ) · 직류 · 교류 · 키르히호프의 법칙 · 중첩의 원리 · 삼상
소자 수동소자 : 직류회로 · RLC회로 ( 커패시터 · 인덕터 · 레지스터), 변압기
능동소자 : 전원 · 다이오드 · 트랜지스터 · 연산 증폭기
응용 및 심화개념
관련 학문 상대론적 전자기학 · 양자 전기역학 · 응집물질물리학 · 고체물리학 · 전자공학 · 전기공학 · 제어공학 · 물리화학
토픽 광자 · 와전류 · 다중극 전개 · 전기음성도 · 반도체 · 맥스웰 변형 텐서 · 게이지 장( 역장 · 장이론) · 방전 · 물질파
음향 앰프 ( 파워앰프 · 프리앰프 · 인티앰프 · 진공관 앰프) · 데시벨 · 네퍼
열 반 데르 발스 힘( 분산력) · 복사 · 전도( 전도체 · 열전 효과) · 초전도체 · 네른스트 식
광학 렌즈 · 프리즘 · 거울 · 수차( 색수차) · 편광 · 분광학 · 산란 · 광전효과 · 색( 색의 종류)
전산 논리 연산 · 논리 회로 · CG · 폴리곤
생물 생체신호( 생체전기 · BCI) · 신경계( 막전위 · 활동전위 · 능동수송)
그 밖에
<colbgcolor=#fff,#191919> 물리학 관련 정보 · 틀:전기전자공학 · 전기·전자 관련 정보 · 틀:컴퓨터공학 }}}}}}}}}


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. 교환법칙 / 결합법칙 / 분배법칙3.3. 동일법칙(idempotent)3.4. 흡수법칙(absorption)3.5. 이중부정 법칙(involution)3.6. 드모르간 법칙(De Morgan law)3.7. 합의(Consensus) 법칙3.8. 그 밖의 연산 법칙
4. 연산 우선 순위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) 개수 n에 대해 2n개이다. 즉, 불 속의 원소 개수는 2의 제곱수대로 올라간다고 보면 된다.

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

2. 논리 연산의 종류

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

2.1. 부정 (NOT; ¬)

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

2.2. 논리곱 (AND; ∧)

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

2.3. 논리합 (OR; ∨)

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

2.4. 부정 논리곱 (NAND; ⊼)

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

2.5. 부정 논리합 (NOR; ⊽)

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

2.6. 배타적 논리합 (XOR; ⊻)

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

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

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

2.7. 동치 (EQV; ≡)

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

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

3. 성질[14]

3.1. 항등원(identity)

A·1 = A = 1·A
A+0 = A = 0+A

3.2. 교환법칙 / 결합법칙 / 분배법칙[15]

A+B=B+A
A·B=B·A
A⊕B = B⊕A
(A+B)+C=A+(B+C)
(A·B)C=A·(B·C)
(A⊕B)⊕C = A⊕(B⊕C)
A·(B+C)=A·B+A·C
A+(B·C)=(A+B)·(A+C)
A·(B⊕C) = A·B⊕A·C

산수랑 거의 똑같다. 다만 여기서 주의할 점은 분배 법칙에서 A+(B·C)=(A+B)·(A+C)가 된다는 것이다. 드모르간의 법칙 하단의 설명을 보면 쉽게 이해할 수 있다. 또한 NXOR을 포함하여 NAND, NOR 등 모든 부정 연산은 결합법칙이 성립하지 않는다.

3.3. 동일법칙(idempotent)[16]

A·A = A
A + A = A

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

3.4. 흡수법칙(absorption)

A+A·B=A
A·(A+B)=A

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

수학적 증명은
A·(A+B)
A·A + A·B (∵분배법칙)
A + A·B (∵동일법칙 A·A = A)
A·1 + A·B (∵항등원 A·1 = A)
A·(1 + B) (∵분배법칙)
A·1 (∵ B + 1 = 1)
A (∵항등원 A·1 = A)
위 식의 증명은 위의 증명에서 3번째 줄부터 같다.

3.5. 이중부정 법칙(involution)

(A')' = A

3.6. 드모르간 법칙(De Morgan law)

(A·B)'=A'+B'
(A+B)'=A'·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이다.

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

3.7. 합의(Consensus) 법칙

AB + BC + CA' = AB + CA'
(A + B)(B + C)(C + A') = (A + B)(C + A')

자세히 보면 가운데 마디가 사라진 것을 볼 수 있다.

위 식의 증명은
BC
1·BC (∵항등원 A·1 = A)
(A+A')·BC (∵A+A' = 1)
ABC + A'BC (∵분배법칙)
ABC + CA'B (∵교환법칙)
을 이용해서
AB + BC + CA'
AB + ABC + CA'B + CA'
(AB + AB·C) + (CA'·B + CA') (∵결합법칙)
(AB + AB·C) + (CA' + CA'·B) (∵교환법칙)
AB + CA' (∵흡수법칙 A+A·B=A)
아래식도 비슷하다.

3.8. 그 밖의 연산 법칙

A + A' = 1
A·A' = 0
A+1=1
A·0 = 0
(A⊕B)' = A⊕B' = A'⊕B
A'⊕B' = A⊕B
A+A'·B=A+B
A·(A'+B)=A·B

마지막 식의 증명
A·(A'+B)
A·A' + A·B (∵분배법칙)
0 + A·B (∵ A·A' = 0)
A·B (∵항등원 0+A = A)
그 위의 식도 비슷하다.

4. 연산 우선 순위

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

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

A·(B+C)=(A·B)+(A·C)=A·B+A·C

그리고 부정(NOT) 연산은 AND와 OR보다 연산 우선 순위가 높다.

결국 NOT > AND > OR의 연산 순서가 되겠다.

5. 관련 문서


[1] 원소가 두 개(Binary)뿐인 집합이라는 의미도 함의하고 있다. [2] 혹은 결괏값. [3] ~는 C언어에서도 마찬가지로 부정으로 사용되긴 하나, 논리 연산이 아닌 비트 연산이다. [4] 프라임이라 읽는다. 미분 기호로도 쓰인다. [5] 주의하자면 곱셈이 절대로 아니다! A and B. [6] A 논리곱 B. 이래도 헷갈린다(...) [7] A or B [8] [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)] [9] ((not A) and B) or (A and (not B)) 이래도 헷갈리긴 매한가지 [10] C언어에서 제곱은 math.h라는 헤더 파일을 include(포함)하고(#include <math.h>), pow(밑, 지수) 함수를 사용하면 가능하다. [11] PHP 5.6 이상이나 Python 등의 언어에서는 또 **로 지수를 표현하는 것이 가능하다. [12] 예를 들어, AX라는 레지스터를 0으로 초기화 할 땐 MOV AX,0을 써도 되지만 XOR AX,AX를 해도 된다는 의미이다. AX에 뭔 값이 들어있는지는 알 수 없지만, 같은 것끼지 연산시키면 무조건 0을 반환하는 XOR의 특성 상 해당 연산의 결과는 AX의 원래 값과는 상관 없이 항상 0이 된다. [13] A=A⊻B; B=A⊻B; A=A⊻B [14] 공리(axiom) 내지 전제(postulation)이라고도 부른다. [15] 영어로 각각 commutatitve, associative, distributive이다. [16] 멱등(冪等)법칙이라고도 한다.

분류