콰인-매클러스키 논리식 간소화 계산기

카르노맵은 눈으로 인접한 칸을 묶어보는 방법이라 변수 4개까지는 편하지만 5개, 6개로 늘면 3차원·4차원 큐브를 머릿속에 그려야 해 사실상 쓰기 어렵습니다. 콰인-매클러스키는 "비트가 정확히 하나만 다른 두 항을 묶어 그 자리를 돈케어(-)로 바꾼다"는 규칙을 기계적으로 반복하는 알고리즘이라 변수 개수와 무관하게 똑같은 절차로 계산할 수 있습니다.

어떤 최소항을 담당할 수 있는 소항이 단 하나뿐일 때, 그 소항은 반드시 최종 답에 들어가야 합니다. 이런 소항을 필수 소항이라 부르며, 먼저 이것들을 뽑아 놓고 남은 최소항만 추가로 덮으면 계산이 훨씬 간단해집니다.

필수 소항까지는 항상 정확합니다. 다만 필수 소항으로 다 덮이지 않는 최소항이 남으면, 이 계산기는 그 시점에서 가장 많은 최소항을 덮는 소항을 고르는 욕심(greedy) 알고리즘을 씁니다. 이 방식은 대부분 최소이거나 최소에 가깝지만, 이론적으로 절대 최소를 보장하지는 않습니다 — 정확한 최소를 구하려면 집합 덮개 문제를 완전 탐색해야 하는데 이는 NP-난해 문제입니다.

실제 회로에서는 "이 입력 조합은 절대 들어올 리 없다"는 경우가 있습니다(예: 7세그먼트 디코더에서 10~15는 쓰이지 않음). 이런 입력은 결과가 0이든 1이든 상관없으므로, 식을 더 간단하게 만드는 데 자유롭게 이용할 수 있습니다. 다만 돈케어 자체를 "반드시 참으로 만들어야 할 값"으로 취급하지는 않습니다.