불 대수 간소화 도구
불 대수 식 — A·B + A·¬B + ¬A·B 또는 최소항이 있는 진리표 — 을 입력하면 이 간소화 도구가 Quine-McCluskey 알고리즘으로 최소 곱의 합(sum-of-products) 형태를 반환하고, 최대 6개 변수까지 Karnaugh map 시각화도 제공합니다. 주항(prime implicant), 필수 주항(essential prime implicant), 피복표 등 모든 단계를 보여주므로 숙제뿐 아니라 합성 도구 내부의 간소화기가 선택한 결과를 검토할 때도 유용합니다.
불 대수 간소화가 실행되는 과정
-
1
식 또는 최소항 입력
연산자 · (AND), + (OR), ' 또는 ¬ (NOT), ⊕ (XOR)를 사용합니다. 또는 m(0,1,3,7)처럼 최소항 인덱스를 붙여넣으세요.
-
2
진리표 생성
모든 변수 할당을 평가하고 함수 출력을 표로 정리합니다.
-
3
Quine-McCluskey가 주항 탐색
최소항을 그룹화한 뒤 반복적으로 결합합니다. 한 변수만 다른 인접 그룹이 더 이상 줄일 수 없을 때까지 병합됩니다.
-
4
필수 주항이 함수를 피복
Petrick 방법의 피복표가 최소 주항 집합을 선택합니다. 결과는 간소화된 SOP입니다. POS 형태는 보수(complement)에서 유도됩니다.
지원하는 연산자 표기
| 연산 | 허용되는 기호 |
|---|---|
| AND | ·, *, &, ∧, 공백 |
| OR | +, |, ∨ |
| NOT | \', ¬, !, ~, 윗줄(윗줄 친 A는 A\'로 표시됨) |
| XOR | ⊕, ^ |
| 상수 | 0, 1 |
예시
입력: A·B + A·¬B + ¬A·B
진리표:
| A | B | F |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
최소항: m(1, 2, 3). 최소 SOP는 A + B(두 변수의 OR)로 줄어듭니다. 간소화 도구는 다음 과정을 보여줍니다.
- 1의 개수로 최소항 그룹화
- 인접한 쌍 결합: (1,3) →
-B, (2,3) →A- - 피복표에서 둘 다 필수(essential)임을 표시 — 최종 형태:
A + B
왜 최소화하나요?
- 게이트 수 감소: 각 AND/OR 항은 실리콘 면적이나 FPGA LUT 비용으로 이어집니다.
- 짧아진 임계 경로: 논리가 작을수록 보통 전파 지연도 낮아집니다.
- 전력 감소: 스위칭하는 노드가 줄어듭니다.
알고리즘의 한계
- 변수 개수: Quine-McCluskey는 최악의 경우 O(3^n / n)로 증가합니다. 이 도구는 최대 8개 변수까지 무리 없이 처리합니다. 그 이상은 Espresso 계열의 휴리스틱 간소화기를 쓰세요(최소성이 보장되지는 않지만 계산은 가능합니다).
- 돈트케어 항(don't-care): 발생할 수 없는 입력 조합이 있을 때 더 작은 결과를 얻으려면
d(indices)구문으로 포함하세요.
자주 묻는 질문
Sum-of-products는 AND의 OR(AB + CD처럼)이고, product-of-sums는 OR의 AND((A+B)(C+D)처럼)입니다. 같은 함수를 다른 구조로 표현한 것입니다. 간소화 도구는 둘 다 반환하므로 후속 도구에 맞는 쪽을 고르세요.
네. 최소항과 함께 d(index1, index2, ...) 형태로 입력하세요. 간소화기는 이를 더 작은 결과를 만드는 데 유리한 값으로 자유롭게 배정합니다.
올바르게 묶으면 둘 다 최소 비용을 만들지만, K-map은 사람이 가능한 가장 큰 그룹을 찾아내는 데 의존합니다. Quine-McCluskey는 결정론적이며 항상 최적해를 찾습니다.
XOR는 최소화 전에 AND/OR/NOT으로 전개됩니다. 동등한 SOP는 얻을 수 있지만 XOR 구조는 사라집니다. XOR를 보존하는 최적화에는 다른 알고리즘(Reed-Muller)이 필요합니다.
관련 도구
JSON 포매터
JSON을 붙여넣어 2칸 또는 4칸 들여쓰기로 읽기 좋게 만들고, compact 출력으로 압축하거나 결과를 복사하기 전에 구문을 빠르게 확인하세요.
HEX 색상 선택기
색상을 눈으로 선택하고 HEX, RGB, HSL, HSV, CMYK 값과 흰색·검정 대비를 바로 확인하세요.
색상 팔레트 생성기
기준 HEX 색상에서 단색, 유사색, 보색, 삼색 또는 사색 팔레트를 만들고 바로 복사할 수 있는 CSS 변수를 내보냅니다.
랜덤 색상 생성기
1개부터 50개까지 랜덤 HEX 색상을 만들고, 색상 견본을 확인한 뒤 CSS, 테스트 또는 팔레트 탐색에 쓸 코드를 복사하세요.
랜덤 색상 팔레트 생성기
2~15개의 색상으로 랜덤 팔레트를 만들고, 비비드, 파스텔, muted, dark 스타일을 선택한 뒤 HEX 코드나 CSS 변수를 복사하세요.
랜덤 영어 글자 생성기
A-Z 영어 글자를 무작위로 생성합니다. 개수와 대문자, 소문자, 혼합 대소문자를 선택해 게임, 과제, 수업 활동에 활용하세요.