4강 / 20강

부울대수 — 논리를 계산으로 바꾸기

그리고 그 계산을 그대로 만든 전자 회로

1854년, 조지 부울(George Boole)이라는 사람이 이런 생각을 합니다. "참·거짓도 숫자처럼 계산할 수 있지 않을까?"

그래서 참을 1, 거짓을 0으로 놓고 ∧를 곱하기(·), ∨를 더하기(+)처럼 다루기로 했습니다. 이것이 부울대수(Boolean algebra)입니다.

논리	부울대수	확인
p ∧ q	p · q (곱)	1·1=1, 1·0=0, 0·0=0 — 정확히 AND
p ∨ q	p + q (합)	0+0=0, 1+0=1, 1+1=1 — 여기만 다름
¬p	p' 또는 p̄	1'=0, 0'=1

1 + 1 = 1 이 눈에 걸리죠? 참에 참을 더해도 그냥 참이니까요. "또는"의 세계에서는 참이 아무리 많아도 참일 뿐입니다.

고등학생논리를 계산으로 바꾸기

2강의 진리표는 2ⁿ 줄이었습니다. 그걸 계산으로 줄이는 것이 부울대수예요.

논리식을 수식처럼 다룬다 — 규칙에 따라 줄인다

숫자 대수와 비교하면

숫자	논리
a + 0 = a	A ∨ 거짓 = A
a × 1 = a	A ∧ 참 = A
a × 0 = 0	A ∧ 거짓 = 거짓
분배법칙	있다 ✔

익숙한 규칙이 거의 그대로 통한다

다른 점도 있습니다

논리에만 있는 규칙	—
A ∨ A = A	멱등 — 숫자에는 없다
A ∨ (A ∧ B) = A	흡수
∨ 도 ∧ 에 분배된다	숫자는 한쪽만

a + a = a 는 숫자에서 안 되지만 논리에서는 된다

비유 — 물감 섞기

빨강에 빨강을 더하면? 여전히 빨강입니다.

	숫자	물감
같은 것을 두 번	두 배	그대로 ✔

"있다/없다" 의 세계에서는 두 번 있어도 있는 것이다

AND 는 곱셈, NOT 은 1에서 빼기. 논리가 산수가 되었습니다.

Python 브라우저에서 실행

# 부울대수를 0과 1로 직접 계산해 봅니다
def AND(a, b): return a * b
def OR(a, b):  return 1 if (a + b) > 0 else 0   # 1+1 도 1
def NOT(a):    return 1 - a

print("a b | AND  OR  NAND")
print("-" * 26)
for a in (0, 1):
    for b in (0, 1):
        print(f"{a} {b} |  {AND(a,b)}    {OR(a,b)}    {NOT(AND(a,b))}")

🎮 게이트를 직접 켜 보세요

입력 스위치를 켜고 끄면 출력 전구가 바뀝니다. NAND 게이트 하나만으로 AND · OR · NOT 을 전부 만들 수 있다는 것도 확인해 보세요. 그래서 실제 반도체 공장은 NAND 하나만 잘 만들면 됩니다.

고등학생이 강의가 컴퓨터 구조론과 만나는 곳

note 의 이 대목이 이론과 하드웨어를 잇습니다.

논리 규칙이 그대로 전자 회로가 된다

대응 관계

논리	회로	물리
참 / 거짓	1 / 0	전압 있음 / 없음
∧	AND 게이트	스위치 직렬
∨	OR 게이트	스위치 병렬
¬	NOT 게이트	반전

추상적인 논리가 전선의 연결 방식으로 실현된다

그래서 간소화가 곧 돈입니다

식을 줄이면	결과
게이트 수가 준다	칩이 작아진다
—	싸진다 · 전력이 준다
단계가 준다	빨라진다

수학적 간소화가 실제 제품의 원가를 정한다

1854년과 1937년

연도	일
1854	불이 논리를 대수로 만들었다
1937	섀넌이 스위치 회로와 같다는 것을 보였다 ⭐

83년 뒤에야 쓰임을 찾았다 — 순수 수학의 흔한 이야기다

섀넌의 이 논문은 석사 논문이었고 "20세기 가장 중요한 석사 논문" 이라 불립니다.

두 분야를 잇는 것이 새 발명만큼 중요할 수 있다

부울대수의 법칙들

산수와 닮았지만 딱 두 군데가 다릅니다.

교환·결합·분배 — 산수와 같습니다. p·q = q·p, p·(q+r) = p·q + p·r
흡수법칙 — 산수에 없습니다. p + p·q = p ("비가 오거나, 비가 오면서 춥거나" = 그냥 "비가 온다")
멱등법칙 — 산수에 없습니다. p + p = p, p · p = p

이 법칙들로 식을 줄이는 것을 간소화라고 합니다. 게이트 수가 줄면 칩이 작아지고 전기를 덜 먹어요. 코드에서는 if 조건이 짧아집니다.

코드 리뷰에서 조건문이 길다고 지적받았다면 흡수법칙을 떠올리세요.

Python 브라우저에서 실행

# 흡수법칙을 네 경우 모두에서 확인합니다:  p + p·q = p
print("p q | p + p·q | p  | 같은가")
print("-" * 34)
for p in (0, 1):
    for q in (0, 1):
        왼쪽 = 1 if (p + p * q) > 0 else 0
        print(f"{p} {q} |    {왼쪽}    | {p}  | {왼쪽 == p}")
print()
print("→ 조건 'A or (A and B)' 는 그냥 'A' 로 줄일 수 있습니다.")

고등학생조건문 간소화는 실전 기술입니다

note 의 이 말이 매일 쓰는 기술을 가리킵니다.

복잡한 if 를 줄이면 버그가 준다

예를 들어

# 복잡한 조건
if (A and B) or (A and not B):
    ...

# 간소화 — 분배법칙
if A:
    ...

단계	식
원래	(A ∧ B) ∨ (A ∧ ¬B)
분배	A ∧ (B ∨ ¬B)
배중률	A ∧ 참
결과	A ✔

B 는 아무 상관이 없었다 — 계산으로 드러난다

흡수법칙도 자주 쓰입니다

# 원래
if 회원 or (회원 and 쿠폰있음):
# 간소화
if 회원:

A ∨ (A ∧ B) = A — 뒤쪽은 이미 앞에 포함된다

왜 이런 코드가 생기나

원인	설명
기능을 덧붙이다	조건이 쌓인다
여러 사람이 고친다	전체를 안 본다
지우기가 무섭다	"혹시 필요할까 봐"

간소화가 정말 같은지 를 대수가 보장해 준다 — 그게 값어치다

비유 — 분수 약분

—	—
6/8	3/4 — 같은 값, 더 간단

뜻은 그대로 두고 모양만 단순하게 — 그게 간소화다

같은 결과, 5분의 1 크기. 이것이 논리 설계의 일입니다.

Python 브라우저에서 실행

# 게이트가 몇 개나 필요할까 — 식을 줄이면 회로가 작아집니다
식_긴것 = "A·B + A·B' + A'·B"     # 게이트 여러 개
# A·B + A·B' = A·(B + B') = A·1 = A   (분배 + 상보 + 항등)
식_짧은것 = "A + B"                 # OR 하나!

def 긴것(A, B):  return (A and B) or (A and not B) or ((not A) and B)
def 짧은것(A, B): return A or B

print("A B | 긴 식  짧은 식")
print("-" * 26)
for A in (0, 1):
    for B in (0, 1):
        print(f"{A} {B} |  {int(긴것(A,B))}      {int(짧은것(A,B))}")
print()
print("게이트 5개짜리 회로가 게이트 1개가 되었습니다.")

고등학생꼭 기억하세요

4강의 정리와 기억법입니다.

논리식은 대수처럼 다룰 수 있다 — 규칙만 알면

꼭 알 규칙 다섯

이름	식
교환	A ∧ B = B ∧ A
분배	A ∧ (B ∨ C) = (A∧B) ∨ (A∧C)
드모르간	¬(A ∧ B) = ¬A ∨ ¬B ⭐
흡수	A ∨ (A ∧ B) = A
배중률	A ∨ ¬A = 참

드모르간이 가장 자주 쓰인다 — 2강에서 이미 봤다

쌍대성 — 재미있는 성질

어떤 참인 등식에서 ∧↔∨, 참↔거짓 을 전부 바꾸면?

그것도 참인 등식이 된다 — 쌍대 원리

식	쌍대
A ∧ 참 = A	A ∨ 거짓 = A ✔
A ∨ (A ∧ B) = A	A ∧ (A ∨ B) = A ✔

규칙을 절반만 외우면 된다 — 나머지는 뒤집으면 나온다

8강에서 다시 만납니다

집합 연산이 정확히 같은 구조를 가집니다.

논리	집합
∧	∩
∨	∪
¬	여집합

겉모습이 다른 두 세계가 같은 규칙을 따른다 — 수학의 아름다움

🤔 확인 문제

부울대수에서 1 + 1 의 값은?

해설 + 는 OR 입니다 — "참이거나 참"은 그냥 참이므로 1이에요. 자리올림이 생기는 이진수 덧셈(1+1=10)과 혼동하기 쉬운데, 그건 부울대수가 아니라 산술 덧셈입니다.

🤔 확인 문제

A or (A and B) 를 간소화하면?

해설 흡수법칙입니다. A가 참이면 뒷부분을 볼 필요도 없이 전체가 참이고, A가 거짓이면 A and B도 거짓이라 전체가 거짓 — 결국 A의 값만 그대로 나옵니다.

🤔 확인 문제

NAND 게이트가 특별히 중요한 이유는?