불 대수

expanded=격자 순서론과 추상대수학, 논리학에서 **불 대수**(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언어=en * 직교모듈러 격자이며, 임의의 원소 x\in L\setminus\\{\bot\\}에 대하여, 다음 세 조건들을 만족시키는 함수 s\colon L\to\\{0,1\\}가 존재한다.언어=en ** s(\top)=s(x)=1 ** 임의의 a,b\in L에 대하여, s(a\lor b)\le\max\\{s(a),s(b)\\} ** 임의의 a,b\in L에 대하여, a\le\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가 유일하게 존재한다.언어=de * 분배 격자이며, 임의의 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\\})가 존재한다.언어=en 여기서 \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)은 콤팩트 완전 분리 하우스도르프 공간이다.언어=en 스톤 공간과 연속 함수의 범주를 \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)에 부분 공간 위상을 부여한 것과 같다.
## 범주론적 정의
모든 원순서 집합은 작은 얇은 범주로 간주할 수 있다. 이 경우, 부분 순서 집합은 서로 동형인 두 대상이 항상 같은 원순서 집합이며, 헤이팅 대수는 유한 완비 범주이자 유한 쌍대 완비 범주이자 데카르트 닫힌 범주인 부분 순서 집합이다. **불 대수**는 다음 조건을 만족시키는 작은 얇은 범주이다.언어=en * 서로 동형인 두 대상은 같다. * 유한 완비 범주이며 유한 쌍대 완비 범주이다. * 데카르트 닫힌 범주이다. * 임의의 두 대상 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는 지수 대상이다.
## 서로 다른 정의들의 비교
불 대수의 서로 다른 정의들은 다음과 같이 대응된다. {| class="wikitable" |- ! 해석 !! 가환환 !! 격자 !! 직교 여원 격자 !! 헤이팅 대수 !! 스톤 공간 X의 부분 집합 || 범주론적 정의 |- | 논리곱 || 곱 x\cdot y | colspan=3| 만남 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\times0^y)\sqcup(y\times0^x) |- | 논리합 || x+y+xy | colspan=3 | 이음 x\lor y || 합집합 x\cup y || 쌍대곱 x\sqcup y |- | 거짓 || 덧셈 항등원 0 | colspan=3 | 최소 원소 \bot || 공집합 \varnothing || 시작 대상 0 |- | 참 || 곱셈 항등원 1 | colspan=3 | 최대 원소 \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\ne x이므로 불 대수가 아니다.)
### 아이디얼
불 대수의 임의의 몫환은 불 대수이다. 불 대수의 임의의 부분환은 불 대수이다. 불 대수의 스펙트럼은 스톤 공간이다. 특히, 불 대수의 모든 소 아이디얼은 극대 아이디얼이다. 불 대수 B의 임의의 극대 아이디얼 \mathfrak p\in\operatorname{Spec}B에 대한 몫환은 크기 2의 유한체이다. :B/\mathfrak p\cong\mathbb F_2 불 대수는 폰 노이만 정칙환이며, 따라서 그 위의 모든 가군은 평탄 가군이다. 불 대수의 모든 유한 생성 아이디얼은 주 아이디얼이다. 구체적으로 :(x,y)=(x+y+xy) 이다.
## 범주론적 성질
불 대수의 모임은 대수 구조 다양체를 이루며, 따라서 그 범주는 완비 범주이자 쌍대 완비 범주이며 자유 대상을 갖는다.
# 예

## 멱집합
크기가 16=222인 불 대수. 이는 두 개의 생성원으로 생성되는 자유 불 대수이다. 임의의 집합 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\ge\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년에 조지 불이 논리학을 형식화하기 위하여 도입하였다.언어=en언어=en 이후 불은 1854년의 저서에서 이 개념을 추가로 설명하였다.언어=en 불은 논리곱과 배타적 논리합을 기초적 연산으로 삼았는데, 이는 오늘날에 불 대수를 가환환의 일종으로 여기는 것과 같다. 이후 윌리엄 스탠리 제번스(William Stanley Jevons, 1835~1882) · 찰스 샌더스 퍼스(1839~1914) · 에른스트 슈뢰더(Ernst Schröder, 1841~1902) 등이 불의 논리 대수의 연구를 계속하였다. 제번스는 1864년의 저서에서 불이 사용한 배타적 논리합 대신 (배타적이지 않은) 논리합을 최초로 사용하였다.언어=en 이 책에서 제번스는 다음과 같이 적었다. 76, §177–179 1913년 논문에서 미국의 헨리 모리스 셰퍼(Henry Maurice Sheffer, 1882~1964)가 "불 대수"(불리언 앨지브라)라는 용어를 최초로 사용하였다.언어=en언어=en278, 주석 이 논문에서 셰퍼는 불 대수의 모든 연산을 부정논리곱으로서 정의할 수 있음을 보였다. 스톤 표현 정리는 마셜 하비 스톤이 1936년에 증명하였다.언어=en