부울 대수 (Boolean Algebra)

부울 대수 (Boolean Algebra)

부울 대수는 참(True/1)과 거짓(False/0) 두 값만 다루는 수학 체계로, 디지털 회로와 논리 설계의 기초입니다.

---

기본 연산

연산기호의미

AND	A · B 또는 AB	둘 다 참이어야 참
OR	A + B	하나라도 참이면 참
NOT	Ā 또는 ¬A	반전

---

핵심 법칙

기본 항등식

A + 0 = A        A · 1 = A      (항등 법칙)
A + 1 = 1        A · 0 = 0      (소거 법칙)
A + A = A        A · A = A      (멱등 법칙)
A + Ā = 1        A · Ā = 0      (보수 법칙)

교환·결합·분배

A + B = B + A               (교환 법칙)
A + (B + C) = (A + B) + C  (결합 법칙)
A(B + C) = AB + AC          (분배 법칙)
A + BC = (A + B)(A + C)     (분배 법칙 OR형)

드 모르간의 법칙 (매우 중요)

̄̄̄̄̄̄̄̄̄̄
A · B  =  Ā + B̄      NOT(A AND B) = (NOT A) OR (NOT B)
̄̄̄̄̄̄̄̄̄̄
A + B  =  Ā · B̄      NOT(A OR B)  = (NOT A) AND (NOT B)

흡수 법칙

A + AB = A
A(A + B) = A

---

진리표 예시

F = A·B + Ā·C

ABCABĀCF

0	0	0	0	0	0
0	0	1	0	1	1
0	1	0	0	0	0
0	1	1	0	1	1
1	0	0	0	0	0
1	0	1	0	0	0
1	1	0	1	0	1
1	1	1	1	0	1

---

회로 설계와의 연결

부울 식은 직접 논리 게이트로 구현됩니다.

F = AB + C

    A ──┐
        AND ──┐
    B ──┘     OR ── F
    C ────────┘

식을 간소화할수록 → 게이트 수 감소 → 비용·전력 절감

---

간소화 기법

1. 대수적 방법 — 법칙을 적용해 직접 변환
2. 카르노 맵(K-map) — 4~6변수까지 시각적으로 묶어서 간소화
3. Quine-McCluskey — 변수가 많을 때 알고리즘으로 처리

 

관련 알고리즘 문제들

 

1. 비트마스크 (Bitmask)

가장 흔하게 만나는 유형입니다.

 

 

정수 하나가 곧 부울 배열
  0b1010  =  [false, true, false, true]

AND → 교집합
OR  → 합집합
XOR → 대칭차집합
NOT → 여집합

예시 문제: 부분집합 열거, 방문 상태 표현, 집합 DP

 

 

python

# n개 원소의 모든 부분집합
for mask in range(1 << n):
    subset = [i for i in range(n) if mask & (1 << i)]

---

2. 비트 연산 트릭

 

 

python

x & (x-1)   # 최하위 비트 제거  (x가 2의 거듭제곱인지 판별)
x & (-x)    # 최하위 비트만 추출
x ^ x = 0  # 같은 수 XOR → 0  (중복 찾기)

예시 문제: 배열에서 딱 한 번만 나오는 수 찾기 → 전부 XOR하면 끝

---

3. 카르노 맵 / 논리식 최소화

회로 설계보다는 SAT 문제 계열로 등장합니다.

• 2-SAT 문제 — 코딩테스트 고난이도 단골
• 변수들의 AND/OR/NOT 조합이 참이 되는 조건 찾기

---

4. 집합 DP (SOS DP)

 

 

Sum over Subsets Dynamic Programming
부분집합의 합을 부울 연산으로 빠르게 계산
O(n · 2^n) 으로 처리

---

난이도별 정리

난이도유형

입문	비트마스크로 상태 표현
중급	비트 DP, XOR 트릭
고급	2-SAT, SOS DP