부울 대수

이번 게시글에서는 부울 대수에 대해 살펴보도록 하겠습니다. 부울 대수(Boolean Algebra)는 어떤 명제의 참과 거짓을 이진수 1과 0에 대응시켜서 명제와 명제간의 관계를 수학적으로 표현하는 것입니다. 다시 말해 디지털 논리회로를 수식으로 표현한 것입니다. 이러한 수식을 풀어나가는 것이 바로 부울 대수의 응용이라고 할 수 있습니다. 전산직 공무원 시험에서는 반드시 출제되니 준비하시는 분들은 꼭 연습하시기 바랍니다.

 

우선 부울대수의 기본 연산자는 아래와 같습니다.

 

(1) 피연산자: X, Y 등 대문자 기호를 사용

(2) 연산자

AND: 두 값이 모두 1일 때 1이 됩니다. ( X·Y or XY )

OR: 둘 중 하나만 1이어도 1이 됩니다. ( X+Y )

NOT: 0이면 1이 되고 1이면 0이 됩니다. ( X' )

 

 

또한 부울 대수에서는 아래의 법칙들이 성립합니다.

 

(1) 교환 법칙

X+Y = Y+X

X·Y = Y·X

 

(2) 결합 법칙

(X+Y)+Z = X+(Y+Z)

(X·Y)·Z = X·(Y·Z)

 

(3) 분배 법칙

X·(Y+Z) = X·Y+X·Z

X+Y·Z = (X+Y)·(X+Z)

 

(4) 드모르간 법칙

(X+Y)' = X'·Y'

(X·Y)' = X'+Y'

 

(5) 흡수 법칙

X+X·Y = X

X·(X+Y) = X

 

(6) 이 외

X·1 = 1·X = X

X·0 = 0·X = 0

X+0 = 0+X = X

X+1 = 1+X = 1

X·X = X

X+X = X

X·X' = 0

X+X' = 1

X'' = X

 

 

예시1) [19년도 국가직 공무원 9급 컴퓨터일반]

 

출력(⑤): ( ( x2 + x3 ) · x1' ) + x3'

= ( ( x2 + x3 ) + x3' ) · ( x1' + x3' )  ---[ 분배 법칙 ]

= ( x2 + ( x3 + x3' ) ) · ( x1' + x3' )  ---[ 결합 법칙 ]

= ( x2 + 1 ) · ( x1' + x3' )   ---[ x3 + x3' = 1 ]

= 1 · ( x1' + x3' )  ---[ x2 + 1 = 1 ]

= x1' + x3'   ---[ 1· X = X ]

 

 

예시2) [19년도 지방직 공무원 9급 컴퓨터일반]

( x + y ≥ z AND ( x + y ≥ z OR x - y ≤ z ) AND x - y ≥ z ) OR x + y < z

 

다음과 같이 치환

x + y ≥ z : A

x + y < z : A'

x - y ≤ z : B

x - y > z : B'

 

( A · ( A + B' ) · B' ) + A'

= ( ( A · A + A · B' ) · B' ) + A'  ---[ 분배 법칙 ]

= ( ( A + A · B' ) · B' ) + A'  ---[ A · A = A ]

= ( A · ( 1 + B' ) · B' ) + A'  ---[ 분배 법칙 ]

= ( A · B' ) + A'  ---[ 1 + B' = B' ]

= ( A + A' ) · ( B' + A' )  ---[ 분배 법칙 ]

= 1 · ( B' + A' )  ---[ A + A' = 1 ]

= ( B' + A' )  ---[ 1 · X = X ]

= A' + B' ---[ 교환 법칙 ]

 

치환을 풀면

x + y < z OR x - y > z