부울 대수 - 정보처리 필기 해설 2

부울 대수(Boolean algebra) 또는 불 대수는 조지 불(George Boole)이 창안한 논리 대수입니다. 대수(代數)의 사전적 의미는 "숫자 대신에 그 숫자를 대표하는 문자를 써서 수학 법칙을 간명하게 나타내는 수학의 한 분야"로 부울 대수는 논리 문제로 기호로 설명하는 것이라 할 수 있습니다. 부울 대수는 값의 범위가 참(True)과 거짓(False)으로 한정되는 대수의 한 분야로 컴퓨터에서 부울 대수가 기본적으로 언급되는 이유는 바로 컴퓨터의 논리 회로가 1, 0만의 디지털 신호를 다루기 때문입니다. 부울 대수는 회로 뿐만아니라 소프트웨어와도 깊은 연관성을 가지는데 프로그래밍 언어에서 조건을 기술하는 if , for, while 등의 문장에서는 부울 대수와 연관성을 가지는 논리 연산이 수행됩니다. 기본적인 부울 대수 법칙을 숙지해두면 회로 관련 문제 뿐만아니라 추후 프로그래밍 과정에서 복잡한 조건을 보다 명확한 방식으로 기술하는데 도움을 받을 수 있습니다.

NOT, AND, OR를 기본적인 연산자로 사용하며 관련 내용은 "정보처리기능사 필기 해설 1 - 논리게이트"를 참조하실 수 있습니다. 부울 대수의 법칙들은 아래와 같습니다.

■ 결합(Associativity) 법칙

논리합, 논리곱 등 동일한 연산자가 연속되어 있을때 괄호의 위치를 변경해도 동일한 결과를 가져옴

■ 교환(Commutativity) 법칙

논리합, 논리곱 연산자 앞뒤의 연산 대상의 순서를 바꾸어도 동일한 결과를 가져옴

■ 배분(Distributivity) 법칙

괄호로 묶인 대상과 논리합, 논리곱을 수행하는 경우 괄호 내의 대상과 개별적인 연산을 수행한 다음 괄호내 연산을 수행해도 동일한 결과를 가져옵니다. 배분법칙에서 주의할 점은 일반 대수의 경우에도 a(b+c)=ab + ac는 성립합니다. 그렇지만 a+(bc) = (a+b)(a+c)는 일반 대수에서는 성립하지 않는 다는 점입니다. a+(bc) = (a+b)(a+c)는 부울 대수에서만 성립합니다.

일반 대수로 a=1, b=2, c=3으로 a+(bc) = 7이지만 (a+b)(a+c) = 12입니다. a+(bc) = (a+b)(a+c) 배분 법칙이 일반대수에서는 성립되지 않습니다. 반면에 부울 대수로 a=1, b=0, c=1을 대입하면 a+(bc) = 1(0) = 1이고 (a+b)(a+c) = (1)(1) = 1로 이며  a=0, b=0, c=1을 대입해도 a+(bc) = 0(0) = 0이고 (a+b)(a+c) = (0)(1) = 0으로 부울대수의 a+(bc) = (a+b)(a+c) 배분 법칙은 성립합니다.

■ 항등(Identity) 법칙

0과 논리합, 1과 논리곱하면 원래 값과 동일한 결과를 가져옴

■ 소멸(Annihilator) 법칙

1과 논리합, 0과 논리곱하면 원래값이 원어지는 결과를 가져옴. 논리식 간소화에 매우 유용한 법칙.

■ 멱등(Idempotence) 법칙

동일한 연산 대상에 대해서 논리합, 논리곱을 여러번 수행해도 동일한 결과를 가져옴

■ 흡수(Absorption) 법칙

항등 법칙과 소멸 법칙이 응용된 법칙으로 괄호 바깥과 내부에 동일한 대상이 서로 다른 논리합, 논리곱 연산자로 묶인 경우 괄호 내외부에 동일하게 등장하는 연산 대상으로 흡수되는 결과를 가져옴

■ 부정(Complementation) 법칙

집합의 여집합 또는 보집합과 동일한 결과를 가져옴. 부울 대수의 부정을 일반 대수의 음수(-)로 대치시키면 법칙이 성립되지 않음에 주의해야 합니다.  3 * -3 = 0이 아니라 -9입니다. 3+ -3 = 1이 아니라 0입니다. 

■ 드모르간(De Morgan)의 법칙

두 연산 대상에 대한 논리합, 논리곱 연산 결과의 부정은 연산 대상 각각의 부정을 논리곱, 논리합으로 전환한 것과 동일한 결과를 가져옴. 필자의 경우 프로그램을 작성하다가 복자한 조건문을 명확하게 하기 위해서 이 법칙을 자주 사용합니다. 예를 들어 "if (a > b && c < d)..."라는 C 코드를 거꾸로 기술하면 드 모르간의 법칙을 따라서 부등호를 전환하고 &&(AND)는 ||(OR)로 바꾸어 주면 "if (a <=b || c>=d) ..."로 작성할 수 있습니다. 두 문장중에 더 명쾌한 방식으로 조건문을 기술하는 것입니다.

■ 논리식 간소화

복잡한 논리식은 위에서 언급한 여러가지 법칙을 응용해서 최소화할 수 있습니다. 항의 개수가 줄어들거나 없어지는 항등, 소멸, 멱등, 흡수, 부정 법칙을 곧바로 적용할 수 있다면 곧바로 논리식이 간소화 되겠지만 그렇지 않다면 결합, 배분, 드 모르간의 법칙 및 기타 간소화 예제를 활용하여 논리식을 변형해가며 간소화 시킵니다. 기본 법칙들을 활용한 간소화 예제들은 아래와 같습니다.

• 

  배분법칙으로 식을 전개한 다음 부정법칙으로 1(a+b)를 유도하고 항등법칙에 따라 1과의 논리곱 a+b가 남습니다.
  같은 방식을 적용하면  입니다.

  
  

• 
  배분법칙으로 식을 전개한 다음 멱등법칙으로 aa=a, 흡수법칙으로 a+ac=a, a+ab=a가 됩니다.
  같은 방식을 적용하면  입니다.

  
  

• 

  배분법칙으로 식을 전개한 다음 멱등법칙으로 a+a=a, 부정법칙으로 1이 되고 흡수법칙으로 a가 남은 상태에서 항등법칙에 따라 최종적으로 a가 남습니다.

• 부정법칙과 항등법칙을 활용하여 논리식에 영향을 주지 않는  를 더하거나(a+0=a) 를 곱한(a*1=a) 다음 논리식 간소화를 진행하는 여분의 항 추가 방법도 좋은 방법입니다.

정보처리기능사 필기 문제에서는 부울 대수의 기본 법칙이나 기본 게이트에 대한 논리식 위주의 문제가 출제되고 있습니다. 간소화 문제가 나오기도 합니다. 정답보기를 클릭하면 답을 확인할 수 있습니다.

1. 불 대수의 관계가 옳은 것은? (정답보기☜)

   가.   나. 

   다.          라. 

※ (나)번 보기는 헷갈릴 수 있는데 드 모르간의 법칙을 확인해 보세요.

2. 다음 논리 회로를 나타내는 불 대수식은? (정답보기☜)

    가. X = ABC 나. X = A'+B'+C'

    다. X = AB+C 라. X = A+B+C

3. 다음 보기의 논리회로도에 맞는 불 대수식은? (정답보기☜)

    가. Y=AB          나. Y=A+B

    다. Y=A(A+B)   라. Y=(A+B)B

※ 회로도를 그대로 옮기면 (A+B)+B 이고 결합법칙을 적용하면 A+(B+B), 멱등법칙을 적용하면 A+B가 됩니다.

4. 불 대수(Boolean Algebra)의 정리 중 틀린 것은? (정답보기☜)

    가. A+A=A   나. AA'=0

    다. A+A'=1  라. A+0=0

※ 멱등법칙과 부정법칙을 확인하세요.

5.  와 같은 논리식은? (정답보기☜)

   가.  나. 

   다.   라. 

※ 드모르간의 법칙과 배분법칙, 부정법칙, 항등법칙을 차례로 적용하면

6. 다음 논리회로의 논리식은? (정답보기☜)

    가. f = A + B'         나. f = A' + B

    다. f = A·B 라. f = A + B

※ 처음 식은 A'+B'에 대한 NOR이므로 (A'+B')'입니다. 드 모르간의 법칙을 적용하면 f=AB가 됩니다.

7. 다음 회로에 해당하는 출력 Y의 논리식은? (정답보기☜)

    가. A' + B 나. A + B'

    다. A' + B' 라. A + B

※ 입력 A가 연결되는 게이트가 NOT이 아니라 NAND 게이트 이지만 입력이 하나이므로 NOT으로 간주하면 됩니다. NOT, AND, OR를 응용한 NOR, NAND, XOR, XNOR에 대한 기본 논리식과 간소화된 논리식은 숙지할 필요가 있습니다. XOR : A'B+AB',  NAND : (AB)'=A'+B', NOR : (A+B)'=A'B', XNOR : AB+A'B'

8. 논리식를 간소화 하면 결과는? (정답보기☜)

   가. Z=A+B   나. Z=A'B

   다. Z=A      라. Z=1

※ 흡수법칙을 참고하세요.