| '''이론 컴퓨터 과학 {{{#!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> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
[[컴퓨터공학|컴퓨터 과학 & 공학
Computer Science & Engineering
]]- [ 펼치기 · 접기 ]
- ||<tablebgcolor=#fff,#1c1d1f><tablecolor=#373a3c,#ddd><colbgcolor=#0066DC><colcolor=white> 기반 학문 ||수학(해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학(환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학(형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 ||
하드웨어 구성 SoC · CPU · GPU(그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품 기술 기계어 · 어셈블리어 · C/C++ · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시(SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속 연구
및
기타논리 회로(보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영 체제 · 데이터베이스 · 프로그래밍 언어{컴파일러(어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩(유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도(최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리(기계 번역 · 음성인식) · 버전 (버전 관리 시스템 · Git · GitHub)
1. 개요
論理回路 / logic circuit불 대수(Boolean algebra)를 이용하여 1개 이상의 논리 입력을 넣었을 때 일정한 논리 연산에 의해 1개의 논리 출력을 얻는 회로이다. 1937년에 석사 과정 대학원생이던 클로드 섀넌이 불 대수를 전자 회로의 해석에 도입하여 디지털 논리 회로 이론을 창시하였다. 즉, 서로를 반대하는 수로 0과 1뿐인 2진법의 해석을 따른다.
전자 회로(electronic circuit)의 구성 요소들을 이용하여 만든 논리 게이트(NAND, NOR, NOT 등)를 이용해 원하는 동작을 구현하는, 현대의 디지털 시대를 이끈 학문이다.[1]
간단하고 쉽게 설명하자면, ‘모여서 전자 기기 등 다른 더 복잡한 전기 회로들을 구성하는 가장 기초적인 회로’ 정도로 생각하면 된다.
2. 설명
정보 대학과 공과 대학의 전기 전자 공학부 및 컴퓨터 공학부의 전공 과목 중 하나이다. 디지털 공학이라고도 한다. 논리 연산의 방법과 현대의 디지털 회로에 쓰이는 여러 가지 개념 및 적용법을 배우는 과목이다. 이 과목에선 기본적으로 입력값과 출력값이 0 과 1로 구성되어 있기 때문에 접근 방식이 기존에 학생들이 배우던 아날로그 방식과는 확연히 다르며[2] 아날로그 회로를 생각하고 이 과목을 듣게 되면 곤란해진다.기본적인 접근 방식이 불 대수이기 때문에 집합(a set of elements)[3]을 생각하면 쉽다. 그러나 사실 이 과목은 엄밀히 말하면 논리 연산의 방법 자체를 배우는 것에 중점을 두기 보다는 디지털 회로에 쓰이는 개념들에 더 중점을 두는 과목이기 때문에 앞부분을 잘한다고 뒷부분까지 잘하게 된다는 보장은 없다. 특히 이 과목은 교수의 재량권이 매우 큰 과목이고, 딱 어디까지가 디지털 논리 회로고 어디부터가 디지털 시스템 설계인가 하는 명확한 기준이 없다. 따라서 교수의 강의 방식과 강의 역량에 따라서도 공부량과 흥미가 좌우될 수 있는 과목.
일반적으로 전기 전자 공학부와 컴퓨터 공학부의 1, 2학년 또는 3학년 학생들이 주로 배우게 되며 당연하게도 전공 기초인 학교가 많기 때문에 웬만한 전자 공학도라면 한 번쯤은 듣게 되는데 앞부분은 몰라도 뒷부분에서 상당히 머리가 아픈 개념들이 많이 나온다. 기초 과목이므로 전공과목 중 가장 쉬운 과목이라 생각하는 학생도 많이 있고, 어렵게 느끼는 학생도 많은 등 체감 난이도가 사람마다 천차만별인 과목이다. 낯선 개념들이 쏟아지므로 이들과 어서 친해지자.
논리 회로 과목은 일반적으로 디지털 개요를 시작으로, 수 체계, 불 대수, 조합 회로, 순서 회로, 그리고 기타 응용 회로 순으로 학습이 진행된다.
3. 주요 개념
3.1. 불 대수와 논리 연산
불 대수와 논리 연산은 논리 회로 해석의 가장 기본이 되는 부분이다. 논리 연산의 상세한 설명은 논리 연산를 참고하자.| 이름 | AND | OR |
| 항등 법칙 | [math(\rm 1A=A)] | [math(\rm 0+A=A)] |
| 지배 법칙 | [math(\rm 0A=0)] | [math(\rm 1+A=1)] |
| 동일 법칙[4] | [math(\rm AA=A)] | [math(\rm A+A=A)] |
| 역원 법칙 | [math(\rm A\overline A =0)] | [math(\rm A+\overline A =1)] |
| 교환 법칙 | [math(\rm AB=BA)] | [math(\rm A+B=B+A)] |
| 결합 법칙 | [math(\rm \left( AB \right) C = A \left( BC \right) )] | [math(\rm \left( A+B \right) + C = A + \left( B + C \right) )] |
| 분배 법칙 | [math(\rm A+BC = \left( A+B \right)\left( A+C \right) )] | [math(\rm A\left( B+C \right) =AB+AC)] |
| 흡수 법칙 | [math(\rm A\left( A+B \right)=A)] | [math(\rm A+AB=A)] |
| 드모르간 법칙 | [math(\rm \overline{AB} = \overline A + \overline B)] | [math(\rm \overline{A+B} = \overline A\ \overline B)] |
논리 회로를 간호화 하는 방법으로 카르노 맵, 콰인-맥클러스키 알고리즘(Quine-McCluskey method), ESPRESSO 등이 있다. 특히 드모르간 법칙은 논리식을 간단히 만드는 데 많이 쓰이므로 필수적으로 익혀 두어야 한다.
3.1.1. SOP와 POS
논리식은 SOP(Sum of Products) 또는 POS(Product of Sums) 둘 중 하나로 표현이 가능하다.SOP(Sum of Products)는 곱의 합이라고도 불리며, 여러 개의 곱셈 항들(minterm)을 더한 형태다. minterm은 진리표에서 출력이 1인 경우에 대한 입력 조합을 곱(AND)으로 나타낸 것이다. 예를 들어서, [math(AB+BC+CA)]로 표현하는 것이 SOP이다.
POS(Product of Sums)는 합의 곱이라고도 불리며, 여러 개의 덧셈 항들(maxterm)을 곱한 형태다. maxterm은 진리표에서 출력이 0인 경우에 대한 입력 조합을 덧셈(OR)로 나타낸 것이다. 예를 들어서, [math((A+B)(B+C)(C+A))]로 표현하는 것이 POS이다.
=====# 예제 #=====
예를 들어서, 다음과 같이 어떤 논리식의 진리표가 있다고 할 때, SOP와 POS 형태의 논리식을 구하는 방법은 다음과 같다.
- 진리표에서 minterm과 maxterm을 구함
- minterm은 [math(Y=1)]인 경우 구함 (빨간색)
- maxterm은 [math(Y=0)]인 경우 구함 (파란색)
- 모든 minterm을 더하여 SOP 형태의 논리식을 구함
- 모든 maxterm을 더하여 SOP 형태의 논리식을 구함
2. SOP 또는 POS 형태의 논리식을 구함
| [math(A)] | [math(B)] | [math(Y)] | minterm | maxterm |
| 0 | 0 | 0 | - | [math(\textcolor{blue}{A + B})] |
| 0 | 1 | 1 | [math(\textcolor{red}{\overline{A} B})] | - |
| 1 | 0 | 0 | - | [math(\textcolor{blue}{\overline{A} + B})] |
| 1 | 1 | 1 | [math(\textcolor{red}{A B})] | - |
SOP로 표현한 논리식: [math(Y=(\overline{A} B)+(A B))]
POS로 표현한 논리식: [math(Y=(A + B)(\overline{A} + B))]
3.1.2. 카르노 맵
카르노 맵(카노 맵, Karnaugh map, K-map)은 논리 회로를 간소화하기 위해 Maurice Karnaugh가 고안한 방법이다.[5] 카르노 맵은 진리표를 2차원 테이블로 변환한 것을 가리킨다.카르노 맵을 사용한 논리식 간소화 과정은 다음과 같다.
- 간소화하고자 할 논리 회로의 진리표를 작성
- 진리표를 기반으로 카르노 맵을 작성
- 카르노 맵에서 인접한 셀들은 하나의 변수만 다르도록 배치해야 함 (주로 그레이 코드 사용함)
- 그룹화: 값이 1인 칸을 직사각형 또는 정사각형 형태로 묶음
- 그룹 크기는 1, 2, 4, 8 등 [math(\boldsymbol {2^n})]으로 묶어야 함
- 가능한 한 큰 그룹으로 묶는 것이 최적화에 유리함
- 그룹화를 통해 최소화된 논리식을 생성함
예를 들어서 [math(\overline{A}BC+A\overline{B}C+AB\overline{C}+ABC)]와 같은 논리식을 가지는 논리 회로가 있다고 가정하자. 이 논리 회로의 진리표를 작성하면 다음과 같다.
| A | B | C | 출력 |
| 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 | 1 |
| 1 | 1 | 1 | 1 |
이 진리표를 기반으로 카르노 맵으로 작성하고, 값이 1인 칸을 사각형 그룹으로 묶으면 다음과 같다.
- [math(B=1)]이고, [math(C=1)]인 사각형 → [math(BC)]
A \\ BC 00 01 11 10 0 0 0 1 0 1 0 1 1 1 - [math(A=1)]이고, [math(C=1)]인 사각형 → [math(AC)]
A \\ BC 00 01 11 10 0 0 0 1 0 1 0 1 1 1 - [math(A=1)]이고, [math(B=1)]인 사각형 → [math(AB)]
A \\ BC 00 01 11 10 0 0 0 1 0 1 0 1 1 1
각 그룹에서 도출한 최소 논리식을 OR 연산으로 결합하면, 다음과 같이 간소화된 논리식이 도출된다.
[math(\overline{A}BC+A\overline{B}C+AB\overline{C}+ABC=\mathbf{BC+AC+AB})]
3.2. 조합 회로
조합 회로(combinational circuit 또는 structural design)는 기억 장치가 없고, 외부의 입력만을 사용하여 출력을 만들어내는 논리 회로이다. 기본적인 논리 게이트들도 조합 회로이고, 가산기(adder), 비교기(comparator), 디코더(decoder), 인코더(encoder), 멀티플렉서(multiplexer 또는 MUX), 디멀티플렉서(demultiplexer 또는 DEMUX) 등이 논리 게이트를 응용한 것들도 조합 회로이다.
3.2.1. 논리 게이트
논리 게이트는 논리 회로에서 가장 기본이 되는 AND, OR, NOT와 같은 논리 연산을 구현한 회로다. 논리 게이트는 스위치로 쉽게 구현할 수 있다.[8] 논리 연산에 대한 논리식 및 진리표와 같은 자세한 내용은 논리 연산 문서를 참고하자.Circuit Scramble처럼 논리 회로를 모델로 한 게임을 해보면 직관적으로 이해할 수 있다.[9] Circuit Scramble 1-20 스테이지 공략
- NOT 게이트
- NAND 게이트
- 모든 논리 게이트는 NAND 게이트만으로 구현이 가능하다. 모든 논리 게이트를 만들 수 있기에 따로 범용 게이트(universal gates)라고도 불린다. 구현 방법은 위키백과 NAND logic 문서 참고.
- NOR 게이트
- NAND 게이트와 마찬가지로 모든 논리 게이트는 NOR 게이트만으로 구현이 가능하다. 모든 논리 게이트를 만들 수 있기에 따로 범용 게이트(universal gates)라고도 불린다. 구현 방법은 위키백과 NOR logic 문서 참고.
- XOR 게이트
- OR 게이트가 입력값 중 하나라도 1이라면 1을 출력하는 데 반해 XOR은 입력이 서로 다르면 1을 출력하고, 같으면 0을 출력한다.
- 입력이 3개 이상인 경우에는 입력의 1이 홀수 개일 때 1을 출력한다.
- 암호화에 주로 사용된다. 암호키와 원본 데이터를 서로 XOR하면 암호문이 만들어진다. 암호문과 암호 키를 둘 다 가지고 있어야 원문을 알아낼 수 있다.
XNOR은(는) 여기로 연결됩니다.
작곡가 Frums의 곡에 대한 내용은 XNOR XNOR XNOR 문서 참고하십시오.- XNOR 게이트
- 입력값이 서로 같으면 1을 출력하고, 다르면 0을 출력한다. 그래서 비교 게이트나 일치 확인 게이트라고도 불린다.
- 버퍼(BUF) 게이트
3.2.1.1. 기호
| |
| 위: IEC 기호 / 중간: ANSI 기호 / 아래: DIN 기호[12] |
3.2.2. 가산기
3.2.3. 멀티플렉서
멀티플렉서(multiplexer, MUX)는 여러 입력 신호 중 하나만 선택하여 출력으로 내보내는 조합 회로이다. 예를 들어서, 위 이미지의 4x1 멀티플렉서는 s0과 s1 제어 신호에 따라서 x0, x1, x2, x3 입력 신호 중 하나를 출력 신호 y로 내보낸다. 이 4x1 멀티플렉서의 진리표는 다음과 같다.
| 제어 신호 | 출력 신호 | ||
| s1 | s0 | y | |
| 0 | 0 | x0 | |
| 0 | 1 | x1 | |
| 1 | 0 | x2 | |
| 1 | 1 | x3 | |
3.2.4. 해저드
해저드(hazard)란 조합 회로에서 짧은 시간 동안 잘못된 값을 출력하는 것을 가리키며, 글리치(glitch)라고도 불린다. 주로 전파 지연(propagation delay)이나 레이스 조건(race condition)에 의해서 발생한다.해저드는 크게 2가지 유형으로 나뉜다.
- 정적 해저드(static hazard)
- 출력이 논리적으로 변하지 않아야 할 때, 잠시 잘못된 값이 출력되는 것
- 예시: 출력이 1로 유지되어야 하는데 잠시 0으로 떨어지는 경우
- 동적 해저드(dynamic hazard)
- 출력이 한 상태에서 다른 상태로 변할 때, 중간에 여러 번 값이 변하는 것
- 예시: 출력이 0에서 1로 변할 때, 중간에 0→1→0→1처럼 여러 번 값이 변하는 경우
3.3. 순차 회로
순차 회로는 기억 장치가 있어서 내부적으로 특정한 상태를 가질 수 있고, 외부 입력과 내부 상태를 모두 사용하여 출력을 만들어내는 논리 회로이다. 래치, 플립플롭, 레지스터, 카운터, FSM 등이 순차 회로이다.
순차 회로는 내부 상태가 클럭과 동기화되어 변화하는지에 따라서 동기식과 비동기식이 나뉜다. 동기식은 클럭 펄스에 동기되어 입력이 바뀌면서 내부 상태가 변하는 논리 회로다. 비동기식은 클럭 펄스에 동기되지 않고(또는 클럭 펄스를 사용하지 않고) 입력이 바뀌는 즉시 내부 상태가 변하는 논리 회로다. 플립플롭이 동기식 순차 회로이고, 래치(latch)가 비동기식 순차 회로다.
동기식 순차 회로는 클럭 신호에 따라 동작하므로, 회로가 어떻게 작동하는지 이해하려면 파형(waveform)과 타이밍 다이어그램(timing diagram)을 살펴보는 것이 중요하다.
3.3.1. 래치
래치는 1 bit의 정보를 저장하는 가장 기본적인 순차 회로이다. 래치는 입력 신호가 특정한 레벨(0 또는 1)일때만 출력이 변화하기 때문에 레벨 트리거(level triggered) 방식 순차 회로라고도 불린다.종류는 구현 방식에 따라서 SR 래치, D 래치 등으로 분류된다.
- SR 래치 회로도
NOR 게이트로 구현한 SR 래치 NAND 게이트로 구현한 SR 래치
- D 래치 회로도
3.3.2. 플립플롭
플립플롭 또한 래치와 마찬가지로 1 bit의 정보를 저장하는 가장 기본적인 순차 회로이다. 래치와는 달리 클럭 신호의 엣지(edge, 0→1 또는 1→0로 변화하는 순간)에서만 출력이 변화하기 때문에 에지 트리거(edge triggered) 방식 순차 회로라고도 불린다.
3.3.3. 레지스터
레지스터란 플립플롭이 여러 개로 구성되어 여러 비트의 정보를 저장하는 회로이다.
위 이미지의 회로는 레지스터를 응용한 것으로, 직렬 신호를 병렬 신호로 변환하는 SIPO 시프트 레지스터(Serial In Parallel Output shift register)이다.
3.3.4. 유한상태기계(FSM)
4. 각종 시험에서의 출제
전자 분야 관련 시험에서는 거의 다 출제된다. 논리회로라는 이름의 과목으로 출제되는 경우도 있지만, 다른 이름을 가진 과목의 내용으로서 출제되는 경우가 더 많다.- 전자계산기기사 - 논리회로 단독 과목으로 출제
- 전기기사, 전기공사기사 - 회로이론 및 제어공학의 내용(시퀀스 제어)으로서 출제.
- 소방설비기사, 소방설비산업기사[13] - 소방전기일반의 내용(자동 제어)으로서 출제.
- 전자기사, 전자산업기사 - 전자 회로의 내용으로서 출제.
- 전자계산기조직응용기사 - 전자계산기구조의 내용으로서 출제.
- 임베디드기사 - 임베디드하드웨어의 내용으로서 출제.
- 무선설비기사, 무선설비산업기사 - 디지털전자회로의 내용으로서 출제.
- 철도신호기사 - 회로이론 및 제어공학(시퀀스 제어), 전자공학의 내용으로서 출제.
- 철도신호산업기사 - 전자공학의 내용으로서 출제.
- 전자계산기제어산업기사 - 디지털공학의 내용으로서 출제.
- 정보처리기능사 - 부울대수 논리연산 및 가산기 등이 출제.
5. 관련 도서
- Contemporary Logic Design 2판 - Randy H. Katz
6. 관련 문서
- 클로드 섀넌
- 컴퓨터 구조론 및 컴퓨터 구조[14]
- 임베디드 시스템
- 홈브루 컴퓨터
- 논리 연산(logical operation, logical connective)
- 플래시 메모리
- 순서도
- 경우의 수
- 마인크래프트/팁/레드스톤 회로[15]
- 러스트(게임)/전기장치
- Oxygen Not Included/연구
[1] 엄밀히 말하면 전자가 아닌 다른 물질을 기반으로 한 논리 게이트도 얼마든지 존재한다. 이론적으로는 전자 회로와 똑같은 일을 수행할 수 있다. 단지 전자 기반 회로보다 훨씬 비효율적이라 도태됐을 뿐.유체 기반 논리 회로[2] 비록 최근에는 기기의 소형화 및 정밀화 때문에 혼성 신호 모델이 각광을 받고 있긴 해도 이 과목을 배우는 사람은 대부분의 경우 어디까지나 학부생이라는 점을 알아둘 필요가 있다.[3] 단순히 집합이라기보다는 환(ring)으로 접근하는 것이 더 적절할 수 있다. 잘 정의된 독자적인 연산 체계가 있기 때문.[4] 멱등 법칙이라고도 한다.[5] 1953년, Maurice Karnaugh가 "The Map Method for Synthesis of Combinational Logic Circuits"라는 제목의 논문을 발표했다.[6] 예를 들어서, 그룹에서 [math(A)]와 [math(B)]가 항상 1이라면 [math(AB)]로 묶고, [math(C)]가 0 또는 1로 변하면 [math(C)]는 생략함[7] 예를 들어서, 각 그롭에서 도출한 논리식이 각각 [math(AB)]와 [math(BC)]라면 최종적으로 [math(AB+BC)]로 결합함[8] 집적 회로에서 이러한 스위치를 구성하는 핵심 요소가 트랜지스터이기 때문에, 집적 회로 설계에서 트랜지스터는 매우 중요한 역할을 한다.[9] 애석하게도 맨 아래의 BUF 같은 건 등장하지 않는다.[10] 유접점 회로, 릴레이 회로[11] 해당 접점과 관련된 부품이 작동 시 접점이 붙어서 회로가 닫혀 흐르게 하는 A 접점과 달리 오히려 떨어져서 회로를 열리게 한다.[12] 그림에서는 NOT이 INV(Inverted)로 표시되어 있다.[13] 전기만 해당. 기계는 해당되지 않음.[14] 컴퓨터는 당연히 회로가 존재하기에 제대로 된 컴퓨터 구조책에는 논리 회로 개념이 들어간다.[15] 논리 게이트들을 구성해 이를 통한 멀티플렉서나 플립플롭, 래치 등을 전부 구현할 수 있으며, 작동도 한다. 이를 통해 계산기나 시계 등을 만드는 유튜브 영상도 찾아볼 수 있다.