변수: p, q

p	q	출력
⊥	⊥
⊤	⊥
⊥	⊤
⊤	⊤

출력 값을 눌러 참(⊤)과 거짓(⊥)을 번갈아 바꿉니다

만들어진 식

선언 표준형 (곱의 합)

(p ∧ ¬q) ∨ (¬p ∧ q)

계산기에서 분석하기

진리표를 불 대수식으로 바꾸는 방법

모든 진리표는 어떤 식의 진리표이며, 그중 두 가지 식은 표에서 곧바로 읽어 낼 수 있습니다. 대수 변형도, 어림짐작도 필요 없습니다.

변수가 n개면 2ⁿ개의 행을 모두 적고, 출력이 ⊤인 행에 표시합니다.
⊤인 행마다 최소항을 씁니다. 모든 변수를 AND로 잇되, 그 행에서 거짓이 되는 변수에는 부정을 붙입니다. 최소항들을 OR로 이으면 DNF입니다.
⊥인 행마다 최대항을 씁니다. 모든 변수를 OR로 잇되, 그 행에서 참이 되는 변수에는 부정을 붙입니다. 최대항들을 AND로 이으면 CNF입니다.
두 식 모두 처음의 진리표를 그대로 가지므로 어느 쪽도 정답입니다. 가장 짧은 형태가 필요하면 그다음에 간소화하면 됩니다.

최소항

모든 변수를 부정하거나 부정하지 않고 AND로 이은 항으로, 표에서 정확히 한 행에서만 참이 됩니다. DNF는 출력이 ⊤인 행들의 최소항을 OR로 이은 것이므로, ⊤인 행 하나당 항이 하나씩 생깁니다.

최대항

모든 변수를 부정하거나 부정하지 않고 OR로 이은 항으로, 표에서 정확히 한 행에서만 거짓이 됩니다. CNF는 출력이 ⊥인 행들의 최대항을 AND로 이은 것이므로, ⊥인 행 하나당 항이 하나씩 생깁니다.

풀이 예시: 배타적 논리합

위의 표가 도구를 열었을 때 나오는 표입니다. p와 q의 값이 서로 다른 두 행에서만 참이 됩니다.

두 행이 ⊤이므로 DNF에는 최소항이 둘 있습니다: (p ∧ ¬q) ∨ (¬p ∧ q)
나머지 두 행이 ⊥이므로 CNF에는 최대항이 둘 있습니다: (p ∨ q) ∧ (¬p ∨ ¬q)

둘 다 더 줄일 수 없습니다. 배타적 논리합에는 두 항이 정말로 다 필요하기 때문인데, 이는 한 번쯤 볼 만합니다. 표준형이 언제나 먼 길인 것은 아닙니다. 「p, q, r 가운데 많아야 하나」 같은 표에 이르러야 최소 형태가 확실히 앞섭니다.

불 대수 합성 이해하기

선언 표준형 (DNF)

DNF는 식을 논리곱들의 논리합(곱의 합)으로 나타냅니다. 출력이 참인 행마다 최소항을 하나씩 만드는데, 모든 변수를 AND로 잇고 그 행에서 거짓인 변수에는 부정을 붙입니다. 이렇게 만든 최소항들을 OR로 이어 붙이면 전체 식이 됩니다.

논리곱 표준형 (CNF)

CNF는 식을 논리합들의 논리곱(합의 곱)으로 나타냅니다. 출력이 거짓인 행마다 최대항을 하나씩 만드는데, 모든 변수를 OR로 잇고 그 행에서 참인 변수에는 부정을 붙입니다. 이렇게 만든 최대항들을 AND로 이어 붙이면 전체 식이 됩니다.

DNF와 CNF 비교

관점	선언 표준형 (곱의 합)	논리곱 표준형 (합의 곱)
만드는 재료	출력이 ⊤인 행들, 행마다 최소항 하나	출력이 ⊥인 행들, 행마다 최대항 하나
형태	논리곱들의 논리합: AND의 OR	논리합들의 논리곱: OR의 AND
이럴 때 고릅니다	식을 참으로 만드는 경우를 모두 늘어놓고 싶거나, AND-OR 회로를 구성할 때	동시에 모두 성립해야 하는 제약이 필요하거나, SAT 솔버가 요구하는 절 형태가 필요할 때

표는 얼마나 커지나요?

변수가 n개인 함수의 진리표는 2ⁿ행이므로 변수를 하나 더할 때마다 표는 두 배가 됩니다. 두 변수면 4행, 세 변수면 8행, 네 변수면 16행, 다섯 변수면 32행이고 이 도구는 거기까지입니다. DNF는 ⊤인 행마다, CNF는 ⊥인 행마다 항을 하나씩 가져가므로 둘이 합쳐 모든 행을 정확히 한 번씩 감당하며, 둘 중 하나는 언제나 더 짧은 출발점이 됩니다.

진리표 합성의 활용

진리표를 논리식으로 바꾸는 것은 컴퓨터 과학과 디지털 전자공학의 기본 기법입니다. 이 도구는 다음에 도움이 됩니다:

디지털 회로 설계 - 원하는 입출력 동작에서 논리 게이트의 불 대수식을 이끌어 내기
소프트웨어 개발 - 명세 표에서 조건 논리 만들어 내기
학습 - 불 대수와 명제 논리를 배우고 연습하기
논리 최적화 - DNF와 CNF를 견주어 더 간단한 동치식 찾기

자주 묻는 질문

논리 계산기 사용에 대해 자주 묻는 질문과 답변

진리표에서 논리식으로 만드는 도구는 무엇을 하나요?

계산기를 거꾸로 돌립니다. 각 행을 눌러 진리표의 출력 열을 정하면, 바로 그 진리표를 갖는 식을 만들어 냅니다. 선언 표준형(논리곱들의 논리합)이나 논리곱 표준형(논리합들의 논리곱)으로 나옵니다.

선언 표준형과 논리곱 표준형은 어떻게 다른가요?

선언 표준형은 곱의 합입니다. 출력이 참인 행마다 논리곱 항을 하나씩 만들어 전부 논리합으로 잇습니다. 논리곱 표준형은 합의 곱으로, 출력이 거짓인 행마다 논리합 항을 하나씩 만들어 전부 논리곱으로 잇습니다. 둘 다 같은 함수를 나타내므로 표에 따라 짧아지는 쪽을 고르면 됩니다. 거짓이 많은 열이면 선언 표준형이, 참이 많은 열이면 논리곱 표준형이 짧아집니다.

합성 도구는 변수를 몇 개까지 받나요?

최대 다섯 개, 즉 32행짜리 표까지입니다. 변수를 하나 더할 때마다 행이 두 배가 되고, 다섯 개를 넘으면 손으로 채울 수 있는 표가 아니게 됩니다.

생성된 식은 왜 이렇게 긴가요?

표준형은 행 단위로 세워집니다. 덮어야 할 행마다 모든 변수를 담은 항이 하나씩 붙으므로, 길이는 식 뒤에 있는 착상이 아니라 진리표를 따라갑니다. 구성 방식상 옳음은 보장되지만 간결함은 보장되지 않습니다. 줄이고 싶다면 계산기에서 열어 보세요. 최소화된 선언 표준형을 포함한 동치 형식이 나열됩니다.

식을 간단히 정리한 형태를 얻을 수 있나요?

네. 계산기에 입력한 뒤 진리표 아래의 동치 형식을 보세요. 대수 법칙으로 다시 쓴 형태와, 진리표에서 읽어 낸 선언 표준형·논리곱 표준형, 그리고 최소화된 선언 표준형이 함께 나옵니다.

모든 질문 보기

진리표에서 식을 만드는 도구