본문으로 건너뛰기

Boolean Algebra

Discrete Mathematics and Its Applications · Kenneth H. Rosen · Ch. 11

Intuition

디지털 세계의 모든 복잡한 연산은 0과 1, 그리고 이를 다루는 세 가지 기본 연산(AND, OR, NOT)의 조합인 부울 함수로 환원된다.

One-liner​

부울 대수는 {0,1}\{0, 1\} 집합 위에서 정의된 연산 규칙을 통해 논리 회로를 모델링하고, 이를 수학적으로 최적화하는 도구이다.

Prerequisites​

이 챕터를 학습하기 위해 다음 배경 지식이 필요하다.

Goals​

  • 부울 연산(보원, 합, 곱)을 수행하고 부울 함수의 값을 계산할 수 있다.
  • 부울 함수를 Sum-of-Products (SOP) 형태나 Product-of-Sums (POS) 형태로 표현할 수 있다.
  • 기본 논리 게이트를 조합하여 특정 부울 함수를 구현하는 회로를 설계할 수 있다.
  • Karnaugh Map 및 Quine-McCluskey 방법을 사용하여 회로를 최소화할 수 있다.

Core Concepts​

11.1 Boolean Functions (부울 함수)​

부울 대수는 집합 B={0,1}B = \{0, 1\} 위에서 정의된 대수 구조이다.

Definition

Boolean Operations (부울 연산):

  1. Complementation (보원): 0ˉ=1,1ˉ=0\bar{0} = 1, \bar{1} = 0
  2. Boolean Sum (부울 합): 1+1=1,1+0=1,0+1=1,0+0=01+1=1, 1+0=1, 0+1=1, 0+0=0 (OR 연산)
  3. Boolean Product (부울 곱): 1⋅1=1,1⋅0=0,0⋅1=0,0⋅0=01 \cdot 1 = 1, 1 \cdot 0 = 0, 0 \cdot 1 = 0, 0 \cdot 0 = 0 (AND 연산)
  • Boolean Variable (부울 변수): BB에서만 값을 가지는 변수.
  • Boolean Function (부울 함수): Bn→BB^n \to B인 함수로, 차수(degree) nn은 입력 변수의 개수를 의미한다.
  • Number of Functions: 차수가 nn인 서로 다른 부울 함수의 개수는 22n2^{2^n}개이다. (p. 752)

11.2 Representing Boolean Functions (부울 함수의 표현)​

모든 부울 함수는 부울 변수와 연산자의 조합인 부울 식(Boolean expression)으로 표현 가능하다.

Definition

Minterm (최소항): 변수 x1,x2,…,xnx_1, x_2, \dots, x_n에 대하여, 각 변수 또는 그 보원이 한 번씩 곱해진 형태의 부울 곱. nn개의 변수가 있을 때 특정 입력 조합에서만 1이 되는 항이다.

  • Sum-of-Products Expansion (곱의 합 전개): 부울 함수가 1의 값을 가지는 모든 입력 조합에 대해 각각의 minterm을 구한 뒤, 이들을 모두 부울 합(+)으로 연결한 형태이다. Disjunctive Normal Form (논리합 표준형)이라고도 한다. (p. 758)
  • Functional Completeness (기능적 완비성): 어떤 연산자 집합이 모든 부울 함수를 표현할 수 있을 때 이를 기능적으로 완비되었다고 한다. {+,⋅, ˉ}\{+, \cdot, \bar{\,}\}는 완비적이며, NAND(∣|)나 NOR(↓\downarrow)는 단일 연산자만으로도 완비성을 가진다. (p. 759)

11.3 Logic Gates (논리 게이트)​

부울 연산을 하드웨어로 구현한 기본 소자가 게이트이다.

  • Inverter (인버터): NOT 연산 수행.
  • OR Gate: 부울 합 연산 수행. 입력 중 하나라도 1이면 출력은 1.
  • AND Gate: 부울 곱 연산 수행. 모든 입력이 1이어야 출력은 1.
  • Combinational Circuits (조합 회로): 출력이 현재의 입력에만 의존하며 메모리(상태)가 없는 회로. (p. 761)
  • Adders (가산기):
    • Half Adder (반가산기): 두 비트 x,yx, y를 더해 합(ss)과 올림수(cc)를 생성.
    • Full Adder (전가산기): 두 비트와 이전 단계의 올림수까지 총 세 비트를 더함. (p. 764)

11.4 Minimization of Circuits (회로 최소화)​

회로의 효율성을 높이기 위해 게이트의 수와 입력 수를 줄이는 과정이다.

  • Karnaugh Map (카르노 맵): 인접한 셀(한 비트만 다른 minterm)을 시각적으로 묶어 변수를 제거하는 방법. 2~6개 변수까지 유용하다. (p. 768)
  • Implicant (항): 함수 값이 1인 셀들의 묶음.
  • Prime Implicant (주항): 더 큰 묶음에 포함될 수 없는 최대 크기의 묶음.
  • Essential Prime Implicant (필수 주항): 특정 1을 덮을 수 있는 유일한 주항. 최소화 과정에서 반드시 포함되어야 한다. (p. 770)
  • Quine-McCluskey Method: 카르노 맵의 시각적 한계를 극복하기 위해 표를 사용하여 체계적으로 최소항을 결합하는 알고리즘. 컴퓨터 프로그래밍에 적합하다. (p. 775)

Notation​

기호의미비고
xˉ\bar{x}보원 (NOT)교재에 따라 x′x'로 표기하기도 함
x+yx + y부울 합 (OR)x∨yx \lor y와 대응
x⋅yx \cdot y부울 곱 (AND)x∧yx \land y와 대응, 생략하여 xyxy로 표기
x⊕yx \oplus y배타적 합 (XOR)(x+y)xy‾(x+y)\overline{xy}
FdF^d듀얼 함수 (Dual)연산자와 상수를 상호 교환한 함수

Key Theorems & Formulas​

Theorem (Duality Principle)

조건: 부울 대수의 임의의 항등식 E1=E2E_1 = E_2.

결론: 양변의 부울 식을 듀얼(dual)로 바꾸어도 항등식 성질이 유지된다.

  • ++와 ⋅\cdot를 바꾼다.
  • 00과 11을 바꾼다.

증명 스케치: 부울 대수의 정의 자체가 연산자 쌍에 대해 대칭적으로 구성되어 있으므로, 연산자를 치환해도 구조적 유효성이 보존된다. (p. 754)

Boolean Identities (주요 항등식)
  • Distributive Laws (분배 법칙): x+yz=(x+y)(x+z)x + yz = (x+y)(x+z) (일반 대수와 다른 점에 주의)
  • De Morgan's Laws (드 모르간 법칙): xy‾=xˉ+yˉ\overline{xy} = \bar{x} + \bar{y}, x+y‾=xˉyˉ\overline{x+y} = \bar{x}\bar{y}
  • Absorption Laws (흡수 법칙): x+xy=x,x(x+y)=xx + xy = x, x(x+y) = x

Intuitions​

  • 카르노 맵의 인접성: 맵의 끝과 끝(왼쪽 끝과 오른쪽 끝, 위쪽 끝과 아래쪽 끝)은 서로 연결된 것으로 간주한다. 이는 맵이 평면이 아니라 토러스(Torus, 도넛 모양) 구조 위에 그려진 것으로 이해하면 직관적이다. (p. 771)
  • 최소화의 기하학적 해석: nn개의 변수를 가진 부울 함수는 nn-차원 큐브(nn-cube)의 정점들로 표현할 수 있다. 인접한 정점들을 묶는 것은 큐브의 변(edge), 면(face) 등을 찾는 과정과 같다. (p. 751)

Worked Examples​

Example 1: Sum-of-Products Expansion 구하기​

문제: F(x,y,z)=(x+y)zˉF(x, y, z) = (x + y)\bar{z}의 SOP 전개를 구하라.

핵심 단계:

  1. 분배 법칙 적용: F=xzˉ+yzˉF = x\bar{z} + y\bar{z}
  2. 누락된 변수 보충 (x+1=1x+1=1 이용):
    • xzˉ(y+yˉ)=xyzˉ+xyˉzˉx\bar{z}(y + \bar{y}) = xy\bar{z} + x\bar{y}\bar{z}
    • yzˉ(x+xˉ)=xyzˉ+xˉyzˉy\bar{z}(x + \bar{x}) = xy\bar{z} + \bar{x}y\bar{z}
  3. 중복 항 제거 (Idempotent law): xyzˉ+xyˉzˉ+xˉyzˉxy\bar{z} + x\bar{y}\bar{z} + \bar{x}y\bar{z}

요점: 모든 항이 모든 변수(x,y,zx, y, z)를 포함하는 minterm의 합 형태로 나타나야 한다. (p. 760)

Example 2: Karnaugh Map 최소화​

문제: 3변수 함수 xyzˉ+xyˉzˉ+xˉyˉz+xˉyˉzˉxy\bar{z} + x\bar{y}\bar{z} + \bar{x}\bar{y}z + \bar{x}\bar{y}\bar{z}를 최소화하라.

핵심 단계:

  1. 맵에 1 표시: (1,1,0),(1,0,0),(0,0,1),(0,0,0)(1,1,0), (1,0,0), (0,0,1), (0,0,0) 위치.
  2. 묶기:
    • (1,1,0)(1,1,0)과 (1,0,0)(1,0,0)을 묶으면 xzˉx\bar{z} (y 소거).
    • (1,0,0),(0,0,0)(1,0,0), (0,0,0)을 묶으면 yˉzˉ\bar{y}\bar{z} (x 소거).
    • (0,0,0),(0,0,1)(0,0,0), (0,0,1)을 묶으면 xˉyˉ\bar{x}\bar{y} (z 소거).
  3. 필수 주항 선택: 모든 1을 덮는 최소 조합을 찾는다.

요점: 시각적으로 가장 큰 블록(2k2^k 크기)을 먼저 찾아야 가장 간단한 식이 나온다. (p. 769)

Common Pitfalls​

Pitfall

일반 대수와의 혼동: 일반 수학에서는 x+yz=(x+y)(x+z)x + yz = (x+y)(x+z)가 성립하지 않지만, 부울 대수에서는 분배 법칙이 합과 곱 양방향으로 모두 성립한다.

Pitfall

최소화의 유일성: 부울 함수의 최소화 결과(최소 SOP)는 반드시 하나로 정해지지 않을 수 있다. 주항을 선택하는 조합에 따라 서로 다른 형태의 최소식이 존재할 수 있다. (p. 770)

Connections​

  • 선행 개념: Ch. 1의 논리 연산자와 Ch. 2의 집합 연산은 부울 대수와 동형(isomorphic)인 구조이다. Ch. 8 Lattice (부분 순서 집합의 심화가 부울 대수이다).
  • 후속 개념: Ch. 12 Modeling Computation (논리 회로는 유한 상태 기계로 확장됨). 이후 과정에서는 하드웨어 설계 언어(VHDL, Verilog) 및 알고리즘의 시간 복잡도 분석으로 연결된다.
  • 응용 분야: 디지털 논리 회로 설계, 컴파일러의 조건문 최적화, 스위칭 이론.

Critical Notes​

교재가 강조하는 것

  • 부울 대수의 추상적 정의와 논리/집합과의 연관성.
  • 카르노 맵을 통한 시각적 최적화의 절차적 정당성.

실제로 중요한 것

  • 현대 반도체 설계에서는 수만 개의 변수를 다루므로 카르노 맵보다는 Quine-McCluskey를 확장한 알고리즘(예: Espresso)이나 CAD 도구가 실무적으로 더 중요하다.
  • 최소화가 왜 중요한가: 게이트 수가 줄어들면 칩의 면적(Cost)이 줄고, 전력 소비가 낮아지며, 신호 전달 속도(Performance)가 빨라진다. (p. 767)

교재가 생략하거나 얼버무리는 것

  • 하드웨어의 물리적 특성(지연 시간, 전압 레벨 등)은 다루지 않는 순수 수학적 모델링이다.
  • 다중 출력 회로(Multiple-output circuit)의 동시 최소화 문제는 개별 함수 최소화보다 복잡하지만 깊게 다루지 않는다.

Open Questions​

이해하지 못한 것

  • 5변수 이상의 카르노 맵에서 인접성을 판단하는 시각적 규칙이 여전히 직관적이지 않음. Gray Code와의 연관성을 재검토할 필요가 있음.

더 알고 싶은 것

  • 회로 최소화가 NP-완전 문제라면, 실제 상용 EDA(Electronic Design Automation) 툴은 어떤 휴리스틱 기법을 사용하는가?
  • 래치(Latch)나 플립플롭(Flip-flop) 같은 순차 회로(Sequential Circuit)는 부울 대수로 어떻게 확장 모델링되는가?