1. 부울식(논리식)의 표현
ㅇ 모든 부울식(논리식)은, `최소항들의 합(SOP)` 또는 `최대항들의 곱(POS)` 형태로 표현 가능
ㅇ 例)
- 논리 결과값 1을 기준으로 (SOP), {# Y = \bar{A}B + AB #}
- 논리 결과값 0을 기준으로 (POS), {# Y = (A + B)(\bar{A} + B #}
2. 부울식(논리식)의 표현 형태 둘(2)
ㅇ 최소항 (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 만 사용되는 것으로 제한시킴
※ 통상, 최대항들의 곱으로 표현하는 것 보다, 최소항들의 합으로 표현하는 것이,
- 회로 면적 측면에서 유리함
3. 부울식의 간략화
ㅇ 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} #}
- 부울식의 간략화에 크게 도움이 됨
ㅇ 간략화 방법 구분
- 대수학적 처리방법 (Algebraic Manipulation)
. 시간이 많이 걸리고 비현실적인 간략화 방법임
. 체계적인 방법(특정 규칙)이 없음
.. 각 항들을 묶어가며, 그때그때 마다 부울 대수 정리들을 이용하여,
.. 최소 축약식을 만들어냄
. 최소 축약식은 유일하지 않음(다양함)
- 카르노맵 (Karnaugh Map)
. 1953년 벨연구소의 Maurice Karnaugh 개발
. 진리표를 도식화하여 논리식의 간략화 과정을 시각적으로 보여줌
. 통상 4개까지로 제한되나, 시각화 용이 및 통찰력에 도움이 됨
- 도표 이용 방법 (Tabulation Method, Quine-McCluskey 방법)
. 1956년 Willard Van Orman Quine(최초개발), Edward J. McCluskey(개선)
. 처리과정이 다소 복잡하고 시각화에 불편하지만, 알고리즘화에 용이함