[논리와 회로설계] 항을 줄이는 방법

이 글과 시리즈는 Fundamentals of Logic Design 수업을 정리하였습니다

 

Consensus Theorem

두 항으로 된 식에서 두 항이 공통으로 갖고 있는 변수가 서로 보수 관계에 놓여있는 경우

공통으로 갖고 있는 변수를 뺀 나머지 변수끼리의 곱으로 표현할 수 있다.

 

\(XY + X'Z + YZ = XY + X'Z \)

 

증명

\(XY+X'Z+YZ = XY + X'Z + (X+X')YZ \)

\(XY+XYZ+X'YZ+X'Z = XY(1+Z) + X'Z(Y+1) = XY+X'Z\)

 

Example

\(a'b'+ac+bc'+b'c+ab\)

\(=a'b'+ac+bc'+ab\)

\(=a'b'+ac+bc' \)

Dual Form of Consensus Theorem

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

 

Consensus Theorem 사용시, 여러 항을 동시에 제거할 가능성도 있습니다. 
또한, Consensus Term을 추가하여 표현을 간소화할 수도 있습니다.

 

Example

1. \(A'C'D+A'BD+BCD+ABC+ACD'\)

이 경우에, BCD를 제거하는 방법도 있다.

하지만, A'BD와 ABC를 제거함으로써 항을 3개로 줄일 수 있다.

 

2. \(F = ABCD+B'CDE+A'B'+BCE'\)

\(B'CDE\)와 \(A'B'\)을 보자.

만약 \(ACDE\)항을 추가한다면, \(B'CDE\) 항을 지울 수 있다.

\(BCE'\)과 \(ACDE\)항을 보면, \(ABCD\)도 줄일 수 있다.

결국에는 다음과 같이 정리된다.

\(F = A'B' + BCE' + ACDE\)

 

대수적 간단화

Combining Terms ( 항 결합 )

\(XY+XY'=X\)

Eliminating Terms ( 항 제거 )

\(X+XY=X\)

Eliminating literals ( 리터럴 제거 )

\(X+X'Y=X+Y\)

 

Example

\(A'B+A'B'C'D'+ABCD'\)

\(=A'(B+B'C'D')+ABCD'\)

\(=A'(B+C'D')+ABCD'\)

\(=A'B+A'C'D'+ABCD'\)

\(=B(A'+ACD')+A'C'D'\)

\(=B(A'+CD')+A'C'D' = A'B+BCD'+A'C'D'\)

 

Adding Redundant Term ( 불필요한 항 추가)

Example

\(WX+XY+X'Z'+WY'Z'\)

\(=WX+XY+X'Z'+WY'Z'+WZ' \) adding \(WZ'\) by consensus thm.

\(=WX+XY+X'Z'+WZ'(1+Z') = WX+XY+X'Z'+WZ'\)

\(=WX+XY+X'Z'\) removing \(WZ'\) by consensus thm (WX, X'Z')

 

등식이 옳은지 증명하는 방법

1. 진리표 구성해서 양 변을 검증하는 방법 -> 비효율적

2. 다른 변과 일치할 때까지 한쪽 변에 theorem들을 적용하기

3. 양 변을 독립적으로 줄이기

4. 양쪽 변에 똑같은 연산을 적용하기

 

일반 대수에서는 적용되는 이론이, 불 대수에서는 적용되지 않을 수 있습니다.

 

If \( x+y=x+z\), then \(y=z\)

\(1+0 = 1 + 1\) but \(0 \neq 1 \)

 

If \(xy=xz\), then \(y=z\)

\(0 \cdot 0 = 0 \cdot 1 \), but \( 0 \neq 1 \)

 

If \(y=z\), then \(x+y = x+z\) //일반대수에서 참

If \(y=z\), then \(xy=xz\) //불대수에서도 참