불 대수

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

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

정의[편집]

불 대수 여원 분배 격자이다. 즉, 다음 조건을 만족시키는 대수 구조이다.

  • 격자이다. 즉, 다음이 성립한다.
    • (멱등법칙)
    • (교환법칙) ,
    • (결합법칙) ,
  • 유계 격자이다. 즉, 다음이 성립한다.
    • (흡수법칙) , , ,
  • 분배 격자이다. 즉, 다음이 성립한다.
    • (분배법칙) ,
  • 여원 격자이다. 즉, 다음이 성립한다.
    • ,

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

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

  • 모든 에 대하여, 이다.

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

가환환 격자 해석
논리곱
배타적 논리합
논리합
거짓
부정

[편집]

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

임의의 집합 멱집합 은 크기가 인 불 대수를 이룬다. 반대로, 모든 유한 불 대수는 어떤 유한 집합의 멱집합의 불 대수와 동형이다. 특히, 공집합의 멱집합 은 가장 작은 불 대수이며, 또한 인 유일한 불 대수이다.

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

로 정의하자. 만약 이거나 이라면, 이는 둘 다 불 대수를 이룬다. 예를 들어, 일 경우, 는 크기가 인 불 대수이며, 따라서 멱집합과 동형일 수 없다.

자유 불 대수[편집]

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

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

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

만약 가 유한할 경우, 자유 불 대수의 크기는 이며, 만약 가 무한할 경우 자유 불 대수의 크기는 이다.

성질[편집]

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

이다.

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

  • 집합으로서, 위의 모든 극대 필터의 집합이다. 이는 불 대수 준동형사상 의 집합과 표준적으로 일대일 대응한다. (는 크기가 2인 유일한 불 대수).
  • 기저이다 .

또한, 불 대수의 준동형사상 은 스톤 대수 사이의 연속함수 를 이루며, 그 역 또한 성립한다. 범주론적으로, 불 대수의 범주 는 스톤 대수와 그 사이의 연속함수들의 범주 반대 범주동치이다.

응용[편집]

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

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

역사[편집]

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

참고 문헌[편집]

바깥 고리[편집]

같이 보기[편집]