왜 부울대수인가 — 세 가지 얼굴을 가진 하나의 구조

3편에서 명제 논리(참/거짓, AND/OR/NOT)를, 6편에서 집합 연산(교집합/합집합/여집합)을 배웠다. 두 단원을 나란히 놓고 보면 신기하게도 규칙이 서로 대응된다 — 드모르간 법칙이 명제에도, 집합에도 똑같이 존재했다. 부울대수(Boolean algebra, 영국 수학자 George Boole의 이름을 딴 대수 체계)는 이 공통 구조를 명제·집합 중 하나에 얽매이지 않고 추상적인 대수 법칙 자체로 정리한 것이다.

쉽게 말하면: 부울대수는 “참·거짓”이든 “포함·배제”든 “전류 흐름·차단”이든, 두 가지 상태와 AND/OR/NOT에 대응하는 연산만 있으면 항상 성립하는 공통 계산 규칙 모음이다.

이 공통 구조 덕분에 부울대수의 법칙 하나를 증명해 두면, 명제 논리·집합론·논리회로(17편) 세 분야에 동시에 적용할 수 있다. 이 편에서는 표기를 논리식 기준(연산자 AND는 곱셈처럼 이어 쓰거나 $\cdot$, OR는 $+$, NOT은 윗줄 $\overline{\ \ }$ 또는 프라임 기호 ')으로 통일해 다룬다.

부울대수의 원소와 기본 연산

부울대수는 원소가 $0$과 $1$ 두 개뿐인 집합 $B=\{0,1\}$ 위에서, 세 가지 연산을 정의한 대수 구조다.

• 곱(AND, 논리곱): $x \cdot y$ 또는 $xy$로 표기. 두 값이 모두 $1$일 때만 결과가 $1$이다.
• 합(OR, 논리합): $x + y$로 표기. 두 값 중 하나라도 $1$이면 결과가 $1$이다.
• 여(NOT, 논리부정, complement): $\overline{x}$ 또는 $x'$로 표기. $0$과 $1$을 서로 뒤바꾼다.

이 연산들의 결과를 표로 정리하면 다음과 같다(3편의 진리표와 동일한 규칙이다).

부울대수의 공리

공리(axiom)는 증명 없이 참으로 받아들이는 가장 기본적인 규칙이다. 부울대수의 공리는 다음과 같다(여기서 $0$은 AND의 항등원, $1$은 OR의 항등원 역할을 한다는 의미를 함께 담고 있다).

• 항등원 법칙은 “곱하기 1은 그대로, 더하기 0은 그대로”라는 뜻으로, 일반 산술의 곱하기 1·더하기 0과 똑같은 역할을 한다.
• 영원 법칙은 “곱하기 0은 무조건 0, 더하기 1은 무조건 1”이라는 뜻이며, 일반 산술에서는 곱하기 0만 있고 “더하기 1이 무조건 1”이라는 규칙은 없다는 점이 부울대수만의 독특함이다.
• 보원 법칙은 어떤 값과 그 부정을 AND로 묶으면 항상 거짓(0), OR로 묶으면 항상 참(1)이 된다는 뜻이다 — “비가 온다”와 “비가 오지 않는다”를 동시에 만족(AND)할 수는 없고(모순律), 둘 중 하나는 항상 참(OR)이라는(배중률) 논리적 직관과 정확히 대응된다.
• 분배 법칙의 OR형 $x+(y \cdot z) = (x+y)\cdot(x+z)$는 일반 산술(덧셈이 곱셈에 분배)과 정반대 방향(곱셈이 덧셈에 분배)도 성립한다는 점이 부울대수의 특이한 지점이다. 일반 산술에서는 $x+(y \cdot z) \neq (x+y)(x+z)$가 보통이지만, 부울대수의 세계($0,1$만 있는 세계)에서는 이것도 항상 성립한다.

공리로부터 유도되는 정리들

공리를 조합해 증명할 수 있는 추가 법칙들이 있다. 독학사 문제에서 “다음 단순화에 사용된 법칙의 이름은?”을 묻는 문항의 절반 이상이 이 정리들에서 나온다.

• 흡수 법칙은 $x$가 이미 있는데 $x$와 관련된 항을 더 붙여도 결과가 그냥 $x$로 “흡수”된다는 뜻이다. 예를 들어 “비가 온다 AND (비가 온다 OR 바람이 분다)“는 결국 “비가 온다”와 같은 뜻이다 — 뒤 조건이 참·거짓 어느 쪽이든 앞의 “비가 온다”가 이미 전체를 결정하기 때문이다.
• 드모르간 법칙은 3편(명제 논리)과 6편(집합)에서 이미 다룬 바로 그 법칙이며, 부울대수에서도 형태만 기호를 바꿔 그대로 성립한다. “AND의 부정은 각각 부정한 뒤 OR로, OR의 부정은 각각 부정한 뒤 AND로” 바뀐다고 외우면 세 분야(명제·집합·부울대수) 모두에 그대로 적용된다.

논리식 단순화 — 법칙 이름을 줄마다 적으며 풀기

쉽게 말하면: 복잡한 논리식을 공리·정리를 하나씩 적용해 더 짧은 식으로 바꾸는 것이 단순화다. 시험에서는 답뿐 아니라 “어느 줄에서 어느 법칙을 썼는지”까지 요구한다.

예제 1. $F = x \cdot y + x \cdot y'$를 단순화하라.

• 사용한 법칙: 분배 법칙(AND형, $x \cdot y + x \cdot z = x \cdot (y+z)$의 역방향 적용). 공통 인수 $x$를 밖으로 묶어냈다.

• 사용한 법칙: 보원 법칙(OR형, $y+y'=1$).

• 사용한 법칙: 항등원 법칙(AND형, $x \cdot 1 = x$).

따라서 $F = x \cdot y + x \cdot y' = x$로 완전히 단순화된다.

검산. 진리표로 원래 식과 결과를 대조한다.

네 가지 $x, y$ 조합 모두에서 원래 식과 단순화 결과의 값이 완전히 일치하므로, 단순화가 올바르다는 것이 검증된다.

예제 2. $F = x + x \cdot y$를 단순화하라.

• 사용한 법칙: 흡수 법칙(OR형, $x + xy = x$)을 한 번에 바로 적용한다.

검산. $x=0$일 때 좌변은 $0 + 0 \cdot y = 0$, 우변은 $0$으로 일치한다. $x=1$일 때 좌변은 $1 + 1 \cdot y = 1 + y$이고 영원 법칙(OR형, $1+y=1$)에 의해 $1$, 우변도 $1$로 일치한다.

예제 3 (드모르간 적용). $F = \overline{x \cdot (y+z)}$를 드모르간 법칙과 분배 법칙만으로 AND·OR·NOT이 최대한 $x, y, z$ 각각에 직접 걸리는 형태로 바꿔라.

• 사용한 법칙: 드모르간 법칙(AND형, $\overline{a \cdot b} = \overline{a} + \overline{b}$, 여기서 $a=x$, $b=y+z$).

• 사용한 법칙: 드모르간 법칙(OR형, $\overline{y+z} = \overline{y} \cdot \overline{z}$)을 안쪽 항에 한 번 더 적용.

따라서 $F = \overline{x \cdot (y+z)} = \overline{x} + \overline{y}\,\overline{z}$로 정리된다. 이 결과는 부정 기호가 $x$, $y$, $z$ 각각에 직접 걸려 있어, 회로로 구현할 때 NOT 게이트를 각 입력 신호 하나씩에만 붙이면 되는 형태다(17편에서 실제 게이트 구성으로 다시 다룬다).

부울대수 · 명제 논리 · 집합 대응표

세 분야가 같은 구조를 공유한다는 것을 표로 정리하면 다음과 같다. 이 대응을 알아두면 한 분야에서 외운 법칙을 다른 두 분야에도 그대로 옮겨 쓸 수 있다.

자주 틀리는 점

• 분배 법칙 OR형을 빠뜨리는 실수. $x+(y \cdot z) = (x+y)(x+z)$는 일반 산술 직관과 어긋나서 시험에서 가장 많이 틀리는 법칙이다. 곱셈이 덧셈에 분배되는 것뿐 아니라, 부울대수에서는 덧셈도 곱셈에 분배된다는 것을 기억해야 한다.
• 법칙 이름을 서로 혼동. 흡수 법칙과 멱등 법칙을 헷갈리는 경우가 많다. 멱등 법칙은 같은 변수끼리($x \cdot x = x$)만 성립하는 규칙이고, 흡수 법칙은 서로 다른 항이 섞인 식($x + xy = x$)에서 한쪽이 다른 쪽을 통째로 흡수하는 규칙이다.
• 단순화 과정에서 사용한 법칙을 적지 않고 답만 쓰는 경우. 독학사는 서술형 대비 수준의 답안을 요구하므로, 답이 맞아도 과정과 법칙 이름이 없으면 감점 대상이다.
• 드모르간 법칙을 한 번만 적용하고 끝내는 경우. 예제 3처럼 괄호 안에 다시 OR나 AND가 중첩되어 있으면, 바깥쪽과 안쪽에 드모르간 법칙을 각각 적용해야 완전히 풀린다.

핵심 정리

• 부울대수는 $\{0,1\}$ 위에서 AND·OR·NOT을 정의한 대수 구조이며, 명제 논리·집합론과 동일한 법칙 구조를 공유한다.
• 항등원·영원·멱등·보원·교환·결합·분배 법칙이 공리이고, 흡수·이중부정·드모르간 법칙은 공리로부터 유도되는 정리다.
• 논리식 단순화는 매 단계마다 사용한 법칙 이름을 명시하며 진행하고, 결과는 진리표로 원래 식과 대조해 검산한다.
• 부울대수의 AND는 명제의 AND·집합의 교집합에, OR는 명제의 OR·집합의 합집합에, NOT은 명제의 부정·집합의 여집합에 대응한다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제  — 독학사 2단계 이산수학 출제기준과 부울대수 단원 범위 확인