불 대수

출처 : https://terms.naver.com/entry.nhn?docId=816620&cid=42344&categoryId=42344

불 대수 [ Boolean algebra ]

 

영국의 수학자 G. Boole에 의해서 창시된 논리 수학. 논리 대수를 사용한 연산 과정이 정의되어 있는 대수계이다. 논리 곱(AND), 논리합(OR), 부정(NOT), IF-THEN 등과 같은 논리 연산자(operator)를 사용함으로써 수학적인 연산이 가능하다. 컴퓨터 등에 사용되는 전자 회로 설계에 응용되고 있다. [네이버 지식백과] 불 대수 [Boolean algebra] (컴퓨터인터넷IT용어대사전, 2011. 1. 20., 전산용어사전편찬위원회)

영국의 수학자 조지 불(George Boole)이 19세기 중엽에 창안한 대수의 한 형식. 컴퓨터 동작의 기초가 된다. 불 대수는 x나 y의 수치적 상관관계를 다루지 않고 논리적 상관관계를 다루는데, 이것은 연산의 종류와 변수들이 참인가 거짓인가에 따라서 논리적 명제들이 참 아니면 거짓이라는 논리에 바탕을 두고 있다. 불 대수의 2가지 중요한 측면은 ㉠변수들을 참 또는 거짓의 단지 두 값 중의 하나로 한정할 수 있고, ㉡이들 변수 간의 상관관계를 논리곱(AND), 논리합(OR), 부정(NOT) 등의 연산자로 논리적으로 나타낼 수 있다는 것이다. 불 대수의 이 2가지 측면은 디지털 계산에 사용되는 전자 회로에 응용될 수 있으므로 정보를 처리하고 문제를 해결하는 데 사용된다. 예를 들면, 참과 거짓은 전압의 유무에 의해 쉽게 컴퓨터 고유 언어의 2진수 1(참)과 0(거짓)으로 나타낼 수 있다. 또한 불 논리는 ‘만일 A가 참이고 B가 참이면 결과는 언제나 참이다.’를 의미하는 ‘A AND B＝true’와 같은 명제에 바탕을 두고 있다. 이러한 논리는 컴퓨터 회로에 논리 게이트로 설계해 놓을 수 있다. 논리 게이트는 비트 1과 비트 0이 불 논리에 일치하는 결과(출력)를 생성하도록 전기의 흐름을 제어한다. 하나의 컴퓨터 내에 AND, OR, NOT이나 기타 불 연산자를 나타내는 논리 게이트를 결합할 수 있으며, 하나의 논리 게이트 출력이 다른 논리 게이트 입력으로 투입되어 최종 결과가 두 수의 합과 같은 의미 있는 데이터가 되도록 할 수 있다. [네이버 지식백과] 불 대수 [Boolean algebra, -代數] (IT용어사전, 한국정보통신기술협회)

요약 )현대수학에 속하는 대수학의 한 분과로, G.불이 논리계산을 형식화하여 도입한 대수계이다. 교환법칙, 분배법칙, 흡수법칙의 속항등식 및 가보속 ·분배속을 만족하는 것을 말한다. 두 가지의 2항연산 ∩(논리곱)과 ∪(논리합)에 관하여 다음과 같이 ① 교환법칙 ② 결합법칙 ③ 흡수법칙을 만족하는 것을 속(束)이라 하고, ①∼③의 등식은 속항등식이라 한다. ① x∩y=y∩x, x∪y=y∪x ② x∩(y∩z)=(x∩y)∩z x∪(y∪z)=(x∪y)∪z ③ x∩(x∪y)=x, x∪(x∩y)=x 멱등법칙 x∩x=x, x∪x=x는 흡수법칙으로부터 유도된다. 속의 원소로서 0(최소단위 또는 零元) 및 1(최대단위 또는 單位元)이 존재할 때 x∩y=0이고 x∪y=1을 만족하는 원소 x,y를 서로 상보적이라 하며, 한쪽을 다른쪽의 보원(또는 否定)이라 한다. x의 보원을 x'로 나타내는 경우가 많다. 속의 임의의 원소에 대하여 그 보원이 속 안에 적어도 하나 있을 때 가보적(可補的)이라 하며, 그 속을 가보속(可補束)이라 한다. 또, 분배법칙 x∩(y∪z)=(x∩y)∪(x∩z) x∪(y∩z)=(x∪y)∩(x∪z) 를 만족할 때 분배적이라 하고, 그 속을 분배속이라 한다. 이들 ①∼③의 속항등식 및 가보속 ·분배속의 모든 것을 만족시키는 것이 가보분배속(可補分配束, 불束) 또는 불대수이며, 또 그 연구영역도 같이 불대수라고 한다. 쌍대성이 성립하므로 한쪽의 성질을 증명하면, 이것과 쌍대인 다른쪽의 성질도 동시에 증명한 셈이 된다. 또 0, 1인 2수의 대수이므로 2진법에 적용시킬 수 있다. 더욱 집합론의 논리곱 ·논리합 ·부정에 각각 and, or, not를 대응시키면 불대수의 또 하나의 모델로서 논리연산의 체계가 성립한다. [네이버 지식백과] 불대수 [Boolean algebra] (두산백과)

불 대수는 논리학의 연산인 논리합 , 논리곱 , 부정  등이 만족하는 관계를 추상화한 대수 구조로 영국 수학자 불(Boole, G. ; 1815~1864)의 이름을 땄다.

불 대수의 정의 과 이라고 하는 원소들을 가지는 집합에 대해, 다음 성질들을 만족하는 두 이항연산 , 과 단항연산 이 있을 때, 불 대수라고 한다. A1.  A2.  A3.  A4.  A5.  O1.  O2.  O3.  O4.  O5.  D1.  D2.  D3.  D4.  N1.  N2.  N3.  N4.  N5.  DM1.  DM2.  이들 공리에는 불필요한(redundant) 공리들이 섞여 있다. 예를 들어, 마지막 두 공리를 드모르간 공리라고 하는데, 이들 공리가 있으면 O1부터 O5까지의 공리는 A1부터 A5까지의 공리로부터 자연스럽게 나온다. 실제로 O4와 같은 공리는 다음과 같이 유도할 수 있다.   따라서 엄밀히 말하면 , , 만 있으면 와 을 정의할 수 있고, 이들과 관련된 성질을 모두 증명할 수 있다. 표준 논리학에서 논리합, 논리곱, 부정, 항진명제, 모순명제는 불 대수의 기본 공리들을 만족한다. [네이버 지식백과] 불 대수 (수학백과, 2015.5)

멱집합과 불 대수 집합 의 모든 부분집합을 모은 멱집합(power set) 는 다음 연산에 의해 불 대수 구조를 가진다.  : 교집합 연산   : 합집합 연산   : 여집합 연산   : 공집합   : 전체집합  한편 2원소 집합 에 줄 수 있는 불 대수 구조는 유일하다. 이때  역시 항별 연산에 의해 불 대수 구조를 가진다. 예를 들어, 에서   이다. 사실 이러한 대수 구조는 의 멱집합 불 대수 구조와 같다. 에 대해 이면 로 정의하고 이면 으로 정의한 의 원소 을 대응할 수 있다. 예를 들어, 의 부분집합 은 에 대응한다. 이런 대응에 의해 두 불 대수 구조가 동일하다. 이를테면 (1)은   로 해석할 수 있다. 일반적으로 유한 불 대수는 멱집합 불 대수와 동형이라는 스톤(M. H. Stone) 표현정리가 알려져 있다. [네이버 지식백과] 불 대수 (수학백과, 2015.5)

부분순서집합과 불 대수 불 대수가 있으면 다음에 의해 부분순서 관계를 정의할 수 있다.   이때 이면 도 성립한다. 특히 이 항상 성립한다. 는 자명하고, 이 관계 가 추이성(transitivity)을 만족한다는 사실은 다음과 같이 보인다. 이고, 라고 하자. 이때 를 보여야 한다. 가정에 의해 이고 이다.   이므로 추이성을 보일 수 있다. 멱집합 불 대수인 경우 이 부분순서 관계는 집합에서의 '포함 관계'와 일치한다. [네이버 지식백과] 불 대수 (수학백과, 2015.5)

불 환과 불 대수 덧셈과 곱셈을 가지는 환(ring)이 모든 에 대해 를 만족하면 '불 환'(Boolean ring)이라고 한다. 불 환으로부터 항상 불 대수를 만들 수 있다.  : 를 로 정의한다.  : 를 대칭차 연산(symmetric difference) 로 정의한다.  : 는 로 정의한다.  : 덧셈의 항등원  : 곱셈의 항등원 예를 들어, 임을 보이는 것은 곱셈의 교환법칙을 보이는 것과 같다. 그런데 불 환에서는   이므로 , 즉 가 성립한다. 특히 인 경우 이 성립해야 하므로 이다. 따라서 가 성립하므로 교환법칙이 항상 성립한다. 역으로 불 대수로부터   라고 정의하면 불 환 구조를 가진다. 예를 들어, 임을 쉽게 알 수 있다. [네이버 지식백과] 불 대수 (수학백과, 2015.5)

논리합 두 명제 , 에 대해 ' 또는 이다.' 혹은 ' or '라는 합성명제를 논리합이라고 하며, 기호로   와 같이 나타낸다. 두 명제의 논리합은 문장의 의미가 통하든 통하지 않든  나  중 어느 하나가 참이면 참인 명제이다. [네이버 지식백과] 논리합 (수학백과, 2015.5)

보기 1 가 '는 무리수이다.'라는 명제이고 가 '은 유리수이다.'라는 명제라고 하면 는 '는 무리수이거나 은 유리수이다.'라는 명제이다. 이때 는 참인 명제이고 는 거짓인 명제이므로 는 참인 명제이다. 보기 2 '소수는 홀수이거나 이다.'라는 합성명제는 참인 명제이다. '소수는 홀수이다.'라는 명제와 '이다.'라는 명제 사이에는 특별한 관계가 없지만, 이 논리합은 어엿한 명제다. 보기 3 '또는(or)'을 포함하는 문장이라고 해서 모두 논리합인 것은 아니다. 예를 들어 '커피에 크림을 넣는다.'와 '커피에 우유를 넣는다.' 및 '커피에 크림이나 우유를 넣는다.'라는 문장들은 모두 명제가 아니다. 따라서 이런 문장은 논리학이나 수학에서 다룰 필요가 없다. [네이버 지식백과] 논리합 (수학백과, 2015.5)

논리합의 성질 두 명제 가 동치이면   와 같이 나타낸다.  ~ 는 항진명제이며 배중률이라 한다. 논리합에 대하여 다음 두 명제들은 각각 동치이다.   교환법칙:  결합법칙:  드모르간의 법칙: ~  ~ ~