부울 대수의 기본 정의와 공리적 정의

*학부생이기에 틀릴 수 있는 부분이 있으니 잘못된 부분이 있다면 알려주시면 감사하겠습니다.

개요

---

부울 대수(Boolean algebra)는 컴퓨터나 디지털 회로를 다루는 사람들에게 필수적인 수학이다. 우리가 전자 회로를 만들 때 고려해야 될 사항은 다음과 같다.

1. 어떻게 하면 싸게 만들 수 있는가?
2. 어떻게 하면 간단하게 만들 수 있는가?
3. 어떻게 하면 위 2개의 조건을 만족하면서 우리가 원하는 성능을 낼 수 있는가?

이 모든 걸 만족시키는 물건을 만드는 건 간단하지는 않다. 하지만 우리는 부울 대수를 통해 이러한 문제들을 좀 더 쉽게 풀 수 있다. 부울 대수는 복잡한 회로가 필요할 때 이를 간단하게 만들어 주는 역할을 한다.

 

 

 

부울 대수의 기본 정의

---

부울 대수도 일반적인 수학처럼 원소(element)와 연산자(operator), 공리(axiom), 공준(postulate)으로 정의할 수 있다.

부울 대수를 정의하기 앞서 부울 대수를 이루는 기본적인 요소들에 대해 정의하겠다.

• 집합의 원소(element)들은 집합(set)을 이루는 각각의 개체들이다.
  (An element of a set is any one of the distinct objects that belong to that set)
  
  
• 집합(set)은 공통적인 성질을 가지는 원소들의 모임이다.
  (A set of elements is any collection of objects, usually having a common property)
  
  
• 만약 S가 집합이고, x와 y가 원소라면 x ∈ S는 x는 S의 원소이다라는 것을 나타내며 y ∉ S는 y는 S의 원소가 아니라는 것을 나타낸다.
  (If S is a set, and x and y are certain objects, then the notation x ∈ S means that x is a member of the set S and y ∉ S means that y is not an element of S.)
  
  
• 자연수 집합과 1대1 대응이 가능한(denumerable) 원소의 집합 A는 중괄호를 표현해 나타낼 수 있다.
  A = {1, 2, 3, 4}는 집합 A의 원소가 1, 2, 3, 4라는 의미이다.
  (A set with a denumerable number of elements is specified by braces: A = {1, 2, 3, 4} indicates that the elements of set A are the numbers 1, 2, 3, and 4.)
  
  
• a*b = c를 만족하는 이진 연산자 *는 유일한 원소 c를 한 쌍의 원소 (a, b)에 대응시키는 집합 S에서 정의된 규칙이다. 이때 a, b, c ∈ S이고 a, b, c중 하나라도 S의 원소가 아니면 식은 성립하지 않는다.
  (A binary operator defined on a set S of elements is a rule that assigns, to each pair of elements from S, a unique element from S. As an example, consider the relation a *b = c. We say that * is a binary operator if it specifies a rule for finding c from the pair (a, b) and also if a, b, c ∈ S. However, * is not a binary operator
  if a, b ∈ S, and if c ∉ S.)
  
  

 

위에 내용은 우리가 어떤 집합에서 원소를 가지고 연산을 할 때 그 연산식을 정의하는데 있어서 필요한 내용이다.

물론 이걸 외워야 할 필요는 없지만 그것들이 무엇을 의미하는지는 대략적인 파악을 해야 한다.

 

부울 대수의 공리적 정의

---

대수학에서의 공준

부울 대수의 공리적 정의를 하기에 앞서 일반적인 대수학에서 사용되는 보편적인 공준을 설명하겠다.

1. 닫힘. 2진 연산자가 한 쌍의 원소쌍으로부터 유일한 원소로 대응시키는 규칙을 가지고 있다면 집합 S는 그 2진 연산자에 대해 닫혀 있다라고 한다. (A set S is closed with respect to a binary operator if, for every pair of elements of S, the binary operator specifies a rule for obtaining a unique element of S.)
   
   
2. 결합법칙. 집합 S에 대한 2진연산자 *가 (x * y) * z = x * (y * z) (모든 x, y, z ∈ S)이면 이를 결합적이라고 한다. (Associative law. A binary operator * on a set S is said to be associative whenever (x * y) * z = x * (y * z) (for all x, y, z ∈ S))
   
   
   
3. 교환법칙. 집합 S에 대한 2진연산자 *가 x * y = y * x (모든 x, y ∈ S)이면 이를 교환적이라고 한다.(Commutative law. A binary operator * on a set S is said to be Commutative whenever x * y = y * x (for all x, y ∈ S))
   
   
4. 항등원. 집합 S가 e*x = x*e = x (모든 x ∈ S)을 만족하는 e∈S인 원소 e를 가지면, 집합 S는 2진 연산자 *에 대해 항등원을 갖는다라고 한다. (Identity element. A set S is said to have an identity element with respect to a binary operation * on S if there exists an element e ∈ S with the property that e*x = x*e = x (for every x ∈ S))
   
   
5. 역원. 2진 연산자 *에 관하여 단위 원소 e를 가지는 집합 S가 모든 x ∈ S 에 대하여 x*y = e를 만족시키는 y ∈ S를 가지고 있다면, 집합 S는 역원을 갖는다라고 한다. (Inverse. A set S having the identity element e with respect to a binary operator * is said to have an inverse whenever, for every x H S, there exists an element y ∈ S such that x*y = e)
   
   
6. 분배법칙. *와 ·가 집합 S에 대한 2진 연산자라고 한다면, x*(y · z) = (x*y) · (x*z)일 때 *는 · 에 대해 분배적이라 한다.
   (If * and · are two binary operators on a set S, * is said to be distributive over · whenever x*(y · z) = (x*y) · (x*z))

 

혹시나 헷갈릴 수 있는 사항들이나 추가적인 설명은 여기에 하겠다.

일단 binary operator: 이진 연산자 또는 이항 연산자는 이진수를 계산하는 연산자가 아니라 2개의 항을 계산하는 연산자이다. 예를 들어 a + b, a - b, a * b, a / b에서 +, -, *, /는 항이 2개라서 이항 연산자이다. 

 

공준1에서 닫혀 있는 연산자의 예로는 자연수 집합에서 정의된 +가 될 수 있다. 자연수 1 + 2 = 3으로 대응되기 때문이다. 하지만 -는 성립할 수 없다. 앞서 우리가 정의한 연산자의 조건은 피연산자인 두 원소와 연산자로 연산했을 때 나온 결과값이 모두 같은 집합에 속해야 한다. 근데 -는 3 - 4 = -1로 -1은 자연수가 아니기 때문에 성립하지 않는다.

 

 

 

부울 대수의 공준

 

부울 대수는 헌팅턴 공준을 만족하는 +, ·의 2진 연산자를 가지는 집합 B로 정의된 대수 구조이다.

헌팅턴 공준은 다음과 같다.

 

1. (a) 구조는 +연산자에 대해 닫혀 있다. (The structure is closed with respect to the operator +. )
   (b) 구조는 · 연산자에 대해 닫혀 있다. (The structure is closed with respect to the operator · . )
   
   
2. (a) 원소 0은 +연산자에 대해 항등원이다. 즉, x + 0 = 0 + x = x. (The element 0 is an identity element with respect to +.)
   (b) 원소 1은 · 연산자에 대해 항등원이다. 즉, x · 1 = 1 · x = x. (The element 1 is an identity element with respect to · .)
   
   
3. (a) 구조는 +연산자에 대해 교환적이다. 즉, x + y = y + x. (The structure is commutative with respect to +.)
   (b) 구조는 · 연산자에 대해 교환적이다. 즉, x · y = y · x. (The structure is commutative with respect to · .)
   
   
4. (a) · 연산자는 +에 대해 분배적이다. 즉, x · (y + z) = (x · y) + (x · z). (The operator · is distributive over +.)
   (b) +연산자는 · 에 대해 분배적이다. 즉, x + (y · z) = (x + y) · (x + z). (The operator + is distributive over · .)
   
   
5. 모든 x ∈ B에 대해 x + x' = 1과 x · x' = 0을 만족하는 x' ∈ B이 존재한다. (For every element x ∈ B, there exists an element x' ∈ B (called the complement of x) such that (a) x + x' = 1 and (b) x · x' = 0.)
   
   
6.  x ≠ y를 만족하는 원소 x, y ∈ B가 최소 두 개는 존재한다.(There exist at least two elements x, y ∈ B such that
   x ≠ y. )

 

부울 대수를 구성하기 위한 조건은 다음과 같다.

1. 집합 B의 원소,(the elements of the set B,)
2. 2개의 이항 연산자에 대한 연산 규칙, 그리고 (the rules of operation for the two binary operators, and)
3. 2개의 이항 연산자을 가지는 집합 B는 6개의 헌팅턴 공준을 만족해야 한다.(the set of elements, B, together with the two operators, satisfy the six Huntington postulates. )

우리는 위 조건을 만족하는 대수 구조를 부울 대수라고 한다. 우리가 부울 대수라고 하면 1과 0만을 가지는 수체계라고 생각할 수 있지만 엄연히 말해서 1과 0을 가지는 부울 대수는 2개의 값만을 사용하는 부울 대수인 것이지 그 자체가 부울 대수인건 아니다. 그렇기 때문에 우리는 0, 1, 2만을 사용하는 부울 대수도 만들 수 있다. 즉, 위 헌팅턴 공준을 만족하는 대수 체계는 모두 부울 대수라고 할 수 있다.

 

 

 

2값 부울 대수

---

컴퓨터에서 사용하는 부울 대수는 2값 부울 대수(two-valued Boolean algebra)이다. 원소를 1과 0 2개만을 사용하는 부울 대수이다. 컴퓨터에선 켜짐과 꺼짐만을 표현할 수 있기 때문에 부울 대수로 표현하기 좋다. 그러면 2값 부울 대수가 어떻게 헌팅턴 공준을 만족시키고 그 성질이 어떠한지 알아보자.

 

 

2값 부울 대수는 아래 표에서와 같이 2개의 연산자에 대한 규칙을 가지는 집합 B = {0, 1}에 의해 정의된다.

 

 

2값 부울 대수의 연산 규칙

 

1. 공준 1에 대한 증명
   위 표에서 두 연산자의 연산 결과와 피연산자 모두 집합 B에 속해 있으므로 위 대수 구조는 두 연산자에 대해 닫혀 있다. 그러므로 공준1을 만족한다.
   
   
2. 공준 2에 대한 증명
   위 표에서 다음과 같은 식이 성립한다.
   (a) 0 + 0 = 0   0 + 1 = 1 + 0 = 1
   (b) 1 · 1 = 1   0 · 1 = 1 · 0 = 0
   그러므로 0은 + 연산자에 대한 항등원이고 1은 · 연산자에 대한 항등원이므로 공준2를 만족한다.
   
   
3. 위 표에서 교환법칙이 성립함을 보이므로 공준3을 만족한다.
   
   
4. (a)모든 경우의 수를 이용하여 x + (y · z) = (x + y) · (x + z)를 증명할 수 있다.
   (b)모든 경우의 수를 이용하여 x · (y + z) = (x · y) + (x · z)를 증명할 수 있다.
   (a), (b)에 제시된 식에 1과 0을 대입하면 식이 성립함을 확인할 수 있다. 그러므로 +연산자는 · 대해 분배적이고 · 연산자는 + 대해 분배적이므로 공준4를 만족한다.
   
   
5. 보수는 다음과 같이 증명된다.
   (a) 0 + 0' = 0 + 1 = 1  1 + 1' = 1 + 0 = 1 
   (b) 0 · 0' = 0 · 1 = 0  1 · 1' = 1 · 0 = 0
   그러므로 공준5를 만족한다.
    
   
6. 2값 부울 대수는 1≠ 0를 만족하는 원소 0, 1을 가지고 있기 때문에 공준6을 만족한다.
   

이로써 부울 대수에 대한 기본적인 정의와 그 정의를 바탕으로 우리가 사용하는 0과 1을 이용하는 부울 대수에 대한 증명을 해보았다. 우리가 사용하는 0과 1만을 가지는 부울 대수는 앞서 설명했듯이 2값 부울 대수라고 한다. 2값 부울 대수는 2개의 값만을 가지고 있으며 이는 스위치를 껐다 켰다하는 것과 비슷하기 때문에 공학자들은 이를 스위칭 대수(switching algebra)라고 부른다. 컴퓨터 공학에서는 2값 부울 대수를 많이 사용함으로 부울 대수라고 하면 2값 부울 대수를 가리킨다. 그러므로 앞으로 이 포스팅 이후부터 2갑 부울 대수는 부울 대수로 칭할 것이다.