부울대수

부울대수의 정규형

• 논리식을 체계적으로 정리하는 방법
• 논리식을 AND와 OR 연산을 사용해 일정한 규칙에 따라 정의한 것
• 부울함수를 일관성있게 정리하기 위해 사용함
• 두 가지 주요 표현 방식은 최솓항의 합, 최대항의 곱이 있음
  • 최소항의 합: 논리식을 AND 연산으로 구성된 최소항들의 OR 연산으로 표현식이
  • 최대항의 곱: 논리식을 OR 연산으로 구성된 최대항들의 AND 연산으로 표현식이

최소항과 최대항

2개의 논리변수 X, Y가 있는 경우

• 최소항

  • 논리곱(AND)로 표현되는 $XY, X \overline Y, \overline XY, \overline{XY}$

• 최대항

  • 논리합(OR)로 표현되는 $X + Y, X + \overline Y, \overline X + Y, \overline{XY}$

• 최소항

  • 각 변수의 문자 1개씩 모두 n개 문자의 논리곱 항으로 그 결과가 논리: 1인 경우
    • $m_j$로 표시
  • 특정 조합에서만 논리: 1이 되고 그 외의 모든 조합에서 논리 0이 됨
  • 최소항의 합 형태로 진리표를 부울함수로 표현
    • $F = \overline{X}\,\overline{Y}\,\overline{Z} + \overline{X}\,\overline{Y}\,Z + \overline{X}\,Y\,\overline{Z} + \overline{X}\,Y\,Z + X\,\overline{Y}\,\overline{Z} + X\,\overline{Y}\,Z + X\,Y\,\overline{Z} + X\,Y\,Z$
    • $F = m_0 + m_1 + m_2 + m_3 + m_4 + m_5 + m_6 + m_7$
    • $F(X, Y, Z) = \sum m(0,1,2,3,4,5,6,7)$
    • 진리표에서 출력이 1이 되는 최소항들을 OR로 묶으면 정규형 부울함수가 구해 짐

• 최대항

  • 각 변수의 문자 1개씩 모두 n개 문자의 논리합 항으로 그 결과가 논리: 0인 경우
    • $M_j$로 표시
  • 특정 조합에서만 논리: 0이 되고 그 외의 모든 조합에서 논리 1이 됨
  • 최대항의 곱 형태로 진리표를 부울함수로 표현
    • $F = (X + Y + Z)(X + Y + \overline{Z})(X + \overline{Y} + Z)(X + \overline{Y} + \overline{Z})(\overline{X} + Y + Z)(\overline{X} + Y + \overline{Z})(\overline{X} + \overline{Y} + Z)(\overline{X} + \overline{Y} + \overline{Z})$
    • $F = M_0 \cdot M_1 \cdot M_2 \cdot M_3 \cdot M_4 \cdot M_5 \cdot M_6 \cdot M_7$
    • $F(X, Y, Z) = \prod M(0,1,2,3,4,5,6,7)$
    • 진리표에서 출력이 0이 되는 최대항들을 AND로 묶으면 정규형 부울함수가 구해 짐

표준형

• 정규형을 간소화한 함수 형태

• 정규형은 진리표에서 바로 얻을 수 있지만, 최소 혹은 최대항에 대한 모든 변수가 포함되어 형태가 복잡함

• 정규형 부울함수를 간소화 해야 할 필요가 있음

• 표준형 부울함수

  • 간소화된 형태로 부울함수를 표현하는 방법
  • 각 항은 하나 이상의 문자로 표현
  • 곱의 합, 합의 곱 형태가 존재함