3.2 부울대수

3.2 부울대수
3.2.1 개요
부울대수(Boolean algebra) - 0 또는 1의 값을 갖는 논리변수와 논리연산을 다루는 대수, 영국의 수학자 조지불(George Boole)이 논리적 판단을 하기 위해 사용한 수학적 기법.
부울대수 변수 - 영문자로 표시, 논리연산에는 AND, OR와 보수의 세 가지 연산.
부울함수 (Boolean Function) - 논리변수의 상호관계를 나타내기 위해 부울변수, 부울상수(0 또는 1), 부울 연산기호(,, +, -), 괄호 및 등호 등으로 나타내는 대수적 표현.

부울함수 - 논리게이트로 구성되는 회로도로 작성할 수 있는데, 이를 '주어진 부울함 수를 논리회로도(logic circuit diagram)로 구현한다'라고 함.

함수를 구성하는 독립변수들(X, Y, Z) - 회로의 입력, 종속변수 F - 논리변수로 회로의 출력.

논리회로도는 일반적으로 입력을 왼쪽(또는 위쪽)에, 출력을 오른쪽(또는 아래쪽)에 두도록 작성하되 선과 선이 이해되기 쉽게 논리 게이트를 정렬시키는 것이 좋음. 또한 선과 선이 겹칠 때에는, 두 선이 연결(결선)된 경우에만 교차점에 까만 점을 둠으로써 혼돈을 피하도록 작성.

부울함수를 진리표 - 진리표가 하나로 결정.
대수식으로 나타낼 때 - 다양한 형태의 식으로 표현.

진리표는 오직 하나이지만 동일한 진리 표를 만족하는 부울함수는 여러 개가 됨.

부울함수를 구성하는 부울연산과 부울변수의 수는 결국 게이트의 수 그리고 각 게이트의 입력수를 줄이는 만큼 논리회로는 단순해짐. 따라서 부울함수를 가능한 한 단순한 식으로 변환해야 함.

3.2.2 기본공식ㅔ
부울대수에서 중요한 원리 - 쌍대성 원리(principle of duality). 부울대수식에 •서 논리연산자인 +와, 그리고 논리상수 1과 0을 맞바꾸면 쌍대형태(dual Form)를 얻을 수 있음.
부울대수에서 어떤 부울공식이 항상 성립하고 자신의 쌍대형태를 구할 수 있다면 그 쌍대형태의 부울식도 성립.
* 부울대수의 특성 - 쌍대성 원리

부울대수 - 교환법칙, 결합법칙, 분배법칙.

드모르간(De Morgan)의 법칙 - 변수의 전체 합의 보수는 각 변수의 보수의 곱과 같다는 것을 의미하는 것, OR로 결합되는 2개 이상의 변수의 보수는 각각의 변수의 보수를 취한 다음 AND한 것과 같음.
변수의 전체 곱의 보수 - 각 변수의 보수의 합과 같음, AND로 결합되는 2개 이상의 변수의 보수는 각각의 변수의 보수를 취한 다음 OR한 것과 같음.

공식 (18)과 (19) - 흡수정리(absorption theorem)라고 부르며, 서로 쌍대형태를 취함.

3.2.3 부울함수의 대수적 간소화
부울함수의 대수적 간소화(algebraic simplification) - 주어진 부울함수에 대하여 부울대수의 공식을 이용하여 변환한 다음, 변환된 여러 함수 중에서 가장 간단한 형태의 함수를 찾아내는 것.

부울함수 - AND, OR, NOT 등의 논리게이트로 구성되는 논리회로로 변환될 수 있음.

부울함수에서 문자(literal) - 정상형(X) 또는 보수형으로 나타난 논리변수로 논리회로 구현 시에 게이트 의 입력으로 쓰임.

부울함수에서 항(term) - 문자가 논리연산자에 의해 서로 연결된 것, 논리회로 구현 시에 게이트로 나타남.


(1) 항 결합
2개의 항을 결합하여 하나의 항으로 만드는 방법.

(2) 문자 소거
중복된 문자를 제거하는 방법.

(3) 중복항 첨가
주어진 함수식의 의미가 변하지 않도록 주의하면서 적절한 항을 함수식에 첨가하는 방법.

3.2.4 부울함수의 보수
부울함수 F의 보수는 F이며, 이는 F의 값을 0은 1로, 1은 0으로 바꿈으로써 얻을 수 있음. 드모르간의 법칙을 이용하여 대수적으로 얻을 수도 있음.
* 부울식의 보수를 취하려면 AND와 OR 연산을 서로 바꾸고 각 변수의 보수를 취하면 된다는 사실을 일반화한 것.

함수의 보수를 쉽게 구하는 또 다른 방법 - 논리연산자인
.(AND)는 +(OR)로, +(OR)는 .(AND)로 바꾸어 쌍대형태를 취한 후, 각 문자의 보수를 취하는 것. (일반화한 드모르간의 법칙을 이용하는 방법.)


3.3 부울함수의 정규형 및 표준형
3.3.1 정규형
부울함수의 정규형(canonical Form) - 부울함수를 최소항의 합(sum of minterm)이나 최대 항의 곱(product of maxterm)으로 표현한 것. 그 외의 함수 - 비정규형(non-canonical Form).
* 부울함수의 정규형 중 최소항의 합형태와 최대항의 곱형태의 부울함수는 진리표와 1:1 관계로 각 각 오직 하나만 존재.


(1) 최소항과 최대항
논리변수 - 정상형(X) 또는 보수형.
2개의 논리변수 X, Y가 논리곱(AND) 연산 으로 묶인 경우 -  각 변수는 정상형 또는 보수형으로 나타낼 수 있음.
XY, XY, XY, XY와 같이 네 가지 조합 - 논리변수 X, Y의 최소항(minterm)
-> 2개의 변수는 2개의 최소항을 형성, 같이 3개 변수의 경우 동일한 방법으로 각각의 최소항이 결정. 각 최소항은 n개의 변수에 관한 문자(정상형이든 보수형이든 관계없이)들을 논리곱 (AND)항으로 결합하되, 그 결과가 논리-10이 되도록 결합. 각 최소항에 대한 기호는 mj 형태로 표현. 여기서는 최소항에 해당하는 2진수를 10진수로 표시한 것.

-> 2개의 변수는 2개의 최대항(maxterm)을 형성. 7개의 변수의 값이 이루는 각각의 2진수 조합에 대하여 각 변수에 관한 문자들을 논리합(OR)으로 결합하되, 그 결과가 논리-0 이 되도록 결합하면 해당 최대항을 얻을 수 있음.
각 최대항은 Mj형태로 나타내는데 여기서 최대항에 해당하는 2진수를 10진수로 나타낸 것.

n개의 논리변수로 구성되는 부울함수에서 최소항 - 각 변수의 문자 1개씩 모두 2개의 문자의 논리곱항으로 그 결과가 논리-1인 경우. 최소항은 Mj로 표시하는데 만일 논리변수가 X, Y, Z인 경우 M5는 XYZ를 의미.

2개의 논리변수로 구성되는 부울함수에서 최대항 - 각 변수의 문자 1개씩 모두 2개의 문자로 구성되는 논리합항으로 그 결과가 논리-0인 경우. 최대항은 Mj로 표시하는데 만일 논리변수가 X, Y, Z인 경우 MS는 X+Y+Z를 의미한다.
주어진 변수값의 2진수 조합에 대해 최소항과 최대항은 서로 보수관계. 즉, mj=Mj. (드모르간의 법칙으로 증명 가능.)
진리표에서 출력이 1이 되는 변수들의 각 조합에 대해서 최소항을 형성 하고 각각의 최소항을 논리합(OR)으로 묶으면 해당 진리표를 만족하는 정규형 부울함수를 얻을 수 있음.

진리표 하나에 대응되는 최소항의 곱형태의 부울함수는 오직 하나밖에 없음.

부울함수의 보수 - 진리표에서 함수를 0으로 하는 최소항을 얻은 다음 이들의 OR 연산을 취하면 부울함수의 보수를 구할 수 있음.

진리표 하나에 대응되는 최대항의 곱형태의 부울함수는 오직 하나밖에 없음.

부울함수의 정규형 - 최소항의 합형 태와 최대항의 곱형태

(2) 최소항의 합
부울함수에서 7개의 2진 변수는 최대 2개의 서로 다른 최소항(AND 연산)으로 구성, 구성된 최소항을 논리합(OR)으로 결합하여 해당 부울함수를 표시.


(3) 최대항의 곱
부울함수에서 7개의 논리변수는 최대 2개의 서로 다른 최대항으로 구성, 그중 필요한 최대항을 논리곱(AND)으로 결합함으로써 해당 부울함수를 표시. 주어진 부울함수를 최대항의 곱형태로 나타내려면 먼저 합항의 곱형태로 전개. 주로 분배법칙 이용. 그리고 만일 각 합항에 변수 X가 빠져 있으면 XX를 더해 줌. 이런 방법으로 합 항에 2개의 변수가 모두 들어가면 원하는 최대항의 곱형태를 얻을 수 있음.

(4) 정규형 간의 관계
최소항의 합으로 표시된 함수의 보수 - 원래 함수에서 제외된 최소항들의 합. 어떤 함수를 표현하는 최소항은 함수를 1로 하는 데 비해, 그것의 보수를 표현하는 최소항은 처음 함수를 0 으로 함.

3.3.2 표준형
표준형(standard Form) 또한 부울함수를 표현하는 대표적인 방법 가운데 하나.
표준형의 각 항 - 하나 또는 그 이상의 문자로 구성, 표준형에는 곱의 합(sum of products)과 합의 곱 (product of sums).

(1) 곱의 합
최소항의 합형태 - 진리표로부터 직접 구할 수 있는 표준형의 부울식, 최대수의 곱항으로 구성되며 각 항은 최대수의 문자를 갖음.

논리함수를 간소화하려면 최소항의 합을 진리표로부터 구한 다음, 곱항의 수와 문자 의 수를 줄일 수 있는지 여부를 따져 봄.


(2) 합의 곱
대수적으로 표현한 부울함수의 또 다른 표준형 - 합의 곱(product of sums)형태로 합항들이 논리곱형태로 구성. 각 논리합의 항은 논리변수의 전체 수보다 적은 수의 문자를 가질 수 있음.