이산수학 4. 부울 대수, 논리회로 설계 - swkim0128/PARA GitHub Wiki

type: 이산수학 archive: false

이산수학: 부울대수와 논리회로 설계(1)

논리회로설계 문제를 푸는 과정

논리회로설계 문제 → 입력,출력 정의 → 부울함수 정의 → 부울식 생성 → 부울식 최소화 → 논리회로

⇒ 논리회로설계 문제를 풀기위해 부울대수 필요

부울대수

어떤 명제의 참과 거짓을 이진수 1과 0에 대응시켜서 명제와 명제간의 관계를 수학적으로 표현하는 것이다

종류

보수

  • '로 표시
  • 0' = 1, 1'=0

부울 합

  • (또는 or)로 표시

    1+1=1 1+0=1 0+1=1 0+0=0

부울 곱

  • · (또는 and)로 표시 (·는 생략하여 표기하기도 함)

    1 · 1=1 1 · 0=0 0 · 1=0 0 · 0=0

연산 우선순위 : 보수 > 곱 > 합

부울 변수

  • 집합 S={0,1}의 원소 값만 갖는 변수

부울 함수

  • 0 또는 1의 입력값들에 대하여 0또는 1의 출력값을 갖는 함수

부울 식

  • 하나 또는 여러개의 변수나 기본 연산들이 결합하여 만들어진 형태
  • 0, x, y 와 같은 하나의 부울변수 또한 부울 식으로 볼 수 있다

항등(equivalent)

  • n개의 변수로 이루어진 부울 함수 F, G가 있을때 모든변수 x1, x2, ..., xn 값에 대하여 F(x1, x2, ..., xn) = G(x1, x2, ..., xn) 이면, 부울함수 F와 G는 동등(equivalent)하다고 한다
  • 동일한 변수값에 대해서 진리표의 결과값이 동일하면 두 부울 함수는 동등하다

부울 대수의 법칙

!Untitled 37.png

증명방법

  1. 연산의 정의에 따라 진리값을 만들어 보여주는 방법

  2. 이미 증명된 명제(규칙)를 이용해 증명

    x(x+1) = x 증명 x(x+1) = (x+0)(x+y) (항등법칙) = x+0y (분배법칙) = x+y0 (교환법칙) = x+0 (지배법칙) = x (항등법칙)

정리: 쌍대성의 원리 (duality principle)

  • 주어진 부울식과 그것의 쌍대는 진리값이 같다
  • 부울 대수의 쌍대는 · 과 +를 교환하고, 0과 1을 교환하여 구할수 있다
  • 부울 대수의 모든 항등 법칙에 대하여 다음 2개의 식이 쌍으로 존재한다 x+0 = x , x · 1 = x 이러한 쌍을 쌍대(dual)라고 한다

최소항

  • 함수의 모든 변수에 대하여 부울 곱의 형태로 표현한 것으로 각 변수는 원래 형태 또는 보수형태로 1개만 나타난다

논리합 형식 : 곱들의 합

  • 부울 함수를 최소항들의 부울 합으로 나타내는 형식
  • 함수의 값이 1이되는 변수값의 조합들에 대하여 최소항들을 구하고, 그 최소항들의 부울합을 취하면 부울 식을 구할 수 있다

부울 함수 → 부울 식 예시

x y F(x,y) 1 1 1 ⇒ xy 1 0 0 0 1 1 ⇒ x'y 0 0 1 ⇒ x'y' ⇒ F(x,y) = xy + x'y + x'y'

논리 회로의 설계

이산수학: 부울대수와 논리회로 설계(2)- 수정

전자 장치의 입력과 출력은 0 또는 1이기 때문에 전자 회로를 설계하는데 부울 대수를 사용할 수있다

논리회로의 기본게이트와 부울 연산과의 매핑

기본게이트 | 부울 연산 인버터 : 보수 OR 게이트 : 부울 합 AND 게이트 : 부울 곱

부울식의 최소화

이산수학: 부울대수와 논리 회로 설계(3)- 부울식의 최소화: 카르노 맵

부울식 최소화의 예

xyz' + xy'z' + x'yz' = xyz' + xyz' + xy'z' + x'yz'
= xyz' + xy'z' + xyz' + x'yz'
= xz'y + xz'y' + yz'x + yz'x'
= xz'(y+y') + yz'(x+x')
= xz'·1 + yz'·1
= xz' + yz'

최소화된 부울식을 찾아내는 방법

  • 카르노맵

카르노맵

  • 규칙

    변수가 2개면 2x1, 변수가 3개면 4x2, 변수가 4개면 4x4, ...

    인접하는 칸들은 동일한 변수를 갖고 있어야 한다

    인접되는 칸들은 원통처럼 연결되어 있다

    인접한 칸들을 묶을때는 2^n, 2^(n-1)... 순으로 묶는다 변수가 3개일때는 2^2, 2^1 순서로 인접하는 항을 묶는다 (크게 묶을수 있는거 존재하면 큰거부터 묶어야함)

  • 2변수 카르노맵

    !Untitled20(1).png

  • 3변수 카르노 맵

    !Untitled20(2).png

  • 4변수 카르노 맵

    !Untitled20(3).png

⚠️ **GitHub.com Fallback** ⚠️