[Circuits]부울대수

📚부울대수

📄개요

부울대수는 0또는 1의 값을 갖는 논리변수와 논리연산을 다루는 대수입니다. 영국의 수학자 조지 불이 사용한 수학적 기법입니다. 부울대수의 논리연산에는 AND(\(\cdot\)), OR(\(+\)), 보수(\(\overline{}\)) 세 가지 연산이 있습니다. 부울함수는 논리변수의 상호관계를 나타내기 위해 부울변수, 부울상수, 부울연산기호 등으로 나타내는 대수적 표현입니다.

부울함수는 진리표와 논리회로도로 나타낼 수 있습니다. 부울함수에 대한 진리표는 오직 하나이지만 동일한 진리표를 만족하는 부울함수는 여러 개가 될 수 있습니다. 부울함수는 하나의 논리회로도와 대응되므로 동일한 진리표에 대한 논리회로도 역시 여러 개가 될 수 있습니다.

부울 함수를 구성하는 부울연산과 부울변수는 게이트 수와 게이트의 입력 수와 관계가 있으므로 이들의 수를 줄이는 만큼 논리회로도가 단순해집니다. 같은 논리회로라도 게이트와 게이트 입력 수가 적은게 더 효율적이므로 가장 단순화된 논리회로도를 구현하기 위해 부울함수를 가능한 한 단순한 식으로 변환해야합니다.

📄기본공식

부울대수에서 중요한 원리는 쌍대성 원리입니다. 부울대수식에서 논리연산자인 +와 · 그리고 논리상수 1과 0을 맞바꾸면 쌍대형태를 얻을 수 있습니다. 아래 표에서 공식(9)를 제외한 같은 줄에 있는 왼쪽과 오른쪽의 모든 식이 서로 쌍대형태입니다.

부울대수 기본공식
(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\)	흡수정리

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

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

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

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

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

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

• 중복항 첨가
  함수식의 의미가 변하지 않도록 적절한 항을 식에 첨가하는 방법입니다. 항을 첨가하는 이유는 다른 항을 결합 또는 제거하기 위해서입니다.

\[\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}\]

📚부울함수의 보수

부울함수 F의 보수는 \(\overline{F}\) 이고, F 값을 0은 1로, 1은 0으로 바꿈으로써 얻을 수 있습니다. 부울식의 보수를 취하려면 AND와 OR 연산을 서로 바꾸고 각 변수의 보수를 취하면 됩니다.

아래 식의 보수를 구해봅시다.

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

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

📚부울함수의 정규형

부울함수의 정규형은 부울함수를 최소항의 합이나 최대항의 곱으로 표현한 것입니다. 그 외의 함수를 비정규형이라고 합니다. 최소항의 합 형태와 최대항의 곱 형태의 부울함수는 진리표와 1 : 1 관계로 하나만 존재합니다.

📄최소항과 최대항

논리변수는 정상형(X) 또는 보수형(\(\overline{X}\))으로 나타냅니다. 2개의 논리변수 X, Y가 논리곱(AND) 연산으로 묶인 경우 \(XY, X\overline{Y}, \overline{X}Y, \overline{XY}\) 와 같이 네 가지 조합이 가능합니다. 네 가지 조합의 곱 항을 논리변수 X, Y의 최소항이라고 합니다. n개의 변수는 2ⁿ개의 최소항을 형성합니다. 0부터 2ⁿn - 1까지의 2진수 조합이 n개의 변수 밑에 기록되며 각 최소항은 n개의 변수에 관한 문자들을 논리곱으로 결합하는데 그 결과가 1이 되도록 결합합니다. 최대항도 최소항과 비슷하게 n개의 변수는 2ⁿ개가 형성됩니다. n개의 변수 값이 이루는 각각의 2진수 조합에 대해 각 변수에 관한 문자들을 논리합으로 결합하고 그 결과가 0이 되도록 결합하면 최대항을 얻을 수 있습니다.

X	Y	Z	최소항		최대항
			항	표시	항	표시
0	0	0	\(\overline{XYZ}\)	m0	\(X + Y + Z\)	M0
0	0	1	\(\overline{XY}Z\)	m1	\(X + Y + \overline{Z}\)	M1
0	1	0	\(\overline{X}Y\overline{Z}\)	m2	\(X + \overline{Y} + Z\)	M2
0	1	1	\(\overline{X}YZ\)	m3	\(X + \overline{Y} + \overline{Z}\)	M3
1	0	0	\(X\overline{YZ}\)	m4	\(\overline{X} + Y + Z\)	M4
1	0	1	\(X\overline{Y}Z\)	m5	\(\overline{X} + Y + \overline{Z}\)	M5
1	1	0	\(XY\overline{Z}\)	m6	\(\overline{X} + \overline{Y} + Z\)	M6
1	1	1	\(XYZ\)	m7	\(\overline{X} + \overline{Y} + \overline{Z}\)	M7

📄최소항의 합

부울함수에서 n개의 2진 변수는 최대 2ⁿ개의 서로 다른 최소항(AND 연산)으로 구성할 수 있고 구성된 최소항을 논리합(OR)으로 결합하여 부울함수로 표시할 수 있습니다. 부울함수를 최소항의 합형태로 나타내려면 먼저 부울함수를 곱항의 합으로 전개합니다. 그리고 각 항이 모든 변수를 포함하고 있는지 확인하여 변수들이 빠져 있으면 모든 변수가 포함되도록 합니다.

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

위 부울함수를 최소항 표기를 이용하면 아래와 같이 표현할 수 있습니다.

\[F = m_7 + m_6 + m_5 + m_4 + m_2\]

또한 다음과 같이 나타낼 수도 있습니다.

\[F(X, Y, Z) = \sum m (2, 4, 5, 6, 7)\]

📄최대항의 곱

부울함수에서 n개의 논리변수는 최대 2ⁿ개의 서로 다른 최대항으로 구성할 수 있습니다. 여기서 필요한 최대항을 논리곱으로 결합하여 부울함수를 표현할 수 있습니다.부울함수를 최대항의 곱형태로 나타내려면 먼저 합항의 곱형태로 전개합니다.

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

위 부울함수를 최대항 표기를 이용하면 아래와 같이 표현할 수 있습니다.

\[F = M_0 \cdot M_2 \cdot M_4 \cdot M_5\]

또한 다음과 같이 나타낼 수도 있습니다.

\[F(X, Y, Z) = \prod M (0, 2, 4, 5)\]

📄정규형 간의 관계

최소항의 합으로 표시된 함수의 보수는 원래 함수에서 제외된 최소항들의 합입니다. 어떤 함수를 표현하는 최소항은 함수를 1로 하는데 비해 그것의 보수를 표현하는 최소항은 처음 함수를 0으로 합니다.

\[\begin{aligned} F(X, Y, Z) &= \sum m (2, 4, 5, 6, 7) \\ &= m_2 + m_4 + m_5 + m_6 + m_7 \end{aligned}\]

의 보수는

\[\overline{F}(X, Y, Z) = \sum m (0, 1, 3) = m_0 + m_1 + m_3\]

\(\overline{F}\) 를 드모르간의 법칙을 사용하여 보수를 취하면 최대항의 곱형태로 함수 F를 얻을 수 있습니다.

\[\begin{aligned} F(X, Y, Z) &= \overline{\overline{F}}(X, Y, Z) = \overline{\sum m (0, 1, 3)} \\ &= \overline{m_0 + m_1 + m_3} \\ &= \overline{m_0} \cdot \overline{m_1} \cdot \overline{m_3} \\ &= M_0 \cdot M_1 \cdot M_3 \\ &= \prod M (0, 1, 3) \\ \end{aligned}\]

📚부울함수의 표준형

부울함수의 정규형은 진리표로부터 바로 얻을 수 있지만 최소항 또는 최대항에 항상 모든 변수가 포함되어 있어 부울함수 간소화에는 적합하지 않습니다. 부울함수 표준형 또한 부울함수를 표현하는 방법 가운데 하나입니다.

📄곱의 합

논리함수를 간소화하려면 최소항의 합을 진리표로부터 구한 다음, 곱항의 수와 문자의 수를 줄일 수 있는지 여부를 따져 봐야합니다. 이렇게 하면 곱의 합형태로 간소화한 식을 구할 수 있습니다. 부울함수가 곱의 합형태가 아니라면 분배법칙을 이용하여 표준형으로 바꿀 수 있습니다.

\[F = AC + \overline{A}(B + C\overline{D})\]

위 부울함수를 곱의 합형태로 바꾸면 아래와 같습니다.

\[F = AC + \overline{A}(B + C\overline{D}) = AC + \overline{A}B + \overline{A}C\overline{D}\]

📄합의 곱

대수적으로 표현한 부울함수의 또 다른 표준형은 합의 곱형태로 합항들이 논리곱형태로 구성됩니다. 부울함수가 합의 곱형태가 아니라면 분배법칙을 이용하여 표준형으로 바꿀 수 있습니다.

\[F = AC + \overline{A}(B + C\overline{D})\]

위 부울함수를 합의 곱형태로 바꾸면 아래와 같습니다.

\[\begin{aligned} F &= AC + \overline{A}(B + C\overline{D}) \\ &= (AC + \overline{A})(AC + B + C\overline{D}) \\ &= (A + \overline{A})(C + \overline{A})(A + B + C\overline{D})(C + B + C\overline{D}) \\ &= 1 \cdot (\overline{A} + C)(A + B + C)(A + B + \overline{D})(C + B + C)(C + B + \overline{D}) \\ &= (\overline{A} + C)(A + B + C)(A + B + \overline{D})(B + C)(B + C + \overline{D}) \end{aligned}\]