방송대 이산수학 8강: 논리게이트와 부울함수 간소화

방송대 이산수학 8강: 논리게이트와 부울함수 간소화

겉모양이 다른 두 논리회로가 같은 출력을 낼 수 있다면 더 단순한 회로를 선택할 수 있습니다. 이를 위해서는 게이트를 부울식으로 번역하고, 식의 진리값을 보존하면서 항과 문자를 줄인 뒤, 진리표로 결과를 검산해야 합니다. 이 글은 입력에서 간소화된 출력식까지 그 판단 과정을 재현합니다.

간소화의 목표는 진리표를 바꾸지 않고 회로를 줄이는 것이다

디지털 논리회로는 0과 1로 표현된 입력에 논리연산을 적용하여 0 또는 1을 출력합니다. 같은 진리표를 만드는 부울함수는 같은 논리 기능을 나타내지만, 구현에 필요한 게이트 수와 연결 구조는 다를 수 있습니다. 부울함수의 대수적 간소화는 복잡한 식을 더 적은 항과 문자로 바꾸어 대응하는 회로도 단순하게 만드는 작업입니다.

따라서 식이 짧아졌다는 사실만으로 간소화가 성공한 것은 아닙니다. 원래 식과 새 식의 모든 입력 조합에서 출력이 같아야 합니다. 계산 중에는 부울대수의 항등식을 사용하고, 마지막에는 진리표나 핵심 입력값으로 동치를 검산합니다.

판단 핵심: 간소화는 값을 근사하는 작업이 아닙니다. 입력 조합마다 출력이 완전히 같은 식으로 변형해야 하며, 각 등호에는 적용한 부울 법칙이 있어야 합니다.

게이트를 읽을 때는 언제 1이 되는지 먼저 묻는다

두 입력 X, Y를 받는 게이트는 네 입력 조합 00, 01, 10, 11에서의 출력으로 구분합니다. 이 글에서는 강의의 표기에 맞춰 +를 OR, 붙여 쓰기 또는 ·를 AND, ¬를 NOT으로 사용합니다.

게이트	부울식	출력이 1인 조건	판별용 출력열
AND	XY	두 입력이 모두 1	0, 0, 0, 1
OR	X+Y	적어도 하나가 1	0, 1, 1, 1
NAND	¬(XY)	둘 다 1인 경우를 제외	1, 1, 1, 0
NOR	¬(X+Y)	두 입력이 모두 0	1, 0, 0, 0
XOR	X⊕Y = ¬XY+X¬Y	두 입력이 서로 다름	0, 1, 1, 0
XNOR	¬(X⊕Y) = ¬X¬Y+XY	두 입력이 서로 같음	1, 0, 0, 1

NOT은 입력 하나를 반전하여 ¬0=1, ¬1=0을 만듭니다. 회로 기호 끝의 작은 원은 해당 신호가 반전된다는 뜻입니다. AND 뒤에 반전이 붙으면 NAND, OR 뒤에 반전이 붙으면 NOR입니다.

XOR와 OR를 혼동하기 쉽습니다. 입력 11에서 OR는 1이지만 XOR는 0입니다. 반대로 XNOR는 ‘둘 다 1’만 찾는 게이트가 아니라 두 입력이 같을 때 1이므로 00에서도 1입니다. 게이트 이름보다 이 경계 입력을 대입하면 빠르게 구분할 수 있습니다.

회로·부울식·진리표는 같은 기능의 세 표현이다

논리회로의 선은 부울변수, 게이트는 연산, 최종 선은 부울함수의 출력에 대응합니다. 회로에서 식으로 옮길 때는 입력 쪽의 작은 부분부터 중간 출력을 이름 붙여 계산합니다. 반대로 식에서 회로를 만들 때는 괄호와 연산 우선순위에 따라 안쪽 연산부터 게이트로 바꿉니다.

예를 들어 F=(X+Y)¬Z는 먼저 X와 Y를 OR한 뒤, Z를 NOT한 결과와 AND합니다. 입력 X=0, Y=1, Z=0이면 X+Y=1, ¬Z=1, 따라서 F=1입니다. 중간값을 쓰면 어느 게이트에서 오류가 났는지 찾을 수 있습니다.

1. 입력 변수를 0과 1로 둡니다.
2. NOT이 붙은 신호를 먼저 반전합니다.
3. 괄호 안의 AND·OR 결과를 계산합니다.
4. 최종 게이트의 출력을 구합니다.
5. 변수 n개라면 2n개 입력 행을 모두 확인합니다.

부울대수의 +와 ·는 보통 산술 덧셈·곱셈이 아닙니다. 예를 들어 1+1=1이고 1·1=1입니다. 연산 기호를 산술로 계산하면 OR의 멱등법칙 X+X=X를 이해할 수 없습니다.

부울식은 상수·변수·세 연산으로 닫혀 있다

부울상수 0과 1, 부울변수는 부울식입니다. 부울식 X, Y가 있으면 X+Y, XY, ¬X도 부울식입니다. 이 재귀적 정의는 복잡한 식도 결국 상수와 변수에 OR·AND·NOT을 반복 적용해 만든다는 뜻입니다.

논리학과의 대응은 T↔1, F↔0, ∨↔+, ∧↔·, ¬↔¬입니다. 집합론에서는 합집합·교집합·여집합이 같은 대수적 구조를 보입니다. 이 때문에 논리의 드 모르간 법칙을 부울식과 집합식에서도 같은 원리로 사용할 수 있습니다.

기본정리는 식의 모양이 아니라 제거할 대상을 알려 준다

19개의 기본정리를 번호로만 외우면 간소화할 식에서 어느 법칙을 꺼내야 할지 막힙니다. ‘무엇을 없애거나 묶고 싶은가’를 기준으로 분류하면 선택이 쉬워집니다.

목표	대표 법칙	식에서 찾을 모양
상수 제거	X+0=X, X·1=X	OR의 0, AND의 1
결과 고정	X+1=1, X·0=0	OR의 1, AND의 0
중복 제거	X+X=X, XX=X	같은 항이나 인수 반복
상보쌍 제거	X+¬X=1, X¬X=0, ¬¬X=X	한 변수의 정상형과 보수형
순서·묶음 변경	교환법칙, 결합법칙	결합 가능한 항을 이웃하게 이동
공통부분 묶기	X(Y+Z)=XY+XZ	두 항이 같은 문자를 공유
곱의 합으로 묶기	X+YZ=(X+Y)(X+Z)	합의 곱 형태가 더 유리한 경우
포함된 항 제거	X+XY=X, X(X+Y)=X	큰 조건이 작은 조건에 흡수됨

흡수법칙은 논리 조건으로 보면 자연스럽습니다. X+XY에서 XY=1이면 이미 X=1이므로 XY는 새로운 1인 경우를 만들지 못합니다. 따라서 전체는 X와 같습니다. 법칙을 사용할 때는 단순히 비슷해 보이는 항을 지우지 말고, 한 항이 다른 항이 참인 모든 경우를 이미 포함하는지 확인해야 합니다.

드 모르간 법칙은 보수의 범위를 따라 연산을 바꾼다

드 모르간 법칙은 보수가 괄호 안으로 들어갈 때 OR와 AND를 서로 바꾸고 각 문자에 보수를 붙입니다.

• ¬(X+Y)=¬X¬Y
• ¬(XY)=¬X+¬Y
• ¬(X1+···+Xn)=¬X1···¬Xn
• ¬(X1···Xn)=¬X1+···+¬Xn

괄호 전체의 보수를 각 문자에만 붙이고 연산을 그대로 두는 것은 잘못입니다. 예를 들어 ¬(X+Y)를 ¬X+¬Y로 바꾸면 입력 X=0, Y=1에서 원래 식은 0이지만 잘못된 식은 1이 됩니다. 한 행의 반례로 두 식이 다름을 확인할 수 있습니다.

NAND의 식 ¬(XY)가 ¬X+¬Y와 같고, NOR의 식 ¬(X+Y)가 ¬X¬Y와 같은 것도 드 모르간 법칙의 직접적인 적용입니다.

쌍대성은 항등식 한 쌍을 함께 만든다

부울식에서 +와 ·을 서로 바꾸고 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입니다.

오개념 교정: 임의의 식과 그 쌍대식이 같은 부울함수라는 뜻은 아닙니다. X+Y와 그 쌍대 XY는 입력 01에서 각각 1과 0입니다. 원리는 ‘참인 항등식 전체를 쌍대로 바꾸어도 참’이라는 명제에 적용합니다.

함수의 보수는 두 경로로 같은 답에 도달한다

부울함수 F의 보수 ¬F는 F의 출력 0과 1을 뒤집은 함수입니다. 강의의 함수 F=¬XY¬Z+¬X¬YZ를 두 방법으로 구해 보겠습니다.

드 모르간 법칙을 이용하는 경로

¬F = ¬(¬XY¬Z+¬X¬YZ)

= ¬(¬XY¬Z) · ¬(¬X¬YZ)

= (X+¬Y+Z)(X+Y+¬Z)

첫 단계에서 바깥 OR가 AND로 바뀌고, 각 곱항의 보수에서는 AND가 OR로 바뀌면서 모든 문자가 반전됩니다.

쌍대를 거치는 경로

먼저 F의 쌍대 (¬X+Y+¬Z)(¬X+¬Y+Z)를 만듭니다. 그런 다음 모든 문자를 정상형과 보수형 사이에서 바꾸면 (X+¬Y+Z)(X+Y+¬Z)가 됩니다. 두 경로의 결과가 같으므로 계산을 교차 검산할 수 있습니다.

보수와 쌍대는 다른 연산입니다. 보수는 함수의 출력값을 반전하고, 쌍대는 식 안의 OR·AND와 0·1을 서로 교환합니다. 보수를 쌍대로 구할 때는 쌍대식을 만든 뒤 문자까지 각각 반전하는 추가 단계가 필요합니다.

항 결합은 상보쌍을 만들어 한 변수를 없앤다

두 항이 한 문자만 정상형과 보수형으로 다르고 나머지 부분이 같으면 공통부분을 묶어 문자를 제거할 수 있습니다.

XY+X¬Y = X(Y+¬Y) = X·1 = X

직접 구성한 식 G=¬ABC+A¬BC+ABC를 줄여 보겠습니다. 항 ABC는 멱등법칙 때문에 두 번 써도 함수가 바뀌지 않습니다.

1. G=¬ABC+A¬BC+ABC+ABC
2. =BC(¬A+A)+AC(¬B+B)
3. =BC·1+AC·1
4. =BC+AC

중복항을 더한 목적은 분량을 늘리는 것이 아니라 하나의 ABC를 첫째 항과, 다른 하나를 둘째 항과 각각 결합하기 위해서입니다. 원래 회로는 세 개의 3입력 곱항을 합하지만, 간소화 후에는 두 개의 2입력 곱항만 합하면 됩니다.

문자 소거는 분배법칙으로 숨은 상보쌍을 꺼낸다

X+¬XY에서는 항 결합의 공통인수가 바로 보이지 않습니다. 부울대수의 다른 분배법칙을 사용하면 다음처럼 변형됩니다.

X+¬XY=(X+¬X)(X+Y)=1·(X+Y)=X+Y

또한 X(¬X+Y)=X¬X+XY=0+XY=XY입니다. 첫 식에서는 ¬X가, 둘째 식에서는 괄호 속 ¬X가 결과에서 사라집니다. 문자를 임의로 지운 것이 아니라 분배법칙으로 상보쌍 X+¬X 또는 X¬X를 만든 뒤 상수로 바꾼 것입니다.

이 두 식은 서로 쌍대 관계에 있습니다. 하나의 변형을 확실히 이해하면 쌍대성 원리로 다른 변형의 구조도 기억할 수 있습니다.

중복항 첨가는 다음 결합을 준비할 때만 사용한다

부울대수에서는 F=F+X¬X이고 F=F(X+¬X)입니다. 각각 0을 OR하거나 1을 AND하므로 값이 변하지 않습니다. 또 흡수법칙에 의해 F+X=F+X+XY처럼 이미 X에 흡수되는 항을 더할 수 있습니다.

다만 아무 항이나 더할 수 있는 것은 아닙니다. 첨가한 항이 0, 1, 중복항, 흡수되는 항처럼 전체 진리값을 바꾸지 않는다는 근거가 있어야 합니다. 그리고 첨가 뒤에는 반드시 다른 항과 결합되어 실제로 식을 줄여야 합니다. 근거 없이 원하는 항을 넣는 순간 등호가 깨집니다.

복잡한 곱의 합도 흡수되는 X를 먼저 찾는다

강의의 간소화 흐름을 재현해 보겠습니다.

F=(X+XY)(X+¬XY)(X+YZ)

1. X+XY=X이므로 F=X(X+¬XY)(X+YZ)입니다.
2. X+¬XY=X+Y이므로 F=X(X+Y)(X+YZ)입니다.
3. X(X+Y)=X이므로 F=X(X+YZ)입니다.
4. 다시 흡수법칙을 적용하면 F=X입니다.

검산은 경계 입력으로 시작할 수 있습니다. X=0이면 원래 식의 첫 인수 X+XY가 0이므로 F도 0입니다. X=1이면 세 인수가 모두 1이므로 F는 1입니다. Y와 Z의 값에 관계없이 출력이 X와 같아 최종식 F=X와 일치합니다.

간소화 선택 순서: 0·1과 중복 제거 → 흡수되는 항 찾기 → 공통인수와 상보쌍 만들기 → 필요한 경우에만 값이 변하지 않는 중복항 첨가 → 진리표 또는 경계 입력으로 검산.

핵심 개념 정리

• 게이트 판별: AND·OR는 11, XOR·XNOR는 00과 11에서의 출력 차이를 보면 빠르게 구분된다.
• 표현 연결: 논리회로의 게이트를 부울연산으로 바꾸고, 진리표로 원래 식과 간소화식의 출력을 비교한다.
• 법칙 선택: 상수·중복·상보쌍·흡수항 중 무엇을 없앨지 정한 뒤 그 모양을 만드는 법칙을 고른다.
• 보수와 쌍대: 드 모르간 법칙은 보수의 범위 안에서 연산을 바꾸며, 쌍대성은 참인 항등식을 짝 항등식으로 확장한다.
• 간소화: 항 결합, 문자 소거와 근거 있는 중복항 첨가는 진리값을 보존하면서 회로의 항과 입력 수를 줄인다.

부울함수를 만나면 먼저 각 게이트의 ‘1이 되는 조건’을 식으로 옮기고, 제거하려는 상수·중복·문자·흡수항을 표시하십시오. 이후 등호마다 적용한 법칙을 확인하면서 상보쌍 0 또는 1을 만들고, 필요할 때만 중복항을 더해 결합합니다. 마지막에는 모든 입력의 진리표나 X=0·1 같은 결정적 경계값으로 원래 기능이 보존되었는지 확인해야 간소화가 완성됩니다.

예상문제 10선

1. 입력 순서를 00, 01, 10, 11로 할 때 출력열이 0,1,1,0인 게이트는?

① XOR ② OR ③ NAND ④ XNOR

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: XOR는 두 입력이 서로 다를 때만 1이므로 01과 10에서 출력이 1이다.
• ② 오답: OR는 적어도 하나가 1이면 되므로 11에서도 1이다.
• ③ 오답: NAND는 11을 제외한 세 입력에서 1이므로 출력열이 1,1,1,0이다.
• ④ 오답: XNOR는 두 입력이 같을 때 1이므로 XOR의 반대 출력열이다.

2. NAND 게이트의 부울식과 동치인 것은?

① ¬X¬Y ② ¬(X+Y) ③ XY ④ ¬(XY)=¬X+¬Y

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 이는 드 모르간 법칙에 따라 NOR ¬(X+Y)와 같다.
• ② 오답: OR의 출력을 반전한 NOR의 정의다.
• ③ 오답: AND의 출력 그대로이며 마지막 반전이 빠졌다.
• ④ 정답: NAND는 AND 결과의 보수이고, 드 모르간 법칙으로 각 입력 보수의 OR와 같다.

3. F=(X+Y)¬Z에서 X=0, Y=1, Z=0일 때 F는?

① 0, X+Y=0이기 때문이다. ② 1, X+Y=1이고 ¬Z=1이기 때문이다. ③ 0, ¬Z=0이기 때문이다. ④ 2, 두 중간값을 산술 덧셈하기 때문이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: OR는 입력 중 하나가 1이면 1이므로 0+1=1이다.
• ② 정답: 두 중간값이 모두 1이고 마지막 AND 결과도 1이다.
• ③ 오답: NOT은 0을 1로 반전하므로 ¬Z=1이다.
• ④ 오답: 부울함수의 출력은 0 또는 1이며 마지막 연산은 AND이지 산술 덧셈이 아니다.

4. 쌍대성 원리에 대한 올바른 설명은?

① 임의의 식은 그 쌍대식과 모든 입력에서 같은 값을 낸다. ② 쌍대를 만들 때 변수 X를 모두 ¬X로 바꾼다. ③ 참인 항등식에서 +↔·, 0↔1을 동시에 바꾼 쌍대 항등식도 참이다. ④ 쌍대를 만들 때는 연산자를 그대로 두고 좌우 항만 바꾼다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: X+Y와 쌍대 XY는 01에서 값이 달라 임의의 식끼리 동치가 아니다.
• ② 오답: 변수와 보수 상태는 그대로 두며, 문자 반전은 보수를 쌍대 경로로 구할 때의 추가 단계다.
• ③ 정답: 쌍대성 원리는 성립하는 등식 전체를 규칙대로 변환했을 때 성립성이 보존됨을 말한다.
• ④ 오답: 핵심은 OR와 AND, 0과 1의 교환이며 좌우 항의 위치 교환이 아니다.

5. 드 모르간 법칙으로 ¬(X+Y)를 변형한 것은?

① ¬X¬Y ② ¬X+¬Y ③ XY ④ X+Y

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 바깥 보수가 안으로 들어가며 OR는 AND로 바뀌고 두 변수는 각각 반전된다.
• ② 오답: 변수만 반전하고 OR를 AND로 바꾸지 않은 흔한 오류다.
• ③ 오답: 연산은 바꾸었지만 각 변수의 보수를 빠뜨렸다.
• ④ 오답: 바깥의 NOT을 전혀 반영하지 않았다.

6. XY+X¬Y의 간소화 결과는?

① 0 ② 1 ③ Y ④ X

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: Y와 ¬Y가 서로 다른 합항에 있어 직접 AND되어 0이 되는 구조가 아니다.
• ② 오답: 상보쌍의 합은 1이지만 공통인수 X가 남아 X·1이 된다.
• ③ 오답: 두 항의 공통인수는 Y가 아니라 X이다.
• ④ 정답: X를 묶으면 X(Y+¬Y)=X·1=X이다.

7. X+¬XY에서 ¬X를 근거 없이 지워 X+Y라고 한 풀이를 올바르게 보완한 것은?

① X+¬XY=X+XY=X ② X+¬XY=(X+¬X)Y=Y ③ X+¬XY=(X+¬X)(X+Y)=X+Y ④ X+¬XY=X¬XY=0

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: ¬X를 X로 바꾸면 입력에 따른 진리값이 달라진다.
• ② 오답: 분배 과정에서 첫 항 X를 Y와 곱한 것으로 바꾸어 등식이 성립하지 않는다.
• ③ 정답: 분배법칙 뒤 X+¬X=1을 사용하므로 문자 소거의 근거가 완전하다.
• ④ 오답: 원래의 OR를 AND로 바꾸었으므로 같은 식이 아니다.

8. G=¬ABC+A¬BC+ABC를 간소화한 결과는?

① A+B+C ② BC+AC ③ AB+BC ④ ABC

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 곱항의 동시 조건을 개별 OR로 바꾸면 훨씬 많은 입력에서 1이 된다.
• ② 정답: ABC를 중복해 BC(¬A+A)+AC(¬B+B)로 묶으면 두 상보쌍이 1이 된다.
• ③ 오답: 첫째와 셋째 항은 B와 C를 공유하므로 BC가 남아야 하며 AB가 아니다.
• ④ 오답: 입력 A=0,B=1,C=1에서 원래 식은 1이지만 ABC는 0이다.

9. 부울함수 간소화가 올바른지 최종적으로 확인하는 기준은?

① 새 식의 문자가 알파벳순으로 놓여 있는가 ② 새 식에 보수 기호가 모두 사라졌는가 ③ 모든 입력 조합에서 원래 식과 새 식의 출력이 같은가 ④ 적용한 법칙의 수가 원래 항의 수보다 많은가

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 교환법칙으로 순서를 바꿀 수 있지만 알파벳순은 기능 동치의 조건이 아니다.
• ② 오답: 보수 변수가 남아도 더 이상 줄일 수 없는 올바른 식일 수 있다.
• ③ 정답: 간소화의 필수 조건은 진리표 전체가 같아 논리 기능이 보존되는 것이다.
• ④ 오답: 사용한 법칙 개수는 정확성을 보장하지 않으며 각 등호의 성립이 중요하다.

10. F=(X+XY)(X+¬XY)(X+YZ)를 가장 효율적으로 줄이기 위한 첫 판단은?

① 모든 괄호를 먼저 완전 전개해 항의 수를 늘린다. ② ¬X가 보이므로 식 전체의 보수를 구한다. ③ 세 괄호를 쌍대로 바꾸어 원래 식과 더한다. ④ 첫 인수의 X+XY=X를 적용해 공통적인 X가 전체를 흡수하는 구조를 찾는다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 전개도 가능하지만 이미 보이는 흡수법칙을 놓쳐 계산량과 오류 가능성을 키운다.
• ② 오답: 보수 문자의 존재는 함수 전체를 보수로 바꿀 근거가 아니다.
• ③ 오답: 쌍대식은 임의로 원래 식에 더할 수 있는 중복항이 아니다.
• ④ 정답: 첫 인수를 X로 줄이면 나머지 두 인수도 X에 흡수되어 최종적으로 F=X가 된다.

참고 자료와 작성 기준

이 글은 해당 차시 강의자료를 바탕으로 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 논리게이트와 부울식의 대응, 보수 계산과 대수적 간소화를 학습자가 직접 재현하고 검산할 수 있도록 예제와 오류 분석을 구성했습니다.

• 작성·편집: 올에이클래스 학습연구팀
• 주요 근거: 한국방송통신대학교 이산수학 8강 「부울대수」 강의자료(2021)
• 자료 성격: 강의자료의 정의와 범위를 바탕으로 재구성한 비공식 학습자료
• 편집 원칙: 올에이클래스 편집 정책
• 최종 내용 검토: 2026-09-05