[이산수학] 8강 - 부울대수

✅ 1. 기본사항

(1) 디지털 논리회로

• 디지털 논리회로: 0과 1같은 이산적인(끊어진) 신호를 이용해 정보를 처리하는 전자 회로를 의미한다.
• 쉽게 말해, 입력과 출력이 디지털 신호로 들어오거나 나오게 되는데, 이때 중간에서 디지털 논리회로가 이를 처리를 해주는데, 이것은 0과 1로만 표현되는 하나의 반도체 회로로 볼 수 있음.
• 또한, 0과 1을 통해 논리회로로써 참(True)과 거짓(False)을 전기 신호로 표현해 논리 연산을 수행하는 구조임.
• 즉, 논리회로 자체는 AND, OR, NOT, ... 으로 실제로 물리적으로 구현이 되어있음을 알 수 있음.

(2) 기본 논리게이트 ( AND, OR, NOT )

• AND 게이트: 디지털 신호(0,1)가 입력값 X, Y에 들어오게 될 때, (0,0)인 경우 0(False), (0,1) or (1,0)인 경우 0(False), (1,1)인 경우에만 1(True)로써, 논리곱(AND 연산)이라 불리며, p^q 또는 X · Y 로 표현이 됨.
• 논리곱인 이유는, 0 * 0 = 0; 0 * 1 = 0; 1 * 0 = 0; 1 * 1 = 1 과 같이 두 수를 곱했을 때 나오는 결과 중 1은 둘 다 True 인 경우이기 때문에 이러한 과정을 통해 논리곱으로 보는 이유를 알 수 있음.

• OR 게이트: 논리합으로 불리며, 두 이진수를 더했을 때, 값이 0이면 False, 1이면 True 인 논리게이트임.
• 기호 표현: X + Y 또는 p ∨ q 로 표현이 됨.

• NOT 게이트: 일항 연산에 쓰이며, 입력에 들어온 값을 반전시키는 논리게이트임.
• 이러한 기본 논리게이트를 활용해서 NAND, NOR, XOR, XNOR 을 구성 할 수 있으며, 기본 논리게이트(AND, OR, NOT)로 모든게 이루어져있다고 보면 됨.

(3) 기타 논리게이트 (NAND, NOR, XOR, XNOR)

• NAND: AND 게이트에 NOT 을 붙힌 논리게이트로, AND의 결과에 NOT이 붙어 반전되어 출력이 되는 논리게이트임.

• NOR: OR 게이트에 NOT 을 붙힌 논리게이트로, OR의 결과에 NOT이 붙어 반전되어 출력이 되는 논리게이트임.

• XOR: 베타적 논리합으로, 두 개의 입력값이 서로 다를 때만 1(True)을 출력하고, 같은 경우에는 0(False)을 출력하는 게이트

• XOR 게이트 기호: A ⊕ B 로 표현하며, 논리식은 위와같이 표현하기도 함.
• AB = A * B = A and B 로 AND 연산이며, 해당 연산 두개에 대해서 각각 A, B에 NOT을 붙혀주고 최종적으로 OR 연산 진행

• XNOR 게이트: XOR 게이트의 최종적으로 NOT이 붙은 게이트이며, XOR 게이트의 결과값의 NOT이 되는 원리임.

---

✅ 2. 부울대수

(1) 부울대수 소개

• 부울대수: 수학의 한 분야로써, 컴퓨터의 논리 연산의 기초가 되는 체계로 0(False), 1(True)만으로 표현하는 수학을 의미함.
• 쉽게 말해, 일반적인 수학에서는 1,2,3, ... 같은 무한한 숫자를 다루지만, 부울 대수에서는 0과 1만을 가지는 부울값을 통해서 정해진 부울연산과 합쳐 부울식으로써 부울 대수를 정의하고 있음.
• 부울값(부울상수): 0 = 거짓(False), 1 = 참(True) 와 같이 두 값이 부울값임.
• 부울변수: A, B, X 와 같이 0 또는 1 값을 가질 수 있는 변수를 의미함.
• 부울연산: AND, OR, NOT, ... 등의 부울값끼리 계산하는 연산을 의미함.
• 부울식: 부울값과 부울연산을 이용해서 만든 식으로 예를 들면, A AND B, (A OR B) AND NOT C ... 등이 있음.
• 이런것들을 포함하고 있는 수학 체계가 부울 대수인 것임.

• 부울식: 부울상수 0,1 은 부울식으로 보며, 부울변수 또한 부울식으로 보며, X,Y가 부울식일 때, 합쳐진 부울 연산을 부울식으로 보는 것임. 즉, 아주 작은 단위도 이미 부울식으로 본다는 의미임.

---

(2) 부울대수의 성질

• X + 0 = X 에서 + 는 OR(논리합)을 의미 할 수 있음.
• X * 1 = X 에서 * 는 AND(논리곱)을 의미 할 수 있음.

• 위와 같이 여러 법칙이 존재함.
• (15) 번과 같은 것은 일반적인 실수 법칙에서는 성립하지 않고, 부울 대수에서만 성립이 되는 법칙임. ( 18번, 19번도 일듯 )

• 왼쪽은 논리이며, 오른쪽은 부울대수 표기법이며, 둘의 관련성을 나타냄.
• 논리상에서 p, q, r 은 명제를 의미하지만, 부울대수에선 X, Y, Z 로 부울 변수로 보고 있음.
• 논리상에서 T, F 는 명제에 대한 참, 거짓을 의미하지만 부울대수에선 1, 0 으로 표현함.
• 그 외에도 동일함.

• 논리 및 집합에서의 기본정리이며, 부울대수 법칙에 적용이 될 수 있음.

(3) 쌍대성 원리

• 쌍대성 원리: 부울식에서 논리곱, 논리합인 상태를 서로 바꾸고, 논리상수 0과 1을 서로 바꾸면 원래 부울식의 동일한 결과를 얻을 수 있는데, 이것을 쌍대라고 함. ( 쌍대: 주어진 부울식과 그것의 진리값이 서로 같음을 의미함. )
• 쉽게 말해, 어떤 부울식이나 부울 법칙에서 논리합, 논리곱 서로 바꾸고, 0과 1을 서로 바꾸었을 때, 새로 얻어진 식도 역시 참이 된다는 원리를 의미할 수 있음.

• 쌍대성 원리 예제: 위와 같이 X + 0 = X 의 경우 논리합(+) 와 0을 각각 논리곱(*) 과 1로 바꾸게 된다면 X * 1 = X 가 됨.

• 드 모르간 법칙: 전체를 부정하면, 연산이 반대로 바뀐다는 의미를 가지는 법칙으로, 쉽게 말해 OR 연산을 부정하면 AND 로 바뀌고 AND를 부정하면 OR로 바뀌는 것을 의미함.
• 정리하면 드 모르간 법칙은 보수를 구하기 위한 법칙으로 볼 수 있는 것임.

(4) 부울함수의 보수

• 보수: 결과를 반대로 뒤집는 것으로, 0인 경우에는 1로, 1인 경우에는 0으로 뒤집는 것을 의미함.

• 부울함수의 보수: 부울함수에서의 결과를 뒤집는 것을 의미하며, NOT 논리게이트가 붙어있다고 생각하면 됨.

• 부울함수의 보수 예제1: 드 모르간 법칙을 활용해서 예제를 풀고 있으며, 전체에 부정을 취하게 되면 법칙에 따라 논리합이 논리곱으로 바뀌게 되고, 각 부울변수에서 AND로 연결된 식 전체를 부정하면, 각각을 부정하고 더하기(OR)로 바꾼 것과 동일하기 때문에 X'' + Y' + Z" * X'' + Y'' + Z' 이 만들어지게 되며, 여기서 이중 부정의 법칙으로 부정을 두 번 하면 원래 자기 자신이 되기 때문에 최종적으로 (X + Y' + Z)(X + Y + Z') 가 되는 것임.

• 부울함수의 보수 예제2: 쌍대를 활용해서 예제를 풀고 있으며, 각 문자를 보수(반전)로 바꾸면 위와같은 결과를 얻을 수 있음.

---

✅ 3. 부울함수의 대수적 간소화

(1) 간소화 목적

• 간소화 목적: 위의 논리회로 두개는 동일한 기능을 하는 논리회로이며, 한 눈에 보기 편한 오른쪽의 회로가 좋음을 알 수 있음.
• 처리속도도 빨라지며, 고장도 덜나고, 비용이 절감되는 장점을 가지기 때문에 간소화를 반드시 하는게 좋음.

• 부울함수와 논리회로는 1:1 대응 관계이며, 진리표, 부울함수, 논리회로에 대한 상관관계를 나타내고 있음.

• 복잡한 논리회로는 복잡한 부울함수로 인해서 나오게 된것이며, 간소화를 시켜 간단한 부울함수를 통해 논리회로를 얻음.

(2) 간소화 예

• 항결합: 두 개의 항을 결합하여 하나의 항으로 만드는 방법을 의미함.

• 문자 소거: 중복된 문자를 제거하는 방법으로 흡수법칙을 이용한 방법임.

• 중복항 첨가: 부울함수의 진리값이 변하지 않도록 하면서 간소화를 위한 적절한 항을 첨가하는 방법을 의미함.

• 위와 같이 복잡한 부울함수가 있을 때, 대수적인 방법으로 풀게되면, 결과적으로 X만 남게 됨.
• 여러가지 대수법칙을 활용해서 간소화 시킬 수 있음.