| 논리학 Logic | |||
| {{{#!wiki style="margin: -0px -10px -5px; min-height: 28px" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -6px -1px -11px;" | <colbgcolor=#2ab5b5> 형식 논리 | 명제 논리(논리 연산 · 삼단논법(정언삼단논법) · 순환 논법 · 대당 사각형) ·정언 논리 · 공리 · 진릿값 · 조건문 · 필요조건과 충분조건 · 술어 논리 · 논증(논증의 재구성) · 모순 · 역설 · 논리적 오류(형식적 오류) · 존재함축 · 변증법 | |
| <colcolor=#000,#fff><keepall> 비표준 논리 | 직관 논리 · 양상논리 · 초일관 논리 · 다치논리(퍼지논리) · 선형논리 · 비단조 논리 | ||
| <keepall> 메타 논리 | 집합론 · 완전성 정리 · 불완전성 정리 | ||
| 비형식 논리 | 딜레마(흑백논리) | ||
| <keepall> 비형식적 오류 | 귀납적 오류 · 심리적 오류 · 언어적 오류 · 자료적 오류 · 양비론 · 진영논리 · 편견 및 고정관념 · 궤변 · 거짓 등가성 · 거짓 딜레마 | ||
| 분야 | 수학철학 · 수리논리학 | ||
| 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 · 수리논리학 둘러보기 | |||
1. 개요2. 원소3. 종류
3.1. 부정 (NOT; ¬)3.2. 논리곱 (AND; ∧)3.3. 논리합 (OR; ∨)3.4. 부정 논리곱 (NAND; ⊼)3.5. 부정 논리합 (NOR; ⊽)3.6. 배타적 논리합 (XOR; ⊻)3.7. 함의 (IMPLY; →)3.8. 동치 (EQV; ≡)
4. 성질5. 연산 법칙(law)5.1. 교환법칙(commutative)5.2. 결합법칙(associative)5.3. 분배법칙(distributive)5.4. 멱등법칙(idempotent)5.5. 흡수법칙(absorption)5.6. 이중부정 법칙(involution)5.7. 드모르간 법칙(de Morgan's)5.8. 합의 법칙(consensus)5.9. 흡수원(Absorbing Element)5.10. 자신과 자신의 부정의 연산5.11. 기타 연산 법칙
6. 활용7. 기타8. 관련 문서9. 둘러보기1. 개요
論理演算 / Logical operation19세기 중반 영국의 수학자 조지 불이 고안하고 형식화한 대수적 구조 및 그 위에서 성립하는 연산 체계. 고안자의 이름을 따 불 대수(Boolean algebra), 불 연산(Boolean operation), 불 환(Boolean ring)라고도 한다.[1]
2. 원소
불 대수는 단 두 개의 원소를 가진 대수적 구조이며, 그 원소는 서로 같지 않은 그 무엇도 될 수 있다. 편의상 [math(\{0, 1\})]을 자주 사용하지만 경우에 따라서는 [math(\{{\rm False}, {\rm True}\})] 또는 [math(\{\mathrm F,\mathrm T\})] 를 쓰기도 하며, 어떤 방식을 사용하든 아래 연산이 성립한다면 해당 구조는 불 대수와 동치이다.집합 자체의 기호는 고안자의 이름을 따서 [math(\mathbb B)][2]로 표현한다. 흔히 이 집합을 불리언(Boolean)이라고 읽으며, 해당 집합의 원소들을 뜻하기도 한다. 아래의 연산과 함께 환을 이룬다.
| 0 = False(F) |
| 1 = True(T) |
#!if (문단 == null) == (앵커 == null)
를#!if 문단 != null & 앵커 == null
의 [[진릿값#s-|]]번 문단을#!if 문단 == null & 앵커 != null
의 [[진릿값#|]] 부분을3. 종류
논리 연산의 가장 기본적인 3개 연산은 부정(NOT), 논리곱(AND), 논리합(OR)이다.이들 3개 연산의 진리표는 다음과 같다.
||<tablealign=left><tablebordercolor=#ccc,#444><bgcolor=#ddd,#666><-2> NOT([math(\neg)]) ||
| [math(A)] | [math(\neg A)] |
| T | F |
| F | T |
||<tablebordercolor=#ccc,#444><bgcolor=#ddd,#666><-3> AND([math(\wedge)]) ||
| [math(A)] | [math(B)] | [math(A\wedge B)] |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
||<tablealign=left><tablebordercolor=#ccc,#444><bgcolor=#ddd,#666><-3> OR([math(\vee)]) ||
| [math(A)] | [math(B)] | [math(A\vee B)] |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
처음 보는 연산의 경우 진리표(truth table)를 사용하면 비교적 단순한 연산의 결과는 직접 확인할 수 있다. 다만 변수의 개수가 늘어나면 확인해야 하는 값이 대폭 증가하기 때문에, 기초적인 이해를 돕는 이상의 활용은 어렵다. 아래의 진리표를 보자.
이진 이항연산에 대해 2의 4제곱, 즉 총 16가지 진리표가 존재할 수 있으며, 단항연산(4종)이나 상수(2종)로 환원되지 않는 10가지 연산의 목록은 다음과 같다. 즉, A와 B 모두 결과에 영향을 주는 연산으로, 사실상의 유의미한 이항연산이다. 이 중에서 NAND, NOR는 하나만으로 기본 연산 NOT, AND, OR을 모두 구성할 수 있다. 나머지 8가지는 혼자서 NOT을 만들지 못한다.
| 연산자 | 이름 | 진리표 (A,B) | |||
| (T,T) | (T,F) | (F,T) | (F,F) | ||
| [math(\vee)] | 논리합(OR) | T | T | T | F |
| [math(\wedge)] | 논리곱(AND) | T | F | F | F |
| [math(\overline\vee)] | 부정 논리합(NOR)[3] | F | F | F | T |
| [math(\overline\wedge)] | 부정 논리곱(NAND)[4] | F | T | T | T |
| [math(\underline\vee)] | 배타적 논리합(XOR)[5] | F | T | T | F |
| [math(\leftrightarrow,\, \equiv)] | 동치(EQUIV)[6] | T | F | F | T |
| [math(\rightarrow)] | 함의(IMP, 또는 IMPLY) | T | F | T | T |
| [math(\leftarrow)] | 역(CONV)[7] | T | T | F | T |
| [math(\nrightarrow)] | 비함의(NIMPLY)[8] | F | T | F | F |
| [math(\nleftarrow)] | 역비함의[9] | F | F | T | F |
아래 6개의 진리표는 단항연산자 또는 상수로 환원 가능하므로, 이항연산자로서의 의미가 없다. 단항연산자는 A, B중 하나만이 결과에 영향을 주고, 상수는 A, B 둘 다 결과에 영향을 주지 않기 때문이다.
| 종류 | 연산자 | 진리표 (A,B) | |||
| (T,T) | (T,F) | (F,T) | (F,F) | ||
| 단항연산 | [math(A)] | T | T | F | F |
| [math(\neg A)] | F | F | T | T | |
| [math(B)] | T | F | T | F | |
| [math(\neg B)] | F | T | F | T | |
| 상수 | [math(\mathrm{T})] | T | T | T | T |
| [math(\mathrm{F})] | F | F | F | F | |
3.1. 부정 (NOT; ¬)
참과 거짓을 뒤집는 단항연산이다.| NOT([math(\neg)]) | |
| [math(A)] | [math(\neg A)] |
| T | F |
| F | T |
- 다른 표기법
- [math(\bar{A})], [math(A')][10], [math(\sim A)](중등교육)
- [math(!A)](컴퓨터 공학/프로그래밍 언어)
논리 연산에서 단항연산으로 가능한 것은 4종류밖에 없는데, 부정을 제외한 나머지 3가지는 항등연산[11], 항상 참([math(\top)]), 항상 거짓([math(\bot)])밖에 없어 실용적인 의미가 있는 단항연산은 부정 밖에 없다.
이 연산을 하는 회로는 따로 보수기(inverter)라는 이름으로 불린다.
3.2. 논리곱 (AND; ∧)
두 명제가 모두 참이어야 참값을 돌려준다.| AND([math(\wedge)]) | ||
| [math(A)] | [math(B)] | [math(A\wedge B)] |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
- 다른 표기법
- [math(AB)], [math(A\cdot B)]
- 컴퓨터 공학/프로그래밍 언어: [math(A\&B)][12], [math(A\&\&B)]
C언어의 영향을 받은 프로그래밍 언어에서는 일반적으로
&[13] 또는 &&를 논리곱 연산자로 사용하며, 불 대수에서는 AND는 곱셈과 동치이다. 불 곱(Boolean multiplication) 혹은 논리곱이라 부른다. 아래의 연산결과를 보면 왜 곱셈과 동치인지 쉽게 알 수 있을 것이다. [math(AB)] 또는 [math(A\cdot B)]으로도 표시한다.3.3. 논리합 (OR; ∨)
두 명제 중 하나 이상 참일 때 참값을 돌려준다. 그렇기 때문에 자연 언어(영어)의 or보다는 and/or와 같다고 볼 수 있다.[14]| OR([math(\vee)]) | ||
| [math(A)] | [math(B)] | [math(A\vee B)] |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
불 대수에서는 OR는 덧셈과 동치여서, 논리합(Boolean addition)으로 부른다.
[math(A+B)][16]로도 표시하는데, 참값을 [math(\boldsymbol{1})], 논리합을[math(+)]으로 표기할 때 [math(boldsymbol{1} + boldsymbol{1} = boldsymbol{1})]로 자연수의 덧셈과 다름에 주의해야 한다.
3.4. 부정 논리곱 (NAND; ⊼)
Not AND. 논리곱의 결과값을 부정한 것이다. 즉, 두 명제가 모두 참이면 거짓값을 돌려주고 그 외에는 참값을 돌려준다.| NAND([math(\barwedge)]) | ||
| [math(A)] | [math(B)] | [math(A\barwedge B)] |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | T |
NAND만을 통해 다른 논리 연산식을 모조리 구현할 수 있기 때문에 컴퓨터 공학에서는 NAND만 있으면 모든 논리 회로를 만들 수 있다는 'NAND 유니버설'(NAND universal)의 시작점이다. [17] 현재 사용되는 플래시 메모리들은 대부분이 NAND 회로로 구성되어 있다.
3.5. 부정 논리합 (NOR; ⊽)
Not OR. 논리합의 결과값을 부정한 것이다. 즉, 두 명제가 모두 거짓이면 참값을 돌려주고 그 외에는 거짓값을 돌려준다.| NOR([math(\overline\vee)]) | ||
| [math(A)] | [math(B)] | [math(A\overline\vee B)] |
| T | T | F |
| T | F | F |
| F | T | F |
| F | F | T |
NAND와 마찬가지로 NOR만으로 다른 논리 연산식을 모조리 구현할 수 있기에 초기 플래시 메모리들은 대부분이 NOR 회로로 구성하였다. 그러나 NAND 회로가 훨씬 저렴해 이쪽은 자연스럽게 도태되었다. 부정은 NAND와 같은 방식으로, AND와 OR은 반대 방식으로 조합하면 된다.
3.6. 배타적 논리합 (XOR; ⊻)
eXclusive OR. 두 명제 중 정확히 하나만 참이어야 하는 경우. 즉 두 명제의 참 거짓 여부가 다를 때 참값을 돌려준다. [math(A'B+AB')][18]와 동치이다.[19] 논리학에서는 기호 [math(\veebar)]를 사용하지만, 공학에서는 [math(\oplus)][20]를 사용한다.C언어의 영향을 받은 프로그래밍 언어에서는
^를 배타적 논리합, 배타적 비트합 기호로 사용한다. 다만 일반적인 경우에는 ^가 제곱으로 사용되기 때문에 처음 프로그래밍 언어를 배우는 사람들은 제곱을 하려고 ^ 기호를 사용했다가 낭패를 겪는 경우가 있다.(…)[21][22] 이 방식으로 특정 '키'를 이용해 암호화를 하면 그 '키'로 복호화가 가능해서, 암호화 기법으로도 널리 사용된다. 비교 대상의 비트가 0이든 1이든 상관 없이 같기만 하면 0을 돌려준다는 특성을 이용하여 어셈블리어 등의 언어에서 어떤 레지스터나 변수를 0으로 초기화할 때 사용되기도 한다.[23] 이런 특성 때문에 XOR을 이용해 임시 변수 없이 변수를 스왑하는 기법[24]은 메모리 사용량에서야 좀 이득을 보겠지만 실제론 거의 사용되지 않는다. 스왑하는 값이 같은 주소를 참조한다면 엉망이 되기 때문.결합법칙이 성립하므로 n항연산으로 일반화 가능하다. 이 경우 n개의 입력 중 참의 개수가 홀수이면 출력이 참이 되는 연산으로 정의된다. 하지만 배타적 부정 논리합은 결합법칙이 성립하지 않으므로, n개의 입력 중 참의 개수가 짝수일 때 출력이 참이 되는 연산은 배타적 논리합으로 결합한 식 전체에 부정을 취해야만 한다.
| XOR([math(\veebar)]) | ||
| [math(A)] | [math(B)] | [math(A\veebar B)] |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
3.7. 함의 (IMPLY; →)
Implication. A→B에서 A가 참이고 B가 거짓일 때에만 거짓을 돌려준다. 즉 A가 아니거나 B라는 뜻으로, (not A) or B와 같다.| IMPLY([math(\rightarrow)]) | ||
| [math(A)] | [math(B)] | [math(A\rightarrow B)] |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
식 [math(A \rightarrow B)]는 [math(A)]가 [math(B)]의 충분조건임을 나타낸다.
일반적으로 "A이면 B이다."로 번역되는데, A가 거짓이고 B가 거짓이어도 참이라는 점([math(\mathrm{F} \rightarrow \mathrm{F} = \mathrm{T})])이 의아할 수 있다.
다음 문장(또는 수식)을 보자.
{{{#!wiki style="display:inline; border-bottom: 1px solid #f84" dark-style=" border-bottom: 1px solid #fc8"
[math(x)]가 3보다 크면}}}(A) [math(x)]는 2보다 크거나 같다
(B). (단, [math(x)]는 자연수)[math(x>3 \rightarrow x\ge2\quad (x\in\N))]
위 명제는 [math(x)]에 관계 없이 참이므로, 위 명제의 [math(x)]에 수를 대입해서 다음과 같이 만들어도 참이다.
| [math(x)] | 대입 후의 문장 | 상황 |
| 5 | [math(5 > 3)](T) 이면 [math(5 \ge 2)](T)이다. | T → T |
| 3 | [math(2 > 3)](F) 이면 [math(2 \ge 2)](T)이다. | F → T |
| 1 | [math(1 > 3)](F) 이면 [math(1 \ge 2)](F)이다. | F → F |
이와 같이 A와 B 모두 거짓인 경우에도 "A이면 B이다."([math(A \rightarrow B)])라는 문장은 참이며, [math(A \rightarrow B)]가 거짓인 상황은 A가 참이고 B가 거짓인 상황밖에 없다.
3.8. 동치 (EQV; ≡)
두 명제가 다 참이거나 다 거짓이면, 즉 두 명제의 진리값이 같으면 참값을 돌려준다. 배타적 논리합(XOR)의 부정이라고 할 수 있으므로 부정 배타적 논리합 또는 배타적 부정 논리합(XNOR, NXOR)이라고도 한다. 논리학에서는 기호 [math(\equiv)]를 사용하나, 논리곱의 아래에 밑줄을 그은 [math(\underline{\wedge})] 혹은 배타적 논리합 기호의 위에 밑줄을 그은 [math(\overline\veebar)]를 사용하기도 하고, 공학에서는 [math(⊙)]를 쓰기도 한다. EQV는 XOR와 달리 결합법칙이 성립하지 않는다.수학적으로는 크로네커 델타([math(\delta_{ij} = \left\{\begin{matrix} 0 \; \; \; \text{if} \; \; \; i \neq j \\ 1 \; \; \; \text{if} \; \; \; i = j \end{matrix}\right.)])로 정의돼 있다. C언어 및 그 파생 언어에서 '
='는 대입(:=)을 의미하므로 동치 연산자를 '=='로 표기한다. [math((A\underline{\wedge}B)= AB+A'B')]와 동치이다.| EQUIV([math(\equiv)]) | ||
| [math(A)] | [math(B)] | [math(A\equiv B)] |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
4. 성질
공리(axiom) 또는 전제(postulation)라고도 부른다.4.1. 항등원(identity)
| [math(A\cdot 1 = A = 1\cdot A)] [math(A+0 = A = 0+A)] |
4.2. 연산 우선 순위
NOT > AND > OR 이다.- 부정(NOT) 연산은 AND와 OR보다 연산 우선 순위가 높다.
- 대수학에서 곱셈 연산이 덧셈 연산보다 우선이듯이, 논리 연산에서도 논리곱(AND)이 논리합(OR) 보다 연산 순위가 높다.
분배법칙의 아래 두 식 중에 첫 번째 식의 우변에는 괄호가 없다. 이는 AND가 OR보다 연산 우선 순위가 높기 때문이다. 괄호가 생략된 것이라 보아도 되는데 [math(A\cdot B)]와 [math(A\cdot C)]에 대한 괄호의 존재 여부는 우변의 결과에 영향을 미치지 않는다.
| [math(A\cdot (B+C)=A\cdot B+A\cdot C)] [math(A+(B\cdot C)=(A+B)\cdot (A+C))] |
| [math(A\cdot (B+C)=(A\cdot B)+(A\cdot C)=A\cdot B+A\cdot C)] |
4.3. 쌍대성 원리(principle of duality)
불 대수의 모든 등식에서 AND([math(\cdot)])와 OR([math(+)]), 그리고 0과 1을 서로 맞바꾸어도 그 등식은 여전히 성립한다는 원리이다. 불 대수의 정의로부터 도출되는 성질이며, 이렇게 변환된 식을 원래 식의 쌍대(Dual)라고 한다.이 원리 때문에 후술할 '연산 법칙'의 수식들이 모두 쌍으로 존재한다.
- 항등원: [math(A + 0 = A)] [math(\leftrightarrow)] [math(A \cdot 1 = A)]
- 분배법칙: [math(A \cdot (B + C) = A \cdot B + A \cdot C)] [math(\leftrightarrow)] [math(A + (B \cdot C) = (A + B) \cdot (A + C))]
변환 방법은 다음과 같다.
- [math(\cdot)] (AND) [math(\leftrightarrow)] [math(+)] (OR)
2. [math(1)] (True) [math(\leftrightarrow)] [math(0)] (False)
3. 변수([math(A, B, ...)])는 그대로 둔다. (부정을 취하지 않는다)
드모르간 법칙과는 비슷해 보이지만 다르다. 드모르간 법칙은 변수까지 모두 부정(NOT)을 취하지만, 쌍대성 원리는 변수는 건드리지 않고 연산자와 항등원만 교체한다는 점에서 차이가 있다.
| 구분 | 수식 |
| 원본 식 | [math(f(A, B, \cdot, +, 1, 0))] |
| 쌍대(Dual) | [math(f(A, B, +, \cdot, 0, 1))] |
| 드모르간(Complement) | [math(f(A', B', +, \cdot, 0, 1))] |
5. 연산 법칙(law)
혼동 방지를 위해, 다음 기호만을 사용하여 표기한다.| 연산 | 표기 |
| NOT | [math(')] |
| AND | [math(\cdot)] |
| OR | [math(+)] |
| XOR | [math(\oplus)] |
5.1. 교환법칙(commutative)
| [math(A+B=B+A)] [math(A\cdot B=B\cdot A)] [math(A\oplus B = B\oplus A)] |
NAND, NOR, EQV(NXOR)도 교환법칙이 성립한다.
5.2. 결합법칙(associative)
| [math((A+B)+C=A+(B+C))] [math((A\cdot B)C=A\cdot (B\cdot C))] [math((A\oplus B)\oplus C = A\oplus (B\oplus C))] |
동치 연산(EQV)이라고도 하는 NXOR을 포함하여, NAND, NOR 등 모든 부정 연산은 결합법칙이 성립하지 않는다.
5.3. 분배법칙(distributive)
| [math(A\cdot (B+C)=A\cdot B+A\cdot C)] [math(A+(B\cdot C)=(A+B)\cdot (A+C))] [math(A\cdot (B\oplus C) = A\cdot B\oplus A\cdot C)] |
논리연산의 분배법칙 결과는 [math(A+(B\cdot C)=(A+B)\cdot (A+C))]가 된다. 드모르간 법칙 하단의 설명을 보면 쉽게 이해할 수 있다.
5.4. 멱등법칙(idempotent)
| [math(A\cdot A = A)] [math(A + A = A)] |
멱등성은 계산하려는 두 숫자가 똑같으면 결과도 그 똑같은 값이 나온다는 뜻이다. [math(A)]에 0을 대입했을 때도 성립하고 1을 대입했을 때도 성립하는 것으로 해당 성질을 증명할 수 있다.
nand, nor는 반대로 자기 자신과 연산하면 자기 자신의 부정이 나온다. 이것이 바로 nand, nor만으로 and, or, not을 모두 만들 수 있는 이유이기도 하다.
5.5. 흡수법칙(absorption)
| [math(A+A\cdot B=A)] [math(A\cdot (A+B)=A)] |
두 흡수법칙 식의 증명은 아래와 같다. 증명의 3행에 흡수법칙의 위쪽 식이 등장한다.
| [math(\def\arraystretch{1.5} \begin{array}{clr} &A \cdot (A+B) &\\ =&A \cdot A + A \cdot B &\because 분배법칙\\ =&A + A\cdot B &\because 동일법칙\ A\cdot A = A\\ =&A\cdot 1 + A\cdot B &\because 항등원\ A\cdot 1 = A\\ =&A\cdot (1 + B) &\because 분배법칙\\ =&A\cdot 1 &\because B + 1 = 1\\ =&A &\because 항등원\ A\cdot 1 = A\\ \end{array})] |
5.6. 이중부정 법칙(involution)
| [math((A')' = A)] |
이 법칙을 이용하여 삼중부정 등 홀수 번 부정은 단일 부정과 같고, 이중부정, 사중부정 등 짝수 번 부정은 원래의 논리값과 같음을 알 수 있다.
5.7. 드모르간 법칙(de Morgan's)
| [math((A \cdot B)'=A'+B')] [math((A+B)'=A' \cdot B')] |
사실 머리를 좀 굴려보면 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이다.
이걸 이용해 드모르간 법칙을 쉽게 증명할 수 있을 뿐만 아니라 성질 항목에 나와있는 한쌍의 공식이 서로를 유도할 수 있다는 걸 쉽게 보일 수 있다.
5.8. 합의 법칙(consensus)
| [math(AB + {\color{red}BC} + CA' = AB + CA')] [math((A + B){\color{red}(B + C)}(C + A') = (A + B)(C + A'))] |
수학적으로는 논리식의 간소화를 위해 사용되지만, 공학적 관점에서는 회로의 안정성을 확보하고 글리치(glitch)를 방지하기 위해 이 정리를 역으로 이용하여 합의항을 추가하기도 한다.
증명은 아래와 같다.
| 우선 [math(\def\arraystretch{1.5} \begin{array}{clr} &BC&\\ =&1\cdot BC &\because 항등원\ A\cdot 1 = A\\ =&(A+A')\cdot BC &\because A+A' = 1\\ =&ABC+ A'BC &\because 분배법칙\\ =&ABC + CA'B &\because 교환법칙\end{array})] 임을 이용한다. [math(\def\arraystretch{1.5} \begin{array}{clr} &AB + BC + CA'&\\ =&AB + ABC + CA'B + CA'&\\ =&(AB+AB\cdot C) + (CA'\cdot B + CA') &\because 결합법칙\\ =&(AB + AB\cdot C) + (CA' + CA'\cdot B) &\because 교환법칙\\ =&AB + CA' &\because 흡수법칙\ A+A\cdot B = A\end{array})] |
| [math(\def\arraystretch{1.5} \begin{array}{clr} &B+C&\\ =&0 + B + C &\because 항등원\ A+0 = A\\ =&A A' + B + C &\because A A' = 0\\ =&(A + B + C)(A' + B + C) &\because 분배법칙\\ =&(A + B + C)(C + A' + B) &\because 교환법칙\end{array})] 임을 이용한다. [math(\def\arraystretch{1.5} \begin{array}{clr} &(A + B)(B + C)(C + A')&\\ =&(A + B)(A + B + C)(C + A' + B)(C + A')&\\ =&(A + B)(A + B + C) \cdot (C + A' + B)(C + A') &\because 결합법칙\\ =&(A + B)(A + B + C) \cdot (C + A')(C + A' + B) &\because 교환법칙\\ =&(A + B)(C + A') &\because 흡수법칙\ A(A+B)=A\end{array})] |
5.9. 흡수원(Absorbing Element)
| [math(A+1=1)] |
| [math(A\cdot 0 = 0)] |
논리곱에서는 0, 논리합에서는 1이 흡수원이다. 항등원은 논리곱이 1, 논리합이 0인 것과는 대조적이다.
5.10. 자신과 자신의 부정의 연산
| [math(A + A' = 1)] |
| [math(A\cdot A' = 0)] |
자신과 자신의 부정을 연산했을 때 항상 1이 되는 경우: or, nand, xor
자신과 자신의 부정을 연산했을 때 항상 0이 되는 경우: and, nor, eqv(xnor)
5.11. 기타 연산 법칙
| [math((A\oplus B)' = A\oplus B' = A'\oplus B)] [math(A'\oplus B' = A\oplus B)] |
| [math(A+A'\cdot B=A+B)] [math(A\cdot (A'+B)=A\cdot B)] |
증명은 다음과 같다.
| [math(\def\arraystretch{1.5} \begin{array}{clr} &A+A'\cdot B\\ =&A\cdot(B+1) + A'\cdot B &\because B+1=1\\ =&A\cdot B + A + A'\cdot B = 0\\ =&A+B\cdot(A+A')=A+B &\because A+A'=1\end{array})] [math(\def\arraystretch{1.5} \begin{array}{clr} &A\cdot (A'+B)&\\ =&A\cdot A' + A\cdot B &\because 분배법칙\\ =&0 + A\cdot B &\because A\cdot A' = 0\\ =&A\cdot B &\because 항등원\ 0 + A = A\end{array})] |
6. 활용
수리논리학이나 컴퓨터과학에서는 두 개의 상태인 참(1, T, true)과 거짓(0, F, false)을 사용하는 연산을 불 연산(Boolean expression)이라 한다. 불 대수의 출현 이후로 논리학은 기호논리학의 성향이 강해지기 시작한다.이산수학에서는 속(lattice) 중 complementary lattice이며 distributive lattice인 lattice를 불 속(Boolean lattice)이라 하며 이를 대수(algebra)식으로 나타낸 것을 불 대수(Boolean algebra)라고 한다. 불 속의 원소 개수는 해당 원자(atom) 개수 [math(n)]에 대해 [math(2^n)]개이다. 즉, 불 속의 원소 개수는 2의 제곱수대로 올라간다고 보면 된다.
프로그래밍에서는 조건에 의한 분기나 반복을 만드는 데 이용되고, 디지털 논리 회로를 배울 때 유용하게 사용된다. 디지털 회로의 신호는 0과 1로만 구성되어 있기 때문이다. 전자계통에선 논리 연산을 하는 소자를 게이트(gate)라고 하며 트랜지스터 여러 개를 조합해서 만들 수 있다. 이를 임의의 [math(k)]차 비트열에 대해 성립하도록 확장한 것이 비트 연산이다.
7. 기타
불 대수는 집합으로 해석할 수 있다. [math(A)], [math(B)], [math(C)] 등 문자를 전체집합 [math(U=\{0, 1\})]의 공집합이 아닌 진부분집합으로 생각할 때, 논리합(or)은 합집합으로, 논리곱(and)는 교집합으로, 부정(not)은 여집합으로[25][26], 배타적 논리합(xor)은 대칭차집합으로 생각할 수 있다.8. 관련 문서
- 비트 연산
- 논리 회로
- 논리학 관련 정보
- 마인크래프트/레드스톤: 본격 게임 속 논리 연산 시뮬레이터, 누군가 아예 컴퓨터도 만들었다.
- Oxygen Not Included/건조물/자동화: NOT, AND, OR은 기본, 용도에 따라 온갖 논리연산자를 이용해야 한다.
회로도 직접 연결해야 한다. 꼬이는 순간... - 러스트(게임)/전기 및 함정: 게임 내 전기 시스템에 논리 게이트 역할을 하는 부품들이 존재한다.
9. 둘러보기
| 수학기초론 Foundations of Mathematics | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 다루는 대상과 주요 토픽 | ||
| 수리논리학 | 논리 · 논증{귀납논증 · 연역논증 · 귀추 · 유추} · 정리(보조정리) · 공리 및 공준 · 증명{반증 · PWW · 자명함 · 귀류법 · 수학적 귀납법 · 더블 카운팅 · 자동정리증명(증명보조기)} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문(조각적 정의) · 명제 논리(명제 · 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리(존재성과 유일성) · 형식문법 · 타입 이론 · 모형 이론 | ||
| 집합론 | 집합(원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계{이항 관계 · 동치관계} · 대칭성 · 순서론{순서 관계(부분 순서 · 하세 다이어그램) · 격자} · 순서쌍(튜플) · 함수 · 서수(큰 가산서수 · 초한귀납법) · 수 체계 · ZFC 공리계(선택공리) · NBG 공리계 · 기수(초한기수) · 초한수 · 절대적 무한 · 모임 · 첨수 집합족 | ||
| 범주론 | 범주(여러 가지 범주) · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성 | ||
| 계산 가능성 이론 | 계산 · 오토마타 · 튜링 머신 · 바쁜 비버 · 정지 문제 · 재귀함수 | ||
| 정리 | |||
| 드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 초른의 보조정리 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 퍼스의 법칙 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리(괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리 | |||
| 기타 | |||
| 예비사항(약어 및 기호) · 추상화 · 동형(수학) · 벤 다이어그램 · 수학철학 | |||
| 틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 | }}}}}}}}} | ||
| [[이론 컴퓨터 과학|'''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"]] | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36,#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 · 디지털 물리학 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법, 분할 정복 알고리즘) | ||||
| 정보이론 | 정보 엔트로피 · 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타프로그래밍 · 람다 대수 · 타입 이론 · 프로그래밍 언어 의미론 · 어휘 분석 · 파싱 · 구문 트리(완전 구문 트리 · 추상 구문 트리) · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set) · 트리^이진 트리(레드-블랙 트리, 힙), B-트리, 피보나치 힙^ · 큐 · 스택 | ||||
| 수학적 최적화 | <keepall> 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| <keepall> 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| <keepall> 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 · 난수생성 | ||||
| <keepall> 대칭키 암호화 방식 | 블록 암호 알고리즘(파이스텔 네트워크 · DES · AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| <keepall> 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
| [[컴퓨터공학|'''컴퓨터 과학 및 공학 {{{#!wiki style="font-family: Times New Roman, serif; display: inline;"]] | ||
| {{{#!wiki style="margin: 0 -10px -5px; min-height:calc(1lh + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" | <colbgcolor=#1282d7,#1282d7><colcolor=#fff,#fff> 기반 학문 | 수학(이산수학 · 수리논리학 · 선형대수학 · 대수학(환론 · 범주론) · 정수론 · 해석학 · 미적분학 · 미분방정식) · 이론 컴퓨터 과학(튜링 머신 · 정보이론 · 재귀 이론) · 암호학 · 전자공학 · 언어학(음운론 · 형태론 · 통사론 · 의미론 · 화용론) · 인지과학 |
| 하드웨어 | SoC · CPU · GPU(그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품 | |
| 시스템 | 컴퓨터 구조론 · 폰노이만 구조 · 마이크로아키텍처 · 논리 회로(논리 연산 · 카르노 맵 · 가산기 · 보수기 · 플립플롭) · FPGA · 하드웨어 가속 · 바이오스 · UEFI · ACPI · LinuxBoot · 운영체제(인터럽트 · 멀티태스킹 · 프로세스 스케줄링 · 뮤텍스 · 세마포어 · 데드락 · 식사하는 철학자 문제) · 네트워크(네트워크 포트) · 대역폭 · 와이파이 · gRPC · GPS · 임베디드 시스템 · 사물인터넷 · 슈퍼컴퓨터 · 양자 컴퓨터 | |
| 소프트웨어 | 시간 복잡도(최적화) · 이진 탐색 · 난수생성 · 컴퓨터 언어 · 기계어 · 어셈블리어 · 프로그래밍 언어(타입 이론 · 어휘 분석 · 파싱 · 컴파일러(어셈블러 · JIT) · 인터프리터 · 링커 · 난해한 프로그래밍 언어) · 마크업 언어 · 프로그래밍 패러다임(절차적 프로그래밍 · 객체 지향 프로그래밍 · 함수형 프로그래밍) · 데이터베이스(DBMS · NoSQL) · 메타데이터 · 인코딩(유니코드 · MBCS) · 소프트웨어 개발 방법론(애자일 · 워터폴) · 디자인 패턴 · 행위자 모델 · 놀람 최소화 원칙 · 버전(버전 관리 시스템) · 프레임워크 · 라이브러리 · 모듈 · API · ABI | |
| 응용 | 인공지능 · 기계학습 · 인공신경망 · 딥러닝 · 자연어 처리(기계 번역 · 음성인식) · 컴퓨터 비전 · OCR · 빅데이터 · 컴퓨터 그래픽스 · OpenGL · EXIF · HCI · UI · UX · 컴퓨터 보안 · 해킹 · 리버스 엔지니어링 · 해시(SHA · salt · 브루트 포스 · 레인보우 테이블 · 암호화폐) · 디피-헬만 키 교환 · RSA 암호화 · ROT13 · 일회용 비밀번호 |
[1] 장음과 단음을 구별하는 구식 표기로 "부울"이라고 표기하는 경우도 있으나, 1986년 외래어 표기법 개정 이후 국어 규범 표기는 "불"이며 실제 발음 차이도 거의 없다.[2] 어원은 아니지만 원소가 두 개(binary)뿐인 집합이라는 의미도 함의하고 있어 영어권에선 해당 기호가 훨씬 직관적이다.[3] not OR[4] not AND[5] exclusive OR[6] equivalent 또는 배타적 부정 논리합(XNOR, exclusive not OR)[7] converse[8] not IMP[9] converse nonimplication[10] 임의의 변수(또는 상수)가 이미 지정된 것과 유사하지만 구분할 필요가 있을 때 사용되기도 하며, 해석학에서는 도함수 기호로, 경제학 등 응용 쪽에서 실수체 위의 전치행렬 기호로도 쓰이는 등 중구난방이므로 이 표기법은 주의해서 사용해야 한다.[11] 연산 결과가 변수 자신과 같음[12] 경우에 따라 논리곱이 아니라 비트곱 연산자일 때도 있다. 단, 진리값을 0과 1로 정의한 경우 비트곱과 논리곱 연산은 동치가 된다.[13] 경우에 따라 논리곱이 아니라 비트곱 연산자일 때도 있다. 단, 진리값을 0과 1로 정의한 경우 비트곱과 논리곱 연산은 동치가 된다.[14] or의 중의성으로 인해, 수리논리학에서는 이 문서의 맥락으로 or를 사용한다고 약속했다.[15] 경우에 따라 논리합이 아니라 비트합 연산자일 때도 있다. 단, 진리값을 0과 1로 정의한 경우 비트합과 논리합 연산은 동치가 된다.[16] [math(A \boldsymbol{\text{ or }} B)][17] [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)][18] ((not A) and B) or (A and (not B))[19] (A or B) and not(A and B)로 표현할 수도 있다.[20] 이 기호는 선형대수학에서 직합을 의미하기도 한다.[21] C언어에서 제곱은
math.h라는 헤더 파일을 include(포함)하고(<math.h>), pow(밑, 지수) 함수를 사용하면 가능하다.[22] PHP 5.6 이상이나 Python 등의 언어에서는 또 **로 지수를 표현하는 것이 가능하다.[23] 예를 들어, AX라는 레지스터를 0으로 초기화 할 땐 MOV AX,0을 써도 되지만 XOR AX,AX를 해도 된다는 의미이다. AX에 뭔 값이 들어있는지는 알 수 없지만, 같은 것끼리 연산시키면 무조건 0을 반환하는 XOR의 특성 상 해당 연산의 결과는 AX의 원래 값과는 상관 없이 항상 0이 된다.[24] [math(A=A\veebar B)]; [math(B=A\veebar B)]; [math(A=A\veebar B)][25] 단, 0을 원소로 가지는 집합끼리의 교집합은 공집합이므로, 교집합을 논리곱(and)이라고 하려면 공집합 또한 0으로 보아야 한다.[26] 이 방법을 통해 드모르간 법칙이 불 대수에서 성립함을 직접적 증명 없이 이해할 수 있다.