부울대수
1. 부울대수(Boole algebra)
조지 부울(George Boole)이라는 수학자가 소개한 논리 대수의 한 형태로, 논리적인 상태를 다루는 데 사용되는 수학적인 체계입니다. 논리적인 상태는 "0"과 "1", 두 개 값으로 "거짓", "참"을 표현할 수 있습니다. 즉, 참/거짓 명제 문제를 수로 표현한 형태입니다.
2. 논리연산
논리연산은 입력과 출력으로 구분됩니다. 입력변수는 부울변수이며, 부울변수로 구성된 연산식을 부울식이라고 합니다. 또한, 부울식으로 표현된 함수를 부울함수라고 합니다.
(예시) F(X, Y) = X + Y
대표적인 논리연산과 진리표는 다음과 같습니다.
2.1. 논리곱(AND, ⋅)
두 입력이 모두 1일 때에만 출력이 1이 됩니다. XY = F 또는 X⋅Y = F로 표현합니다.
| XY = F | ||||
| X | 1 | 1 | 0 | 0 |
| Y | 1 | 0 | 1 | 0 |
| F | 1 | 0 | 0 | 0 |
2.2. 논리합(OR, ＋)
두 입력 중 하나 이상이 1이면 출력이 1이 됩니다. X + Y = F로 표현합니다.
| X + Y = F | ||||
| X | 1 | 1 | 0 | 0 |
| Y | 1 | 0 | 1 | 0 |
| F | 1 | 1 | 1 | 0 |
2.3. 논리부정(NOT, ′)
입력이 1이면 출력은 0, 입력이 0이면 출력은 1이 됩니다. X′ = F로 표현합니다.
| X′ = F | ||
| X | 1 | 0 |
| F | 0 | 1 |
2.4. 배타적 논리합(XOR, ⊕)
두 입력 중 하나만 1일 때 출력이 1이 됩니다. X ⊕ Y = F로 표현합니다.
| X ⊕ Y = F | ||||
| X | 1 | 1 | 0 | 0 |
| Y | 1 | 0 | 1 | 0 |
| F | 0 | 1 | 1 | 0 |
3. 부울대수의 기본법칙
| 법칙 | 관계 |
| 항등 법칙(Identity Law) | X + 0 = X X ⋅ 1 = X |
| 보수 법칙(Complement Law) | X + X′ = 1 X ⋅ X′ = 0 |
| 결합 법칙(Associative Law) | (X + Y) + Z = X + (Y + Z) (X ⋅ Y) ⋅ Z = X ⋅ (Y ⋅ Z) |
| 교환 법칙(Commutative Law) | X + Y = Y + X X ⋅ Y = Y ⋅ X |
| 분배 법칙(Distributive Law) | X + (Y ⋅ Z) = (X + Y) ⋅ (X + Z) X ⋅ (Y + Z) = (X ⋅ Y) + (X ⋅ Z) |
| 이중 보수 법칙(Double Complement Law) | ( X′)′ = X |
| 드 모르간 법칙(De Morgan's Law) | (X + Y)′ = X′ ⋅ Y′ (X ⋅ Y)′ = X′ + Y′ |
| 흡수 법칙(Absorption Law) | X + X ⋅ Y = X X ⋅ (X + Y) = X |
부울대수의 관계 역시 논리적 동치를 이루는 법칙들과 굉장히 유사합니다. 논리적 동치는 이전 게시글에서 참조할 수 있습니다.
그리고 부울대수에서는 부울식 내 논리연산자 ⋅(AND)를 +(OR)로, +를 ⋅로 맞바꾼 뒤 모든 논리값과 부울변수에 부정(NOT)을 적용하면 변경된 논리식은 기존 논리식과 논리적인 동치가 됩니다. 그리고 이때 이런 원리를 쌍대성 원리(Principle of duality)라고 합니다.
(예시1) X + 0 = X ⇔ X′ ⋅ 1 = X′
(예시2) X + Y = Y + X ⇔ X′ ⋅ Y′ = Y′ ⋅ X′
(예시3) X + X′ = 1 ⇔ X′ ⋅ X = 0
4. 디지털 논리 회로(Digital logic circuit)
디지털 논리 회로는 디지털 입력값으로 연산을 수행하여 디지털 출력값을 생성하는 전자 회로입니다. 디지털 논리 회로는 0과 1의 이진 상태로 동작하며, 논리 게이트를 조합하여 만들어집니다.
5. 논리 게이트
논리 게이트는 디지털 논리 회로에서 기본적인 논리 연산을 수행하는 전자 장치입니다. 대표적인 논리 게이트는 다음과 같습니다.
5.1. AND 게이트
모든 입력이 1일 경우에만 출력이 1이 되는 게이트입니다.
| 회로 기호 | 논리식 | 진리표 | ||
 |
F = AB | A | B | F |
| 1 | 1 | 1 | ||
| 1 | 0 | 0 | ||
| 0 | 1 | 0 | ||
| 0 | 0 | 0 | ||
5.2. OR 게이트
1개 이상의 입력이 1일 경우에 출력이 1이 되는 게이트입니다.
| 회로 기호 | 논리식 | 진리표 | ||
|
F = A + B | A | B | F |
| 1 | 1 | 1 | ||
| 1 | 0 | 1 | ||
| 0 | 1 | 1 | ||
| 0 | 0 | 0 | ||
5.3. NOT 게이트
입력이 1이면 0을, 입력이 0이면 1을 출력하는 게이트입니다.
| 회로 기호 | 논리식 | 진리표 | ||
|
F = A′ | A | F | |
| 1 | 0 | |||
| 0 | 1 | |||
5.4. NAND 게이트
AND 게이트의 부정 논리값을 출력하는 게이트입니다. 즉, 모든 입력이 1일 경우에만 0을 출력합니다.
| 회로 기호 | 논리식 | 진리표 | ||
|
F = (AB)′ | A | B | F |
| 1 | 1 | 0 | ||
| 1 | 0 | 1 | ||
| 0 | 1 | 1 | ||
| 0 | 0 | 1 | ||
5.5. NOR 게이트
OR 게이트의 부정 논리값을 출력하는 게이트입니다. 즉, 모든 입력이 0일 경우에만 1을 출력합니다.
| 회로 기호 | 논리식 | 진리표 | ||
 |
F = (A + B)′ | A | B | F |
| 1 | 1 | 0 | ||
| 1 | 0 | 0 | ||
| 0 | 1 | 0 | ||
| 0 | 0 | 1 | ||
5.6. XOR 게이트
배타적 논리합 결과를 출력하는 게이트입니다. 2개의 입력이 다를 경우에만 1을 출력합니다.
| 회로 기호 | 논리식 | 진리표 | ||
 |
F = A ⊕ B | A | B | F |
| 1 | 1 | 0 | ||
| 1 | 0 | 1 | ||
| 0 | 1 | 1 | ||
| 0 | 0 | 0 | ||
연관 게시글
[이산수학] 이산수학?
이산수학? 1. 이산수학이란? 이산수학(Discrete Mathematics)은 연속적이지 않고 분리된 개체를 다루는 수학의 한 분야입니다. 연속적인 개체에는 실수 등이 있을 것이고, 연속적이지 않는 개체에는 정
brightchords.tistory.com
참조
'IT' 카테고리의 다른 글
| [이산수학] 행렬 (0) | 2024.03.12 |
|---|---|
| [이산수학] 증명 (0) | 2024.03.11 |
| [이산수학] 집합 (0) | 2024.03.09 |
| [이산수학] 명제와 논리 (0) | 2024.03.03 |
| [이산수학] 이산수학? (0) | 2024.03.03 |