불 대수

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

정의

불 대수 $(B,\land ,\lor ,\lnot ,\bot ,\top )$는 여원 분배 격자이다. 즉, 다음 조건을 만족시키는 대수 구조이다.

• $(B,\land ,\lor )$는 격자이다. 즉, 다음이 성립한다.
  • (멱등법칙) $x\land x=x\lor x=x$
  • (교환법칙) $x\land y=y\land x$, $x\lor y=y\lor x$
  • (결합법칙) $x\land (y\land z)=(x\land y)\land z$, $x\lor (y\lor z)=(x\lor y)\lor z$
• $(B,\land ,\lor ,\bot ,\top )$는 유계 격자이다. 즉, 다음이 성립한다.
  • (흡수법칙) $x\land \top =x$, $x\lor \bot =x$, $x\lor \top =\top$, $x\land \bot =\bot$
• $(B,\land ,\lor )$는 분배 격자이다. 즉, 다음이 성립한다.
  • (분배법칙) $(x\land y)\lor z=(x\land z)\lor (x\land z)$, $(x\lor y)\land z=(x\lor z)\land (x\lor z)$
• $(B,\land ,\lor ,\lnot ,\bot ,\top )$는 여원 격자이다. 즉, 다음이 성립한다.
  • $x\land \lnot x=\bot$, $x\lor \lnot x=\top$

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

불 대수는 또한 환론으로도 정의할 수 있다. 불 대수 $(B,\cdot ,+,0,1)$는 다음 성질을 만족시키는 (단위원을 갖는) 가환환이다.

• 모든 $x\in B$에 대하여, $x^{2}=x$이다.

이 정의는 격자로서의 정의와 동치이며, 환의 연산은 격자 연산과 다음과 같이 대응한다.

가환환	격자	해석
$x\cdot y$	$x\land y$	논리곱
$x+y$	$(x\lor y)\land \lnot (x\land y)$	배타적 논리합
$x+y+xy$	$x\lor y$	논리합
$0$	$\bot$	거짓
$1$	$\top$	참
$-x$	$\lnot x$	부정

예

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

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

멱집합과 동형이 아닌 무한 불 대수 또한 존재한다. 예를 들어, 집합 $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$이다.

성질

모든 불 대수는 헤이팅 대수이다. 이 경우, 헤이팅 함의 연산은

$x\implies y=\lnot x\lor y$

이다.

스톤 공간(영어: Stone space)은 콤팩트 완전분리 하우스도르프 공간이다. 스톤 표현 정리(영어: Stone representation theorem)에 따르면, 모든 불 대수는 스톤 공간의 열리고 닫힌 집합들의 격자와 동형이며, 반대로 모든 스톤 공간의 열리고 닫힌 집합들의 격자는 불 대수를 이룬다. 이 경우, 불 대수 $B$에 대응되는 스톤 공간 $\operatorname {Stone} (B)$는 다음과 같다.

• 집합으로서, $\operatorname {Stone} (B)$는 $B$ 위의 모든 극대 필터의 집합이다. 이는 불 대수 준동형사상 $B\to 2$의 집합과 표준적으로 일대일 대응한다. ($2$는 크기가 2인 유일한 불 대수).
• $\operatorname {Stone} (B)$의 기저는 $\{\{{\mathcal {F}}\in \operatorname {Stone} (B)|x\in {\mathcal {F}}\}\}_{x\in B}$이다 .

또한, 불 대수의 준동형사상 $B\to B'$은 스톤 대수 사이의 연속함수 $\operatorname {Stone} (B')\to \operatorname {Stone} (B)$를 이루며, 그 역 또한 성립한다. 범주론적으로, 불 대수의 범주 $\operatorname {BoolAlg}$는 스톤 대수와 그 사이의 연속함수들의 범주 $\operatorname {Stone}$의 반대 범주와 동치이다.

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

응용

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

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

역사

조지 불이 19세기 중반에 논리학을 형식화하기 위하여 도입하였다.

참고 문헌

• 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. 
• 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. 
• Johnstone, Peter T. (1983년 4월). 《Stone spaces》. Cambridge Studies in Advanced Mathematics (영어) 3. Cambridge University Press. ISBN 978-052123893-9. MR 0698074. Zbl 0499.54001. 
• Vladimirov, D. A. 《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. 

바깥 고리

• “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. 
• Weisstein, Eric Wolfgang. “Boolean algebra”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Boolean ring”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Pratt, Vaughan. “Boolean algebras” (영어). Stanford University. 
• Monk, J. Donald (2014년 6월 14일). “The Mathematics of Boolean Algebra”. 《Stanford Encyclopedia of Philosophy》 (영어). 
• “Boolean algebra”. 《nLab》 (영어). 
• “Boolean ring”. 《nLab》 (영어). 

같이 보기

• 헤이팅 대수
• 명제 논리