불 대수

고전 명제 논리의 모형을 이루는 격자
(스톤 표현 정리에서 넘어옴)

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

정의

편집

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

직교 여원 격자를 통한 정의

편집

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

  • 분배 격자이다.
  • 임의의 원소  에 대하여,  이며   가 유일하게 존재한다. (이는 물론  이다.)
  • (엘칸 법칙 영어: Elkan’s law) 임의의  에 대하여,  [1]
  • 직교모듈러 격자이며, 임의의 원소  에 대하여, 다음 세 조건들을 만족시키는 함수  가 존재한다.[2]
    •  
    • 임의의  에 대하여,  
    • 임의의  에 대하여,  라면  

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

유계 격자를 통한 정의

편집

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

  • 모듈러 격자이며, 임의의  에 대하여,  이자  인 원소  가 유일하게 존재한다.[3]
  • 분배 격자이며, 임의의  에 대하여,  이자  인 원소  가 적어도 하나 이상 존재한다.
  • 임의의  에 대하여,  이자  인 원소  가 유일하게 존재하며, 또한   가 존재한다.[4]

여기서  부분 순서 집합  극소 원소들의 집합이다.

헤이팅 대수를 통한 정의

편집

헤이팅 대수  에 대하여,

 

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

  • (대합)  대합이다. 즉, 임의의  에 대하여,  이다.
  • (배중률) 모든 원소  에 대하여,  이다.

이 경우,  직교 여원 격자를 이룬다.

환론적 정의

편집

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

  • 모든 원소가 멱등원이다. 즉, 모든  에 대하여,  이다.[5]:39, Definition 1
  •  유한체  직접곱  부분환과 동형이다 ( 는 임의의 기수).

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

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

위상수학적 정의

편집

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

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

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

 

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

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

 

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

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

 

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

 
 

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

 

이는  이산 위상을 부여하고, 멱집합  곱위상을 부여한 뒤,  부분 공간 위상을 부여한 것과 같다.

범주론적 정의

편집

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

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

여기서  범주론적 곱이며,  쌍대곱이며,  시작 대상이며,  지수 대상이다.

서로 다른 정의들의 비교

편집

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

해석 가환환 격자 직교 여원 격자 헤이팅 대수 스톤 공간  의 부분 집합 범주론적 정의
논리곱   만남   교집합    
배타적 논리합    ,  라면,          
논리합   이음   합집합   쌍대곱  
거짓 덧셈 항등원   최소 원소   공집합   시작 대상  
곱셈 항등원   최대 원소   전체 집합   끝 대상  
부정    ,  인 유일한   직교 여원     여집합   지수 대상  
함의    ,  라면,         지수 대상  

성질

편집

순서론적 성질

편집

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

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

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

환론적 성질

편집

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

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

임의의 불 대수  가환환이고 표수가 2이며 (즉 모든 원소는 자신의 덧셈 역원이다) 따라서 유한체   위의 결합 대수이다.[5]:39–40, Theorem 1

증명:

가환성: 임의의  에 대하여  이다.

표수 2: 위에서  이라면  이다.

(그러나 그 역은 성립하지 않는다. 예를 들어, 다항식환   이므로 불 대수가 아니다.)

아이디얼

편집

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

불 대수의 스펙트럼은 스톤 공간이다. 특히, 불 대수의 모든 소 아이디얼극대 아이디얼이다. 불 대수  의 임의의 극대 아이디얼  에 대한 몫환은 크기 2의 유한체이다.

 

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

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

 

이다.

범주론적 성질

편집

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

멱집합

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

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

집합  에 대하여, 멱집합  에 대응하는 스톤 공간은  스톤-체흐 콤팩트화이다.

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

 

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

자유 불 대수

편집

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

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

 

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

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

사유한군

편집

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

응용

편집

논리학

편집

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

컴퓨터 과학

편집

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

역사

편집

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

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

불 교수는 ‘+’ 기호를 사용하여 항들을 결합시킬 때, 이들이 서로 논리적으로 반대되는 것이라는 것을 가정합니다. 즉, 이들은 같은 대상에 모순 없이 적용되거나 결합될 수 없습니다. […] 이에 대하여 나는 이의를 제기합니다. 일상적인 접속사의 용례에서는 서로 배타적이지 않은 항들을 결합시킬 수 있습니다. […] 예를 들어, "귀족은 공작이거나 후작이거나 백작이거나 자작이거나 남작이다."라는 명제를 불 교수의 기호로 나타낸다면, 귀족이 공작이자 동시에 후작, 또는 후작이자 동시에 백작이 될 수 없습니다. 그러나 실제로는 많은 귀족들은 두 개 이상의 작위들을 소유합니다. 예를 들어, 웨일스 공은 콘월 공작이자 체스터 백작이자 렌프루 남작입니다.

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.

 
[11]:76, §177–179

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

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

같이 보기

편집

각주

편집
  1. 近藤 溢血 (こんどう みちろう) (2006). “On orthocomplemented lattices with Elkan’s law” (PDF). 《数理解析研究所講究録》 (영어) 1503: 10–16.  |저자=에 templatestyles stripmarker가 있음(위치 1) (도움말)
  2. Pták, Pavel; Pulmannová, Sylvlia (1994). “A measure-theoretic characterization of Boolean algebras among orthomodular lattices” (PDF). 《Commentationes Mathematicae Universitatis Carolinae》 (영어) 35 (1): 205–208. ISSN 0010-2628. 
  3. Bergmann, Gustav (1929). “Zur Axiomatic der Elementargeometrie”. 《Monatschrift für Mathematik und Physik》 (독일어) 36 (1): 269-284. doi:10.1007/BF02307616. ISSN 0026-9255. MR 1549684. 
  4. Birkhoff, Garrett; Ward, Morgan (1939년 7월). “A characterization of Boolean algebras”. 《Annals of Mathematics》 (영어) 40 (3): 609–610. Bibcode:1939AnMat..40..609B. doi:10.2307/1968945. JSTOR 1968945. MR 0000009. 
  5. Stone, Marshall H. (1936). “The theory of representations of Boolean algebras”. 《Transactions of the American Mathematical Society》 (영어) 40: 37–111. doi:10.2307/1989664. JSTOR 1989664. 
  6. 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. 
  7. Szabo, M. E. (1974). “A categorical characterization of Boolean algebras”. 《Algebra Universalis》 (영어) 4 (1): 192–194. doi:10.1007/BF02485724. ISSN 0002-5240. 
  8. Boole, George (1847). 《The mathematical analysis of logic, being an essay towards a calculus of deductive reasoning》 (영어). 케임브리지: MacMillan, Barclay, & MacMillan. 
  9. Boole, George (1848). “The calculus of logic”. 《Cambridge and Dublin Mathematical Journal》 (영어) 3: 183–198. 
  10. Boole, George (1954). 《An investigation of the laws of thought, on which are founded the mathematical theories of logic and probabilities》 (영어). 런던: Walton and Maberly. 
  11. Jevons, William Stanley (1864). 《Pure logic or the logic of quality apart from quantity: with remarks on Boole’s system and on the relation of logic and mathematics》 (영어). 런던: Edward Stanford. 
  12. Sheffer, Henry Maurice (1913). “A set of five independent postulates for Boolean algebras, with application to logical constants”. 《Transactions of the American Mathematical Society》 (영어) 14: 481–488. doi:10.1090/S0002-9947-1913-1500960-1. ISSN 0002-9947. JSTOR 1988701. MR 1500960. 
  13. Huntington, Edward V. (1933). “New sets of independent postulates for the algebra of logic, with special reference to Whitehead and Russell’s Principia mathematica”. 《Transactions of the American Mathematical Society》 (영어) 35 (1): 274–304. doi:10.1090/S0002-9947-1933-1501684-X. ISSN 0002-9947. MR 1501684. 

외부 링크

편집