드 모르간의 법칙 (Link) 에 대해 알아볼 것이다.
중학교 1학년, 고등학교 1학년 집합과 명제 단원에서 줄창 다루는 탓에 이미 많은 학생들이 익숙하다고는 하는데 True, False로 바꿔놓으니까 모르겠다는 사람들이 있어서 글을 쓴다.

조건들의 검사 결과들을 나타내는 원소들을 모두 가진 전체 집합 U를 가정한다.
조건 p를 참으로 만드는 원소들을 포함한 집합을 집합 A로, 조건 q를 참으로 만드는 원소들을 포함한 집합을 집합 B로 가정한다.
참고로 p를 거짓으로 만드는 원소들은 ~p (not p) 조건을 참으로 만드는 것이므로 집합 A의 여집합으로 나타낼 수 있으며 B의 경우도 마찬가지다.

벤 다이어그램으로 드 모르간 법칙을 나타낸 사진이다. 색칠 공부한다고 생각하면서 하나씩 알아보면 금방 와닿을 것이다.

이를 True, False (bool 대수)로 표현해보자.

p? 라는 질문에 True 결과를 뱉는 원소들이 집합 A에 속하고, q? 라는 질문에 True 결과를 뱉는 원소들이 집합 B에 속한다.
반대로 p?에 False 인 원소들은 A의 여집합에 속할 것이고, q?에 False 인 원소들은 B의 여집합에 속할 것이다.
즉 not p?에 True 인 원소들이 A의 여집합으로, not q?에 True인 원소들이 B의 여집합으로 표현된다.

또한 p? and q? 에 True인 원소는 A∩B 에 속할 것이고, p? or q? 에 True인 원소는 A∪B 에 속할 것이다.

이제 복합적인 연산으로 not (p? or q?) 에 대해 알아보자.
p? or q?가 A∪B로 표현되는 것을 보았고 not 은 여집합으로 표현된다는 것을 보았다. 따라서 not (p? or q?)는 (A∪B)의 여집합에 해당된다. 위 사진에서 보면 A 여집합과 B 여집합의 교집합으로 표현되는 것도 알 수 있다. 이를 다시 옮겨적으면 not p? and not q? 가 된다.

not (p? and q?)에 대해서도 똑같다. not p? or not q? 로 쓸 수 있을 것이다.

부정의 부정, 즉 이중 부정의 경우로 표현하면 복잡한 식이 간단해지기도 한다.
이중 부정은 조건식의 결과에 전혀 영향을 주지 않는다. 참의 부정은 거짓이고 거짓의 부정은 참이므로 참의 부정의 부정은 참이고 거짓의 부정의 부정은 거짓이다. 따라서 검사 결과에 전혀 영향을 주지 않으므로 not not 연산을 이용해서 수식을 수정할 수 있을 것이다.
예를 들어, not p? and not q? 라는 검사가 있다고 하자. 이 검사에 not not 연산을 덧붙이면 not( not ( not p? and not q? ) ) 와 같다.
안쪽의 not을 드모르간 법칙을 사용해서 바꿔쓰면 not( (not( not p?)) or (not( not q?)) ) 가 된다.
not( not p?)는 p? 와 같고, not( not q?)는 q? 와 같다. 따라서 위 수식은 다시 not( p? and q?)로 바꿔쓸 수 있다. 되돌아보니 드모르간 법칙을 이용해 역으로 묶어내는 것과 동일한 결과가 나왔다.

주어진 숫자가 양수인가? 소수인가? 와 같이 True, False만을 내뱉는 어떤 질문들, 함수들(predicate)을 가지고 연산하다보면 not 연산들을 적절히 이용해서 수식을 간편히 바꿀 수 있는 경우가 많다.
혹은 제공되는 함수가 [양수인가?] 만을 검사할 수 있는데 음수들을 다루는 어떤 프로그램을 이용해야할 경우도 있다.
드 모르간 법칙을 이용해서 수식을 자유자재로 수정하다보면 논리 오류들을 찾아내기 쉬워질 수 있으니 익숙해지는 것이 좋다.