[DiscreteMath]부울대수

April 29, 2023

📚기본사항Permalink

📄디지털 논리회로Permalink

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

📄기본 논리게이트Permalink

AND 게이트
논리적 곱 $p \land q$ 를 수행하는 기능을 가집니다. 두 개 이상의 입력과 한 개의 출력으로 구성됩니다. 입력이 모두 1인 경우에만 출력이 1이 되고, 그렇지 않은 경우에 출력이 0이 됩니다.
OR 게이트
논리적 합 $p \lor q$ 를 수행하는 기능을 가집니다. 두 개 이상의 입력과 한 개의 출력으로 구성됩니다. 입력 중 어느 한 개 이상이 1인 경우 출력은 1이고, 그렇지 않은 경우에 출력은 0이 됩니다.
NOT 게이트
인버터라고도 부릅니다. 논리적 부정 $\sim p$ 를 수행하는 기능을 가집니다. 한 개의 입력과 한 개의 출력으로 구성됩니다. 입력이 1이면 출력은 0, 입력이 0이면 출력은 1이 됩니다.
NAND 게이트
논리적 곱의 보수 $\sim (p \land q)$ 를 수행하는 기능을 가집니다. 두 개 이상의 입력과 한 개의 출력으로 구성됩니다. 입력 중 한 개 이상의 입력이 0이면 출력은 1이고, 모든 입력이 1일 때만 출력은 0이 됩니다.
NOR 게이트
논리적 합의 보수 $\sim (p \lor q)$ 를 수행하는 기능을 가집니다. 두 개 이상의 입력과 한 개의 출력으로 구성됩니다. 입력들 중 어느 한 개 이상의 입력이 1이면 출력이 0이고, 모든 입력이 0일 때만 출력은 1이 됩니다.
XOR 게이트
배타적 논리합 $p \oplus q$ 을 수행하는 기능을 가집니다. 입력되는 두 비트의 값이 서로 같은지 다른지 비교합니다. 두 개의 입력이 다르면 출력이 1이고, 서로 같으면 출력이 0입니다.
XNOR 게이트
배타적 논리합의 보수 $\sim (p \oplus q)$ 를 수행하는 기능을 가집니다. XOR 연산의 결과에 NOT연산을 취하는 논리게이트입니다.

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

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

📄부울대수Permalink

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

📄부울식Permalink

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

상수 0, 1은 부울식이다.
부울변수는 부울식이다.
X, Y가 부울식일 때, $X + Y, X \cdot Y, \overset{―}{X}, (X)$ 도 부울식이다.

📄부울함수Permalink

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

F (X, Y, Z) = X \overset{―}{Y} + X Y Z + \overset{―}{X} Y Z

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


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

📄논리회로도Permalink

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

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

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

📄부울대수 기본정리Permalink

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

부울대수 기본정리
(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 + \overset{―}{X} = 1$	(8) $X \cdot \overset{―}{X} = 0$
(9) $\overset{―}{\overset{―}{X}} = X$
(10) $X + Y = Y + X$	(11) $X Y = Y X$	교환법칙
(12) $X + (Y + Z) = (X + Y) + Z$	(13) $X (Y Z) = (X Y) Z$	결합법칙
(14) $X (Y + Z) = X Y + X Z$	(15) $X + Y Z = (X + Y) (X + Z)$	분배법칙
(16) $\overset{―}{X + Y} = \overset{―}{X} \cdot \overset{―}{Y}$	(17) $\overset{―}{X \cdot Y} = \overset{―}{X} + \overset{―}{Y}$	드모르간의 법칙
(18) $X + X \cdot Y = X$	(19) $X \cdot (X + Y) = X$	흡수정리

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

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

📄부울함수의 보수Permalink

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

F = \overset{―}{X Y} + X Y \overset{―}{Z}

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

\begin{aligned} \overset{―}{F} & = \overset{―}{\overset{―}{X Y} + X Y \overset{―}{Z}} \\ = \overset{―}{(\overset{―}{X Y}) (X Y \overset{―}{Z})} \\ = (\overset{―}{\overset{―}{X}} + \overset{―}{\overset{―}{Y}}) (\overset{―}{X} + \overset{―}{Y} + \overset{―}{\overset{―}{Z}}) \\ = (X + Y) (\overset{―}{X} + \overset{―}{Y} + Z) \end{aligned}

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

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

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

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

📄항 결합Permalink

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

\begin{aligned} F & = X \overset{―}{Y} + X Y Z + \overset{―}{X} Y Z \\ = X \overset{―}{Y} + (X + \overset{―}{X}) Y Z \\ = X \overset{―}{Y} + 1 \cdot Y Z \\ = X \overset{―}{Y} + Y Z \end{aligned}

📄문자 소거Permalink

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

X + \overset{―}{X} Y = (X + \overset{―}{X}) (X + Y) = 1 \cdot (X + Y) = X + Y

X (\overset{―}{X} + Y) = X \overset{―}{X} + X Y = 0 + X Y = X Y

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

📄중복항 첨가Permalink

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

\begin{aligned} F & = X \overset{―}{Y} Z + X Y Z + \overset{―}{X} Y Z \\ = X \overset{―}{Y} Z + X Y Z + X Y Z + \overset{―}{X} Y Z \\ = X Z (\overset{―}{Y} + Y) + Y Z (X + \overset{―}{X}) \\ = X Z + Y Z \end{aligned}

Share on

Twitter Facebook LinkedIn

Juwon Cha