최소항 전개
최소항 전개(minterm expansion)는 정규형 중 논리 함수의 모든 변수들을 곱의 합 형태로 표현한 것이다. 즉 F=x+yz라는 것은 곱의 합 형태이므로 최소항 전개 형태이다. 하지만 G=x(y+z)+w와 같은 경우는 전개를 통해서 G=xy+yz+w로 표현 가능하므로 최소항 전개 형태가 아니다. 논리 함수가 1이 되는 모든 경우의 변수들의 곱을 더해주면 그 논리 함수의 최소항 전개 형태를 구할 수 있다. 예를 들어, F(a,b,c)가 a=0, b=1, c=0 or 1이거나 a=1,b=1,c=0인 경우에만 1이 된다면 F(a,b,c)=a'bc'+a'bc+abc'=a'b+abc'으로 표현할 수 있다. 이와 같은 작업은 변수의 개수가 5개 이하일 경우 카르노 맵을 이용하여 비교적 쉽게 가능하나, 변수의 수가 늘어난다면 퀸-매클러스키 알고리즘을 이용하여 컴퓨터를 통하여 처리할 수 있다. 또한 최소항에 번호를 매겨서 수학 기호 Σ을 통하여 나타낼 수 있다. 최소항에 번호를 매기는 방법은 다음과 같다.(변수가 3개일 경우)
열 번호 | A B C | 최소항 |
---|---|---|
0 | 0 0 0 | A'B'C'=m0 |
1 | 0 0 1 | A'B'C=m1 |
2 | 0 1 0 | A'BC'=m2 |
3 | 0 1 1 | A'BC=m3 |
4 | 1 0 0 | AB'C'=m4 |
5 | 1 0 1 | AB'C=m5 |
6 | 1 1 0 | ABC'=m6 |
7 | 1 1 1 | ABC=m7 |
여기서 각 최소항들은 각 A,B,C의 값들이 1이 되는 값을 번호로 갖는다. 즉 A=1,B=0,C=1인 경우 이를 1012로 읽어서 m5가 되는 것이다. 이를 이용하여서 어떠한 논리함수 F가 만약 m0,m3,m7의 합으로 표현된다면 다음과 같이 쓸 수 있다. F=Σm(0,3,7)