[디지털 논리] 2.1 불 대수 개요(Boolean Algebra Introduction)

불 대수(Boolean Algebra)

불 대수 정의

참과 거짓의 두가지 상태를 다루는 논리 수학

특징

스위칭 대수(Switching algebra)

• 두 가지 상태, 두 가지 값이라는 불리언 값만 다룬다

정논리 규약(Positive-logic convention)

• 실제 아날로그 전압의 상태인 낮음과 높음을 각각 논리값 0과 1로 대응 시킨다

단순한 이진수와의 차이

• 불 대수에서 사용하는 0과 1은 수학적인 숫자라기보다는 고전압, 저전압 상태를 나타내는 기호에 가깝다
• 논리 기호 표현: False (F) = 0, True (T) = 1

변수를 통한 신호값 표시

• 신호의 값은 상수가 아닌 변수를 사용하여 나타낸다

핵심 용어 정의

리터럴(literal)

• 변수 그 자체, 또는 변수의 보수(예: $A,A^{\prime }$)

진리표

• 수식에 포함된 변수들이 가질 수 있는 모든 가능한 값의 조합에 대해 논리식이 도출하는 결과를 명시해 놓은 표이다

불 연산자

불 대수에서는 주로 세 가지 기본 연산자를 사용한다. 이는 프로그래밍에서 사용하는 논리 연산자와 완전히 동일한 원리이다

NOT(Inverter, 반전기/보수/반전)

• 입력된 신호의 상태를 정반대로 뒤집는 역할을 한다
• 기호 표기: $X^{\prime }$ 또는 $\bar{X}$

AND(논리곱)

• 주어진 입력이 모두 참일 때만 결과가 참이 되는 연산이다. 스위치가 일렬로 연결된 직렬 회로를 떠올리면 이해가 쉽다
• 기호 표기: $X\cdot Y$ 또는 점을 생략하여 $XY$로 표기

**OR(논리합)

• 주어진 입력 중 하나라도 참이면 결과가 참이 되는 연산이다. 스위치가 나란히 연결된 병렬 회로와 같다
• 기호: $X+Y$

주의

게이트를 그릴때, 가운데 기호는 빼는게 좋다

스위치와 불 연산

논리 연산은 스위치를 켜고 끄는 물지적인 전기 회로에 비유하여 설명할 수 있다

기본 스위치 적용 스위치 연결 상태를 불리언 변수 $X$로 나타낸다

• switch open: 스위치가 끊어져 있어 전류가 흐르지 않는 상태를 의미한다
• switch closed: 스위치가 연결돼ㅣ어 전류가 흐르는 상태를 의미한다

AND 연산: 직렬 연결(Series Connection)

• 수식: $T=A\cdot B$
• 여기서 T는 전달, Transmission을 의미한다

**OR 연산: 병렬 연결(Parallel Connection)

• 수식: $T=A+B$

디지털 논리 연산과 타이밍 다이어그램

스위치 회로가 정적인 상태를 보여준다면, *타이밍 다이어그램은 논리 게이트들이 시간의 흐름에 따라 변하는 디지털 신호에 어떻게 반응하는지를 시각적으로 보여주는 그래프이다

타이밍 다이어그램

• X축: 시간의 흐름을 나타낸다
• Y축: 입력/출력 신호의 전압 상태를 나타낸다
  • 아래쪽은 0(Low, 저전압), 위쪽은 1(High, 고전압)을 나타낸다

불 대수 수식의 계산

비용 분석: 리터럴 개수 세기 리터럴은 논리식에 포함된 변수 또는 변수의 보수를 의미한다, 수식의 복잡도를 파악할 때 리터럴의 총 개수를 세는 것이 도움이 된다

동작 분석: 논리 연산 계산 예제: 조건: A = B = C = 1, D = E = 0 $[A(C+D){]}^{\prime }+BE$ $=[1(1+0){]}^{\prime }+1\cdot 0$ $=[1(1){]}^{\prime }+0$ $=0+0=0$

진리표와 논리 회로

회로의 진리표 작성 논리 게이트로 구성된 회로는 변수들이 가질 수 있는 모든 가능한 값의 조합을 진리표로 만들어 최종 출력값을 한눈에 파악할 수 있다

진리표를 이용한 방정식 증명

불 대수에서 중요한 분배법칙 중 하나인 $A{B}^{\prime }+C=(A+C)(B^{\prime }+C)$가 정말로 성립하는지 진리표를 통해 수학적으로 증명할 수 있다

• 경우의 수 계산: 각 변수는 0또는 1이므로, 변수가 n개일 때 전체 행의 개수는 $2^n$개가 된다. 이 식에서 변수가 총 3개이므로 8개의 행이 필요하다. 따라서 진리표는 아래와 같다

좌변과 우변을 대조해 결과가 일치한다. 따라서 두 식은 논리적으로 동일함이 증명되었다

논리식과 게이트 회로 그리기

논리식을 보고 실제 게이트 회로를 그릴 때는 프로그래밍의 연산자 우선순위와 유사하게 접근한다. 가장 안쪽 괄호부터 바깥쪽으로 AND/NOT 연산에서 OR 연산 순서로 그린다

불 대수의 기본 정리

항등원 및 영원 법칙 $X+0=X$ (아무것도 더하지 않으면 그대로) $X\cdot 1=X$ (1과 AND 연산하면 원래 상태 유지) $X+1=1$ (하나라도 1이면 OR 연산 결과는 무조건 1) $X\cdot 0=0$ (하나라도 0이면 AND 연산 결과는 무조건 0)

멱등 법칙 $X+X=X$ $X\cdot X=X$ 똑같은 값을 여러번 OR 하거나 AND 해도 결과는 원래 값 하나와 같다

이중 부정/ 대합 법칙 $(X^{\prime }{)}^{\prime }=X$ 부정을 다시 부정하면 원래의 상태로 돌아온다

보수 법칙 $X+X^{\prime }=1$ (나와 나의 반대를 OR 하면, 둘 중 하나는 반드시 1이므로 결과는 1) $X\cdot X^{\prime }=0$ (나와 나의 반대를 AND 하면, 둘 중 하나는 반드시 0이므로 결과는 0)

스위치 회로를 이용한 기본 정리 증명

교환법칙과 결합법칙

교환법칙(Commutative Law)

연산자의 앞뒤 순서를 바꿔도 결과는 같다

• AND 연산: $XY=YX$
• OR 연산: $X+Y=Y+X$

결합법칙(Associative Law)

같은 연산자가 연속될 때, 어느 부분을 먼저 묶어서 계산하든 결과는 같다

• AND 연산: $(XY)Z=X(YZ)=XYZ$
• OR 연산: $(X+Y)+Z=X+(Y+Z)=X+Y+Z$
• 결합법칙이 성립하기 때문에, 같은 게이트가 연속될 때는 굳이 괄호를 쓰지 않고 하나로 이어서 표기할 수 있다

AND 연산의 결합법칙 증명

세 변수의 8가지 조합에 대해 각각 계산해보면, 가장 오른쪽 두 열의 결과가 완벽하게 일치라는 것을 볼 수 있다

3-입력(다중 입력) 논리 게이트

결합법칙 덕분에 2개의 입력만 받는 기본 게이트를 여러 개 직렬로 연결하는 대신, 3개 이상의 입력을 한 번에 처리하는 다중 입력 게이트를 논리적으로 그릴 수 있다

분배법칙(Distributive Law)

수식을 전개하거나 공통 인수로 묶어낼 때 사용한다. 특히 제2 분배법칙은 일반 수학에는 없는 불 대수만의 고유한 법칙으므로 반드시 암기해야 한다

제1 분배법칙: $X(Y+Z)=XY+XZ$

제2 분배법칙: $X+YZ=(X+Y)(X+Z)$

간소화 정리와 등가 회로

불 대수의 법칙들을 활용하면 복잡한 수식을 단순하게 줄일 수 있다. 수식이 단순해진다는 것은 곧 회로를 구성하는 게이트의 수가 줄어들어 비용이 절감됨을 의미한다

주요 간소화 정리

• $XY+X{Y}^{\prime }=X(Y+Y^{\prime })=X(1)=X$
• $X+XY=X(1+Y)=X(1)=X$ (흡수 법칙)
• $(X+Y^{\prime })Y=XY+Y^{\prime }Y=XY+0=XY$
• $(X+Y)(X+Y^{\prime })=X+Y{Y}^{\prime }=X+0=X$
• $X(X+Y)=XX+XY=X+XY=X$
• $X{Y}^{\prime }+Y=X+Y$

등가 게이트 회로: 간소화는 회로의 게이트 수를 줄여준다

• 간소화 전 수식: $F=A(A^{\prime }+B)$
• 간소화 과정: $A{A}^{\prime }+AB\to 0+AB\to AB$
• 간소화 후 수식: $F=AB$

논리식의 표준 형태

디지털 논리회로를 설계할 때 수식을 표현하는 가장 대표적인 두 가지 뼈대이다

곱의 합 형태(Sum of Products, SOP)

• 개념: 입력 변수들을 각각 AND(곱) 연산으로 먼저 묶은 다음, 그 결과 그룹들을 마지막에 한 번에 OR(합) 연산으로 더해주는 형태이다

합의 곱 형태(Products of Sum, POS)

• 개념: 입력 변수들을 각각 OR(합) 연산으로 먼저 묶은 다음, 그 결과 그룹들을 마지막에 한 번에 AND(곱) 연산으로 곱해주는 형태이다

수식의 변형

논리식을 우리가 원하는 표준 형태로 만들기 위해 가장 많이 사용하는 방법이다

전개(Expansion)

괄호를 풀어 식을 나열하는 과정이다, 주로 임의의 식을 가장 널리 쓰이는 표준 형태인 곱의 합 형태로 만들기 위해 분배법칙을 사용한다

• 곱의 합 형태의 예시: $ABC+DEFG+H$ (모든 항이 AND 묶음이고, 이들이 OR로 연결됨)
• 주의사항: $(A+B)CD+EF$는 아직 SOP가 아니다. 괄호가 남아있기 때문이죠. 이를 $ACD+BCD+EF$로 풀어줘야 완벽한 SOP가 된다
• 예제:

인수분해(Factoring)

전개의 반대 과정으로, 공통된 리터럴을 묶어내는 과정이다, 주로 식을 합의 곱 형태로 만들기 위해 사용된다

• 합의 곱 형태의 예시: $(A+B)(C+D+E)F$
• 목적: 가끔 SOP보다 POS 형태가 게이트 수를 더 적게 사용할 때가 있어, 하드웨어 최적화 시 두 방법을 모두 고려한다
• 예제:

대수적 조작을 통한 회로 최적화

불 대수의 법칙들을 적절히 섞어 사용하면 회로의 복잡도를 낮출 수 있다 예시:

드모르간의 법칙(De Morgan’s Laws)

불 논리식 전체를 반전 시킬 때 사용하는 법칙이다. 개별 변수들은 반전되고, AND와 OR 연산자는 서로 뒤바뀐다

기본법칙:

• 제1 법칙(OR의 반전): $(X+Y{)}^{\prime }=X^{\prime }\cdot Y^{\prime }$
• 제2 법칙(AND 의 반전): $(XY{)}^{\prime }=X^{\prime }+Y^{\prime }$

진리표

n개의 변수로 확장: 변수가 아무리 많아도 원리는 같다. 전체에 씌어진 바를 리터럴마다 쪼개서 씌워주고, 모든 + 는 $\cdot$으로, 모든 $\cdot$은 +로 바꿔주기만 하면 된다

드모르간 기호의 등가성(Bubble Pushing)

회로도에서 동그라미(버블)를 앞뒤로 옮기며 게이트 모양을 바꾸는 기술이다. 드모르간의 제2법칙인 $(XY{)}^{\prime }=X^{\prime }+Y^{\prime }$ 가 실제 논리 게이트 회로에서 어떻게 똑같이 구현되는지를 시각적으로 보여준다

OR 연산에 대한 적용

드모르간 등가 기호

회로 설계의 치트키와 같은 버블 푸싱 규칙을 정리했다. 왼쪽의 기본 게이트들을 드모르간의 법칙을 이용해 오른쪽의 등가 기호로 바꿀 수 있다

기호 변환의 절대 규칙 2가지:

• 모양 바꾸기: AND는 OR로, OR는 AND로 바꾼다
• 버블 뒤집기: 입력과 출력 모든 단자에 버블이 없으면 붙여주고, 있으면 뗴어낸다(버블 = NOT 연산)

쌍대성(Duality)

불 대수에서 어떤 등식이 참이라면, 그 식의 연산자와 상수를 정반대로 뒤집어 만든 새로운 등식 역시 무조건 참이라는 강력한 윈리이다

쌍대식을 만드는 가장 쉬운 방법:

• AND는 OR로 바꾼다
• OR는 AND로 바꾼다
• 0은 1로 바꾼다
• 1은 0으로 바꾼다

예시(분배 법칙의 쌍대성):

• 본래 식: $X(Y+Z)=XY+XZ$
• 쌍대 식: $X+YZ=(X+Y)(X+Z)$

수학적, 원론적 유도 방법 쌍대성은 사실 “수식 전체를 한 번 보수화(NOT)한 뒤, 각 개별 변수를 다시 한 번 보수화”한 결과와 같다

• 전체 수식 보수화: $f(X_1,X_2,\cdot ,+,0,1)\to f^{\prime }(X_1^{\prime },X_2^{\prime },+,\cdot ,1,0)$
• 각 변수 다시 보수화: $X_i^{\prime }\to X_i$
• 방금 구한 결과에서, 각 알파벳 변수를 정반대로 뒤집어 준다
• $=(X^{\prime }+Y)Z^{\prime }=(X+Y^{\prime })Z=(X{Y}^{\prime }+Z{)}^D$