[DiscreteMath]부울대수

📚기본사항

📄디지털 논리회로

디지털 논리회로는 디지털 입력값을 가지고 논리적 연산을 수행하여 디지털 출력값을 생성시키는 추상화된 개념적 전자회로를 말합니다. 여기서 입출력값은 0 또는 1을 나타내는 2진 신호로 표시되는 디지털 데이터로서 컴퓨터는 논리회로를 조합하여 디지털 데이터를 처리합니다.

📄기본 논리게이트

• AND 게이트
  논리적 곱 \(p \wedge q\)를 수행하는 기능을 가집니다. 두 개 이상의 입력과 한 개의 출력으로 구성됩니다. 입력이 모두 1인 경우에만 출력이 1이 되고, 그렇지 않은 경우에 출력이 0이 됩니다.

• OR 게이트
  논리적 합 \(p \vee q\)를 수행하는 기능을 가집니다. 두 개 이상의 입력과 한 개의 출력으로 구성됩니다. 입력 중 어느 한 개 이상이 1인 경우 출력은 1이고, 그렇지 않은 경우에 출력은 0이 됩니다.

• NOT 게이트
  인버터라고도 부릅니다. 논리적 부정 \(\sim p\)를 수행하는 기능을 가집니다. 한 개의 입력과 한 개의 출력으로 구성됩니다. 입력이 1이면 출력은 0, 입력이 0이면 출력은 1이 됩니다.

• NAND 게이트
  논리적 곱의 보수 \(\sim(p \wedge q)\)를 수행하는 기능을 가집니다. 두 개 이상의 입력과 한 개의 출력으로 구성됩니다. 입력 중 한 개 이상의 입력이 0이면 출력은 1이고, 모든 입력이 1일 때만 출력은 0이 됩니다.

• NOR 게이트
  논리적 합의 보수 \(\sim(p \vee q)\)를 수행하는 기능을 가집니다. 두 개 이상의 입력과 한 개의 출력으로 구성됩니다. 입력들 중 어느 한 개 이상의 입력이 1이면 출력이 0이고, 모든 입력이 0일 때만 출력은 1이 됩니다.

• XOR 게이트
  배타적 논리합 \(p \oplus q\)을 수행하는 기능을 가집니다. 입력되는 두 비트의 값이 서로 같은지 다른지 비교합니다. 두 개의 입력이 다르면 출력이 1이고, 서로 같으면 출력이 0입니다.

• XNOR 게이트
  배타적 논리합의 보수 \(\sim(p \oplus q)\)를 수행하는 기능을 가집니다. XOR 연산의 결과에 NOT연산을 취하는 논리게이트입니다.

논리게이트 기호와 진리표는 [Circuits]논리연산과 논리게이트를 참고하시길 바랍니다.

📚부울대수, 부울식, 부울함수

📄부울대수

부울대수는 부울값 또는 부울값을 가지는 부울변수에 대한 논리연산을 다루는 수학입니다. 부울대수에서 사용되는 논리연산은 피연산자의 개수에 따라 이항연산과 단항연산으로 나뉩니다.

📄부울식

부울식은 아래와 같이 순환적으로 정의합니다.

1. 상수 0, 1은 부울식이다.
2. 부울변수는 부울식이다.
3. X, Y가 부울식일 때, \(X + Y, \; X \cdot Y, \; \overline{X}, \; (X)\)도 부울식이다.

📄부울함수

부울식으로 표현된 함수를 부울함수라고 합니다. n개의 변수를 가지는 부울함수 F는 n변수 부울함수라고 합니다.

\[F(X, Y, Z) = X\overline{Y} + XYZ + \overline{X}YZ\]

부울함수는 진리표로도 나타낼 수 있습니다. 진리표는 참(T)과 거짓(F) 값 대신 1과 0을 사용합니다.

	X	0	0	0	0	1	1	1	1
입력	Y	0	0	1	1	0	0	1	1
	Z	0	1	0	1	0	1	0	1
출력	F	0	0	0	1	1	1	0	1

📄논리회로도

부울함수는 논리게이트들로 구성되는 논리회로도로 표현할 수 있습니다.

부울함수를 진리표로 나타낼 때는 진리표가 하나로 결정되지만 대수식으로 나타낼 때는 다양한 형태의 식으로 표현 가능합니다. 쉽게 말해, 부울함수에 대한 진리표는 하나지만 동일한 진리표를 만족하는 부울함수는 여러개가 될 수 있다는 말입니다. 하나의 부울함수는 하나의 논리회로도에 대응되기 때문에 동일한 진리표에 대한 논리회로도도 여러 개로 구현될 수 있습니다.

부울함수를 구성하는 부울연산과 부울변수의 수는 게이트의 수, 각 게이트의 입력 수와 직접적으로 관계가 있어서 이것들의 수를 줄이는 만큼 논리회로도는 단순하게 됩니다. 따라서 가장 단순화된 논리회로도를 구현하기 위해서 부울함수를 가능한 단순한 식으로 변환해야합니다.

📄부울대수 기본정리

부울대수의 기본정리는 논리학, 집합론의 기본정리와 개념상 동일합니다.

부울대수 기본정리
(1) \(X + 0 = X\)	(2) \(X \cdot 1 = X\)
(3) \(X + 1 = 1\)	(4 )\(X \cdot 0 = 0\)
(5) \(X + X = X\)	(6) \(X \cdot X = X\)
(7) \(X + \overline{X} = 1\)	(8) \(X \cdot \overline{X} = 0\)
(9) \(\overline{\overline{X}} = X\)
(10) \(X + Y = Y + X\)	(11)\(XY = YX\)	교환법칙
(12) \(X + (Y + Z) = (X + Y) + Z\)	(13) \(X(YZ) = (XY)Z\)	결합법칙
(14) \(X(Y + Z) = XY + XZ\)	(15) \(X + YZ = (X + Y)(X + Z)\)	분배법칙
(16) \(\overline{X + Y} = \overline{X} \cdot \overline{Y}\)	(17) \(\overline{X \cdot Y} = \overline{X} + \overline{Y}\)	드모르간의 법칙
(18) \(X + X \cdot Y = X\)	(19) \(X \cdot (X + Y) = X\)	흡수정리

• 쌍대성 원리
  부울대수에서식에서 논리연산자 \(+\)와 \(\cdot\)을 서로 맞바꾸고 논리값 1과 0을 맞바꾸면 쌍대형태를 얻게 되는데 이때 쌍대인 두 부울대수식은 서로 동치라는 것이 쌍대성 원리입니다.

위 부울대수 기본정리 표를 보면 9번을 제외한 나머지 식들이 서로 쌍대형식을 취하고 있는 것을 확인할 수 있습니다.

📄부울함수의 보수

부울함수 \(F\)의 보수는 \(\overline{F}\)입니다. F 값을 0은 1로, 1은 0으로 바꿔서 얻을 수 있습니다. 대수적으로 드 모르간의 법칙을 이용하면 쉽게 얻을 수 있습니다. AND와 OR 연산을 서로 바꾸고 각 변수의 보수를 취하면 됩니다.

\[F = \overline{XY} + XY\overline{Z}\]

위 부울함수의 보수를 구하면 아래와 같습니다.

\[\begin{aligned} \overline{F} &= \overline{\overline{XY} + XY\overline{Z}} \\ &= \overline{(\overline{XY})(XY\overline{Z})} \\ &= (\overline{\overline{X}} + \overline{\overline{Y}})(\overline{X} + \overline{Y} + \overline{\overline{Z}}) \\ &= (X + Y)(\overline{X} + \overline{Y} + Z) \end{aligned}\]

함수의 보수를 구하는 다른 방법은 주어진 함수에서 논리연산자 AND는 OR로, OR은 AND로 바꾸어 쌍대를 취하고 각 문자에 보수를 취하는 방법입니다.

📚부울함수의 대수적 간소화

부울함수의 대수적 간소화는 주어진 부울함수에 대해 부울대수 정리를 이용하여 변환하고 변환된 여러 함수 중 가장 간단한 형태의 함수를 찾아내는 것을 말합니다.

부울함수는 AND, OR, NOT 등 논리게이트로 구성되는 논리회로로 변환될 수 있습니다. 부울함수에서 문자는 정상형 또는 보수형으로 나타난 논리변수로서 논리회로에서 게이트의 입력으로 쓰입니다. 부울함수에서 항은 문자들이 논리연산자에 의해 연결된 것으로 논리회로에서 게이트로 나타납니다.

📄항 결합

항 결합은 두 개의 항을 결합하여 하나의 항으로 만드는 방법입니다.

\[\begin{aligned} F &= X\overline{Y} + XYZ + \overline{X}YZ \\ &= X\overline{Y} + (X + \overline{X})YZ \\ &= X\overline{Y} + 1 \cdot YZ \\ &= X\overline{Y} + YZ \\ \end{aligned}\]

📄문자 소거

문자 소거는 중복된 문자들을 제거하는 방법입니다.

\[X + \overline{X}Y = (X + \overline{X})(X + Y) = 1 \cdot (X + Y) = X + Y\] \[X(\overline{X} + Y) = X\overline{X} + XY = 0 + XY = XY\]

이 두 식은 서로 쌍대형식입니다.

📄중복항 첨가

중복항 첨가는 주어진 함수식의 의미가 변하지 않도록 하면서 적절한 항을 함수식에 첨가시키는 방법입니다. 0(\(X\overline{X}\))을 더하거나, 1(\(X + \overline{X}\))을 곱하거나 또는 XY를 X에 더하거나, X + Y를 X에 곱하는 방식입니다. 항들을 첨가하는 이유는 다른 항을 결합 또는 제거하기 위해서입니다.

\[\begin{aligned} F &= X\overline{Y}Z + XYZ + \overline{X}YZ \\ &= X\overline{Y}Z + XYZ + XYZ + \overline{X}YZ \\ &= XZ(\overline{Y} + Y) + YZ(X + \overline{X}) \\ &= XZ + YZ \\ \end{aligned}\]