부울 대수

부울 대수(Boolean Algebra)

• George Boole이 논리적 프로세스들을 표현하기 위하여 개발한 대수학
• 부울 대수에 근거하여 표현되는 부울 함수의 구성 요소들
  • {0,1}
  • 2진 변수들{binary variables)
  • 연산자:
    • 부울 합(Boolean sum)의 기호(+)
    • 부울 곱(Boolean product)의 기호( $ \bullet $ )
• 부울 함수의 예 ) F = A + B'C
  
• 부울 연산의 표현

1. 부울 보수(Boolean complement)

• A' 혹은 $ \bar{A} $ ( A = 1 -> A' =0, A=0 -> A' =1)
• 'A프라임' 으로 읽기로 함
• 인버터로 구현 (F =A')
  

2. 부울 덧셈(Boolean addition)

• OR 게이트로 구현
• 결합법칙 성립
• 부울 덧셈의 규칙*
  0 + 0 = 0
  0 + 1 = 1
  1 + 0 = 1
  1 + 1 = 1
• 2-변수 OR 함수: $ F_{2} = A + B $
  
• 3-변수 OR 함수: $ F_{3} = A + B + C $
  
• 4-변수 OR 함수: $ F_{4} = A + B + C + D $
  

3. 부울 곱셈(Boolean multiplication)

• AND 게이트로 구현
  $0 \cdot 0 = 0$
  $0 \cdot 1 = 0$
  $1 \cdot 0 = 0$
  $1 \cdot 1 = 1$

• 2-변수 AND 함수: $ F_{2} = AB $
  

• 3-변수 AND 함수: $ F_{3} = ABC $
  

• 4-변수 AND 함수: $ F_{4} = ABCD $
  

4. 기타 부울 함수들

• NOR 함수: F = (A+B)'
  
• NAND 함수: F = (AB)'
  

1. 부울 대수의 법칙들

• 부울 대수의 법칙과 규칙들
• 회로 구현에 필요한 부품의 수 및 크기를 최소화함으로써 전력소모를 줄이고 신뢰도를 높인다
  • 경우에 따라 처리 속도도 향상된다
• 교환 법칙성립:
  • A+B = B+A
  • AB = BA
    

    

• 결합 법칙성립
  • (A +B)+C = A + (B + C)
  • A(BC) = (AB)C
    

    

• 분배 법칙:
  • A(B+C) = AB + AC
  • A+ BC = (A+B)(A+C)
    • AA+AB+AC+BC = A(1+B+C) +BC = A+BC
• 팩터링(factoring): 공통 변수의 묶음

ex) AB + AC = A(B+C)

2. 부울 대수의 규칙들

3. 쌍대성의 원리(Principle of Duality)

• AND 연산에 관한 규칙에서 연산자 및 변수 값을 반대로 바꾸면 OR연산자 규칙이 된다 (반대도 성립)

AND <-> OR, 1 <-> 0

4. 드모르간의 정리(DeMorgan's theorem)

• (A + B)' = A' $ \bullet $ B'
• (A $ \bullet $ B)' = A' + B'
• (A + B + C + ...)' = A' $ \bullet $ B' $ \bullet $ C' $ \bullet $ ...
• (A $ \bullet $ B $ \bullet $ C $ \bullet $ ...)' = A' + B' + C' + ...

부울 대수를 이용한 논리회로의 분석

1. 분석 절차

1. 논리회로에 대한 부울함수를 유도한다
2. 유도된 부울함수로부터 회로의 논리적 연산 과정을 파악한다
3. 진리표(truth table)를 작성하여 전체적인 연산 과정 및 입출력 관계를 확인한다

ex)
F = D+C(A+B)를 이용한 회로의 특성 분석 결과

• D = 1이면, 출력 F는 다른 입력 값들에 상관없이 항상 1이 된다.
• D = 0일 때 C = 0이라면, F = 0이 된다.
• D = 0일 떄 C =1 이라면, A와 B중의 어느 하나라도 1이면 F=1이 된다.
  

  

부울 대수를 이용한 논리회로의 설계

1. 동작 정의, 즉 진리표를 작성한다
2. 진리표로부터 함수식을 유도한다.
3. 논리 게이트들을 이용하여 회로를 구성한다.

1. 최소항(minterm)과 최대항(maxterm)

• 진리표로부터 부울 함수를 유도하는 방법
  • 최소항 또는 최대항을 이용

2. 최소항

• 표준 곱(standard product)라고도 부름
• 각 항은 입력변수들 간의 AND 연산 결과가 1이 되도록 표현한 결과에 해당

1. 입력값 = 1인 변수는 정상 형(normal form)으로 표현
2. 입력값 = 0인 변수는 보수 형(complement form)으로 표현

변수들을 곱(product)의 형태로 표현

3. 최대항

• 표준 합(standard sum)라고도 부름
• 각 항은 입력변수들 간의 OR 연산 결과가 0이 되도록 표현한 결과에 해당

1. 입력값 = 0인 변수는 정상 형(normal form)으로 표현
2. 입력값 = 1인 변수는 보수 형(complement form)으로 표현

변수들을 합(sum)의 형태로 표현

부울 함수의 유도