불 대수

순서론과 추상대수학, 논리학에서 불 대수(Boole代數, 영어: Boolean algebra)는 고전 명제 논리의 명제의 격자와 같은 성질을 갖는 격자이다. 즉, 논리적 공리들을 만족시키는 논리합과 논리곱 및 부정의 연산이 정의된 대수 구조이다.

정의

불 대수의 개념은 다양하게 정의할 수 있으며, 이 정의들은 서로 동치이다.

• 불 대수는 특정 조건을 만족시키는 유계 격자(또는 직교 여원 격자 또는 헤이팅 대수)로 여길 수 있다.
• 불 대수는 특정 조건을 만족시키는 가환환으로 여길 수 있다.
• 불 대수의 범주는 스톤 공간(Stone空間, 영어: Stone space)이라는 특정 위상 공간의 범주의 반대 범주이다. 이를 통해, 불 대수를 특정 위상 공간 속의 특정 집합족으로 여길 수 있다.

직교 여원 격자를 통한 정의

직교 여원 격자에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 직교 여원 격자를 불 대수라고 한다.

• 분배 격자이다.
• 임의의 원소 $x\in L$에 대하여, $c\land x=\bot$이며 $c\lor x=\top$인 $c\in L$가 유일하게 존재한다. (이는 물론 $\lnot x$이다.)
• (엘칸 법칙 영어: Elkan’s law) 임의의 $x,y\in L$에 대하여, $\lnot (a\land \lnot b)=b\lor \lnot a\land \lnot b$
• 직교모듈러 격자이며, 임의의 원소 $x\in L\setminus \{\bot \}$에 대하여, 다음 세 조건들을 만족시키는 함수 $s\colon L\to \{0,1\}$가 존재한다.
  • $s(\top )=s(x)=1$
  • 임의의 $a,b\in L$에 대하여, $s(a\lor b)\leq \max\{s(a),s(b)\}$
  • 임의의 $a,b\in L$에 대하여, $a\leq \lnot b$라면 $s(a\lor b)=\max\{s(a),s(b)\}$

불 대수의 준동형은 여원과 $\top$ 및 $\bot$을 보존시키는 격자 준동형이다. 불 대수의 정의는 대수적이므로, 불 대수의 모임은 대수 구조 다양체를 이룬다.

유계 격자를 통한 정의

유계 격자 $L$에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 격자를 불 대수라고 한다.

• 모듈러 격자이며, 임의의 $x\in L$에 대하여, $x\land c=\bot$이자 $x\lor c=\top$인 원소 $c\in L$가 유일하게 존재한다.
• 분배 격자이며, 임의의 $x\in L$에 대하여, $x\land c=\bot$이자 $x\lor c=\top$인 원소 $c\in L$가 적어도 하나 이상 존재한다.
• 임의의 $x\in L$에 대하여, $x\land c=\bot$이자 $x\lor c=\top$인 원소 $c\in L$가 유일하게 존재하며, 또한 $\textstyle x=\bigvee A$인 $A\subseteq \min(X\setminus \{\bot \})$가 존재한다.

여기서 $\min(X\setminus \{\bot \})$는 부분 순서 집합 $X\setminus \{\bot \}$의 극소 원소들의 집합이다.

헤이팅 대수를 통한 정의

헤이팅 대수 $H$에 대하여,

$\lnot x=(x\implies \bot )$

를 정의하자. 그렇다면 다음 조건들이 서로 동치이며, 이를 만족시키는 헤이팅 대수를 불 대수라고 한다.

• (대합) $\lnot$은 대합이다. 즉, 임의의 $x\in H$에 대하여, $\lnot \lnot x=x$이다.
• (배중률) 모든 원소 $x\in H$에 대하여, $x\lor \lnot x=\top$이다.

이 경우, $(H,\lnot )$은 직교 여원 격자를 이룬다.

환론적 정의

(단위원을 갖는) 환 $R$에 대하여 다음 두 조건이 서로 동치이며, 이를 만족시키는 환을 불 대수라고 한다.

• 모든 원소가 멱등원이다. 즉, 모든 $x\in B$에 대하여, $x^{2}=x$이다.^{:39, Definition 1}
• $R$는 유한체 $\mathbb {F} _{2}$의 직접곱 $\mathbb {F} _{2}^{\times \kappa }$의 부분환과 동형이다 ($\kappa$는 임의의 기수).

특히, 자명환은 불 대수이다. (둘째 정의에서 이는 $\kappa =0$에 해당한다.)

불 대수 준동형은 두 불 대수 사이의 환 준동형이다.

위상수학적 정의

스톤 공간(영어: Stone space)은 콤팩트 완전 분리 하우스도르프 공간이다. 스톤 공간과 연속 함수의 범주를 $\operatorname {Stone}$이라고 쓰자.

스톤 공간의 열린닫힌집합들의 족은 유계 격자를 이룬다. 스톤 공간의 열린닫힌집합들의 족과 동형인 유계 격자를 불 대수라고 한다.

열린닫힌집합의 연속 함수 아래의 원상은 열린닫힌집합이다. 따라서, 두 불 대수 $B$, $B'$에 대응하는 스톤 공간 $X$, $X'$가 주어졌을 때, 연속 함수 $f\colon X'\to X$는 함수

$f^{-1}\colon B\to B'$

를 유도한다. 두 불 대수 사이의 불 대수 준동형은 이와 같이 스톤 공간 사이의 연속 함수로 유도될 수 있는 함수이다.

이에 따라, 다음과 같은 범주의 동치가 존재한다.

$\operatorname {Stone} \simeq \operatorname {Bool} ^{\operatorname {op} }$

이 정의가 불 대수의 다른 정의들과 동치라는 사실은 스톤 표현 정리(영어: Stone representation theorem)라고 한다.

특히, 이 정의는 환론적 정의와 다음과 같은 관계를 갖는다. 모든 가환환에 대하여, 스펙트럼이라는 위상 공간을 대응시킬 수 있으며, 이는 가환환의 범주 $\operatorname {CRing}$의 반대 범주에서 위상 공간의 범주 $\operatorname {Top}$로 가는 함자

$\operatorname {Spec} \colon \operatorname {CRing} ^{\operatorname {op} }\to \operatorname {Top}$

를 정의한다. 만약 이 가환환이 불 대수를 이룬다면 그 스펙트럼은 스톤 공간을 이룸을 보일 수 있으며, 이는 열린닫힌집합족 함자의 역함자이다. 즉, 다음과 같은 두 함자가 존재하며, 이는 범주의 동치를 이룬다.

$\operatorname {Spec} \colon \operatorname {Bool} ^{\operatorname {op} }\to \operatorname {Stone}$

$\operatorname {Clopen} \colon \operatorname {Stone} \to \operatorname {Bool} ^{\operatorname {op} }$

불 대수의 스펙트럼은 다음과 같이 직접적으로 묘사할 수 있다. 불 대수의 극대 아이디얼은 극대 순서 아이디얼과 일치하며, 불 대수의 쌍대성에 따라 이는 극대 필터와 일대일 대응한다. 따라서, $2$가 두 개의 원소의 불 대수라면, 극대 필터들의 집합은 $\hom _{\operatorname {Bool} }(B,2)$이다. 이 위에 다음과 같은 기저로 생성되는 위상을 부여하면, 스톤 공간을 이룬다.

$\{\{{\mathcal {U}}\in \operatorname {Spec} (B)\colon b\in {\mathcal {U}}\}\}_{b\in B}$

이는 $2$에 이산 위상을 부여하고, 멱집합 ${\mathcal {P}}(B)=2^{B}$에 곱위상을 부여한 뒤, $\operatorname {Spec} (B)\subset {\mathcal {P}}(B)$에 부분 공간 위상을 부여한 것과 같다.

범주론적 정의

모든 원순서 집합은 작은 얇은 범주로 간주할 수 있다. 이 경우, 부분 순서 집합은 서로 동형인 두 대상이 항상 같은 원순서 집합이며, 헤이팅 대수는 유한 완비 범주이자 유한 쌍대 완비 범주이자 데카르트 닫힌 범주인 부분 순서 집합이다.

불 대수는 다음 조건을 만족시키는 작은 얇은 범주이다.

• 서로 동형인 두 대상은 같다.
• 유한 완비 범주이며 유한 쌍대 완비 범주이다.
• 데카르트 닫힌 범주이다.
• 임의의 두 대상 $X,Y\in {\mathcal {C}}$에 대하여, 다음과 같은 동형이 존재한다. (이들은 드 모르간 법칙을 범주론적 용어로 번역한 것이다.)

  $X\times Y\cong 0^{0^{X}\sqcup 0^{Y}}$

  $0^{X\times Y}\cong 0^{X}\sqcup 0^{Y}$

여기서 $\times$는 범주론적 곱이며, $\sqcup$는 쌍대곱이며, $0$은 시작 대상이며, $A^{B}$는 지수 대상이다.

서로 다른 정의들의 비교

불 대수의 서로 다른 정의들은 다음과 같이 대응된다.

해석	가환환	격자	직교 여원 격자	헤이팅 대수	스톤 공간 $X$의 부분 집합	범주론적 정의
논리곱	곱 $x\cdot y$	만남 $x\land y$			교집합 $x\cap y$	곱 $x\times y$
배타적 논리합	합 $x+y$	$x\land y\land c=\bot$, $(x\land y)\lor c=\top$라면, $(x\lor y)\land c$	$(x\lor y)\land \lnot (x\land y)$	$(x\lor y)\land \left((x\land y)\Rightarrow \bot \right)$	$(x\setminus y)\cup (y\setminus x)$	$(x\times 0^{y})\sqcup (y\times 0^{x})$
논리합	$x+y+xy$	이음 $x\lor y$			합집합 $x\cup y$	쌍대곱 $x\sqcup y$
거짓	덧셈 항등원 $0$	최소 원소 $\bot$			공집합 $\varnothing$	시작 대상 $0$
참	곱셈 항등원 $1$	최대 원소 $\top$			전체 집합 $X$	끝 대상 $1$
부정	$1+x$	$x\land c=\bot$, $x\lor c=\top$인 유일한 $c$	직교 여원 $\lnot x$	$x\Rightarrow \bot$	여집합 $X\setminus x$	지수 대상 $0^{x}$
함의	$1+x+xy$	$x\land c=\bot$, $x\lor c=\top$라면, $c\lor y$	$\lnot x\lor y$	$x\Rightarrow y$	$(X\setminus x)\cup y$	지수 대상 $y^{x}$

성질

순서론적 성질

다음과 같은 함의 관계가 성립한다.

				완비 격자	⇐	완비 헤이팅 대수	⇐	완비 불 대수
								⇓
				⇓		⇓		시그마 대수
								⇓
원순서 집합	⇐	부분 순서 집합	⇐	유계 격자	⇐	헤이팅 대수	⇐	불 대수

불 대수를 가환환으로 여겼을 때, 그 아이디얼은 순서 아이디얼과 일치한다.

환론적 성질

다음과 같은 함의 관계가 성립한다.

가환환 ⇐ 가환 축소환 ⇐ 가환 반원시환 ⇐ 가환 폰 노이만 정칙환 ⇐ 불 대수

임의의 불 대수 $B$는 가환환이고 표수가 2이며 (즉 모든 원소는 자신의 덧셈 역원이다) 따라서 유한체 $\mathbb {F} _{2}$ 위의 결합 대수이다.^{:39–40, Theorem 1}

증명:

가환성: 임의의 $x,y\in B$에 대하여 $0=(x+y)^{2}-(x+y)=x^{2}+y^{2}+xy+yx-x-y=xy+yx$이다.

표수 2: 위에서 $x=y=1$이라면 $0=2$이다.

(그러나 그 역은 성립하지 않는다. 예를 들어, 다항식환 $\mathbb {F} _{2}[x]$는 $x^{2}\neq x$이므로 불 대수가 아니다.)

아이디얼

불 대수의 임의의 몫환은 불 대수이다. 불 대수의 임의의 부분환은 불 대수이다.

불 대수의 스펙트럼은 스톤 공간이다. 특히, 불 대수의 모든 소 아이디얼은 극대 아이디얼이다. 불 대수 $B$의 임의의 극대 아이디얼 ${\mathfrak {p}}\in \operatorname {Spec} B$에 대한 몫환은 크기 2의 유한체이다.

$B/{\mathfrak {p}}\cong \mathbb {F} _{2}$

불 대수는 폰 노이만 정칙환이며, 따라서 그 위의 모든 가군은 평탄 가군이다.

불 대수의 모든 유한 생성 아이디얼은 주 아이디얼이다. 구체적으로

$(x,y)=(x+y+xy)$

이다.

범주론적 성질

불 대수의 모임은 대수 구조 다양체를 이루며, 따라서 그 범주는 완비 범주이자 쌍대 완비 범주이며 자유 대상을 갖는다.

예

멱집합

크기가 16=2²²인 불 대수. 이는 두 개의 생성원으로 생성되는 자유 불 대수이다.

임의의 집합 $S$의 멱집합 ${\mathcal {P}}(S)$은 크기가 $2^{|S|}$인 불 대수를 이룬다. 반대로, 모든 유한 불 대수는 어떤 유한 집합의 멱집합의 불 대수와 동형이다. 특히, 공집합의 멱집합 ${\mathcal {P}}(\varnothing )=\{\varnothing \}$은 가장 작은 불 대수이며, 또한 $\top =\bot$인 유일한 불 대수이다.

집합 $S$에 대하여, 멱집합 ${\mathcal {P}}(S)$에 대응하는 스톤 공간은 $S$의 스톤-체흐 콤팩트화이다.

멱집합과 동형이 아닌 무한 불 대수 또한 존재한다. 예를 들어, 집합 $S$ 및 기수 $\kappa$가 주어졌을 때,

${\mathcal {P}}_{\kappa }(S)=\left\{T\subset S|\kappa >\min\{|T|,|S\setminus T|\}\right\}$

로 정의하자. 만약 $\kappa =0$이거나 $\kappa \geq \aleph _{0}$이라면, 이는 둘 다 불 대수를 이룬다. 예를 들어, $|S|=\aleph _{0}$일 경우, ${\mathcal {P}}_{\aleph _{0}}(S)$는 크기가 $\aleph _{0}$인 불 대수이며, 따라서 멱집합과 동형일 수 없다.

자유 불 대수

불 대수는 대수 구조 다양체를 이루므로, 임의의 생성원의 집합에 대응하는 자유 불 대수가 존재한다.

스톤 표현 정리에 따라서, 임의의 기수 $\kappa$에 대하여, $\kappa$개의 생성원으로부터 생성되는 자유 불 대수에 대응하는 스톤 공간은

$\{0,1\}^{\kappa }$

이다. 여기서 $\{0,1\}$은 2개의 점을 가진 이산 공간이며, $\{0,1\}^{\kappa }$에는 곱 위상을 준다. 이 경우, $\alpha$번째 생성원은 튜플의 $\alpha$번째 성분이 1인 모든 원소들로 구성된 열린닫힌집합에 대응한다.

만약 $\kappa$가 유한할 경우, 자유 불 대수의 크기는 $2^{2^{\kappa }}$이며, 만약 $\kappa$가 무한할 경우 자유 불 대수의 크기는 $\kappa$이다.

사유한군

 이 부분의 본문은 사유한군입니다.

스톤 공간을 이루는 위상군은 사유한군이라고 한다.

응용

논리학

 이 부분의 본문은 명제 논리입니다.

논리학에서, 불 대수는 고전 명제 논리의 모형을 제공한다. 만약 고전 명제 논리를 직관 논리로 약화시키면, 불 대수 대신 헤이팅 대수를 사용하여야 한다.

컴퓨터 과학

불 대수는 디지털 회로 설계에 응용된다. 디지털 회로는 전압의 H(High), L(Low)만으로 정보를 연산하기 때문에, 기본적으로 조합 회로는 불 대수에 있는 논리식을 써서 나타낼 수 있다. (하지만, 플립플롭 등 순차 회로는 단순하게 하나의 논리식으로 나타낼 수 없다.) 높은 전압(H)를 1로, 낮은 전압(L)을 0으로 하는 논리 형식을 정논리, 낮은 전압 (L)을 1로, 높은 전압(H)를 0으로 하는 논리 형식을 부논리라고 한다.

역사

불 대수의 개념은 1847년에 조지 불이 논리학을 형식화하기 위하여 도입하였다. 이후 불은 1854년의 저서에서 이 개념을 추가로 설명하였다. 불은 논리곱과 배타적 논리합을 기초적 연산으로 삼았는데, 이는 오늘날에 불 대수를 가환환의 일종으로 여기는 것과 같다.

이후 윌리엄 스탠리 제번스(영어: William Stanley Jevons, 1835~1882) · 찰스 샌더스 퍼스(1839~1914) · 에른스트 슈뢰더(독일어: Ernst Schröder, 1841~1902) 등이 불의 논리 대수의 연구를 계속하였다. 제번스는 1864년의 저서에서 불이 사용한 배타적 논리합 대신 (배타적이지 않은) 논리합을 최초로 사용하였다. 이 책에서 제번스는 다음과 같이 적었다.

“	불 교수는 ‘+’ 기호를 사용하여 항들을 결합시킬 때, 이들이 서로 논리적으로 반대되는 것이라는 것을 가정합니다. 즉, 이들은 같은 대상에 모순 없이 적용되거나 결합될 수 없습니다. […] 이에 대하여 나는 이의를 제기합니다. 일상적인 접속사의 용례에서는 서로 배타적이지 않은 항들을 결합시킬 수 있습니다. […] 예를 들어, "귀족은 공작이거나 후작이거나 백작이거나 자작이거나 남작이다."라는 명제를 불 교수의 기호로 나타낸다면, 귀족이 공작이자 동시에 후작, 또는 후작이자 동시에 백작이 될 수 없습니다. 그러나 실제로는 많은 귀족들은 두 개 이상의 작위들을 소유합니다. 예를 들어, 웨일스 공은 콘월 공작이자 체스터 백작이자 렌프루 남작입니다. Professor Boole uses the symbol + to join terms together, on the understanding that they are logical contraries, which cannot be predicated of the same thing or combined together without contradiction. […] This I altogether dispute. In the ordinary use of these conjunctions, we do not necessarily join logical contraries only; […] Take, for instance, the proposition—‘A peer is either a duke, or a marquis, or an earl, or a viscount, or a baron.’ If expressed in Professor Boole’s symbols, it would be implied that a peer cannot be at once a duke and marquis, or marquis and earl. Yet many peers do possess two or more titles, and the Prince of Wales is Duke of Cornwall, Earl of Chester, Baron Renfrew, &c.	”
	— :76, §177–179

1913년 논문에서 미국의 헨리 모리스 셰퍼(영어: Henry Maurice Sheffer, 1882~1964)가 "불 대수"(영어: Boolean algebra 불리언 앨지브라^[*])라는 용어를 최초로 사용하였다.^{:278, 주석} 이 논문에서 셰퍼는 불 대수의 모든 연산을 부정논리곱으로서 정의할 수 있음을 보였다.

스톤 표현 정리는 마셜 하비 스톤이 1936년에 증명하였다.

같이 보기

• 부울 도메인
• 불 함수
• 완비 불 대수
• 드 모르간의 법칙
• 강제법
• 헤이팅 대수
• 카노 맵
• 논리 회로
• 이진 행렬
• 콰인-매클러스키 알고리즘
• 벤 다이어그램

각주

• Givant, Steven; Halmos, Paul (2009). 《Introduction to Boolean algebras》. Undergraduate Texts in Mathematics (영어). doi:10.1007/978-0-387-68436-9. ISBN 978-0-387-40293-2. ISSN 0172-6056. Zbl 1168.06001. 
• Halmos, Paul; Givant, Steven (1998). 《Logic as Algebra》. Dolciani Mathematical Expositions (영어) 21. The Mathematical Association of America. 
• Davey, B.A.; H. A. Priestley (2002). 《Introduction to lattices and order》 (영어) 2판. Cambridge University Press. doi:10.1017/CBO9780511809088. ISBN 978-0-521-78451-1. Zbl 1002.06001.  CS1 관리 - 추가 문구 (링크)
• Goncharov, Sergey (1997). 《Countable Boolean algebras and decidability》 (영어). Springer. ISBN 978-0-306-11061-0. Zbl 0912.03019. 
• Vladimirov, D. A. (2002). 《Boolean algebras in analysis》 (PDF). Mathematics and its Applications (영어) 540. Springer-Verlag. doi:10.1007/978-94-017-0936-1. ISBN 978-1-4020-0480-3. 
• Sikorski, Roman (1969). 《Boolean algebras》. Ergebnisse der Mathematik und ihrer Grenzgebiete (영어) 25 2판. Springer-Verlag. doi:10.1007/978-3-642-85820-8. ISBN 978-3-642-85822-2. MR 126393. Zbl 0087.02503. 

외부 링크

• “Boolean algebra”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Boolean ring”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Stone space”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Boolean algebra”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Boolean ring”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Stone space”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “Boolean algebra”. 《nLab》 (영어). 
• “Boolean ring”. 《nLab》 (영어). 
• “Stone space”. 《nLab》 (영어). 
• “Profinite space”. 《nLab》 (영어). 
• “Definition: Boolean algebra”. 《ProofWiki》 (영어). 
• “Definition: Boolean ring”. 《ProofWiki》 (영어). 
• “Equivalence of definitions of Boolean algebra”. 《ProofWiki》 (영어). 
• “Duality principle (Boolean algebra)”. 《ProofWiki》 (영어). 
• Tao, Terrence (2009년 1월 12일). “245B notes 4: The Stone and Loomis-Sikorski representation theorems (optional)”. 《What’s New》 (영어). 
• Yuan, Qiaochu (2010년 11월 22일). “Boolean rings, ultrafilters, and Stone’s representation theorem”. 《Annoying Precision》 (영어). 
• Pratt, Vaughan. “Boolean algebras” (영어). Stanford University. 
• Monk, J. Donald (2014년 6월 14일). “The Mathematics of Boolean Algebra”. 《Stanford Encyclopedia of Philosophy》 (영어).