디지털 논리회로 3부<드모르간의 법칙>

 

 

목차

1.부울표현과 진리치표

\({F_{1}=A{B}'+C}\)

\({F_{2}=(A+C)({B}'+C)}\)

 

위의 두가지 식이 맞을지 어떻게 판별할까요?

가장 원론적인 방법은 지난번에 배운 AND,OR,NOT게이트를 냅다 때려박는겁니다. 히히

 

백문이 불여일견~ 한번 해볼까요?

 

A	B	C	\({B}'\)	\(A{B}'\)	\(A{B}'+C\)
0	0	0	1	0*1=0	0+0=0
0	0	1	1	0*1=0	0+1=1
0	1	0	0	0*0=0	0+0=0
0	1	1	0	0*0=0	0+1=1
1	0	0	1	1*1=1	1+0=1
1	0	1	1	1*1=1	1+1=1
1	1	0	0	1*0=0	0+0=0
1	1	1	0	1*0=0	0+1=1

 

앞의 A,B,C는 나올수 있는 경우의 수가 \(2^{3}\)이므로 총 8가지의 경우가 나옵니다.

\({B}'\)이 의미하는것은 B의 NOT이므로 B의 반대를 나타냈습니다.

그리고 곱은 AND 연산이므로 A와 \({B}'\)를 연산해보면 표와 같이 나옵니다.

합은 OR연산이므로 표와 같이 결과가 도출이 됩니다.

 

 

A	B	C	\( A+C \)	\({B}'+C \)	\((A+C)({B}'+C)\)
0	0	0	0+0=0	1+0=1	0*1=0
0	0	1	0+1=1	1+1=1	1*1=1
0	1	0	0+0=1	0+0=0	1*0=0
0	1	1	0+1=1	0+1=1	1*1=1
1	0	0	1+0=1	1+0=1	1*1=1
1	0	1	1+1=1	1+1=1	1*1=1
1	1	0	1+0=1	0+0=0	1*0=0
1	1	1	1+1=1	0+1=1	1*1=1

 

이 표 또한 위의 법칙을 그대로 적용시킨 결과가 가장 오른쪽의 결과입니다.

 

그러므로

\({F_{1}=A{B}'+C}\)

\({F_{2}=(A+C)({B}'+C)}\)

는 같다는것을 알 수 있습니다.

---

1-1.Axioms<기본정리&명제>

1-1-1. Duality<쌍대성>

AND는 OR로, 0은 1로 바꾸면 쌍대 수식이 된다.

 

 

이게 무슨말인지 감이 안잡히니 바로 식으로 증명해봅시다.

 

먼저 X+0=X라는 명제를 보도록 합시다.

(여기서 X는 임의의 상태인 0,1을 나타냅니다.)

 

 

여기서 위의 두줄을 보면 이해가 될텐데요. A가 0이라는 고정된 입력이고 B를 X로 생각해보세요.

그러면 OR 연산의 결과는 B 자기 자신이 나온다는 결과가 도출이 될 수 밖에 없습니다.

 

---

 

 

이제는 X*1=X를 생각해봅시다.

(여기서 X는 임의의 상태인 0,1을 나타냅니다.)

이번에도 마찬가지입니다. A가 1이라는 고정된 입력이고 B를 X로 생각해보세요.

이번에도 AND 연산의 결과는 B 자기 자신이 나온다는 결과가 도출이 될 수 밖에 없습니다.

 

이제 이 결과를 한번 표로 정리해보도록 하겠습니다.

 

 

 

1번째 상자를 보면 쌍대성을 생각해볼수 있는데요.

X + 0 = X 와 X * 1 = X이 서로 쌍대성의 법칙을 이루고 있습니다.

X + 1 = 1 과 X * 0 = 0이 서로 쌍대성의 법칙을 이루고 있습니다.

 

그리고 2번째 상자 또한 쌍대성을 생각해 볼 수 있습니다.

X + X' = 1 과 X * X' = 0 또한 쌍대성이 이루어지죠?

 

그러니까  X + 0 = X , X + 1 = 1 , X + X' = 1 이라는 공식 3개만 외우면 나머지는 바꾸면 그대로 따라온다 이거죠 하하 

---

1-1-2. 교환,결합,분배법칙

 i)교환법칙, 결합법칙

\({X + Y = Y + X}\)

\({X * Y = Y * X}\)

 

\({(X + Y)+Z = X+ (Y + Z)}\)

\({(XY)Z = X(YZ)}\)

 

위의 두가지 법칙은 일반적인 대수법칙과 똑같으므로 여기서는 의미에 대해서 생각해보도록 하겠습니다.

 

결합법칙의 의미는 2개의 게이트를 1개로 줄일 수 있다.로 설명이 됩니다.

 

ii) 분배 법칙

\({X+ (Y + Z) = XY + XZ}\)

\({X+YZ = (X+Y)(X+Z)}\)

 

위의 식은 대수법칙에서도 적용되는데 아래는 뭔가 이상하죠?

한번 테이블로 증명해보도록 하겠습니다.

 

X	Y	Z	YZ	X+YZ	X+Y	X+Z	(X+Y)*(X+Z)
0	0	0	0*0=0	0+0=0	0+0=0	0+0=0	0*0=0
0	0	1	0*1=0	0+0=0	0+0=0	0+1=1	0*1=0
0	1	0	1*0=0	0+0=0	0+1=1	0+0=0	1*0=0
0	1	1	1*1=1	0+1=1	0+1=1	0+1=1	1*1=1
1	0	0	0*0=0	1+0=1	1+0=1	1+0=1	1*1=1
1	0	1	0*1=0	1+0=1	1+0=1	1+1=1	1*1=1
1	1	0	1*0=0	1+0=1	1+1=1	1+0=1	1*1=1
1	1	1	1*1=1	1+1=1	1+1=1	1+1=1	1*1=1

 

 

테이블로써 \({X+YZ = (X+Y)(X+Z)}\)  해당 공식이 적용이 됨을 알 수 있습니다.

 

---

1-1-3. 드모르간의 법칙 <중요>

\(\bar{XY}=\bar{X}+\bar{Y}\)   ,   \(\bar{X+Y}=\bar{X}*\bar{Y}\)

 

not (A or B)=(not A) and (not B)

 

not (A and B)=(not A) or (not B)와 같습니다.

 

이렇게 보면 이해가 영 안갈텐데요.

 

아마 밴 다이어그램을 보면 중,고등학생때 이걸 배웠던 기억이 나실겁니다.

 

 

이해를 위해서 아주 간단한 예시를 한번 들어보겠습니다.

 

국어와 수학 성적이 모두 1등급인 학생이 장학금을 받는다는 명제를 세워봅시다.

 

그러면 A는 국어 성적이 1등급이라는 명제이고 B는 수학성적이 1등급이라는 명제가 될겁니다.

 

그래서 \(A\cap B\)라는 조건을 만족해야 장학금을 받을수 있다. 이겁니다.

자 좋습니다. 그런데 말입니다. 장학금을 못받는 조건이 뭐냐고 물어보면 어떻게 답하실거죠?

 

다시 말하면, \(A^{c}\)는 국어 성적이 1등급이 아닌경우를 의미합니다.

\(B^{c}\) 는 수학성적이 1등급이 아닌경우를 의미하구요. 

이 두가지 조건중 하나라도 만족하면, 장학금을 못받죠.

\(A^{c}\cup B ^{c}\) 이 그것을 나타냅니다. 

 

---

 

말보다는 예제를 보여주는게 더 빠를것 같아서 예제를 풀어보시는게 더 빠르실겁니다.

 

\(F = ((X \cdot  Y') \cdot(Y'+Z))'\)를 드모르간의 법칙을 활용하여 변형해보세요.

 

 

<풀이>

\((X \cdot  Y') = A \), \((Y'+Z) =B\)라 칩시다.

 

그러면 식이 \( F = (A \cdot B)' \)으로 정리가 됩니다.

\( F = A' + B' \)는 드모르간의 법칙에 의해 변형이 됩니다.

\(F = ((X \cdot  Y')'  +   (Y'+Z)') \)

\(F = ((X' +  Y)  +   (Y \cdot Z') )\)

가 최종적으로 나옵니다.

 

 

쉽게 요약하자면 다음과 같습니다.

• 전체 부정은 각각 부정으로 나눌 수 있다.
• 이때 전체 부정이 합인부분은 각각 부정일때 곱으로, 전체 부정이 곱인 부분은 각각 부정일때 합으로 바꿔라

 

         

 

이제는 진리표를 거쳐서 간략화 하는 방법 <카르노맵, Q-M 방식> 을 앞으로 배워볼 예정입니다.