부울 대수와 논리 회로 설계(1)

 부울 대수

• 집합 S={0,1} 에 대해 다음의 세 가지 연산이 존재
  • 보수(complement)
  • 부울 합(boolean sum)
  • 부울 곱(boolean product)

보수

• '로 표시
• 원소 0에 대하여 0'=1, 원소 1에 대하여 1'=0
• 합 : +(OR)
  • 1+1=1
  • 1+0=1
  • 0+1=1
  • 0+0=0
• 곱 : *(AND)로 표시 (점은 생략하여 표기하기도 한다.)
  
  • 1*1=1
  • 1*0=0
  • 0*1=0
  • 0*0=0
• 연산 우선 순서 : 보수->곱->합

부울 변수

집합 S={0,1}의 원소 값만을 갖는 변수

부울 함수

0또는 1의 입력값들에 대하여 0또는 1의 출력값을 갖는 함수

차수 n의 부울 함수

부울 식

항등

• n개의 변수로 이루어진 부울 함수 F,G가 있을 때, 모든 변수 x1, x2,...,xn 값에 대하여 F(x1,x2,...,xn)=G(x1,x2,...xn)이면, 부울 함수 F와 G는 동등하다고 한다.
• 즉 동일한 변수 값에 대해서 진리표의 결과값이 동일하면 두 부울 함수는 동등하다.

쌍대성의 원리

• 부울 대수의 모든 항등 법칙에 대하여 다음 2개의 식이 쌍으로 존재한다.
  x+0=x, x*1=x -> 쌍대라고 한다.
• 부울식으로 표현된 함수들 사이에 항등성이 유지되면, 이들의 쌍대도 항등성을 유지한다.
• 부울 대수의 쌍대는 *과 +를 교환하고, 0과 1을 교환하여 구할 수 있다.

최소항

• n개의 부울 변수(x1, x2, ..., xn)으로 이루어진 부울식이 있을 때, 이 부울식의 최소항은 부울 곱 y1, y2,...,yn이다.
  yi=xi 또는 yi=xi'이다.
• 최소항은 함수의 모든 변수에 대하여 부울 곱을 취한 것으로 변수는 변수 문자 또는 변수 문자의 보수 형태가 한번씩만 나타난다.

논리합 형식

• 곱들의 합
• 부울 함수를 최소항들의 부울 합으로 나타내는 형식
• 부울 함수의 부울식은 함수의 값이 1이 되는 변수 값의 조합들에 대하여 최소항들을 구하고 그 최소항들의 부울 합(논리합 형식)을 취하면 구할 수 있다.