불 대수

위키백과 ― 우리 모두의 백과사전.

불 대수(Boolean algebra)는 조지 불이 19세기 중반에 고안한 논리 수학의 대표적 형태이다. 불 격자(Boolean lattice)나 불 속(束)이라고도 한다. 불 대수의 연구는 대수적 구조로서 속의 이론을 발전시키는 하나의 계기가 되었다. 수학적인 엄밀한 정의는 다음에 기술한다.

디지털 회로 설계에서는 필수적인 지식이다. 디지털 회로는 전압의 H(High), L(Low)만으로 정보를 연산하기 때문에, 기본적으로 조합 회로는 불 대수에 있는 논리식을 써서 나타낼 수 있다. (하지만, 플립 플랍 등 순차 회로는 단순하게 하나의 논리식으로 나타낼 수 없다.)

높은 전압(H)를 1로, 낮은 전압(L)을 0으로 하는 논리 형식을 정논리, 낮은 전압 (L)을 1로, 높은 전압(H)를 0으로 하는 논리 형식을 부논리라고 한다.

불 대수의 기본 연산(논리 연산)은 논리 부정 ¬ 또는 '(not), 논리합 ∨(or), 논리곱 ∧(and)로 출발된다. 이러한 연산 합성으로부터 만들어지는 연산 중 대표적인 것으로 배타적 논리합(xor)이 있다. 또한, 논리합의 부정인 NOR, 논리곱의 부정인 NAND 등의 연산도 존재한다.

일반적으로, AND와 NOT, 또는 OR과 NOT을 이용하여 모든 논리 회로를 만들 수 있는데, NOR이나 NAND를 이용하면 NOT도 만들 수 있으므로 NAND 또는 NOR 중 하나만으로 논리 회로를 구현할 수 있다.

불 대수를 불 격자(불 속)라고 부르는 이유는, ∨, ∧에 대해서 분배 가능한 격자가 되기 때문이다. 즉, 다음 법칙이 성립한다:

멱등법칙(idempotence): x ∧ x = x ∨ x = x,
교환법칙(commutativity): x ∧ y = y ∧ x, x ∨ y = y ∨ x,
결합법칙(associativity): (x ∧ y)∧ z = x ∧(y ∧ z), (x ∨ y)∨ z = x ∨(y ∨ z),
흡수법칙(absorption): (x ∧ y)∨ x = x, (x ∨ y)∧ x = x,
분배법칙(distributivity): (x ∨ y)∧ z = (x ∧ z)∨(y ∧ z), (x ∧ y)∨ z = (x ∨ z)∧(y ∨ z).