11. Logic and Computers

컴퓨터는 논리 기계다

컴퓨터는 숫자를 계산하는 기계가 아니라 사실 논리 연산을 하는 기계다. 컴퓨터의 모든 데이터는 0과 1로 표현되는데, 이게 바로 명제 논리의 True/False와 1:1로 대응된다.

• 0 ↔ False
• 1 ↔ True

산술 연산, 데이터 저장, 프로그램 명령어 — 전부 이 비트들에 대한 논리 연산으로 이루어져 있다.

---

Logic Gates: 논리의 하드웨어 구현

논리 연산자를 실제 하드웨어로 구현한 게 논리 게이트(Logic Gate)다. 게이트는 하나 이상의 비트를 입력받아 단일 비트를 출력한다.

게이트	논리 연산	설명
AND	x ∧ y	둘 다 1일 때만 1
OR	x ∨ y	하나라도 1이면 1
NOT	¬x	입력을 반전
XOR	x ⊕ y	둘이 다를 때만 1

게이트들을 연결하면 회로(Circuit)가 된다. 한 게이트의 출력이 다음 게이트의 입력이 되는 식으로 체인처럼 이어지고, 이렇게 복잡한 연산을 구현할 수 있다.

---

XOR을 AND, OR, NOT으로 만들기

XOR은 기본 게이트가 아니지만, 아래 동치 관계를 이용하면 AND, OR, NOT만으로 구현할 수 있다.

x ⊕ y ≡ (x ∧ ¬y) ∨ (¬x ∧ y)

이 공식이 이미 AND, OR, NOT만으로 이루어져 있으니까, 공식을 그대로 회로로 그리면 XOR 게이트가 완성된다. 논리식 = 회로도인 셈이다.

---

Functional Completeness와 NAND 게이트

저번 시간에 {∧, ∨, ¬}이 functionally complete하다고 배웠다. 하드웨어 관점에서 보면 이 말은 AND, OR, NOT 게이트만으로 어떤 회로든 만들 수 있다는 뜻이다.

근데 더 놀라운 건, NAND 게이트 하나만으로도 functionally complete하다는 거다.

p NAND q = ¬(p ∧ q)

NAND 하나로 NOT, AND, OR을 전부 표현할 수 있다.

• ¬p ≡ p NAND p
• p ∧ q ≡ (p NAND q) NAND (p NAND q)

실제 반도체 제조에서 NAND 게이트 하나만 대량생산하면 세상의 모든 디지털 회로를 만들 수 있다. 경제적으로 엄청난 장점이다.

---

이진수 표현

컴퓨터는 숫자도 이진수(base-2)로 표현한다. 각 자리가 2의 거듭제곱을 나타낸다.

예를 들어 100100을 10진수로 변환하면:

1×2⁵ + 0×2⁴ + 0×2³ + 1×2² + 0×2¹ + 0×2⁰ = 32 + 4 = 36

---

Half Adder: 1비트 덧셈 회로

1비트 두 개를 더하면 결과가 두 자리가 될 수 있다. (1+1=10) 그래서 출력이 두 개다.

• Sum(s): 결과의 현재 자리
• Carry(c): 윗자리로 올라가는 올림

x	y	c	s
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

진리표를 보면 패턴이 보인다.

• s = x ⊕ y (둘이 다를 때만 1 → XOR)
• c = x ∧ y (둘 다 1일 때만 1 → AND)

이 XOR 게이트 + AND 게이트 조합이 Half Adder(HA)다.

---

Full Adder: carry-in까지 처리

Half Adder는 x랑 y만 더할 수 있다. 근데 실제 멀티비트 덧셈에서는 아랫자리에서 올라온 carry-in도 같이 더해야 한다.

10진수 369 + 451을 생각해보면:

• 1의 자리: 9+1=10 → 0 쓰고 1 올림
• 10의 자리: 6+5+올림 1 = 12 → 2 쓰고 1 올림
• 100의 자리: 3+4+올림 1 = 8

각 자리마다 아랫자리의 올림을 같이 처리해야 한다. 이진수도 똑같다.

Full Adder(FA)는 입력이 세 개(x, y, carry-in)이고 출력이 두 개(sum, carry-out)다. Half Adder 두 개를 이렇게 연결하면 만들 수 있다.

1. 첫 번째 HA로 x와 y를 더한다.
2. 두 번째 HA로 그 결과에 carry-in을 더한다.
3. 두 HA 중 하나라도 carry가 나오면 carry-out = 1.

---

Ripple-Carry Adder: n비트 덧셈

Full Adder 하나는 1비트 덧셈만 한다. n비트 덧셈이 필요하면? FA를 n개 일렬로 연결하면 된다. 각 FA의 carry-out이 다음 FA의 carry-in으로 들어가는 식으로.

이게 Ripple-Carry Adder다. carry가 오른쪽에서 왼쪽으로 물결처럼 전파된다고 해서 붙은 이름이다.

16비트 덧셈 = FA 16개를 연결한 것. 각 FA가 자기 자리만 담당하고, 올림만 옆으로 넘기는 구조다.

---

추상화: CS의 핵심 아이디어

이 강의 전체의 핵심은 추상화(Abstraction)다. 아랫단계의 복잡함을 숨기고 그 위에 더 강력한 걸 쌓는 것.