표준형과 정형

0. 기본 용어

• Literal (리터럴) : 함수에 나타나는 변수를 의미한다.

 

1. Standard Form (표준형)

• SOP (Sum of Product, 곱들의 합)
• POS (Product of Sum, 합들의 곱)

 

어떤 함수가 SOP 형태나 POS 형태로 나타나게 되면 그러한 함수를 표준형이라고 한다. 예를 들어 $F = AB + BC$와 같이 나타나면 곱들이 합해진 형태이기 때문에 SOP가 되고 $F = (A+B) \cdot (B+C)$ 와 같이 나타나면 합들이 곱해진 형태이기 때문에 POS이다. 이렇게 SOP, POS로 나타나지 않는 경우는 표준형이 아니다. 보통 표준형 함수는 아래와 같이 2 Level로 구현된다.

 

[그림] 표준형 함수

 

2. Min Term & Max Term (최소항 & 최대항)

1) Min term (최소항) : 모든변수가 한 번씩 나타나 곱의 형태를 이루고, 그 변수들이 true 혹은 false의 형태를 취하게되는 경우를 최소항이라고 한다. 000부터 111까지 있다면 위 부터 m0, m1, ... m7 등으로 소문자 m을 이용해 표기한다.

 

a	b	c	Min Term
0	0	0	$a' \cdot b' \cdot c'$ (m0)
0	0	1	$a' \cdot b' \cdot c$ (m1)
0	1	0	$a' \cdot b \cdot c'$ (m2)
0	1	1	$a' \cdot b \cdot c$ (m3)
1	0	0	$a \cdot b' \cdot c'$ (m4)
1	0	1	$a \cdot b' \cdot c$ (m5)
1	1	0	$a \cdot b \cdot c'$ (m6)
1	1	1	$a \cdot b \cdot c$ (m7)

 

벤다이어그램에서 보면, 최소항 영역들은 독립된 각 영역으로 생각할 수 있다. 예를 들어 ABC, 세개의 변수가 있고 각각 1, 0, 0이라고 한다면 이 것의 최소항은 아래의 영역이 된다. 

 

 

 

2) Max Term (최대항) : 모든변수가 한 번씩 나타나 합의 형태를 이루고, 그 변수들이 true 혹은 false의 형태를 취하게되는 경우를 최대항이라고 한다. 000부터 111까지 있다면 위 부터 M0, M1, ... M7 등으로 대문자 M을 이용해 표기한다.

 

a	b	c	Max Term
0	0	0	$a + b + c$ (M0)
0	0	1	$a + b + c'$ (M1)
0	1	0	$a + b' + c$ (M2)
0	1	1	$a + b' + c'$ (M3)
1	0	0	$a' + b + c$ (M4)
1	0	1	$a' + b + c'$ (M5)
1	1	0	$a' + b' + c$ (M6)
1	1	1	$a' + b' + c'$ (M7)

 

Max Term과 Min Term은 서로 보수관계이다. 예를 들어 만일 아래의 벤다이어그램에서 100의 Min Term  영역은 위에서 본 영역이였지만 100의 Max Term은 A' + B + C로 아래 영역에 해당한다.

 

 

3) Min Term과 Max Term의 관계 : 위와 같이 Min Term과 Max Term은 보수의 관계를 가진다. 변수 A, B, C가 만약 1, 0, 0의 경우 최소항은 순수한 A의 영역만을 가리키고, 최대항은 순수한 A의 영역을 제외한 모든영역을 가리킨다.

 

3. Canonical Form (정형)

• SOm (Sum of min term, 최소항의 합)
• POM (Product of Max term, 최대항의 곱)

 

정형 함수는 표준형 함수의 특수한 케이스이다. SOP중에서 더해지는 곱들이 모두 최소항의 형태를 띈다면 그런 형태를 SOm (최소항의 합)이라고 하고, POS중에 더해지는 곱들이 모두 최대항의 형태를 띈다면 그런 형태를 POM (최대항의 곱)이라고 한다.

 

예를 들어, 3개의 변수 A, B, C가 있을 때 F = ABC + AB'C + A'BC와 같이 더해지는 모든 곱항들이 최소항인 경우, SOm이라고 할 수 있고 이런 경우 함수 F는 정형이다. 만일 G = ABC + AB'C + A'B와 같이 주어지면 곱들의 합이기 때문에 G는 SOP이고 표준형은 맞지만, 세번째 A'B가 최소항이 아니기 때문에 정형은 아니다.

 

1) SOm 표기법 : 정형과 비정형의 표기법은 다음과 같이 표기할 수 있다. 만약 F = A'B'C' + A'B'C + A'BC'이라고 하면 이 함수는 세개의 최소항이 더해졌으므로 SOm형태의 정형함수이고, F = m0 + m1+ m2와 같이 쓸 수 있다. 이를 합의 기호 시그마를 이용해 표현하면 F = ∑m(0, 1, 2)와 같이 표기할 수 있다.

 

2) POM 표기법 : 만약 F = (A + B + C) (A + B + C') (A + B' + C)와 같이 표기한다면 이 함수는 세개의 최대항이 곱해졌으므로 POM 형태의 정형함수이고, F = M0 M1 M2와 같이 표기할 수 있다. 이를 곱의 기호 프로덕트를 이용해 표현하면 F = ∏M(0, 1, 2)와 같이 표현할 수 있다.

 

3) SOm과 POM의 관계 : SOm인 정형함수 F = ∑m(3, 4, 5, 6, 7)이 있으면, 이 F= ∏M(0, 1, 2)와 같이 쓸 수 있다. POM과 SOm역시 보수관계이기 때문에 뒤집으면 서로가 된다.

 

4. 표준형을 정형으로 만들기

아래처럼 표준형을 정형으로 바꿀 수 있고, 반대로 정형도 정형이 아닌 표준형으로 바꿀 수 있다. 아래처럼 수식을 이용해서 해도 좋지만 카르노맵을 이용하는 것이 훨씬 편리하다.

 

예제 1)

F = ab' + ac

 

ab' = (ab'c + ab'c')

ac = (abc + ab'c)

 

F = ab'c + ab'c' + abc + ab'c

F = m5 + m4 + m0 + m2

F = ∑m(0, 2, 4, 5) <SOm>

F = ∏M(1, 3, 6, 7) <POM>

 

---

 

예제 2)

F = a'b' + a'd + acd'

 

a'b' = a'(0) b'(0) cd(00, 01, 10, 11)

a'd = a'(0) bc(00, 01, 10, 11) d(1)

acd' = a(1) b(0, 1) c(1) d'(0)

 

a'b' = 0000, 0001, 0010, 0011 = ∑m(0, 1, 2, 3)

a'd = 0001, 0011, 0101, 0111 = ∑m(1, 3, 5, 7)

acd' = 1010, 1110 = ∑m(10, 14)

 

F = ∑m(0, 1, 2, 3, 5, 7, 10, 14) <SOm>

F = ∏M(4, 6, 8, 9, 11, 12, 13, 15) <POM>

 

5. 정리

• 표준형 (SOP) : ab + ac + abc + ...
• 표준형 (POS) : (a+b)(a+b+c)(b+c) ...
• Minterm (a, b, c) : a'b'c' , a'b'c , a'bc' ... : 벤다이어그램의 독립된 최소영역
• Maxterm (a, b, c) : (a+b+c), (a+b+c'), (a+b'+c) ... : Minterm의 역(보수)관계
• 정형 (SOm) : a'b'c' + a'b'c + a'bc' + ... / ∑m(0, 1, 2) : Minterm으로 구성
• 정형 (POM) : (a+b+c)(a+b+c')(a+b'+c) ... / ∏M(0, 1, 2) : Maxterm으로 구성

 

6. Reference