불 대수

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

정의[편집]

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

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

불 대수는 또한 환론으로도 정의할 수 있다. 불 대수 (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)
0 \bot
1 \top
-x \lnot x

[편집]

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

임의의 집합 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\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이다.

성질[편집]

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

x\implies y=\lnot x\lor y

이다.

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

  • 집합으로서, \operatorname{Stone}(B)B 위의 모든 초필터(영어: ultrafilter)의 집합이다. 이는 불 대수 준동형사상 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세기 중반에 논리학을 형식화하기 위하여 도입하였다.

참고 문헌[편집]

바깥 고리[편집]

같이 보기[편집]