최소항(minterm) 모든 변수가 단지 한번씩 사용되어 logical AND된 형태의 function으로 n개의 변수에 대해 2n개의 최소항 존재 진리표에서 변수들의 각 조합 변 수 최소항(minterm) 최대항(maxterm) x y z 논리식 기호 항 xyz m0 x + y + z M0 1 xyz m1 x + y + z M1 xy z m2 x + y+ z M2 xy z m3 x + y+ z  M3 x yz m4 x+ y + z M4 x yz m5 x+ y + z M5 x y z m6 x+ y+ z M6 x y z m7 x+ y+ z M7

변 수 최소항(minterm) 최대항(maxterm) w x y z 논리식 기호 항 wxyz m0 w + x + y + z M0 1 wxyz m1 w + x + y + z M1 wxy z m2 w + x + y+ z M2 wxy z m3 w + x + y+ z  M3 wx yz m4 w + x+ y + z M4 wx yz m5 w + x+ y + z M5 wx y z m6 w + x+ y+ z M6 wx y z m7 w + x+ y+ z M7 w xyz m8 w+ x + y + z M8 w xyz m9 w+ x + y + z M9 w xy z m10 w+ x + y+ z M10 w xy z m11 w+ x + y+ z  M11 w x yz m12 w+ x+ y + z M12 w x yz m13 w+ x+ y + z M13 w x y z m14 w+ x+ y+ z M14 w x y z m15 w+ x+ y+ z M15

진리표 ↔ 논리식 ↔회로도 변환 진리표 논리식 입력 출력 x y z F 1 xyz + xyz 진리표 ↔ 논리식 ↔회로도 변환 진리표 논리식 출력이 1인 최소항들을 OR로 연결 입력 출력 x y z F 1 xyz + xyz F = xyz + xyz + xyz xyz

논리식 진리표 F = x + yz 입력 출력 x y z F 1 1 1 1 1 논리식 각 항별로 1이 되는 경우에 대한 진리표 출력 칸에 1을 기록 F = x + yz 입력 출력 x y z F 1 1 1 1 1

논리식 F = xy + xz 회로도

회로도 논리식 F = xy + xz xy x xy + xz xz

논리함수 간소화 1. Algebraic manipulation (대수학적 처리) 2. Karnaugh map (Veitch diagram) (카노맵 이용) 3. Tabulation method (도표 이용)

카노맵 ( Karnaugh Map ) yz wx 00 01 11 10 y x 1 yz x 00 01 11 10 1 순서주의 y x 1 yz x 00 01 11 10 1 2변수 카노맵 3변수 카노맵 4변수 카노맵

진리표와 카노맵 대응관계 진리표 카노맵 입력 출력 x y z F 1 yz x 00 01 11 10 1 xyz 1 1 1 순서주의 yz x 00 01 11 10 1 xyz ⓞ ① ② ③ ④ ⑤ ⑥ ⑦ 1 1 xyz ⓞ ① ③ ② 1 ④ ⑤ ⑦ ⑥ xyz

카노맵에서 인접한 네모칸 yz x 00 01 11 10 1 xyz xyz 1 + = xy(z+z) = xy 1 xyz ⓞ xyz ① 1 ① ② ③ ④ ⑤ ⑥ ⑦ ⓞ + = xy(z+z) = xy yz x 00 01 11 10 1 xyz ④ xyz ⑥ 인접 + = xz(y+y) = xz ① ② ③ ④ ⑤ ⑥ ⑦ ⓞ 1

카노맵에서 인접한 네모칸 wxyz wxyz wxyz wxyz yz wx 00 01 11 10 1 + + + ① wxyz ③ wxyz ⑤ wxyz ⑦ yz wx 00 01 11 10 1 + + + ① ② ③ ④ ⑤ ⑥ ⑦ ⓞ ⑬ ⑭ ⑮ ⑧ ⑨ ⑩ ⑪ ⑫ = wx(y+y)z + wx(y+y)z = wxz + wxz = w(x+x)z = wz yz wx 00 01 11 10 1 인접 = xz

카노맵을 이용한 논리식 간소화 절차 단계 1 변수 갯수에 따른 카노맵을 그림 단계 2 논리식을 1로 하는 카노맵의 네모칸에 1을 기록 단계 2 1이 들어있는 인접한 칸들끼리 그룹화 (그룹화 알고리즘 참조) 단계 3 각 그룹에 대한 논리식을 OR 연산자로 연결하여 최종 논리식을 구함 단계 4

카노맵 그룹화 알고리즘 ① 먼저 혼자 떨어져 있는 1부터 그룹화 시작 ② 단지 2개로만 묶을 수 있는 인접한 1들을 그룹화 (단 2가지 이상의 방법으로 그룹화 할 수 있는 1들은 보류함) ③ 아직 그룹화 안된 1들중 단지 4개로만 묶을 수 있는 인접한 1들을 그룹화 ④ 아직 그룹화 안된 1들중 단지 8개로만 묶을 수 있는 인접한 1들을 그룹화 ⑤ 아직 그룹화 안된 1들을 묶되, 가능한 한 크게 2n개를 그룹화 ⑥ 모든 1이 적어도 한 그룹에는 속하도록 위의 ⑤번 단계 반복 ※ 무정의 조건(don't care) x는 1 또는 0으로 볼 수 있으며, 그룹을 크게 하는 x를 1로 취급하여 그룹화 함.

예 제 진리표 카노맵 입력 출력 x y z F 1 yz x 00 01 11 10 1 1 1 1 F = xyz + xy 예 제 아래 진리표에 대해 카노맵을 이용하여 간소화된 논리식을 구하라. 진리표 카노맵 입력 출력 x y z F 1 순서주의 yz x 00 01 11 10 1 ⓞ ① ② ③ ④ ⑤ ⑥ ⑦ 1 1 ⓞ ① ③ ② 1 ④ ⑤ ⑦ ⑥ F = xyz + xy

F(A,B,C) = AC + AB + ABC + BC 를 간소화 하시오. BC A 00 01 11 10 예 제 F(A,B,C) = AC + AB + ABC + BC 를 간소화 하시오. BC A 00 01 11 10 1 1 1 F = AB + C ① ② ③ ④ ⑤ ⑥ ⑦ ⓞ 1 1

예 제 F(w,x, y, z) = (0, 1, 2, 4, 5, 6, 8, 9, 12, 13) 를 간소화 하시오. yz wx 예 제 F(w,x, y, z) = (0, 1, 2, 4, 5, 6, 8, 9, 12, 13) 를 간소화 하시오. yz wx 00 01 11 10 1 1 1 ① ② ③ ④ ⑤ ⑥ ⑦ ⓞ ⑬ ⑭ ⑮ ⑧ ⑨ ⑩ ⑪ ⑫ 1 1 1 F = wz + y 1 1 1 1

아래 카노맵에 대한 간소화된 논리식을 구하시오. (단, 카노맵에서 x는 무정의 조건(don’t care)을 의미함) BC A 예 제 아래 카노맵에 대한 간소화된 논리식을 구하시오. (단, 카노맵에서 x는 무정의 조건(don’t care)을 의미함) BC A 00 01 11 10 1 x ① ② ③ ④ ⑤ ⑥ ⑦ ⓞ F = BC + A

무정의 조건(don’t care condition) 어떤 최소항의 값이 1 이든 0 이든 관계 없이 일정 한 함수 값을 갖는 경우 그 최소항을 무정의 조건이라고 함. 카노맵에서 무정의 조건의 표시는 x 또는 d 로 표시하며, 간소화시 1 또는 0으로 취급할 수 있으나 일반적으로 그룹을 크게 하는 x를 1로 취급함. 0-5값만 입력. 3 입력시에만 출력=1 조합 회로 x y z F 블록도 입력 출력 x y z F 1 yz x 00 01 11 10 1 1 ⓞ ① ② ③ ④ ⑤ ⑥ ⑦ 1 ① ② ③ ④ ⑤ ⑥ ⑦ ⓞ x x F = yz 카노맵과 논리식 x 무정의 조건 진리표

무정의 조건 간소화 예 (1) yz x 00 01 11 10 1 yz x 00 01 11 10 1 F = yz + x 1 yz x 00 01 11 10 1 ① ② ③ ④ ⑤ ⑥ ⑦ ⓞ ① ② ③ ④ ⑤ ⑥ ⑦ ⓞ F = yz + x F = 1

무정의 조건 간소화 예 (2) yz wx 00 01 11 10 x 1 yz wx 00 01 11 10 x 1 F = yz + ① ② ③ ④ ⑤ ⑥ ⑦ ⓞ ⑬ ⑭ ⑮ ⑧ ⑨ ⑩ ⑪ ⑫ ① ② ③ ④ ⑤ ⑥ ⑦ ⓞ ⑬ ⑭ ⑮ ⑧ ⑨ ⑩ ⑪ ⑫ F = yz + wx F = yz + wz

디지털회로 분류 조합회로 순차회로 조합회로 설계절차 과거의 입력에 관계없이 현재의 입력값의 조합에 의하여 출력이 결정되는 회로(기억능력이 없음) 현재의 입력과 과거의 입력에 의하여 출력이 결정되는 회로. 입력과 플립플롭과 같은 기억장치의 현재상태에 의해서 출 력이 결정되는 회로 순차회로 조합회로 설계절차 문제 정의 입출력 변수 개수 및 문자기호 할당 진리표 작성 간소화된 논리식 작성 회로도 작성 회로 구성 및 실험

예 제 조 합 논 리 회 로 설 계 입력에 ‘0’의 개수보다 ‘1’의 개수가 더 많이 인가될 때 예 제 조 합 논 리 회 로 설 계 입력에 ‘0’의 개수보다 ‘1’의 개수가 더 많이 인가될 때 출력이 ‘1’이 되는 4입력 조합논리회로를 설계하라. 1.문제정의 2. 입력,출력 변수 개수 결정 및 문자기호 할당 입력변수 (4개) : A, B, C, D 출력변수 (1개) : F

3. 진리표 작성 입 력 출력 A B C D F 1 4. 부울 함수로 논리식 작성 CD AB 00 01 11 10 1 1 1 1 1 1 1 F = 1 ABC + ABD + ACD + BCD

5.회로도 작성 F = ABC + ABD + ACD + BCD

곱의합(sum of products) 형태 논리식 합의곱(product of sums) 형태 논리식 곱의합, 합의곱 형태의 논리식 곱의합(sum of products) 형태 논리식 F1 = xy + yz + xz F2 = ABC + ABD + ACD 합의곱(product of sums) 형태 논리식 F3 = (x+y)(y+z)(x+z) F4 = (A+B+C)(A+B+D)(A+C+D)

곱의합 형태 yz x 00 01 11 10 1 진리표 1 1 1 1 1 입력 출력 x y z F 1 F = xz + y 합의곱 형태 yz x 00 01 11 10 1 F = xy + yz F = (F) = (xy+yz) = (x+y)(y+z)

NAND 또는 NOR gate만을 사용한 회로 설계 NAND나 NOR 게이트는 AND 또는 OR 게이트에 비해 제조하기 쉽기 때문에 디지털 회로에서 AND 또는 OR 게이트에 비해 NAND나 NOR 게이트를 많이 사용한다. DeMorgan’s Law

Involution Law NOT 게이트

NAND 게이트 회로구현 곱의합 형태로 논리식을 간소화

NOR 게이트 회로구현 합의곱 형태로 논리식을 간소화

XOR 게이트 XNOR 게이트

Tabulation (Quine-McCluskey) Method 예제 아래 논리함수를 tabulation method를 사용하여 간소화 하라. F(w,x,y,z) = S (1, 4, 6, 7, 8, 9, 10, 11, 15) (1) 먼저 PI(prime implicant) 들을 구함. 0001 0001 1 V 1,9 (8) 0100 0100 4 V 4,6 (2) 0110 1000 8 V V 8,9 (1) V 0111 0110 6 V 8,10 (2) V 1000 1001 9 V 8,9,10,11 (1,2) 6,7 (1) 1001 1010 10 V 8,9,10,11 (1,2) 9,11 (2) 1010 0111 7 V 10,11 (1) 1011 1011 11 V 7,15 (8) 1111 1111 15 11,15 (4) 1. 민텀을 차례로 씀 2. 포함하고 있는 1갯수가 같은것끼리 모아 섹션 만듬.(우측에 10진수표시) 3. 인접섹션간 10진수값 비교하여 아래 섹션 값이 2의 멱승만큼 큰 쌍을 골라 V 표시하고, 우측에 따로모아 섹션 만듬.(괄호안에 두수의 차이 씀) 4. 인접한 두섹션간에 괄호안의 수가 같은 것끼리에 대해서만 절차3 반복 5. V표시 안된것들이 PI 임

F = xyz + wxz + wx + xyz (2) PI(prime implicant) 들중 함수를 최소화하는 것들만 골라 OR로 연결. 1 4 6 7 8 9 10 11 15 2. 민텀 번호를 차례로 씀 V 1,9 (8) V V 4,6 (2) V 6,7 (1) V 3. 해당자리에 V 표시 7,15 (8) V 11,15 (4) V V 8,9,10,11 (1,2) V 5. EPI가 cover하는 모든 민텀들을 V 표시 V V V 7. 답은 EPI + 단계6 결과 1. PI 들을 차례로 씀 6. 아직 cover되지 않은 민텀들을 포함할 수 있는 PI를 선택(가능한 가장 작은 개수로 되도록 선택 0001 1,9 (8) -001 xyz 1001 4. 각 컬럼에 오직 1개의 V 표시만 있는 컬럼을 골라 그것에 해당하는 PI에 V 표시 (EPI : essential prime implicant) wxyz 4,6 (2) 0100 01-0 wxz 8,9,10,11 (1,2) 1000 10-- wx 7,15 (8) 0111 -111 xyz F = xyz + wxz + wx + xyz

F = xyz + wxz + xyz + wx 예 제 아래 논리함수를 tabulation method를 사용하여 간소화하고, 앞에서 테이블을 이용한 방법의 결과와 비교하라. F(w, x, y, z) = (1, 4, 6, 7, 8, 9, 10, 11, 15) F = xyz + wxz + xyz + wx 카노맵 으로 확인 yz wx 00 01 11 10 1 F = xyz + wxz + xyz + wx

예제 아래 논리함수를 tabulation method를 사용하여 간소화 하라. F(w,x,y,z) = S (0, 1, 2, 8, 10, 11, 14, 15) (1) 먼저 PI(prime implicant) 들을 구함. 0,1 (1) 0000 0000 0 V V V 0,2 (2) V 0001 0001 1 0,8 (8) V 0,2,8,10 (2,8) 0010 0010 2 V 2,10 (8) 0,2,8,10 (2,8) 1000 1000 8 V 8,10 (2) 1010 1010 10 V V 10,11 (1) V 1011 1011 11 V 10,14 (4) V 10,11,14,15 (1,4) 1110 1110 14 V 11,15 (4) 10,11,14,15 (1,4) 1111 1111 15 14,15 (1) 1. 민텀을 차례로 씀 2. 포함하고 있는 1갯수가 같은것끼리 모아 섹션 만듬.(우측에 10진수표시) 3. 인접섹션간 10진수값 비교하여 아래 섹션 값이 2의 멱승만큼 큰 쌍을 골라 V 표시하고, 우측에 따로모아 섹션 만듬.(괄호안에 두수의 차이 씀) 4. 인접한 두섹션간에 괄호안의 수가 같은 것끼리에 대해서만 절차3 반복 5. V표시 안된것들이 PI 임

5. EPI가 cover하는 모든 민텀들을 V 표시 (2) PI(prime implicant) 들중 함수를 최소화하는 것들만 골라 OR로 연결. 2. 민텀 번호를 차례로 씀 1 2 8 10 11 14 15 V 0,1 (1) V 3. 해당자리에 V 표시 V 0,2,8,10 (2,8) V V 10,11,14,15 (1,4) V 5. EPI가 cover하는 모든 민텀들을 V 표시 V V V 1. PI 들을 차례로 씀 6. 답은 EPI 4. 각 컬럼에 오직 1개의 V 표시만 있는 컬럼을 골라 그것에 해당하는 PI에 V 표시 (EPI : essential prime implicant) 0,1 (1) 0000 000- wxy 0,2,8,10 (2,8) 0000 -0-0 xz 10,11,14,15 (1,4) 1010 1-1- wy F = wxy + xz + wy

yz wx 00 01 11 10 1 F = wxy + xz + wy 예 제 아래 논리함수를 tabulation method를 사용하여 간소화하고, 테이블을 이용한 방법의 결과와 비교하라. F(w, x, y, z) = (0, 1, 2, 8, 10, 11, 14, 15)) F = wxy + xz + wy 카노맵 으로 확인 yz wx 00 01 11 10 1 F = wxy + xz + wy