직관 — 허용 규칙을 작은 판단 상자에 나눈다
시설의 출입 규칙을 ‘운영 시간이고, 회원이거나 관리자의 허가를 받았다’로 정하자. 한 상자는 회원 여부와 허가 여부를 합치고, 다음 상자는 운영 시간인지 확인한다.
각 상자가 논리 게이트, 상자 사이의 선이 0과 1을 전달하는 연결이다. 부울 함수를 회로로 바꾸면 조건을 어떤 순서로 결합하는지 눈으로 볼 수 있다. 컴퓨터가 수를 더하는 장치도 이런 게이트를 이어 만든다. 이 글은 출력이 현재 입력만으로 정해지는 회로(조합 논리 회로)를 다룬다.
논리 회로는 게이트를 선으로 연결한 구조다
논리 회로(logic circuit)는 입력 신호에 부울 연산을 적용해 출력 신호를 만드는 회로다. 입력은 부울 변수, 출력은 부울 함수로 나타낸다. 전압 같은 물리적 구현 대신 이상적인 0과 1의 기능만 살핀다.
출입 규칙의 변수는 이면 회원, 이면 관리자 허가, 이면 운영 시간이다. 출입 허용 여부를 로 쓰면 다음과 같다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 회원 입력 | member input | 회원이면 1 | |
| 허가 입력 | permission input | 관리자 허가가 있으면 1 | |
| 운영 시간 입력 | opening-hours input | 운영 시간이면 1 | |
| 중간 신호 | intermediate signal | 회원 또는 허가 여부 | |
| 출력 | output | 출입을 허용하면 1 |
기본 연산 하나를 하는 부품을 게이트라 한다. AND 게이트는 부울 곱, OR 게이트는 부울 합, NOT 게이트는 보수를 출력한다. 그림 1은 교과서에서 쓰는 게이트 기호다. 반가산기에 쓰는 XOR 게이트는 두 입력이 다를 때만 1을 낸다.
figures/gate_symbols.pyAND·OR 게이트는 출력 하나를 유지하면서 입력을 셋 이상 받을 수도 있다. 식 (1)은 먼저 OR 게이트로 를 구하고, AND 게이트로 를 구한다. 그림 2는 이 연결이다.
figures/access_circuit.py을 따라가면 , 이다. 반면 에서는 이어도 이다. 중간 결과만 보고 최종 출력을 판단하지 않는다.
모든 부울 함수는 곱의 합으로 쓸 수 있으므로, AND·OR·NOT 세 게이트만으로 어떤 논리 회로든 만들 수 있다. 교과서는 이를 논리 회로의 완전성이라 부른다.
조건표에서 논리 회로를 어떻게 설계하나요?
진리표로 모든 입력의 출력을 먼저 정하고, 출력이 1인 행으로 곱의 합을 만든 뒤 간소화해 게이트로 옮긴다. 마지막에 회로의 출력을 진리표와 다시 대조한다. 입력이 세 개이므로 여덟 조합을 확인한다.
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
빈칸이 있으면 그 상황의 동작이 아직 정해지지 않은 것이다. 출력이 1인 행마다 그 행에서만 1이 되는 곱을 만든다. 011은 , 101은 , 111은 다. 이 세 곱을 OR로 합치면 표와 같은 함수가 된다.
첫째 항과 셋째 항은 만 다르므로 묶인다.
그러면 다. 괄호 안은 분배법칙의 첫 꼴과 역법칙으로 정리한다.
따라서 로 식 (1)이 나온다. 식 (2)를 그대로 회로로 만들면 보수용 NOT 게이트 2개, 세 입력 AND 게이트 3개, 세 입력 OR 게이트 1개로 게이트가 6개다. 식 (1)은 OR와 AND 하나씩, 2개면 된다. 두 회로는 여덟 행에서 같은 출력을 낸다.
논리식의 괄호를 다르게 묶어도 회로가 같나요?
항상 같지는 않다. 를 로 바꾸면 운영 시간이 아니어도 허가 만으로 출력이 1이 된다. 에서 원래 출력은 0, 바꾼 식의 출력은 1이다.
논리식을 간소화하면 회로의 동작도 달라지나요?
올바르게 간소화했다면 입력과 출력의 대응은 그대로다. 출입 회로는 식 (2)로 만들면 게이트 6개, 식 (1)로 만들면 2개지만 여덟 입력의 출력이 같다. 실제 지연이나 전력은 부품과 연결 조건을 더 알아야 비교할 수 있다.
카르노 맵은 이웃한 1을 묶어 회로를 줄인다
카르노 맵은 진리표의 칸을 이웃한 칸끼리 한 변수만 다르게 배치한 표다. 이웃한 1을 2개, 4개씩 묶으면 묶음 안에서 바뀌는 변수가 사라져 곱 하나가 된다. 식 (3)의 계산을 눈으로 하는 셈이다.
교과서의 예를 따라 세 명이 찬성(1)·반대(0)로 투표하는 투표기를 설계하자. 두 명 이상 찬성하면 안건이 통과()한다. 출력이 1인 행은 011, 101, 110, 111이다.
행에 와 를, 열에 , , , 를 놓는다. 열의 가 11, 10, 00, 01 순서라 옆 칸끼리 한 변수만 다르다. 맨 오른쪽 열 와 맨 왼쪽 열 도 만 다르므로 이웃으로 본다. 그림 3은 식 (5)의 네 1을 이 표에 적은 것이다.
figures/majority_kmap.py윗줄 왼쪽 두 칸 와 를 묶으면 가 사라져 다. 첫 열의 두 칸은 가 사라져 , 양 끝의 두 칸은 가 사라져 다.
묶을 때 지키는 규칙은 셋이다.
- 묶음은 1, 2, 4, 8처럼 2의 거듭제곱 개의 칸으로 된 직사각형이다.
- 모든 1을 빠짐없이 덮고, 한 칸을 여러 묶음에 써도 된다. 부울 대수의 멱등법칙 덕분이다.
- 묶음이 클수록 남는 변수가 적다. 세 변수 맵에서 2칸 묶음은 변수 둘, 4칸 묶음은 변수 하나인 곱이다.
식 (5)를 그대로 만들면 NOT 게이트 3개, 세 입력 AND 게이트 4개, 네 입력 OR 게이트 1개로 8개가 든다. 식 (6)은 두 입력 AND 게이트 3개와 세 입력 OR 게이트 1개, 모두 4개다. 그림 4가 그 회로다. 입력선은 점이 찍힌 곳에서만 갈라지고, 연결되지 않고 지나가는 곳은 반원으로 넘어간다.
figures/majority_circuit.py카르노 맵은 변수가 몇 개일 때 쓰나요?
카르노 맵은 보통 변수가 4개 이하일 때 쓴다. 변수가 4개면 칸이고, 양 끝 열뿐 아니라 맨 위·맨 아래 행도 이웃으로 본다. 변수가 늘면 칸이 개로 늘어 이웃을 눈으로 찾기 어려우므로 표로 기계적으로 묶는 방법을 쓴다.
2변수·4변수 맵과 네 모서리 묶음, 겹쳐 묶는 4변수 간소화는 카르노 맵에서 다룬다.
반가산기는 합과 올림을 따로 출력한다
반가산기는 두 비트를 더해 합 비트와 올림을 두 출력선으로 따로 내는 회로다. 처럼 결과를 한 비트로 나타낼 수 없기 때문이다. 입력 이름은 이 절에서 소문자 를 쓴다.
| 합 비트 | 올림 | ||
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
는 두 입력이 서로 다를 때 1인 XOR, 즉 다. 는 둘 다 1일 때만 1인 AND다. 그림 5처럼 입력 는 접점에서 갈라져 두 게이트에 함께 들어간다. 출력 쌍을 이진수로 적을 때 순서는 다.
figures/half_adder.py네 입력에서 다음 등식이 성립한다. 여기서 와 는 부울 연산이 아니라 정수 연산이다.
예를 들어 이면 다. 부울 합의 과 식 (8)의 정수 덧셈은 역할이 다르다. XOR 게이트가 없으면 식 (7)의 를 NOT 2개, AND 2개, OR 1개로 만든다. 같은 XOR을 신경망으로 만드는 방법은 XOR과 다층 퍼셉트론에서 다룬다.
반가산기 하나로 여러 비트의 덧셈을 모두 처리하나요?
아니다. 반가산기는 입력 비트 두 개만 받으므로 앞 자리에서 넘어온 올림을 받을 입력이 없다. 두 비트와 들어온 올림을 함께 더하는 전가산기는 반가산기 2개와 OR 게이트 1개로 만들고, 이진수의 사칙연산의 식 (1)을 계산한다. 그 글의 는 들어온 올림이고, 이 글의 는 나가는 올림이다.
NAND 게이트만으로 모든 논리 회로를 만들 수 있나요?
그렇다. NAND 게이트는 를 내므로 두 입력에 같은 선을 넣으면 로 NOT이 되고, NAND 출력을 이 NOT에 넣으면 AND가 된다. 드모르간의 법칙과 이중보수법칙으로 이므로 OR도 만들 수 있다. NOT은 NAND 1개, AND는 2개, OR는 3개가 들고, 세 게이트를 모두 만들 수 있으니 완전성에 따라 어떤 회로든 된다.
논리 회로는 진리표로 요구를 고정하고, 곱의 합을 부울 대수 법칙이나 카르노 맵으로 간소화한 뒤 게이트로 이어 설계하며, 간소화 전후의 회로는 모든 입력에서 같은 출력을 낸다.
논리 회로의 흔한 오해
- 선이 만나 보이면 연결된 것이다 — 회로도에서 연결은 접점의 점으로 표시한다. 그림 4의 입력선은 와 의 세로선을 지나가지만 반원으로 넘어가므로 그 선들과 이어지지 않는다.
- 카르노 맵에서 이어진 1 세 칸은 한 묶음으로 묶는다 — 그림 3의 윗줄 1 세 칸은 양 끝이 이웃이라 이어져 있다. 그러나 3은 2의 거듭제곱이 아니어서 곱 하나로 줄지 않는다. 두 칸씩 와 로 묶어야 한다.
- 한 번 묶은 1은 다른 묶음에 쓸 수 없다 — 그림 3의 칸을 묶음에만 쓰면 와 가 혼자 남는다. 그러면 식이 로 길어진다. 겹쳐 묶어야 식 (6)이 된다.
직접 해보기
- 새 규칙 에서 입력 101, 011의 출력을 순서대로 구하자.
- 두 입력이 모두 0일 때만 1인 함수를 NOT·OR 게이트로 표현하자.
- 반가산기에 입력 , 을 넣어 를 구하고 식 (8)을 확인하자.
- 출입 규칙에 ‘정비 중이면 출입 금지’ 조건 를 더한다. 이 정비 중일 때 새 출력식을 쓰고, 에서 출력값을 구하자.
- 세 변수 함수의 출력이 입력 001, 011, 101, 111에서만 1이다. 그림 3과 같은 카르노 맵에 1을 적고 묶어 간소화하자.
답과 풀이
- 101에서는 , 011에서는 이다. 입력의 순서는 다.
- 다. OR 게이트 출력에 NOT 게이트를 연결한다. 입력 00, 01, 10, 11에 대한 출력은 1, 0, 0, 0이다.
- , 이다. 정수 등식 이 성립한다.
- 다. 에서는 이므로 출력이 0이다. 원래 허용 조건이 모두 참이어도 정비 조건이 막는다.
- 네 입력은 모두 이므로 1은 열과 열의 두 행 전부, 네 칸에 적힌다. 양 끝 열은 이웃이므로 네 칸이 2행 2열의 직사각형 묶음 하나가 되고, 와 가 사라져 출력은 다. 게이트 없이 입력선 를 그대로 출력에 이으면 된다.
더 읽기
- MIT OCW, Computation Structures 4.1 — 진리표에서 출력 1인 행을 곱으로 나타내고 OR로 합치는 설계 절차를 실제 열어 확인했다.
- Computation Structures, Combinational Logic — Steve Ward의 기능 명세·부울식·회로 구성의 대응을 확인했다. 같은 기능과 구현 특성을 구별하는 근거다.
- 우리교과서, 2022 이산 수학 — ‘부울 함수와 논리 회로’의 교과 범위를 확인했다.
영상 노트
- 00:00 출입 규칙을 세 입력으로 구분
- 00:40 그림 1의 게이트 기호 네 가지
- 01:30 그림 2에서 입력 101의 값 따라가기
- 02:30 진리표에서 식 (2) 만들기
- 03:30 식 (3)과 식 (4)로 간소화하고 게이트 수 6과 2 비교
- 04:40 다수결 투표기와 식 (5)
- 05:30 그림 3의 카르노 맵, 양 끝 열 묶기
- 06:40 그림 4의 접점과 반원 교차
- 07:30 그림 5와 식 (7)의 반가산기, 식 (8) 검산
지도에서의 위치
- 2026-11-16 · 에이전트 초안 (수식 4, 그림 2)
- 2026-11-17 · 전수 검수 반영 — 교과서 게이트 기호와 접점·교차 표기로 회로도를 다시 그리고, 논리 회로의 완전성, 간소화 전후 게이트 수, 3인 다수결 투표기의 카르노 맵 설계, NAND·전가산기 질문, 출처를 단 흔한 오해와 연습 다섯 문항을 보강함 (에이전트 수정, 그림 2→5)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림
- 2026-11-17 · 새 글 ‘카르노 맵’으로 가는 링크와 다음 개념 연결 (에이전트 수정)