진리표 생성기 — 어떤 논리식이든 단계별로

괄호를 먼저 계산하고, 그다음 부정, 논리곱(AND), 배타적 논리합과 함께 논리합(OR), 함의, 마지막으로 동치 순서입니다. 그래서 ~A ∧ B ∨ C ∧ D는 ((~A) ∧ B) ∨ (C ∧ D)를 뜻합니다. 규칙이 하나로 정해지지 않은 경우가 하나 있는데, 괄호 없이 이어 쓴 함의입니다. 수리 논리에서는 A → B → C를 A → (B → C)로 읽지만, 왼쪽부터 계산하는 교재도 있습니다. 함의는 결합법칙이 성립하지 않아 두 읽기의 진리표가 서로 다릅니다. 그래서 도구는 어느 쪽으로 읽었는지 보여 주고 바꿀 수 있게 합니다.

A → B는 “A이면 B이다”라는 약속입니다. 이 약속이 깨지는 것은 A가 참인데 B가 거짓일 때뿐이고, 그것이 1 → 0 = 0인 단 하나의 행입니다. A가 거짓이면 약속을 시험해 볼 일이 없었으니 지켜진 것으로 보아 함의의 값은 1입니다. A → B의 진리표가 ~A ∨ B와 같은 이유이고, 도구가 간소화할 때 함의를 바로 이 식으로 바꾸는 이유입니다.

완전 DNF는 F = 1인 행마다 모든 변수를 넣은 논리곱(최소항)을 하나씩 만듭니다. 그래서 여섯 행에서 1이 되는 함수는 긴 항을 여섯 개 갖게 됩니다. 간소화는 변수 하나만 다른 항을 병합합니다: A∧B∧C ∨ A∧B∧~C = A∧B. 카르노 맵에서는 이런 항이 이웃한 칸이고, 2칸, 4칸, 8칸 묶음이 짧은 항 하나가 됩니다. 퀸-맥클러스키 방법은 같은 병합을 체계적으로 한 다음, 모든 1을 덮으면서 가장 값싼 항의 조합을 고릅니다.

전체 진리표에서 F가 표 조각에 주어진 값을 갖는 행을 적어 보세요. 대개 몇 개 안 됩니다. 그 행들의 공통점을 찾습니다. F = 0일 때 언제나 y = 1이라면, F = 0인 행에 0이 있는 열은 y일 수 없습니다. 그다음 표 조각에서 정보가 가장 많은 행을 골라 전체 표의 어느 행이 될 수 있는지 봅니다. 표 조각의 행은 모두 서로 다르므로 경우가 더 줄어듭니다. “열 퍼즐” 모드가 바로 이 과정을 따라가며 모든 단계를 적어 줍니다.

제갈킨 다항식(대수적 정규형)은 어떤 불 함수든 AND, XOR, 상수 1만으로 적는 방법이고, 함수마다 하나뿐입니다. 함수끼리 비교하거나 선형인지 확인할 때 편리합니다. 포스트의 다섯 클래스는 다른 질문에 답합니다. 주어진 게이트 집합으로 모든 함수를 만들 수 있을까요? 포스트의 정리에 따르면, 다섯 클래스 각각에 대해 그 클래스 밖의 함수를 하나씩 갖고 있을 때에만 그 집합은 함수적으로 완전합니다. NAND와 NOR는 어느 클래스에도 속하지 않습니다. 그래서 둘 중 하나만으로도 어떤 회로든 만들 수 있습니다.