| 이 문단은 불 대수, 부울 대수, 논리 대수 항목으로도 들어올 수 있습니다. |
부울 대수(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) | ||
| A | B | 결과값 |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
1.1 부정 (NOT; ¬)
말 그대로 부정(否定)이다. 즉, 참과 거짓을 뒤집는다. C언어의 영향을 받은 프로그래밍 언어에서는 일반적으로 !를 부정 연산자로 사용하며, 그 외에 ~A도 많은 프로그래밍 언어에서 사용되며, 필기나 서적 등에서는 A' [3]또는 A 위에 ㅡ를 그려넣은 [math]\bar{A} [/math] 기호가 주로 쓰인다. 부울 보수(Boolean Complement)로도 불린다.
| NOT 연산 결과 | |
| 입력값 | 결과값 |
| 0 | 1 |
| 1 | 0 |
1.2 논리곱 (AND; ∧)
두 명제가 모두 참이어야 참값을 돌려준다. C언어의 영향을 받은 프로그래밍 언어에서는 일반적으로 &를 논리곱 연산자로 사용하며, 불 대수에서는 AND는 곱셈과 동치이다. 부울곱(Boolean Multiplication)이라 부른다. 아래의 연산결과를 보면 왜 곱셈과 동치인지 쉽게 알 수 있을 것이다. AB[4] 또는 A·B로 표시한다.
| AND 연산 결과 | |
| 입력값 | 결과값 |
| 0 , 0 | 0 |
| 0 , 1 | 0 |
| 1 , 0 | 0 |
| 1 , 1 | 1 |
1.3 논리합 (OR; ∨)
두 명제 중 어느 한 명제만 참이어도 참값을 돌려준다. C언어의 영향을 받은 프로그래밍 언어에서는 일반적으로 |를 논리합 연산자로 사용한다. 불 대수에서는 OR는 덧셈과 동치여서, 논리합(Boolean Addition)으로 부른다. 아래에서 보듯 1 + 1 = 1 임을 주의해야 한다. A+B로 표시한다.
| OR 연산 결과 | |
| 입력값 | 결과값 |
| 0 , 0 | 0 |
| 0 , 1 | 1 |
| 1 , 0 | 1 |
| 1 , 1 | 1 |
1.4 부정 논리곱 (NAND; ↑)
Not AND. 논리곱의 결과값을 부정한 것이다. 즉, 두 명제가 모두 참이면 거짓값을 돌려주고 그 외에는 참값을 돌려준다. 참고로 NAND만을 통해 다른 논리 연산식을 모조리 구현할 수 있기 때문에 현재 사용되는 플래시 메모리들은 대부분이 NAND 회로로 구성되어 있다.
| NAND 연산 결과 | |
| 입력값 | 결과값 |
| 0 , 0 | 1 |
| 0 , 1 | 1 |
| 1 , 0 | 1 |
| 1 , 1 | 0 |
1.5 부정 논리합 (NOR; ↓)
NOT OR. 논리합의 결과값을 부정한 것이다. 즉, 두 명제가 모두 거짓이면 참값을 돌려주고 그 외에는 거짓값을 돌려준다. NAND와 마찬가지로 NOR만으로 다른 논리 연산식을 모조리 구현할수 있기에 초기 플래시 메모리들은 대부분이 NOR 회로로 구성하였다. 근데 NAND 회로가 값이 싸다보니 이쪽은 자연스럽게 안쓰게 됐다.
| NOR 연산 결과 | |
| 입력값 | 결과값 |
| 0 , 0 | 1 |
| 0 , 1 | 0 |
| 1 , 0 | 0 |
| 1 , 1 | 0 |
1.6 배타적 논리합 (XOR; ⊕)
두 명제 중 정확히 하나만 참이어야 참값을 돌려준다. C언어의 영향을 받은 프로그래밍 언어에서는 ^를 배타적 논리합 기호로 사용한다. 다만 일반적인 경우에는 ^가 제곱으로 사용되기 때문에 처음 프로그래밍 언어를 배우는 사람들은 제곱을 하려고 ^ 기호를 사용했다가 안드로메다로 가는 경우가 있다.(…)[5][6]
| XOR 연산 결과 | |
| 입력값 | 결과값 |
| 0 , 0 | 0 |
| 0 , 1 | 1 |
| 1 , 0 | 1 |
| 1 , 1 | 0 |
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 , 0 | 1 |
| 0 , 1 | 0 |
| 1 , 0 | 0 |
| 1 , 1 | 1 |
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' = 1 | A·A' = 0 |
| A·1 = A | A·0 = 0 |
| A+1=1 | A+0=A |
| A+A·B' = A | |
3 관련항목
- 마인크래프트/레드스톤 : 본격 게임속 논리 연산 시뮬레이터, 누군가 아예 컴퓨터도 만들었다.
- 논리회로
- 논리학 관련 정보