이산수학 8강 - 부울대수
0과 1의 두 값으로 정보를 처리하는 디지털 논리회로와 논리게이트의 동작을 살펴본다. 부울대수의 연산과 기본 법칙, 쌍대성 원리와 드모르간 법칙을 이해하고, 이를 이용해 부울함수와 논리회로를 간소화하는 방법을 학습한다.
1. 디지털 논리회로와 부울대수
디지털 논리회로의 역할
컴퓨터 내부에서는 정보를 두 가지 상태로 표현한다. 이 두 상태는 보통 숫자 0과 1, 논리값 거짓과 참, 또는 전기 신호의 낮은 상태와 높은 상태에 대응한다. 입력된 디지털 신호를 일정한 논리 규칙에 따라 처리하여 새로운 디지털 신호를 출력하는 장치가 디지털 논리회로이다.
논리회로는 하나 이상의 디지털 입력을 받아 논리연산을 수행한 뒤 하나의 출력을 만든다. 복잡한 컴퓨터 회로도 결국 단순한 논리연산을 수행하는 여러 논리게이트를 조합한 것이다. 따라서 논리게이트를 수식으로 표현하고 변형하는 방법을 알면 회로의 동작을 분석하고 더 간단한 회로로 바꿀 수 있다.
부울대수의 의미
부울대수(Boolean algebra)는 0과 1로 이루어진 집합에서 합, 곱, 보수 연산을 정의하고 그 연산 법칙을 다루는 대수 체계이다. 논리학의 명제연산과 디지털 회로의 스위칭 동작을 같은 형식으로 표현할 수 있기 때문에 논리회로 설계의 수학적 기반이 된다.
| 논리 표현 | 부울대수 표현 | 회로 표현 |
|---|---|---|
| 참 T | 1 | 높은 신호 |
| 거짓 F | 0 | 낮은 신호 |
| 논리합 p∨q | X+Y | OR 게이트 |
| 논리곱 p∧q | X·Y 또는 XY | AND 게이트 |
| 부정 ¬p | X̅ | NOT 게이트 |
2. 기본 논리게이트
AND 게이트
AND 게이트는 모든 입력이 1일 때만 1을 출력한다. 두 입력 X, Y에 대한 출력은 F=X·Y로 표현한다. 하나라도 0이면 출력은 0이다.
OR 게이트
OR 게이트는 입력 중 하나 이상이 1이면 1을 출력한다. 출력은 F=X+Y이며, 두 입력이 모두 0일 때만 출력이 0이다.
NOT 게이트
NOT 게이트는 하나의 입력을 반대로 바꾸는 인버터이다. 입력이 0이면 1, 입력이 1이면 0을 출력하며 F=X̅로 표현한다.
| X | Y | AND XY | OR X+Y | NOT X̅ |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 |
3. NAND·NOR·XOR·XNOR 게이트
NAND와 NOR
NAND 게이트는 AND 결과를 부정한다. 따라서 F=(XY)̅이며, 두 입력이 모두 1인 경우에만 0이고 나머지는 1이다. 드모르간 법칙을 적용하면 (XY)̅=X̅+Y̅로도 나타낼 수 있다.
NOR 게이트는 OR 결과를 부정한다. F=(X+Y)̅이고, 두 입력이 모두 0일 때만 1을 출력한다. 드모르간 법칙으로 (X+Y)̅=X̅Y̅가 된다.
XOR와 XNOR
XOR 게이트는 두 입력이 서로 다를 때 1을 출력하는 배타적 논리합 게이트이다. F=X⊕Y=X̅Y+XY̅이다. 반대로 XNOR 게이트는 두 입력이 같을 때 1을 출력하며 F=(X⊕Y)̅=XY+X̅Y̅이다.
| X | Y | NAND | NOR | XOR | XNOR |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
4. 부울식과 부울함수
부울식의 순환적 정의
부울식은 다음과 같이 순환적으로 정의된다. 부울상수 0과 1은 부울식이다. 부울변수 X, Y, Z 등은 부울식이다. X와 Y가 부울식이라면 X+Y, X·Y, X̅도 부울식이다. 이렇게 만들어진 부울식은 변수에 0 또는 1을 대입하면 하나의 부울값을 낸다.
부울함수는 하나 이상의 부울변수를 입력으로 받아 부울값 0 또는 1을 출력하는 함수이다. 같은 진리표를 만드는 서로 다른 부울식은 같은 부울함수를 표현한다. 예를 들어 X+XY와 X는 모양이 다르지만 흡수법칙에 따라 같은 값을 출력한다.
논리와 부울대수의 대응
명제변수 p, q, r은 부울변수 X, Y, Z에 대응하고 참과 거짓은 각각 1과 0에 대응한다. 논리합은 +, 논리곱은 ·, 논리부정은 보수 기호로 바꾸면 논리적 동치 관계를 부울대수의 등식으로 옮길 수 있다. 이 대응을 통해 진리표의 동치 여부를 부울대수 법칙으로 계산할 수 있다.
5. 부울대수의 기본 법칙
부울식의 계산에서는 몇 가지 기본 법칙을 반복적으로 사용한다. 산술대수와 비슷한 이름의 법칙도 있지만, 부울값이 0과 1뿐이라는 점에서 부울대수만의 관계가 나타난다.
| 법칙 | 논리합 형태 | 논리곱 형태 |
|---|---|---|
| 항등법칙 | X+0=X | X·1=X |
| 지배법칙 | X+1=1 | X·0=0 |
| 멱등법칙 | X+X=X | X·X=X |
| 보수법칙 | X+X̅=1 | X·X̅=0 |
| 교환법칙 | X+Y=Y+X | XY=YX |
| 결합법칙 | X+(Y+Z)=(X+Y)+Z | X(YZ)=(XY)Z |
| 분배법칙 | X+YZ=(X+Y)(X+Z) | X(Y+Z)=XY+XZ |
| 흡수법칙 | X+XY=X | X(X+Y)=X |
이중보수법칙은 X̅̅=X이다. 특히 부울대수에서는 논리곱이 논리합에 대해 분배될 뿐 아니라 논리합도 논리곱에 대해 분배된다. 즉 X(Y+Z)=XY+XZ뿐 아니라 X+YZ=(X+Y)(X+Z)도 성립한다.
흡수법칙의 이해
X+XY에서는 X가 1이면 전체가 이미 1이고, X가 0이면 XY도 0이다. 따라서 Y의 값과 관계없이 결과는 X와 같아 X+XY=X가 된다. 같은 원리로 X(X+Y)=X이다. 흡수법칙은 회로에서 불필요한 항을 제거할 때 매우 자주 사용된다.
6. 쌍대성 원리와 드모르간 법칙
쌍대성 원리
쌍대성 원리(principle of duality)는 어떤 부울식에서 논리합 +와 논리곱 ·을 서로 바꾸고, 부울상수 0과 1을 서로 바꾸어 얻은 식을 쌍대식이라고 하는 원리이다. 주어진 부울식이 참인 항등식이면 그 쌍대식도 참이다.
예를 들어 X+0=X의 쌍대식은 X·1=X이고, X+1=1의 쌍대식은 X·0=0이다. X+YZ=(X+Y)(X+Z)의 쌍대식은 X(Y+Z)=XY+XZ이다. 변수와 보수 기호는 그대로 두며 +와 ·, 0과 1만 서로 바꾼다.
드모르간 법칙
드모르간 법칙은 합의 보수와 곱의 보수를 서로 바꾸는 법칙이다.
(X+Y)̅=X̅Y̅
(XY)̅=X̅+Y̅
여러 변수에도 같은 원리가 적용된다. 합 전체의 보수는 각 변수의 보수를 모두 곱한 것과 같고, 곱 전체의 보수는 각 변수의 보수를 모두 더한 것과 같다. 즉 (X₁+X₂+⋯+Xₙ)̅=X̅₁X̅₂⋯X̅ₙ이며, (X₁X₂⋯Xₙ)̅=X̅₁+X̅₂+⋯+X̅ₙ이다.
7. 부울함수의 보수
부울함수 F의 보수 F̅는 F가 0인 입력에서 1, F가 1인 입력에서 0을 출력한다. 식으로 보수를 구할 때는 F 전체에 보수를 취하고 드모르간 법칙을 적용한 다음 이중보수를 정리한다.
예를 들어 F=X̅YZ+XY̅Z라면 다음과 같이 계산한다.
F̅=(X̅YZ+XY̅Z)̅
=(X̅YZ)̅·(XY̅Z)̅
=(X+Y̅+Z̅)(X̅+Y+Z̅)
첫 단계에서 합의 보수를 곱으로 바꾸고, 각 곱항의 보수는 보수된 변수들의 합으로 바꾼다. 이미 보수된 X̅에 다시 보수를 취하면 이중보수법칙으로 X가 된다. 보수 계산은 NAND와 NOR 회로를 서로 변환할 때도 중요하다.
8. 부울함수의 대수적 간소화
간소화의 목적
하나의 부울함수는 서로 다른 여러 부울식과 논리회로로 표현될 수 있다. 이때 복잡한 부울식을 기본 법칙으로 간단하게 만들면 같은 입력·출력 동작을 유지하면서 논리게이트의 수와 연결을 줄일 수 있다. 회로가 단순해지면 구현에 필요한 부품과 연결 구조도 줄어든다.
공통인수 묶기
일반 대수처럼 공통인수를 묶을 수 있다. 예를 들어 XYZ+XY̅Z+XYZ̅+XYZ와 같은 식에서는 공통된 변수들을 찾아 분배법칙으로 묶는다. 특히 XY+X̅Y=Y(X+X̅)=Y처럼 한 변수와 그 보수가 함께 나타나면 보수법칙으로 1을 만들 수 있다.
중복항과 흡수항 제거
멱등법칙에 따라 X+X=X, XX=X이므로 같은 항이 반복되면 하나만 남긴다. 흡수법칙에 따라 X+XY=X, X(X+Y)=X이므로 더 구체적인 항 XY나 괄호 안의 Y를 제거할 수 있다. 또한 X+X̅Y=(X+X̅)(X+Y)=X+Y처럼 분배법칙과 보수법칙을 결합할 수 있다.
적당한 항의 첨가
식의 모양을 바꾸기 위해 값이 변하지 않는 항을 더하거나 곱할 수 있다. X+X̅=1, XX̅=0을 이용하거나 흡수법칙으로 결국 사라지는 항을 추가하면 공통인수를 만들 수 있다. 다만 모든 변형 단계에서 원래 함수와 논리적으로 동치인지 법칙을 명시해야 한다.
간소화 방법의 종류
강의록에서는 부울대수의 기본 성질을 이용한 대수적 간소화를 중심으로 다룬다. 이 밖에도 카르노 맵, 퀸-맥클러스키 방법, 정형적 평가와 같은 방법을 이용할 수 있다. 어떤 방법을 사용하더라도 간소화 전후의 부울함수와 논리회로는 동일한 진리표를 가져야 한다.
핵심 개념 정리
디지털 논리회로는 0과 1의 입력을 논리게이트로 처리하여 0 또는 1을 출력한다. 기본 게이트는 AND, OR, NOT이고, 이들을 변형한 NAND, NOR, XOR, XNOR 게이트가 있다. XOR는 두 입력이 다를 때, XNOR는 두 입력이 같을 때 1을 출력한다.
부울대수는 부울상수 0과 1, 부울변수, 논리합·논리곱·보수 연산으로 이루어진다. 항등·지배·멱등·보수·교환·결합·분배·흡수법칙을 이용하면 서로 다른 모양의 부울식이 같은 함수인지 보이거나 복잡한 식을 간단히 만들 수 있다.
쌍대성 원리는 +와 ·, 0과 1을 동시에 바꾸어도 참인 항등식에서 또 다른 참인 항등식을 얻는다는 원리이다. 드모르간 법칙은 합의 보수를 보수들의 곱으로, 곱의 보수를 보수들의 합으로 바꾼다. 간소화 전후의 식은 반드시 같은 진리표를 가져야 한다.
예상문제 20선
1. 디지털 논리회로가 처리하는 기본 신호값은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
디지털 논리회로는 두 상태를 0과 1로 표현하여 입력을 처리하고 0 또는 1을 출력한다.
2. 두 입력이 모두 1일 때만 1을 출력하는 게이트는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
AND 게이트의 출력은 F=XY이며 모든 입력이 1인 경우에만 1이다.
3. OR 게이트에 대한 설명으로 옳지 않은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
두 입력이 서로 다를 때만 1을 출력하는 것은 XOR 게이트이다. OR 게이트는 두 입력이 모두 1인 경우에도 1이다.
4. 입력 X가 0일 때 NOT 게이트의 출력은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
NOT 게이트는 입력을 반전하므로 X=0이면 X̅=1이다.
5. NAND 게이트의 출력식은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
NAND는 AND 연산 결과를 부정하므로 출력은 (XY)̅이다.
6. 두 입력이 모두 0일 때만 1을 출력하는 게이트는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
NOR는 OR의 출력을 부정한다. OR가 0인 경우는 두 입력이 모두 0일 때뿐이므로 이때 NOR가 1이다.
7. XOR 게이트가 1을 출력하는 경우는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
XOR는 배타적 논리합으로 두 입력값이 다를 때 1을 출력한다.
8. XNOR 게이트의 부울식으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
XNOR는 두 입력이 같은 경우를 나타내므로 둘 다 1인 XY와 둘 다 0인 X̅Y̅를 논리합한 식이다.
9. 부울대수에서 X+1의 값은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
지배법칙에 따라 X+1=1이다. 논리합에서 하나의 입력이 1이면 결과는 항상 1이다.
10. 항등법칙에 해당하는 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
논리합의 항등원은 0이므로 X+0=X이다. 논리곱의 항등원은 1이다.
11. 멱등법칙을 올바르게 나타낸 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
멱등법칙은 같은 변수를 반복 연산해도 값이 변하지 않음을 나타내며 X+X=X, XX=X이다.
12. 보수법칙에 따른 X·X̅의 값은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
한 변수와 그 보수는 동시에 1일 수 없으므로 논리곱 XX̅는 0이다.
13. 부울대수의 흡수법칙에 따라 X+XY를 간소화한 결과는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
X가 1이면 전체가 1이고 X가 0이면 XY도 0이므로 X+XY=X이다.
14. X+YZ와 같은 부울식에 적용되는 분배법칙 결과는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
부울대수에서는 논리합도 논리곱에 대해 분배되어 X+YZ=(X+Y)(X+Z)가 성립한다.
15. 쌍대식을 만들 때 서로 바꾸어야 하는 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
쌍대성 원리에서는 +와 ·을 서로 바꾸고 동시에 0과 1을 바꾼다. 변수와 보수 기호는 그대로 둔다.
16. 드모르간 법칙에 따라 (X+Y)̅와 같은 식은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
합 전체의 보수는 각 변수의 보수의 곱이므로 (X+Y)̅=X̅Y̅이다.
17. 드모르간 법칙에 따라 (XYZ)̅를 변형한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
곱 전체의 보수는 각 변수의 보수를 논리합한 것과 같으므로 (XYZ)̅=X̅+Y̅+Z̅이다.
18. XY+X̅Y를 간소화한 결과는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
공통인수 Y를 묶으면 Y(X+X̅)=Y·1=Y가 된다.
19. 부울함수 간소화의 주된 목적은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
간소화는 함수의 동작을 바꾸지 않으면서 항과 게이트 수를 줄여 더 간단한 회로를 얻는 과정이다.
20. 두 부울식이 같은 부울함수를 나타내는지 가장 직접적으로 검산하는 방법은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
모든 입력 조합에서 두 식의 출력이 같다면 두 부울식은 같은 부울함수를 나타낸다.
댓글
댓글 쓰기