2017년 1월 25일 (수) 06:11에 Maintenance script님의 편집

2017-01-25T06:11:36Z

새 문서

[include(틀:프로젝트 문서,프로젝트=나무위키 컴퓨터 프로젝트)]
|| 이 문단은 [[불 대수]], [[부울 대수]], [[논리 대수]] 항목으로도 들어올 수 있습니다. ||

부울 대수(Boolean Algebra)는 19세기 중반 영국의 수학자 조지 부울(George Boole, 1815년 [[11월 2일]] ~ [[1864년]] [[12월 8일]])이 고안하고 형식화한 대수 체계를 의미한다. 논리 연산(logical operation, logical connective)으로도 불리운다. [[수리 논리학]]이나 [[컴퓨터공학과]]에서, 두 개의 상태인 참(1, T, True)과 거짓(0, F, False)으로 부울 연산(Boolean expression)이라 한다.[* 참고로 [[백괴사전]]에서는 이 불 대수를 불(火) 대수로 해석해서 불 붙은 물건의 성질을 다루는 대수로 묘사했다(...) [[http://uncyclopedia.kr/wiki/불_대수|링크]]]

[[프로그래밍]]에서는 조건에 의한 분기나 반복을 만드는 데 이용되고, [[논리회로|디지털 논리회로]][* 디지털 회로의 신호는 0과 1로 구성되어 있기 때문이다]를 배울때 유용하게 사용된다. 전자계통에선 논리 연산을 하는 소자를 게이트(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의 승수대로 올라간다고 보면 된다.

[목차]

== 논리 연산의 종류 ==
들어가기 앞서 아래 결과가 이해가 안된다면 진리표(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 ||

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

|||| NOT 연산 결과 ||
|| 입력값 || 결과값 ||
|| 0 || 1 ||
|| 1 || 0 ||

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

|||| AND 연산 결과 ||
|| 입력값 || 결과값 ||
|| 0 , 0 || 0 ||
|| 0 , 1 || 0 ||
|| 1 , 0 || 0 ||
|| 1 , 1 || 1 ||

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

|||| OR 연산 결과 ||
|| 입력값 || 결과값 ||
|| 0 , 0 || 0 ||
|| 0 , 1 || 1 ||
|| 1 , 0 || 1 ||
|| 1 , 1 || 1 ||

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

|||| NAND 연산 결과 ||
|| 입력값 || 결과값 ||
|| 0 , 0 || 1 ||
|| 0 , 1 || 1 ||
|| 1 , 0 || 1 ||
|| 1 , 1 || 0 ||

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

|||| NOR 연산 결과 ||
|| 입력값 || 결과값 ||
|| 0 , 0 || 1 ||
|| 0 , 1 || 0 ||
|| 1 , 0 || 0 ||
|| 1 , 1 || 0 ||

=== 배타적 논리합 (XOR; ⊕) ===
두 명제 중 정확히 하나만 참이어야 참값을 돌려준다. [[C언어]]의 영향을 받은 [[프로그래밍 언어]]에서는 ^를 배타적 논리합 기호로 사용한다. 다만 일반적인 경우에는 ^가 제곱으로 사용되기 때문에 처음 프로그래밍 언어를 배우는 사람들은 제곱을 하려고 ^ 기호를 사용했다가 [[안드로메다]]로 가는 경우가 있다.(…)[* C언어에서 제곱은 math.h를 include하고 pow(밑, 지수) 함수를 사용하면 가능하다.][* [[PHP]] 5.6 한정으로 **로 지수 표현이 가능하다.]

|||| XOR 연산 결과 ||
|| 입력값 || 결과값 ||
|| 0 , 0 || 0 ||
|| 0 , 1 || 1 ||
|| 1 , 0 || 1 ||
|| 1 , 1 || 0 ||

=== 동치 (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 ||

== 성질 ==
=== 교환 / 결합 / 분배 법칙 ===
|| 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)가 된다는 것이다. 왜냐면 보통 산수에서는 곱셈이 덧셈보다 먼저지만, 논리 연산에서는 곱과 합의 우선 순위가 똑같기 때문이다.

=== 동일 법칙 ===
|| A·A = A ||
|| A + A = A ||

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

=== 흡수 법칙 ===
|| 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 만 남게 된다.
맨 위의 식도 마찬가지다.

=== 드모르간 법칙 ===
|| (A·B)'=A'+B' ||
|| (A+B)'=A'·B' ||

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

=== Consensus 법칙 ===
|| '''AB''' + BC + '''CA' ''' = '''AB + CA' ''' ||
|| '''(A + B)'''(B + C)'''(C + A')''' = '''(A + B)(C + A')''' ||

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

=== 그 밖의 연산 법칙 ===
|| A + A' = 1 || A·A' = 0 ||
|| A·1 = A || A·0 = 0 ||
|| A+1=1 || A+0=A ||
|||| A+A·B' = A ||

== 관련항목 ==
* [[마인크래프트/레드스톤]] : 본격 게임속 논리 연산 시뮬레이터, [[http://youtu.be/0xkYXbgiNxY|누군가 아예 컴퓨터도 만들었다.]]
* [[논리회로]]
* [[논리학 관련 정보]]

[[분류:수리논리학]][[분류: 논리학]]

논리 연산 - 편집 역사

2017년 1월 25일 (수) 06:11에 Maintenance script님의 편집