[Book] 비트 / 불리언 대수 / 드모르간의 법칙 (한 권으로 읽는 컴퓨터 구조와 프로그래밍- 1. 컴퓨터 내부의 언어 체계)

비트

bit는 2진법의 'binary'와 숫자의 'digit'이 결합된 말이다.

 

비트를 사용하는 방법 중 하나는 예//아니오로 대답할 수 있는 질문에 대한 답을 표현하는 것이다. 예를 들어, 배가 고픈가? 와 같은 질문은 예/아니오 로 대답할 수 있기 때문에 비트로 표현할 수 있다. 하지만 무슨 음식이 먹고 싶은가?와 같은 질문은 예/아니오 로 대답할 수 없기 때문에 비트로 표현할 수 있다. 

 

다른 비트들이 표현하는 내용으로부터 새로운 비트를 만들어 내는 동작을 '논리 연산'이라고 한다. 예를 들어, 배가 고프고 돈이 없다면, 라면을 먹는다. 라는 문장에서 '배가 고프다'가 '참'이고, '돈이 없다'가 '참'이면, '라면을 먹는다'는 '참'이 되는 것이다. 앞의 두 비트에 따라 라면을 먹는 마지막 비트가 나오는 것이다. 

 

불리언 대수 

불리언 대수는 '비트에 대해 사용할 수 있는 연산 규칙의 집합'이다. 영국 수학자 George Boole이 만들어 냈다. 불리언 연산자는 NOT, AND, OR, XOR 이 있고, 불리언 대수에도 일반 대수처럼 결합 법칙, 교환 법칙, 분배 법칙이 적용된다. 

 

NOT : '논리적 반대' 즉 참에 NOT을 하면 거짓, 거짓에 NOT을 하면 참이다. NOT TRUE = FALSE, NOT FALSE = TRUE

AND : 둘 이상의 비트일 때 사용 가능한 연산으로, AND 연산을 적용하는 모든 비트가 참이면 결과가 참이다. 그 외는 모두 거짓.
따라서 두 개 비트의 AND 연산 결과를 보면 T AND T = T, T AND F = F, F AND T = F, F AND F = F 와 같다. 

OR : 둘 이상의 비트일 때 사용 가능한 연산으로 OR 연산을 적용하는 비트 중 하나라도 참이면 결과가 참이다.
따라서 두 개 비트의 OR 연산 결과를 보면 T OR T = T, T OR F = T, F OR T = T, F OR F = F 와 같다. 

XOR : eXclusive OR로서 첫 번째 비트와 두 번째 비트가 다른 경우에만 참이 된다.
따라서 두 개 비트의 XOR 연산 결과를 보면 T XOR T = F, T XOR F = T, F XOR T= T, F XOR F = F 와 같다.

 

위  네 연산자 중 NOT, AND, OR은 기본 연산자 이고, XOR 연산자는 합성 연산자이다. 합성 연산자라는 것은 다른 기본 연산들을 사용해서 XOR 연산을 만들 수 있다는 의미이다. 예를 들어, A XOR B 는 (A OR B) AND (NOT(A AND B))와 같다. 

 

드모르간의 법칙

어렸을 때 학교에서 배웠던 것만 같은 법칙. 이름은 기억 나는데 내용이 기억나지 않았는데, 내용을 봐도 기억이 안나네. 언제 배운거지..?! 집합과 명제 배울 때 배웠을 것만 같은데 새롭다. 드모르간의 법칙은 a AND b 연산은 NOT(NOT A OR NOT B) 연산과 같다는 법칙이다. 

 

이 법칙이 중요한 이유는 NOT을 충분히 사용하면 AND 연산을 OR 연산으로 대체하거나, OR 연산을 AND 연산으로 대체할 수 있기 때문이다 ! 입력 자체가 부정인 경우, 예를 들어 배가 고프다, 돈이 없다 와 같은 긍정적인 논리(정논리)가 아닌, NOT 배가 고프다, NOT 돈이 없다 와 같은 부정적인 논리(부논리)를 사용하는 경우에 드모르간의 법칙을 이용하면 최소의 연산을 통해 결과를 얻을 수 있다. 

 

입이 심심하거나(OR) 졸리면, 껌을 씹는다 라는 논리를 사용해서 진리표를 만들어 보자.

입이 심심하다	졸리다	껌을 씹는다
T	T	T
T	F	T
F	T	T
F	F	F

이번에는 입이 심심하지 않고(AND) 졸리지 않으면, 껌을 씹지 않는다는 논리를 사용해서 진리표를 만들어 보자.

NOT 입이 심심하다	NOT 졸리다	NOT 껌을 씹는다
F	F	F
F	T	F
T	F	F
T	T	T

이때 이 진리표를 계산 하기 위해서 NOT(NOT 입이 심심하다 AND NOT 졸리다)= (NOT NOT 입이 심심하다) OR (NOT NOT 졸리다)와 같이 연쇄적인 계산을 해야 하지만, 드모르간의 법칙을 사용해서 이를 입이 심심하다 OR 졸리다 로 간단하게 연산할 수 있다. 위 진리표의 결과에 NOT을 붙이면 아래 진리표의 결과가 된다! 

 

 

 

 

---

 

출처: 스타인하트조너선 . (2022). 한 권으로 읽는 컴퓨터 구조와 프로그래밍. 책만.

한 권으로 읽는 컴퓨터 구조와 프로그래밍 - YES24