[Bool Algebra] 논리 연산

1과 0은 전기의 켜짐, 꺼짐 그리고 true와 false를 나타낸다. 우리가 컴퓨터에서 참, 거짓을 나타내는 Boolean 타입의 Bool은 불 대수(Bool Algebra)에서 나온 것이다. 17세기에 라이프니츠가 논리를 기호로 표현하기 전까지, 논리는 언어로 전개되었다. 하지만 언어는 판단해야할 명제가 많아질 수록 참거짓을 판단하기가 어려워진다.

 

예를 들어 이런 명제를 보자.

 

''그가 사람이거나 그녀가 뱀파이어'라는 게 아니고 그가 사람이 아니라는 게' 아니다. 

 

보기만 해도 머리가 아파진다. 그러나 조지 불과 드 모르간에 의해 참 거짓을 수로 표현할 수 있게 되고 또 연산을 할 수 있게 되었다. 이렇게 되면서 위와 같은 논리는 매우 명료해질 수 있다. 

 

1. 교환 법칙 (Commutative Law)

 

명제의 순서를 바꾸어도 결과는 같다.

명제를 X와 Y라고 하면, 'X or Y' = 'Y or X' / 'X and Y' = 'Y and X'이다.

맞는지 확인해보려면 기호에 명제를 넣어보면 된다.

 

 

2. 결합 법칙 (Associative Law)

 

인접한 명제끼리 결합해도 결과는 같다. (X or Y) and Z 와 X or (Y and Z)는 같다.

이번엔 말로 풀어서 확인해보자. 문장만 놓고 봤을 때 두 식은 같다.

 

X = 그는 사람이다
Y = 그녀는 뱀파이어다
Z = 그녀는 피를 마신다

(X or Y) and Z = 그는 사람이거나 그녀는 뱀파이어이고 그녀는 피를 마신다
X or (Y and Z) = 그가 사람이거나 그녀는 뱀파이어며 그녀는 피를 마신다

 

3. 분배 법칙 (Distribute Law)

 

Z or (X and Y) = (Z or B) and (Z or C)

 

 

4. 드 모르간 법칙

 

not(X and Y) = not(X) or not(Y)

'그는 사람이 아니고 그녀가 뱀파이어'라는 것은 사실이 아니다 = 그가 사람이 아니거나 그녀가 뱀파이어가 아니다.

 

not(X or Y) = not(X) and not(Y)

'그가 사람이거나 그녀가 뱀파이어'라는 것은 사실이 아니다 = 그가 사람인 것도 아니고 그녀가 뱀파이어인 것도 아니다.

 

+ 부정 연산에서는 '결합 법칙이 성립하지 않는다.'

 

 

그럼 드 모르간 법칙을 사용해 아까의 복잡했던 명제를 간단하게 바꿔보자.

 

X = 그는 사람이다.
Y = 그녀는 뱀파이어다.

''그가 사람이거나 그녀가 뱀파이어'라는 게 아니고 그가 사람이 아니라는 게' 아니다
= not(not(X or Y) and not(X))
= not(not(X) and not(X or Y)) # 교환 법칙
= not(not(X) and not(X) and not(Y) ) # 드 모르간 법칙
= not(not(X) and not(Y))
= not(not(X or Y)) #드 모르간 법칙
= X or Y #이중부정
=그는 사람이거나 그녀는 뱀파이어다

 

명제가 훨씬 간단해졌다.