부울연산
- 부울대수(Boolean Algebra) / 논리대수(Logic Algebra): 0 또는 1을 입력 받아 0 또는 1을 출력하는 회로의 논리 계산을 형식화한 것
- 부울값(Boolean Value): 디지털 신호, 0 또는 1
- 부울변수(Boolean Variable): 부울값 0 또는 1을 받는 변수
- 부울함수(Boolean Function): n개의 부울변수와 부울 연산자로 구성되는 식
- 부울보수(Boolean Complement): 부울변수의 값을 반전시키는 단항연산자
- 부울합(Boolean Addition): 부울변수의 값을 더하는 이항 연산자로 부울변수의 값 중 하나만이라도 1이면 그 결과가 1
- 부울곱(Boolean Multiplication): 부울변수의 값을 곱하는 이항 연산자로 부울변수의 값 중 하나만이라도 0이면 그 결과가 0
- 부울 연산자의 우선순위: 괄호 → 부울보수 → 부울곱 → 부울합
부울대수법칙
| 부울대수법칙 | 법칙의 이름 | |
| x + x = x | x · x = x | 멱등법칙 |
| x + 0 = x | x · 1 = x | 항등법칫 |
| x + 1 = 1 | x · 0 = 0 | 유계법칙 |
| x + y = y + x | xy = yx | 교환법칙 |
| (x')' = x | 이중보수법칙 | |
| x + x' = 1 | x · x' = 0 | 보수법칙 |
| (x + y) + z = x + (y + z) | (xy)z = x(yz) | 결합법칙 |
| x · (y + z) = xy + xz | x + yz = (x + y) · (x + z) | 분배법칙 |
| (x + y)' = x'y' | (xy)' = x' + y' | 드모르간의 법칙 |
| x + xy = x | x(x + y) = x | 흡수법칙 |
드모르간의 법칙 증명
- x · x' = 0 이므로 (x + y) · (x + y)' 이 성립함
- 그러므로 (x + y) · (x + y)' = (x + y) · x'y' = 0 임을 증명
- (x + y) · (x + y)' = (x + y) · x'y'
- = xx'y' + yx'y' (분배법칙)
- = xx'y + x'yy' (교환법칙)
- = 0 · y' + x' · 0 (보수법칙)
- = 0 + 0 (유계법칙)
- = 0 (멱등법칙)
- ∴ (x + y) · (x + y)' = (x + y) · x'y' = 0 이 성립하므로 (x + y)' = x'y'
부울대수의 표현
리터럴
- Literal
- 부울변수와 부울보수 연산을 한 부울변수 모두를 일컫는 말
- n차 부울함수에서 가능한 리터럴은 2n개가 됨
최소항
- Minterm
- n차 부울함수 f(x₁, x₂, ... , xₙ)를 구성하는 항들 중 n개 리터럴의 부울곱으로 구성된 항
- n차 부울함수의 최소항은 n개의 리터럴의 부울곱으로 만들어짐
최대항
- Maxterm
- n차 부울함수 f(x₁, x₂, ... , xₙ)를 구성하는 항들 중 n개 리터럴의 부울합으로 구성된 항
- n차 부울함수의 최대항은 n개의 리터럴의 부울합으로 만들어짐
정규형
- Normal Form
- 부울함수를 구성하는 부울변수들을 부울합이나 부울곱으로 나타낸 형태
- 최소항 전개: 정규형의 부울함수를 구성하는 모든 항이 최소항의 합인 형태
- 최대항 전개: 정규형의 부울함수를 구성하는 모든 항이 최대항의 곱인 형태
최소항 전개
- 부울함수 f(x₁, x₂, ... , xₙ)의 최소항: n개의 서로 다른 x 또는 x'의 곱으로 이루어진 항
- 부울함수의 최소항 전개: 부울함수를 최소항의 합으로 표현
- f(x, y) = x + x'y
부울대수법칙을 이용한 최소항 전개
- 각 항에 포함되지 않은 부울변수를 파악
- 각 항에 포함되지 않은 부울변수에 대해 부울곱에 대한 항등법칙(x · 1 = x)과 부울합에 대한 보수법칙(x + x' = 1)을 이용해 각 항에 없는 부울변수를 추가
- 예시: 정규형의 부울함수 f(x, y, z) = x + y'z + x'z'
- 최소항 전개 정규식으로 만들기 위해 모든 항을 최소항으로 만들어야 함
- xyz + xyz' + xy'z + xy'z' + x'y'z + x'yz' + x'y'z'
진리표를 이용한 최소항 전개
- n변수 진리표에서 부울함수에 포함된 변수를 포함하는 항을 모두 1로 표기
- 1로 표기된 최소항을 모두 부울합으로 전개
- 예시: 정규형의 부울함수 f(x, y, z) = x + y'z + x'z'
- 3차 부울함수이므로 3변수 진리표를 이용
- xyz + xyz' + xy'z + xy'z' + x'y'z + x'yz' + x'y'z'
| x | y | z | 최소항 | f(x, y, z) |
| 0 | 0 | 0 | x'y'z' | 1 |
| 0 | 0 | 1 | x'y'z | 1 |
| 0 | 1 | 0 | x'yz' | 1 |
| 0 | 1 | 1 | x'yz | 0 |
| 1 | 0 | 0 | xy'z' | 1 |
| 1 | 0 | 1 | xy'z | 1 |
| 1 | 1 | 0 | xyz' | 1 |
| 1 | 1 | 1 | xyz | 1 |
카르노 맵
- Karnaugh Map
- 부울함수를 단순화하기 위해 부울변수의 상호관계를 이용하는 방법
- 부울함수를 간략화하는 방법
- 일반적으로 2차 이상 5차 이하의 부울함수에 사용
- 카르노 맵은 부울함수에 있는 부울변수들의 조합을 2차원 평면에 표시하고 연관된 부울변수들이 가지는 공통 변수를 찾아내는 방식
- n차 부울함수에 대해 2n개의 부울변수의 조합이 가능하므로 2n개의 셀을 갖는 카르노 맵이 작성
4변수 카르노 맵
| wx \ yz | yz | y'z | y'z' | yz' |
| wx | wxyz | wxy'z | wxy'z' | wxyz' |
| w'x | w'xyz | w'xy'z | w'xy'z' | w'xyz' |
| w'x' | w'x'yz | w'x'y'z | w'x'y'z' | w'x'yz' |
| wx' | wx'yz | wx'y'z | wx'y'z' | wx'yz' |
- 상하좌우로 위치한 부울변수의 조합 사이에 공통변수 하나가 반드시 있어야 함
- 4변수 카르노 맵에서 첫 번째 행 제목 wx와 네 번째 행 제목 wx' 사이에는 공통변수 w가 있음
- 열 제목도 마찬가지로 yz와 y'z 사이에 z, y'z와 y'z' 사이에 y', y'z와 yz' 사이에 z', 첫 번째 열 제목 yz와 네 번째 열 제목 yz' 사이에 y와 같은 공통 변수가 있음
카르노 맵을 이용한 부울함수의 간략화
- n차 부울함수에 대응하는 n변수 카르노 맵을 작성
- 부울함수에 있는 항들 각각에 대응하는 카르노 맵 셀에 1을 표시
- 인접하는 1들을 2ⁿ, 2ⁿ⁻¹, 2ⁿ⁻², ... 의 순서로 묶음
- 묶음에 있는 공통변수들을 찾아 논리합으로 전개
예시 1: f(x, y) = x'y + xy + x'y' → f(x, y) = y + x'
| x \ y | y | y' |
| x | 1 | |
| x' | 1 | 1 |
예시 2: f(x, y, z) = xyz + x'yz + xy'z + xyz' + x'yz' → f(x, y, z) = y + xz
| x \ yz | yz' | yz | y'z | y'z' |
| x | 1 | 1 | 1 | |
| x' | 1 | 1 |
논리 게이트
- 부울대수를 물리적 장치로 구현하기 위해 사용하는 기호
- NOT: 하나의 입력을 받아 부울보수 연산 후 하나의 출력
- AND: 두 개의 입력을 받아 부울곱 연산 후 하나의 출력
- OR: 두 개의 입력을 받아 부울합 연산 후 하나의 출력
- NAND: AND 게이트와 NOT 게이트를 결합, 두 개의 입력을 받아 부울곱 연산 후 부울보수한 결과를 출력
- NOR: OR 게이트와 NOT 게이트를 결합, 두 개의 입력을 받아 부울합 연산 후 부울보수한 결과를 출력
- XOR: 두 입력이 같은 값이 입력되면 0, 다른 값이 입력되면 1이 출력
- XNOR: XOR 게이트와 NOT 게이트를 결합, 두 개의 입력을 받아 XOR 연산 후 부울보수한 결과를 출력
