1. 부울식(논리식)의 표현
ㅇ 모든 부울식(논리식)은, `최소항들의 합 (SOP)` 또는 `최대항들의 곱 (POS)` 형태로 표현 가능
- SOP : 출력이 1인 경우에 해당하는 항들을, 모두 OR(+) 연산으로 연결한 형태
- POS : 출력이 0인 경우에 해당하는 항들을, 모두 AND(·) 연산으로 연결한 형태
2. SOP 또는 POS에 의한 부울식 표현 例)
ㅇ 논리 결과값 1을 기준으로 (SOP), {# Y = \bar{A}B + AB #}
- 각 행의 0 입력은 해당 변수의 NOT, 1 입력은 그 자체로써 AND로 묶고, 이들을 OR시킴
ㅇ 논리 결과값 0을 기준으로 (POS), {# Y = (A + B)(\bar{A} + B) #}
- 각 행의 0 입력은 해당 변수 자체로, 1 입력은 NOT을 붙여 OR로 묶고, 이들을 AND시킴
3. 부울식(논리식)의 표현 형태 둘(2) : (SOP : 곱들의 합, POS : 합들의 곱)
ㅇ 최소항 (Minterm) or 표준곱 (standard product)
- {# AB,\; \overline{A}B,\; A\overline{B},\; \overline{A}\,\overline{B} #}
. 모든 부울 변수를 포함시켜, 곱 형태로 조합될 수 있는 항
- 例) 최소항들의 합 (SOP) : {# F = \overline{A}B + AB #}
. 여기서, {#\overline{A}B,AB#}는 각각 최소항
- SOP (Sum of Product Forms) : `곱의 합` 형태
. 1 이상 논리변수들의 곱 항들(AND terms)의 합(OR) 형태
ㅇ 최대항 (Maxterm) or 표준합 (standard sum)
- {# A+B,\; \overline{A}+B,\; A+\overline{B},\; \overline{A}+\overline{B} #}
. 모든 부울 변수를 포함시켜, 합 형태로 조합될 수 있는 항
- 例) 최대항들의 곱 (POS) : {# F = (A+B)(\overline{A}+B) #}
. 여기서, {#(A+B),(\overline{A}+B)#}는 각각 최대항
- POS (Product of Sum Forms) : `합의 곱` 형태
. 1 이상 논리변수들의 합 항들(OR terms)의 곱(AND) 형태
※ 여기서, 오직 AND,OR,NOT 만 사용되는 것으로 제한시킴
※ 통상, 최대항들의 곱(POS)으로 표현하는 것 보다, 최소항들의 합(SOP)으로 표현하는 것이,
- 회로 면적 측면에서 유리함
4. SOP 표현으로부터 부울식 간략화 例)
ㅇ (SOP) : 부울식을 논리적으로 명확히 표현하는 표준형
- {# Y = \bar{A}\bar{B}C + \bar{A}BC + ABC #}
ㅇ (간략화) : SOP 또는 POS 형태를 더 간단한 형태로 줄여 효율적인 회로 설계 가능
- {# Y = \bar{A}\bar{B}C + \bar{A}BC + ABC = C(\bar{A}\bar{B} + \bar{A}B + AB)
= C(\bar{A} + AB) = C(\bar{A} + B) #}
5. 부울식의 간략화 이란?
ㅇ 2치 부울 대수에 의한 부울식(논리식)을 체계적으로 간략화시키는 방법들
- 결국, `최소 축약식`을 도출하기 위함
ㅇ 부울식의 간략화를 위한 주요 정리/법칙들
- 특히, `흡수 법칙`,`상보성 법칙`,`드모르간 법칙` 셋(3)이, ☞ 부울 대수 정리 참조
. {# A \cdot (A+B) = A \quad A \cdot(\overline{A} + B) = A \cdot B \quad
A + A \cdot B = A \quad A + \overline{A} \cdot B = A + B #}
. {# A \cdot \overline{A} = 0 \quad A + \overline{A} = 1 #}
. {# \overline{\overline{A}+\overline{B}} = \overline{A}\cdot\overline{B}\cdot \quad
\overline{\overline{A}\cdot\overline{B}\cdot} = \overline{A}+\overline{B} #}
- 이들은, 부울식의 간략화에 크게 도움이 됨
6. 부울식 간략화 방법의 구분
ㅇ 대수학적 처리방법 (Algebraic Manipulation)
- 시간이 많이 걸리고 비현실적인 간략화 방법임
- 체계적인 방법(특정 규칙)이 없음
. 각 항들을 묶어가며, 그때그때 마다 부울 대수 정리들을 이용하여,
. 최소 축약식을 만들어냄
- 최소 축약식은 유일하지 않음(다양함)
ㅇ 카르노맵 (Karnaugh Map)
- 1953년 벨연구소의 Maurice Karnaugh 개발
- 진리표를 도식화하여 논리식의 간략화 과정을 시각적으로 보여줌
- 통상 4개까지로 제한되나, 시각화 용이 및 통찰력에 도움이 됨
ㅇ 도표 이용 방법 (Tabulation Method, Quine-McCluskey 방법)
- 1956년 Willard Van Orman Quine(최초개발), Edward J. McCluskey(개선)
- 처리과정이 다소 복잡하고 시각화에 불편하지만, 알고리즘화에 용이함