DeMorgan의 정리

DeMorgan이라는 수학자는 부울 대수에서 그룹 보완에 관한 한 쌍의 중요한 규칙을 개발했습니다.

그룹 별 보완, 하나 이상의 변수 위에 긴 막대로 표시되는 용어 그룹의 보완을 나타냅니다.

게이트에 대한 모든 입력을 반전하면 해당 게이트의 필수 기능이 AND에서 OR로, 또는 그 반대로 반전되고 출력도 반전된다는 논리 게이트 장에서 기억해야 합니다.

따라서 모든 입력이 반전된 OR 게이트(음의 OR 게이트)는 NAND 게이트와 동일하게 동작하고 모든 입력이 반전된 AND 게이트(음의 AND 게이트)는 NOR 게이트와 동일하게 동작합니다.

DeMorgan의 정리는 "역방향" 형태로 동일한 동등성을 나타냅니다. 즉, 게이트의 출력을 반전하면 반전된 입력이 있는 반대 유형의 게이트(AND 대 OR)와 동일한 기능이 발생합니다.

AB라는 용어에 걸쳐 연장된 긴 막대는 그룹화 기호 역할을 하므로 A와 B가 독립적으로 반전된 곱과 완전히 다릅니다.

즉, (AB)'는 A'B'와 같지 않습니다. "소수" 기호(')는 막대 캔처럼 두 개의 변수에 걸쳐 확장될 수 없기 때문에 앞 문장의 전체 용어 AB에 적용되도록 괄호를 사용해야 합니다.

그러나 막대는 둘 이상의 변수에 걸쳐 확장될 때 자체 그룹화 기호 역할을 합니다.

이것은 부울 표현식이 평가되고 축소되는 방식에 중대한 영향을 미치며 앞으로 보게 될 것입니다.

드모건의 정리

DeMorgan의 정리는 파괴 측면에서 생각할 수 있습니다. 긴 막대 기호.

긴 막대가 끊어지면 나누기 바로 아래의 연산이 덧셈에서 곱셈으로 변경되거나 그 반대로 변경되고 끊어진 막대 조각은 개별 변수 위에 남아 있습니다. 설명:

표현식에 막대의 "레이어"가 여러 개 있는 경우 한 번에 하나의 막대만 끊을 수 있습니다. , 그리고 일반적으로 가장 긴(가장 높은) 막대를 먼저 끊어 단순화를 시작하는 것이 더 쉽습니다.

설명을 위해 (A + (BC)')'라는 표현을 사용하고 DeMorgan의 정리를 사용하여 축소해 보겠습니다.

가장 긴(가장 높은) 막대를 먼저 깨라는 조언에 따라 첫 번째 단계로 전체 표현식을 덮는 막대를 깨는 것으로 시작하겠습니다.

결과적으로 원래 회로는 A 입력이 반전된 3입력 AND 게이트로 축소됩니다.

당신은 절대 해서는 안됩니다 여기에 설명된 대로 한 단계에서 둘 이상의 막대를 끊습니다.

걸음 수를 줄이고 한 번에 둘 이상의 막대를 끊는 것이 유혹적일 수 있지만 종종 잘못된 결과로 이어지므로 하지 마십시오!

긴 막대를 먼저 끊지 않고 짧은 막대를 먼저 끊으면 이 표현을 적절하게 줄일 수 있습니다.

최종 결과는 같지만 가장 긴 막대가 먼저 부러지는 첫 번째 방법을 사용할 때보다 더 많은 단계가 필요합니다.

세 번째 단계에서 우리가 두 곳에서 긴 막대를 어떻게 끊었는지 주목하십시오.

이것은 합법적인 수학 연산이며 한 번에 두 개의 막대를 깨는 것과는 다릅니다!

한 단계에서 둘 이상의 막대를 깨는 것을 금지하는 것은 아닙니다. 둘 이상의 장소에서 막대를 깨는 것을 금지합니다.

둘 이상의 장소 침입 한 번에 괜찮습니다. 둘 이상의 막대 깨기 한 단계에서 그렇지 않습니다.

다음 단계에서 방금 제거한 것을 고려할 때 하위 표현식 B' + C' 주위에 괄호를 배치한 이유가 궁금할 것입니다.

나는 DeMorgan의 정리의 중요하지만 쉽게 간과되는 측면을 강조하기 위해 이것을 했습니다.

긴 막대가 그룹화 기호로 기능하기 때문에 이전에 깨진 막대로 그룹화된 변수는 적절한 우선순위(작업 순서)가 손실되지 않도록 그룹화된 상태를 유지해야 합니다.

이 예에서는 짧은 줄을 끊은 후 괄호를 넣는 것을 잊어도 상관없지만 다른 경우에는 그럴 수 있습니다.

다른 표현식으로 시작하는 다음 예를 고려하십시오.

보시다시피, 이 표현식에 대한 보완 막대가 의미하는 그룹화를 유지하는 것은 정답을 얻는 데 중요합니다.

DeMorgan의 정리 원리를 게이트 회로의 단순화에 적용해 보겠습니다.

항상 그렇듯이 이 회로를 단순화하는 첫 번째 단계는 동등한 부울 표현식을 생성하는 것이어야 합니다.

입력이 알려지면 각 게이트의 출력에 하위 표현식 레이블을 배치하여 이를 수행할 수 있습니다. 이 프로세스의 첫 번째 단계는 다음과 같습니다.

다음으로 첫 번째 NOR 게이트와 NAND 게이트의 출력에 레이블을 지정할 수 있습니다.

역출력 게이트를 다룰 때 없이 게이트 출력에 대한 표현식을 작성하는 것이 더 쉽다는 것을 알았습니다. 반전 거품 직전을 가리키는 화살표가 있는 최종 반전.

그런 다음, 게이트 밖으로 이어지는 와이어(거품 뒤)에 완전하고 보완된 표현을 씁니다.

이렇게 하면 표현식 작성 작업을 두 단계로 분할하여 하위 표현식의 보완 표시줄을 잊지 않도록 하는 데 도움이 됩니다.

마지막으로 마지막 NOR 게이트에 대한 표현식(또는 표현식 쌍)을 작성합니다.

이제 부울 대수의 항등식, 속성, 규칙 및 정리(DeMorgan's)를 사용하여 이 식을 줄입니다.

이 훨씬 단순화된 표현에 대한 등가 게이트 회로는 다음과 같습니다.

검토:

<울>

DeMorgan의 정리는 입력이 반전된 게이트와 출력이 반전된 게이트 간의 동등성을 설명합니다. 간단히 말해서 NAND 게이트는 Negative-OR 게이트에 해당하고 NOR 게이트는 Negative-AND 게이트에 해당합니다.

부울 식에서 보완 막대를 '끊는' 경우 나누기 바로 아래의 연산(덧셈 또는 곱셈)이 반전되고 깨진 막대 조각이 각 항 위에 남습니다.

가장 긴(가장 높은) 막대를 깨고 그 아래에 있는 막대를 깨뜨리면 문제에 접근하는 것이 더 쉬운 경우가 많습니다. 절대 해서는 안 됩니다. 한 번에 두 개의 막대를 깨려고 시도하십시오!

보완 막대는 그룹화 기호 역할을 합니다. 따라서 막대가 깨져도 그 아래에 있는 용어는 그룹화되어 있어야 합니다. 우선 순위 변경을 방지하기 위해 이러한 그룹화된 용어를 괄호로 묶을 수 있습니다.

관련 워크시트:

<울>

부울 대수학 워크시트