[include(틀:이산수학·수리논리학)] [목차] == 개요 == 불 대수(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에 대해 2^^n^^개이다. 즉, 불 속의 원소 개수는 2의 제곱수대로 올라간다고 보면 된다. [[집합]] 기호는 고안자의 이름을 따서 [math(\mathbb B)]로 표현한다.[* 원소가 두 개('''B'''inary)뿐인 집합이라는 의미도 함의하고 있다.] 아래의 연산과 함께 [[환(대수학)|환]]을 이룬다. == 논리 연산의 종류 == 시작하기 앞서, 처음 보는 연산의 경우 진리표(Truth Table)를 사용하면 비교적 단순한 연산의 결과는 직접 확인할 수 있다. 다만 변수의 개수가 늘어나면 확인해야 하는 값이 대폭 증가하기 때문에, 기초적인 이해를 돕는 이상의 활용은 어렵다. 아래의 진리표를 보자. ||<-3> A ∧ B (AND) || || A || B || 반환값[* 혹은 결괏값.] || || 0 || 0 || 0 || || 0 || 1 || 0 || || 1 || 0 || 0 || || 1 || 1 || 1 || === 부정 (NOT; ¬) === 말 그대로 부정(否定)이다. 즉, 참과 거짓을 뒤집는다. [[C언어]]의 영향을 받은 [[프로그래밍 언어]]에서는 일반적으로 !를 부정 연산자로 사용하며, 그 외에 ~A도 많은 프로그래밍 언어에서 사용되며, 필기나 서적 등에서는 A' [* 프라임이라 읽는다. [[미분]] 기호로도 쓰인다.]또는 A 위에 ㅡ를 그려넣은 [math(\bar{A} )] 기호가 주로 쓰인다. 불 보수(Boolean Complement)로도 불린다. 이 연산을 하는 회로는 따로 [[보수기]](inverter)라는 이름으로 불린다. ||<-2> NOT 연산 결과 || || 입력값 || 반환값 || || 0 || 1 || || 1 || 0 || === 논리곱 (AND; &) === 두 명제가 모두 참이어야 참값을 돌려준다. [[C언어]]의 영향을 받은 [[프로그래밍 언어]]에서는 일반적으로 &를 논리곱 연산자로 사용하며, 불 대수에서는 AND는 [[곱셈]]과 동치이다. 불 곱(Boolean Multiplication) 혹은 논리곱이라 부른다. 아래의 연산결과를 보면 왜 곱셈과 동치인지 쉽게 알 수 있을 것이다. AB[* 주의하자면 '''곱셈이 절대로 아니다'''! A '''and''' B.] 또는 A·B[* A 논리곱 B. ~~이래도 헷갈린다(...)~~]로 표시한다. ||<-2> AND 연산 결과 || || 입력값 || 반환값 || || 0 , 0 || 0 || || 0 , 1 || 0 || || 1 , 0 || 0 || || 1 , 1 || 1 || === 논리합 (OR; ∨) === 두 명제 중 어느 한 명제만 참이어도 참값을 돌려준다. [[C언어]]의 영향을 받은 [[프로그래밍 언어]]에서는 일반적으로 |를 논리합 연산자로 사용한다. 불 대수에서는 OR는 [[덧셈]]과 동치여서, 논리합(Boolean Addition)으로 부른다. 아래에서 보듯 '''1 + 1 = 1''' 임을 주의해야 한다. A+B[* A '''or''' B]로 표시한다. ||<-2> OR 연산 결과 || || 입력값 || 반환값 || || 0 , 0 || 0 || || 0 , 1 || 1 || || 1 , 0 || 1 || || 1 , 1 || 1 || === 부정 논리곱 (NAND; ↑) === '''N'''ot '''AND'''. 논리곱의 결과값을 부정한 것이다. 즉, 두 명제가 모두 참이면 거짓값을 돌려주고 그 외에는 참값을 돌려준다. 참고로 [[드모르간 법칙#s-3|NAND만을 통해 다른 논리 연산식을 모조리 구현할 수 있기 때문에]] 현재 사용되는 [[플래시 메모리]]들은 대부분이 NAND 회로로 구성되어 있다. ||<-2> NAND 연산 결과 || || 입력값 || 반환값 || || 0 , 0 || 1 || || 0 , 1 || 1 || || 1 , 0 || 1 || || 1 , 1 || 0 || === 부정 논리합 (NOR; ↓) === '''N'''ot '''OR'''. 논리합의 결과값을 부정한 것이다. 즉, 두 명제가 모두 거짓이면 참값을 돌려주고 그 외에는 거짓값을 돌려준다. NAND와 마찬가지로 NOR만으로 다른 논리 연산식을 모조리 구현할수 있기에 초기 [[플래시 메모리]]들은 대부분이 NOR 회로로 구성하였다. 근데 NAND 회로가 값이 싸다보니 이쪽은 자연스럽게 도태되었다. ||<-2> NOR 연산 결과 || || 입력값 || 반환값 || || 0 , 0 || 1 || || 0 , 1 || 0 || || 1 , 0 || 0 || || 1 , 1 || 0 || === 배타적 논리합 (XOR; ⊕) === 두 명제 중 정확히 하나만 참이어야, 혹은 두 명제의 참거짓 여부가 다를 때 참값을 돌려준다. A'B+AB'[* ((not A) and B) or (A and (not B)) --이래도 헷갈리긴 매한가지--]와 동치이다. [[C언어]]의 영향을 받은 [[프로그래밍 언어]]에서는 ^를 배타적 논리합 기호로 사용한다. 다만 일반적인 경우에는 ^가 제곱으로 사용되기 때문에 처음 프로그래밍 언어를 배우는 사람들은 제곱을 하려고 ^ 기호를 사용했다가 [[안드로메다]]로 가는 경우가 있다.(…)[* C언어에서 제곱은 math.h라는 [[헤더 파일]]을 include(포함)하고(#include <math.h>), pow(밑, 지수) 함수를 사용하면 가능하다.][* [[PHP]] 5.6 이상이나 [[Python]] 등의 언어에서는 또 **로 지수를 표현하는 것이 가능하다.] 이 방식으로 특정 '키'를 이용해 암호화를 하면 그 '키'로 복호화가 가능해서, 암호화 기법으로도 널리 사용된다. 비교 대상의 비트가 0이든 1이든 상관 없이 같기만 하면 0을 돌려준다는 특성을 이용하여 어셈블리어 등의 언어에서 어떤 레지스터나 변수를 0으로 초기화할 때 사용되기도 한다.[* 예를 들어, AX라는 레지스터를 0으로 초기화 할 땐 MOV AX,0을 써도 되지만 XOR AX,AX를 해도 된다는 의미이다. AX에 뭔 값이 들어있는지는 알 수 없지만, 같은 것끼지 연산시키면 무조건 0을 반환하는 XOR의 특성 상 해당 연산의 결과는 AX의 원래 값과는 상관 없이 항상 0이 된다.] 이런 특성때문에 XOR을 이용해 임시변수 없이 변수를 스왑하는 기법[* A=A⊕B; B=A⊕B; A=A⊕B]은 메모리사용량에서야 좀 이득을 보겠지만 실제론 거의 사용되지 않는다. 스왑하는 값이 같은 주소를 참조한다면 엉망이 되기 때문. 결합법칙이 성립하므로 n항연산으로 일반화 가능하다. 이 경우 n개의 입력중 참의 개수가 홀수이면 출력이 참이 되는 연산으로 정의된다. ||<-2> XOR 연산 결과 || || 입력값 || 반환값 || || 0 , 0 || 0 || || 0 , 1 || 1 || || 1 , 0 || 1 || || 1 , 1 || 0 || === 동치 (EQV; =) === 두 명제가 다 참이거나 다 거짓이면, 즉 두 명제의 진리값이 같으면 참값을 돌려준다. 배타적 논리합(XOR)의 부정이라고 할 수 있으므로 배타적 부정 논리합 (XNOR) 또는 배타적 논리곱이라고도 한다. 수학적으로는 [[크로네커 델타]]([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과 달리 결합법칙이 성립하지 않는다. ||<-2> EQV 연산 결과 || || 입력값 || 반환값 || || 0 , 0 || 1 || || 0 , 1 || 0 || || 1 , 0 || 0 || || 1 , 1 || 1 || == 성질[* 공리(axiom) 내지 전제(postulation)이라고도 부른다.] == === 항등원(identity) === || A·1 = A = 1·A || || A+0 = A = 0+A || === 교환법칙 / 결합법칙 / 분배법칙[* 영어로 각각 commutatitve, associative, distributive이다.] === || 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 등 모든 부정 연산은 결합법칙이 성립하지 않는다. === 동일법칙(idempotent)[* 멱등(冪等)법칙이라고도 한다.] === || A·A = A || || A + A = A || 계산하려는 두 숫자가 똑같으면 결과도 그 똑같은 값이 나온다는 뜻이다. A에 0을 대입했을 때도 성립하고 1을 대입했을 때도 성립하는 것으로 해당 성질을 증명할 수 있다. === 흡수법칙(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번째 줄부터 같다. === 이중부정 법칙(involution) === || (A')' = A || === [[드모르간 법칙]](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이다. 이걸 이용해 [[드모르간 법칙]]을 쉽게 증명할 수 있을 뿐만 아니라 성질 항목에 나와있는 한쌍의 공식이 서로를 유도할 수 있다는 걸 쉽게 보일 수 있다. === 합의(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) || 아래식도 비슷하다. === 그 밖의 연산 법칙 === || 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) || 그 위의 식도 비슷하다. == 연산 우선 순위 == 대수학에서 곱셈 연산이 덧셈 연산보다 우선이듯이, 논리 연산에서도 논리곱(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의 연산 순서가 되겠다. == 관련 문서 == * [[마인크래프트/레드스톤]] : 본격 게임속 논리 연산 시뮬레이터, [[http://youtu.be/0xkYXbgiNxY|누군가 아예 컴퓨터도 만들었다.]] * [[Oxygen Not Included/시설/자동화(Automation)]]: NOT, AND, OR은 기본, 용도에 따라 온갖 논리연산자를 이용해야한다. --회로도 직접 연결해야한다. 꼬이는 순간...-- * [[논리 회로]](logic circuit) * [[논리학 관련 정보]] [[분류:수리논리학]][[분류:논리학]]