논리 연산

(부울 대수에서 넘어옴)

이 문단은 불 대수, 부울 대수, 논리 대수 항목으로도 들어올 수 있습니다.

부울 대수(Boolean Algebra)는 19세기 중반 영국의 수학자 조지 부울(George Boole, 1815년 11월 2일 ~ 1864년 12월 8일)이 고안하고 형식화한 대수 체계를 의미한다. 논리 연산(logical operation, logical connective)으로도 불리운다. 수리 논리학이나 컴퓨터공학과에서, 두 개의 상태인 참(1, T, True)과 거짓(0, F, False)으로 부울 연산(Boolean expression)이라 한다.[1]

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

전자과의 경우에는 플로트 상태니 3-state니 하는 용어를 볼 기회가 있을텐데 이 상태는 '비결정'상태라고 해서 0도 1도 아닌 상태를 말한다. 컴퓨터공학에서는 이런 상태를 다루지 않기 때문에 2비트 논리회로(00: False, 01, 10: Float, 11: True)를 써야 하므로 전자과가 회로도 짤 때 디지털 회로에 이런 값이 들어가지 않게 주의할 것.

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

1 논리 연산의 종류

들어가기 앞서 아래 결과가 이해가 안된다면 진리표(Truth Table)를 만들어서 확인해 볼수도 있다.. 만 변수(0또는 1)가 4개만 되도 단순히 AND 만 확인해보려고 해도 16개나 확인해봐야한다. 아래가 진리표다. 쉽게 말해 집합의 연산법칙에서 합집합을 +로, 교집합을 ·, 공집합을 0, 전체집합을 1, '을 여집합으로 바꾸었다고 생각하면 편하다.

A ∧ B (AND)
AB결과값
000
010
100
111

1.1 부정 (NOT; ¬)

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

NOT 연산 결과
입력값결과값
01
10

1.2 논리곱 (AND; ∧)

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

AND 연산 결과
입력값결과값
0 , 00
0 , 10
1 , 00
1 , 11

1.3 논리합 (OR; ∨)

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

OR 연산 결과
입력값결과값
0 , 00
0 , 11
1 , 01
1 , 11

1.4 부정 논리곱 (NAND; ↑)

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

NAND 연산 결과
입력값결과값
0 , 01
0 , 11
1 , 01
1 , 10

1.5 부정 논리합 (NOR; ↓)

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

NOR 연산 결과
입력값결과값
0 , 01
0 , 10
1 , 00
1 , 10

1.6 배타적 논리합 (XOR; ⊕)

두 명제 중 정확히 하나만 참이어야 참값을 돌려준다. C언어의 영향을 받은 프로그래밍 언어에서는 ^를 배타적 논리합 기호로 사용한다. 다만 일반적인 경우에는 ^가 제곱으로 사용되기 때문에 처음 프로그래밍 언어를 배우는 사람들은 제곱을 하려고 ^ 기호를 사용했다가 안드로메다로 가는 경우가 있다.(…)[5][6]

XOR 연산 결과
입력값결과값
0 , 00
0 , 11
1 , 01
1 , 10

1.7 동치 (EQV; =)

두 명제가 다 참이거나 다 거짓이면 참값을 돌려준다. 배타적 부정 논리합 (XNOR) 또는 배타적 논리곱이라고도 한다. 수학적으로는 크로네커 델타([math]\delta_{ij} = \left\{\begin{matrix} 0 \; \; \; \text{if} \; \; \; i \neq j \\ 1 \; \; \; \text{if} \; \; \; i = j \end{matrix}\right.[/math])로 정의돼 있다.

EQV 연산 결과
입력값결과값
0 , 01
0 , 10
1 , 00
1 , 11

2 성질

2.1 교환 / 결합 / 분배 법칙

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+A·C
A+(B·C)=(A+B)·(A+C)

산수랑 똑같다. 다만 여기서 주의할 점은 분배 법칙에서 A+(B·C)=(A+B)·(A+C)가 된다는 것이다. 왜냐면 보통 산수에서는 곱셈이 덧셈보다 먼저지만, 논리 연산에서는 곱과 합의 우선 순위가 똑같기 때문이다.

2.2 동일 법칙

A·A = A
A + A = A

계산하려는 두 숫자가 똑같으면 결과도 그 똑같은 값이 나온다는 뜻이다.

2.3 흡수 법칙

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

전기 회로에서 곱연산을 직렬로, 합연산을 병렬로 생각해보면 이해가 쉽다. B는 A와 병렬이라서 B가 끊어졌어도 A가 이어져 있으면 그대로 전기가 흐르기 때문에(1) 사실상 B는 없는 것이나 다름없고, 동시에 이어졌다가 끊어지는 걸 몇 개 씩 다는 것이나 그냥 그 스위치 하나만 다는 것이나 결국 똑같다기 때문에 식이 저렇게 A로 흡수되는 것이다.

더 간단히 쉽게 이해를 돕자면, 밑의 식을 예로 풀어서 해석하면

A·A + A·B
A·A = A 누승법칙, ∴ A + A·B
A + A · A + B
A + A·B

이렇게 되는 데 여기서 A = 1 , B = 0 혹은 A = 0 , B = 1 로 가정 해 보면 A 만 남게 된다.
맨 위의 식도 마찬가지다.

2.4 드모르간 법칙

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

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

2.5 Consensus 법칙

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

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

2.6 그 밖의 연산 법칙

A + A' = 1A·A' = 0
A·1 = AA·0 = 0
A+1=1A+0=A
A+A·B' = A

3 관련항목

  1. 참고로 백괴사전에서는 이 불 대수를 불(火) 대수로 해석해서 불 붙은 물건의 성질을 다루는 대수로 묘사했다(...) 링크
  2. 디지털 회로의 신호는 0과 1로 구성되어 있기 때문이다
  3. 프라임이라 읽는다. 미분 기호로도 쓰인다.
  4. 주의하자면 곱셈이 절대로 아니다!
  5. C언어에서 제곱은 math.h를 include하고 pow(밑, 지수) 함수를 사용하면 가능하다.
  6. PHP 5.6 한정으로 **로 지수 표현이 가능하다.