드모르간 정리: 불 대수 보수와 게이트 등가성 마스터하기

불 대수의 기초 개념인 드모르간 정리는 입력이나 출력이 반전될 때 논리 게이트의 동작을 연결합니다. 수학자 아우구스투스 드모르간의 이름을 딴 이 규칙들은 AND, OR, NAND, NOR 게이트를 서로 변환할 수 있게 하여 논리 식과 물리적 회로 설계를 모두 단순화합니다.

불 대수에서 '그룹 보수'는 여러 변수 위에 긴 바로 표시되어 전체 곱이나 합이 반전됨을 나타냅니다. 이는 단일 변수만 반전시킬 수 있는 프라임 기호(')와 다릅니다. 예를 들어 (AB)^′은 A′B′와 다르며, 괄호는 바가 전체 곱에 적용됨을 알리는 데 필수적입니다.

게이트의 모든 입력이 반전되면 게이트의 핵심 기능이 뒤바뀝니다: 모든 입력이 반전된 OR 게이트는 NAND 게이트와 동일하게 동작하고, 입력이 반전된 AND 게이트는 NOR 게이트와 등가입니다. 드모르간 정리는 게이트 출력을 반전시키는 것이 게이트 타입을 바꾸고 입력을 반전시키는 것과 같은 효과임을 공식화합니다.

핵심 등가성을 시각적으로 보여주는 그림:

불 식에서 긴 바가 '깨지면', 깨진 부분 바로 아래 연산이 반전됩니다(덧셈↔곱셈). 바의 깨진 조각들은 개별 변수 위에 남습니다. 이 미묘한 규칙이 식 단순화를 지배합니다.

여러 겹의 바가 있는 식에서는 가장 길고 최상단의 바를 먼저 깨는 것이 가장 안전합니다. 두 바를 동시에 깨면 잘못된 결과로 이어질 수 있습니다.

예를 들어 (A + (BC)′)′ 단순화 과정:

먼저 바깥쪽 바를 깹니다:

A 입력이 반전된 3입력 AND 게이트가 됩니다.

한 단계에서 두 개 이상의 바를 깨지 마세요:

대신 짧은 안쪽 바를 먼저 깰 수 있지만 추가 단계가 필요합니다:

한 단계에서 한 바를 여러 곳에서 깨는 것은 허용됩니다. 제한은 여러 개의 서로 다른 바를 동시에 깨는 것입니다.

괄호는 바가 그룹화 기호 역할을 하므로 중요합니다. 바를 깬 후에는 그룹화된 항들이 함께 있어야 연산자 우선순위가 보존됩니다.

올바른 그룹화의 중요성을 보여주는 식:

이제 드모르간 정리를 실제 게이트 회로에 적용해 봅시다. 첫 단계는 각 게이트의 출력을 레이블링해 회로를 불 식으로 변환하는 것입니다:

체계적으로 진행해 첫 NOR과 NAND 게이트의 출력을 작성하되, 반전 전 식과 최종 반전 출력을 분리해 보수 바를 놓치지 않도록 합니다:

마지막 NOR 게이트의 출력을 표현합니다:

불 항등식과 드모르간 정리를 사용해 결과 식을 단순화하면 간소화된 형태가 나옵니다:

등가 단순화 회로는 아래와 같습니다:

핵심 요약

• 드모르간 정리는 게이트 출력을 반전시키는 것이 게이트 타입 전환(AND↔OR)과 입력 반전과 동등함을 보여줍니다.
• 보수 바를 깨면 하부 연산이 반전되며, 깨진 조각들은 영향을 받는 변수 위에 남습니다.
• 항상 가장 길고 최상단의 바를 먼저 깨고, 두 개의 서로 다른 바를 한 단계에서 깨지 마세요.
• 바는 그룹화 기호로 작동하므로, 바를 깬 후 괄호로 적절히 그룹화해 우선순위를 보존해야 합니다.

관련 워크시트

• 불 대수 워크시트