2. Boole 대수와 논리 게이트.

Presentation on theme: "2. Boole 대수와 논리 게이트."— Presentation transcript:

1 2. Boole 대수와 논리 게이트

2 Boole 대수와 논리 게이트 기본적인 정의 1. 폐쇄 : 집합 S의 모든 원소 쌍에 대하여 2진식 연산자가 집합 S의 한 원소로 대응된다면 집합 S는 폐쇄되어 있다고 함. 2. 결합법칙 : (x*y)*z=x*(y*z) 모든 x,y,z∈S 에 대해서 3. 교환법칙 : x*y=y*x 모든 x,y∈S 에 대해서 4. 단위원 : 모든 x∈S 에 대해서, e*x=x*e=x ex) 자연수의 집합 I={…, -3, -2, -1, 0, 1, 2, 3, …}, x+0=0+x=x 5. 역원 : 집합 S가 단위원을 가질때 모든 x∈S , y∈S 에 대해 x*y=e 6. 분배법칙 : x*(y z)=(x*y) (x*z)

3 Boole 대수의 기본 이론과 성질 쌍대성 - OR와 AND 연산자들을 교환해주고 1은 0으로, 0은 1로 교환
연산자 우선 순위 1. 괄호 2. NOT 3. AND 4. OR

4 Boole 함수 F1 = x + y'z F2 = x'y'z + x'yz +xy‘ = x'z(y'+y) + xy'
= x'z + xy'

5 Boole함수 – 대수적 조작 Ex 2-1) 다음의 Boole 함수를 최소의 리터럴 수로 간략화하자.
  1. x(x'+y) = xx' + xy = 0 + xy = xy.   2. x +x'y = (x+x')(x+y) = 1(x+y) = x + y.   3. (x+y)(x+y') = x + xy + xy' + yy' = x(1+y+y') = x.   4. xy + x'z + yz = xy + x'z + yz(x+x')                   = xy + x'z + xyz + x'yz                     = xy(1+z) + x'z(1+y)                    = xy + x'z   5. (x+y)(x'+z)(y+z) = (x+y)(x'+z) : 함수 4의 쌍대성에 의함. (A + B + C)'= (A+x)'      B+C=x 로 놓으면 = A'x'          5(a)의 정리에 의함. = A'(B+C)'     B+C=x 를 대입   = A'(B'C')      5(a)의 정리에 의함.   = A'B'C'       4(b)의 정리에 의함. => (A+B+C+D+…+F)' = A'B'C'D'…F' (ABCD…F)' = A' +B'+ C' + D' + … + F'

6 Boole 함수 – 함수의 실수화 Ex 2-2) 함수의 보수를 구하라. F1=x'yz'+x'y'z, F2=x(y'z'+yz).
F1' = (x'yz'+x'y'z)' = (x'yz')'(x'y'z)' = (x+y'+z)(x+y+z') F2' = [x(y'z'+yz)]' = x'+(y'z'+yz)' = x'+(y'z')'(yz)'  = x'+(y+z)(y'+z') Ex 2-3) 쌍대성과 각 리터럴의 보수를 사용해서 예제 2-2의 함수 F1 과 F2 의 함수의 보수를 구하라.   1. F1 = x'yz' + x'y'z.     F1 의 쌍대는 (x'+y+z')(x'+y'+z)    각 리터럴을 보수화 : (x+y'+z)(x+y+z')=F1' 2. F2 = x(y'z'+yz). F2 의 쌍대는 x+(y'+z')(y+z)이다. 각 리터럴을 보수화 : x'+(y+z)(y'+z')=F2'

7 정준과 표준 형식 최소항과 최대항

8 정준과 표준형식 f1 = x'y'z+xy'z'+xyz = m1+m4+m7
f2 = x'yz+xy'z+xyz'+xyz = m3+m5+m6+m7 f1 = (x+y+z)(x+y'+z)(x'+y+z')(x'+y'+z) = M0M2M3M5M6 f2 = (x+y+z)(x+y+z‘)(x+y'+z)(x'+y+z)   = M0M1M2M4

9 정준과 표준형식 최소항의 합 Ex 2-4) Boole 함수 F=A+B'C 를 최소항의 합으로 나타내어라.
A = A(B+B') = AB +AB' = AB(C+C') + AB'(C+C') = ABC + ABC' + AB'C +AB'C' B'C = B'C(A+A') = AB'C + A'B'C F = A + B'C  = A' B'C + AB'C' + AB'C + ABC' + ABC = m1 + m4 + m5 + m6 + m7 = ∑(1, 4, 5, 6, 7)

10 정준과 표준형식 최대항의 곱 Ex 2-5) Boole함수 F = xy + x'z 를 최대항의 곱 형태로 나타내라.
F = xy + x'z = (xy+x')(xy+z) = (x+x')(y+x')(x+z)(y+z) = (x'+y)(x+z)(y+z) x' + y= x' + y + zz'= (x'+y+z)(x'+y+z') x + z= x + z + yy'= (x+y+z)(x+y'+z) y + z= y + z + xx'= (x+y+z)(x'+y+z) F = (x+y+z)(x+y'+z)(x'+y+z)(x'+y+z')   = M0M2M4M5 F(x, y, z) = ∏(0, 2, 4, 5)

11 정준과 표준형식 정준형식 사이의 변환 F(A, B, C) = ∑(1, 4, 5, 6, 7)
F' (A, B, C) = ∑(0, 2, 3) = m0 + m2 + m3 F = (m0+m2+m3)' = m0'm2'm3' = M0M2M3 = ∏(0, 2, 3) , mj' = Mj Ex) F = xy + x'z F(x, y, z) = ∑(1, 3, 6, 7) F(x, y, z) = ∏(0, 2, 4, 5)

12 정준과 표준형식 표준형식 - 곱의 합 : F1 = y' +xy + x'yz'
- 합의 곱 : F2 = x(y'+z)(x'+y+z'+w) - Ex) F3 = AB + C(D+E) = AB +CD + CE

13 기타 논리 연산

14 디지털 논리 게이트

15 디지털 논리 게이트

16 F = [(ABC)'(DE)']' = ABC + DE
디지털 논리 게이트 다중 입력으로의 확장 - NAND와 NOR연산자는 결합법칙이 성립하지 않음. (x↓y)↓z≠x↓(y↓z) (x↓y)↓z= [(x+y)'+z]' = (x+y)z'= xz' + yz' x↓(y↓z)= [x+(y+z)'] ' = x'(y+z)= x'y + x'z x↓y↓z= (x+y+z)' x↑y↑z= (xyz)' F = [(ABC)'(DE)']' = ABC + DE

17 디지털 논리 게이트 - exclusive-OR 양논리와 음논리