주요 내용 부울 대수 부울 함수의 표현 카노우 맵(Karnaugh Map) 논리 회로의 최소화.

Presentation on theme: "주요 내용 부울 대수 부울 함수의 표현 카노우 맵(Karnaugh Map) 논리 회로의 최소화."— Presentation transcript:

1

2 주요 내용 부울 대수 부울 함수의 표현 카노우 맵(Karnaugh Map) 논리 회로의 최소화

3 부울 대수(Boolean algebra)
부울 대수는 집합 {0, 1}에 대한 연산(operations)과 규칙(rules)을 다룬다. 부울 연산(Boolean operations)  보수 (complementation)  부울 합 (boolean sum)  부울 곱 (boolean product)

4 정의: 보수(complement) 정의: 부울 곱 정의: 부울 합 보수는 ′로 표시
원소 0에 대하여 0′ = 1, 원소 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 (∙는 생략하여 표기하기도 한다.) 연산 우선순위의 정의 여러 부울 연산자가 혼용될 때는 ′ ∙ + 순서 예를 들면, x+y∙z는 x+(y∙z)와 같다.

5 예제 다음 식의 값을 구하라. (1) 1∙0 + (0 + 1') (2) (0 + 1)' ∙ (0 + 1) (1) 1∙0 + (0 + 1') = 1∙0 + (0 + 0)                     = 0 + (0 + 0)                  = 0 + 0                  = 0 (2) (0 + 1)' ∙ (0 + 1) = (1)' ∙ (0 + 1)                          = 0  ∙ (0 + 1)                          = 0  ∙ 1                          = 0

6 정의: 부울 변수(Boolean variable)
정의: 부울 함수(Boolean function) 0 또는 1의 입력값들에 대하여 0 또는 1의 출력값을 갖는 함수이다. 정의: 차수 n의 부울 함수(Boolean function) Bn내의 임의의 n-튜플 {(x1, x2, ..., xn)|xi ∊ B, 1≤i≤n} 에서 B로의 함수

7 예 x, y: 부울 변수 부울 함수 F(x, y) F(1, 1) = 0,  F(1, 0) = 1,  F(0, 1) = 0,  F(0, 0) = 0

8 예제: x, y, z의 부울 변수를 가지는 부울 함수 F(x, y, z)의 진리표를 구하라.
F(1, 1, 1) = 1,  F(1, 1, 0) = 0,   F(1, 0, 1) = 0,   F(1, 0, 0) = 1 F(0, 1, 1) = 1,  F(0, 1, 0) = 0,   F(0, 0, 1) = 0,   F(0, 0, 0) = 1 x y z F(x,y,z) 1

9 정의: 부울 식(Boolean expression)
부울 변수 x1, x2, ..., xn (1) 0, 1, x1, x2, ..., xn은 부울식이다. (2) E1, E2가 부울식이면, E1', (E1⋅E2), (E1+E2)도 부울식이다. 예 부울 변수 x, y에 대해 다음은 부울 식이다. (1) x (2) y (3) x⋅y (4) x+y (5) x+y⋅0 (6) (1+x)' 부울 함수는 부울 변수와 부울 연산자로 구성된 부울 식으로 표현할 수 있다.

10 부울식의 부울 변수에 0, 1을 대입하면 부울 함수 값을
얻을 수 있다. 예: 부울 함수 F(x, y, z) = xy + z일 때 부울 함수 값을 다음 표와 같이 구할 수 있다. x y z xy F(x,y,z) 1

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

12 부울 대수의 법칙 항등성(identity) 법칙 (x')' = x 이중 보수 법칙 (double complement laws)
x + x = x, xx = x 멱등 법칙 (idempotent laws) x + 0 = x, x1= x 항등법칙 (identity laws) x + 1 = x, x0 = 0 지배법칙 (dominance laws) x + y = y + x xy = yx 교환 법칙 (commutative laws) x + (y+ z) = (x+y)+ z 결합 법칙 (associative laws) x+yz = (x+y)(x+z) x(y+z) = xy + xz 분배 법칙 (distributive laws) (xy) ' = x + y (x+y) ' = xy 드모르강의 법칙 (De Morgan's laws) x + x' = 1, xx' = 0 보수 법칙

13 x y z y+z xy xz x(y+z) xy+xz 1 예제: 분배법칙 x(y+z) = xy + xz가 성립하는 것을 보여라.
식이 성립하는 것을 진리표를 이용하여 보일 수 있다. x y z y+z xy xz x(y+z) xy+xz 1

14 예제: 부울 대수의 법칙을 이용하여 다음을 증명하라.
x(x+y) = x x(x+y) = (x+0)(x+y)      (항등법칙)          = x+0y            (분배법칙)          = x +y0           (교환법칙)          = x + 0           (지배법칙)          = x                (항등법칙)

15 정리: 쌍대성의 원리 (duality principle)
부울 대수의 모든 항등 법칙에 대하여 다음 2개의 식이 쌍으로 존재한다. x+0=x, x∙1=x 이러한 쌍을 쌍대(dual)라고 한다. 부울식으로 표현된 함수들 사이에 항등성이 유지되면, 이들의 쌍대(dual)도 항등성을 유지한다. 부울 대수의 쌍대는 ∙과 +를 교환하고, 0과 1을 교환하여 구할 수 있다. 예를 들어, (1) x+(y∙1)의 쌍대는 x∙(y+0) (2) (x+y) = x’y’의 쌍대는 (xy)’=x’+y’

16 예제: 다음 부울식의 쌍대를 구하라.         (1) x +y         (2) x(y+1)         (3) xz' + x0 (4) x+x’(y+1) = x (1) x'y' (2) x'+y'0 (3) (x'+z)(x'+1) (4) x(x+y0) = x

17 <요약> 부울 대수 원소 0과 1을 갖는 집합 B에 대한 연산
두 개의 이진 연산 ∙과 +, 단항 연산 ‘를 갖는다. 다음과 같은 규칙을 만족한다. (x, y, z  B)         x+0 = x   x∙1 = x                            (항등법칙)         x+x' = 1   x∙x' = 0                            (보수법칙)         (x+y)+z = x+(y+z)   (x∙y)∙z = x∙(y∙z)          (결합법칙)         x+y = y+x    x∙y = y∙x                       (교환법칙)         x+(y∙z) = (x+y)∙(x+z)   x∙(y+z) = (x∙y)+(x∙z)   (분배법칙)

18 주요 내용 부울 대수 부울 함수의 표현 카노우 맵(Karnaugh Map) 논리 회로의 최소화

19 최소항 부울 함수 값이 주어졌을 때 이 함수를 부울식으로 표현할 수 있다.
n개의 부울 변수 x1, x2, ... xn으로 이루어진 부울식이 있을때, 이 부울식의 최소항(minterm)은 부울 곱 y1y2...yn이다. 이때, yi=xi 또는 yi=xi이다. 즉, 최소항은 함수의 모든 변수에 대하여 부울 곱을 취한 것으로 변수는 변수 문자 또는 변수 문자의 보수 형태가 한번씩만 나타난다.

20 예제 x1 = 1, x2 = 0, x3 = 1 일 때, 1의 값을 갖는 최소항을 구하라. xi = 1일 때는 yi = xi, xi = 0일 때는 yi = xi'를 취하면 1이 되므로, 최소항은 x1x2'x3이다. 부울 함수의 부울식은 함수의 값이 1이 되는 변수값의 조합들에 대하여 최소항들을 구하고 그 최소항들의 부울 합을 취하면 구할 수 있다.

21 예제: 부울 함수 F(x, y, z)가 다음의 진리표로 주어졌을 때 이 함수를 표현하는 부울식을 구하라.
1 함수 F 값은 x=1, y=1, z=0과 x=0, y=1, z=0일 때 1이고 그 외의 경우는 0이다. 즉, xyz 와 xyz일 때만 함수 값이 1이 되므로 함수의 부울식은 F(x, y, z) = xyz + xyz로 나타낼 수 있다.

22 논리합 형식(disjunctive normal form): 곱들의 합
부울 함수를 최소항들의 부울 합으로 나타내는 형식 논리곱 형식(conjunctive normal form): 합들의 곱 부울 함수를 부울합들의 부울 곱으로 나타내는 형식 이것은 쌍대성을 이용하여 논리합 형식에서부터 구할 수 있다. 예제: 다음 부울 함수를 논리합 형식으로 표현하라. F(x, y) = x' + y x y F(x,y) 1 F(x, y) = xy + x'y + x'y'

23 예제: 다음 함수 F(x, y, z) = (x+y)z'의 곱들의 합을 구하라.
1 함수 F의 곱들의 합은 F(x, y, z) = xyz' + xy'z' + x'yz'

24 주요 내용 부울 대수 부울 함수의 표현 카노우 맵(Karnaugh Map) 논리 회로의 최소화

25 카노우 맵 부울 함수의 간단한 논리합 형식을 찾아내는 방법 두 변수 x, y를 갖는 부울 함수를 위한 카노우 맵은
최소항을 의미한다. (2)부울 함수에서 해당 최소항이 있으면 그 칸을 1로 표시한다.

26 예제: 두 변수를 갖는 다음 부울 함수를 카노우 맵으로 그려라.
  (1) x'y'   (2) xy + xy' + x'y + x'y' (1) (2)

27 부울식의 최소화 하나의 변수만이 다른 최소항들을 서로 인접(adjacent)한다고 한다.
예) x'y와 xy, x'y와 x'y' 카노우 맵에서 두개의 인접한 칸이 1일 때 인접된 칸을 나타내는 최소항은 두 변수 중에서 공통된 변수 하나만으로 나타낼 수 있다. 예) xy'와 x'y'는 변수 y'하나로 나타낼 수 있다. 왜냐하면, xy' + x'y' = (x + x')y' = y' xy x'y x'y' 이러한 성질을 이용하면 주어진 부울식에서 항의 수를 최소화할 수 있다.

28 예제: 다음 부울식을 카노우 맵을 사용하여 최소화하라.
  (1) xy + x'y   (2) xy' + x'y + x'y' xy와 x'y는 서로 인접하며 공통 변수 y로 나타낼 수 있다. x'y와 x'y'는 x'로 나타낼 수 있고, xy'와 x'y'는 y'로 나타낼 수 있다. 따라서 x' + y'로 최소화된다.

29 세 개의 변수를 가진 카노우 맵 xyz 인접하는 네 개의 칸에 1이 있으면 네 개의 최소항은 공통변수
인접하는 네 개의 칸에 1이 있으면 네 개의 최소항은 공통변수 하나의 최소항으로 합성될 수 있다. 예) xyz, xy'z, xyz', xy'z‘ 왜냐하면,     xyz +xy'z + xyz' + xy'z' = (y+y')xz + (y+y')xz'= xz + xz‘ = (z+z')x                                = x 맨 왼쪽 칸과 맨 오른쪽 칸은 이어진 것처럼 간주되며 인접된 칸으로 묶을 수 있다. 최대 인접된 칸을 취하는 방법이 다양할 수 있으므로 구한 최소항도 다양할 수 있다. z xyz xy'z xyz' xy'z' z' xy xy' x'y' x'y

30 예제: 다음 부울식을 카노우 맵을 사용하여 최소화하시오.
  (1) xy'z' + x'y'z'   (2) xy'z + xy'z' + x'y'z + x'y'z' 두 최소항이 인접해 있으므로 공통된 y'z'로 최소화된다. (2) 인접해 있는 네 개의 칸을 묶어서 한 개의 항으로, 즉, 4개의 항이 공통적으로 가지고 있는 y'로 최소화할 수 있다.

31 네 개의 변수를 갖는 카노우 맵 xyzw xy'zw x'y'zw x'yzw xyzw' xy'zw' x'y'zw' x'yzw'
네 개의 변수를 갖는 카노우 맵 xy xy' x'y' x'y zw xyzw xy'zw x'y'zw x'yzw xyzw' xy'zw' x'y'zw' x'yzw' xyz'w' xy'z'w' x'y'z'w' x'yz'w' xyz'w xy'z'w x'y'z'w x'yz'w zw' z'w' z'w 예제: 다음 부울식을 카노우 맵을 사용하여 최소화하라.    xy'zw + xyzw' + xyz'w' + xy'z'w + x'yzw' + x'yz'w' 1 yw' + xy'w

32 주요 내용 부울 대수 부울 함수의 표현 카노우 맵(Karnaugh Map) 논리 회로의 최소화

33 게이트와 부울 연산 기본 게이트 부울 연산 전자 장치의 입력과 출력은 0 또는 1이기 때문에 전자 회로를
설계하는데 부울 대수를 사용할 수 있다. 게이트(gate): 회로의 기본 요소 기본 게이트와 부울 연산과의 매핑 기본 게이트 부울 연산 인버터(inverter) 보수 OR 게이트 부울 합 AND 게이트 부울 곱

34 인버터 하나의 입력과 하나의 출력을 가진다. 입력으로 받은 값의 보수를 출력한다. 즉, 인버터의 입력이 1이면 0을 출력하고 0을 입력하면 1을 출력한다. OR 게이트 두 개 이상의 부울 변수 값을 입력으로 받아 이 값들의 부울 합을 출력한다. AND 게이트 두 개 이상의 부울 변수 값을 입력으로 받아 이 값들의 부울 곱을 출력한다.

35 다음 그림은 부울 식 xy + x'y를 출력하는 회로이다. 하나의 게이트에서 나온 출력이 다른 게이트의 입력이 될 수 있다.
회로를 만드는 법 (1) 회로의 기능을 부울 함수로 표현한다. 부울 함수는 부울 식으로 나타낸다. (2)구한 부울 식을 최소화한다. 예 다음 그림은 부울 식 xy + x'y를 출력하는 회로이다. 하나의 게이트에서 나온 출력이 다른 게이트의 입력이 될 수 있다. xy

36 예제1: 다음 부울 식을 논리 회로로 그려라. (1) x'y' (2) ((x'+z)(y+z'))' (1) (2)

37 예제2: 다음 회로에 해당하는 부울 식을 구하라. (1) xy + (x+y) (2) xyz +xy'z

38 예제3: 두 개의 스위치를 사용하여 전구의 불 켜기를 제어하는 회로가 있다. 전구는 두 스위치가 모두 닫혀있거나 모두
열려있을 때 켜지고 그렇지 않은 경우는 꺼진다고 하자. x=1: 첫 번째 스위치가 닫혀있을 때 x=0: 스위치가 열려있을 때 y=1:두 번째 스위치가 닫혀있을 때 y=0:두 번째 스위치가 열려있을 때 F(x, y) =1: 전구가 켜진 상태 F(x, y) =0: 꺼진 상태 따라서, F(1, 1) = 1, F(0, 0) = 1, F(1, 0) = F(0, 1) = 0 x y F(x,y) 1

39 이 진리표를 사용하여 부울 식을 최소항의 부울 합으로
표현하면 F(x, y) = xy + x'y' 이 부울 함수를 회로로 설계하면 다음과 같다.

40 회로의 비용은 사용되는 게이트 수에 따라 달라진다.
즉, 적은 수의 게이트를 사용하여 회로를 만드는 것이 비용이 적게 든다. 일반적으로 회로를 설계할 때 진리표를 사용하여 최소항의 부울 합으로써 회로를 구성할 수 있다. 예제: 입력 부울 변수가 x, y, z이고 x=1, y=1, z=1일 때와 x=1, y=0, z=1일 때 출력이 1인 회로를 설계하라. 최소항들의 부울 합을 취하여 부울식을 구하면 xyz + xy'z이다. 이것은 카노우 맵을 사용하면 이 부울식은 xz로 단순화할 수 있어 다음과 같이 최소의 게이트를 갖는 간단한 회로를 구성할 수 있다.