부울 대수 - 논리 회로

부울 대수 개요 .부울대수와관련된전반적인논제들을학습함 .부울식의기본연산과부울식의법칙및표현방법을설명함 .최소항들의합으로표현되는곱의합을통한부울함수를살펴봄 .부울함수를카노우맵을이용하여간소화하는방법과논리합, 논리곱, 논리부정등의게이트를사용하여부울함수의연산을실행하기위한논리회로를학습함 .논리회로응용분야인전자레인지, 전자투표기, 가산기의경우에대하여살펴봄개요 .부울대수와관련된전반적인논제들을학습함 .부울식의기본연산과부울식의법칙및표현방법을설명함 .최소항들의합으로표현되는곱의합을통한부울함수를살펴봄 .부울함수를카노우맵을이용하여간소화하는방법과논리합, 논리곱, 논리부정등의게이트를사용하여부울함수의연산을실행하기위한논리회로를학습함 .논리회로응용분야인전자레인지, 전자투표기, 가산기의경우에대하여살펴봄 CONTENTS CONTENTS 11.1 부울식 11.2 부울식의 표현 11.3 부울 함수의 간소화 11.4 논리 회로 설계 11.5 논리 회로의 응용 11. 부울대수11. 부울대수 부울 대수 (Boolean algebra) . 1854년 영국의 수학자 부울 (Boole) 이 쓴《사고의 법칙 연구 (An Investigation of the Laws of Thought) 》에서 수학적 논리 형태로 처음 소개됨 . 1938년 섀넌 (Shannon) 이 부울 대수의 기본 개념을 이용하여 회로 함수에 대한 설계로 발전시킴 . 전기 장치나 컴퓨터 회로는 켜짐과 꺼짐의 두 가지 상태로 나타냄 . 스위치나 회로는 닫힘과 열림의 두 가지 상태 중 하나인 참 또는 거짓 , 1 또는 0으로 표현될 수 있음 . 0과 1의 조합으로 연산되는 것을 부울 대수라고 함 Discrete Mathematics Chapter 11. 부울 대수 4 11.1 부울식11.1 부울식 Discrete Mathematics Chapter 11. 부울 대수 5 11.1 부울식11.1 부울식 Discrete Mathematics Chapter 11. 부울 대수 6 11.1 부울식11.1 부울식 Discrete Mathematics Chapter 11. 부울 대수 7 11.1 부울식11.1 부울식 . 부울식에서 부울 변수 x, y, z 가 가질 수 있는 값인 0 또는 1을 정해줌 으로써 각 부울식에 대한 값을 구할 수 있음 . 두 부울식이 같은 진리표 (truth table) 를 가질 경우 두 부울식을 동치 (equivalent) 라함 . 두 함수 f1과 f2가 동치인 경우 f1 ＝ f2로 표시함 Discrete Mathematics Chapter 11. 부울 대수 8 11.1 부울식11.1 부울식 Discrete Mathematics Chapter 11. 부울 대수 9 11.1 부울식11.1 부울식 Discrete Mathematics Chapter 11. 부울 대수 10 11.1 부울식11.1 부울식 Discrete Mathematics Chapter 11. 부울 대수 11 11.1 부울식11.1 부울식 Discrete Mathematics Chapter 11. 부울 대수 12 11.2 부울식의표현11.2 부울식의표현 부울 변수들에 대한 함수를 부울 함수 (Boolean function) 라 하며 , n개의 부울 변수 x1, x2, …, xn에 대한 부울 함수는 f (x1, x2, …, xn)으로 표시함 부울 함수로 표시하면 Discrete Mathematics Chapter 11. 부울 대수 13 11.2 부울식의표현11.2 부울식의표현 부울 함수 (Boolean function) . 부울 변수와 부울 연산자로 구성된 부울식으로 표현할 수 있음 . n개의부울 변수가 있을 때그 변수들로부터 얻을 수있는 조합은 00…0, 00…1, …, 11…1로 2n개임 . 0은 그에 해당되는 원소가 없는 경우임 . 1은 있는 경우로 생각함 최소항 (Minterm) : n개 부울 변수로 만들어지는 진리표에서 변수의 각 조항 N개의 변수 . 2n 개의 최소항 각 최소항들은 n개의 부울 변수의 곱으로 나타낸다 . Discrete Mathematics Chapter 11. 부울 대수 14 11.2 부울식의표현11.2 부울식의표현 Discrete Mathematics Chapter 11. 부울 대수 15 11.2 부울식의표현11.2 부울식의표현 Discrete Mathematics Chapter 11. 부울 대수 16 11.2 부울식의표현11.2 부울식의표현 . 곱의 합 (sum of products) 또는 논리합 표준형 (Disjunctive Normal Form : DNF) 은 부울 함수를 나타내는 데 있어서 최소항들 의 합으로 표현하는 것임 . 최소항들은 부울 변수의 곱으로 표현됨 . 부울 함수는 부울 변수의 곱의 합으로 표현됨 부울 함수 최소항들 중에서 1의 값을 갖는 최소항들의 부울합을 식으로 표현하는 함수 (곱의 합 , sum of products) Discrete Mathematics Chapter 11. 부울 대수 17 11.2 부울식의표현11.2 부울식의표현 Discrete Mathematics Chapter 11. 부울 대수 18 11.2 부울식의표현11.2 부울식의표현 Discrete Mathematics Chapter 11. 부울 대수 19 11.3 부울함수의간소화11.3 부울함수의간소화 . 부울 변수의 최소항들로부터 얻어진 부울 함수는 좀 더 간단한 형태의 식으로 만들 수 있음 . 간소한 형태의 식이란 같은 기능이나 결과를 도출하면서도 더 적은 변수와 연산자를 사용한 식을 말함 . 부울 함수식을 간소하게 표현하는 방법 (1) 부울식의 기본 법칙 사용 (2) 카노우맵을 사용 . 부울식의 법칙을 이용하여 부울 함수를 간소하게 하는 방법은 부울식의 기본 법칙을 이용 하는 것으로 , 그 과정이 복잡하고 간소화에 대한 확인이 쉽지 않음 Discrete Mathematics Chapter 11. 부울 대수 20 11.3 부울함수의간소화11.3 부울함수의간소화 Discrete Mathematics Chapter 11. 부울 대수 21 11.3 부울함수의간소화11.3 부울함수의간소화 . 카노우맵을 그릴 때는 부울 변수들로부터 나타내어지는 모든 경 우의 최소항들을 사각형으로 연결시켜서 , 최소항들 중 1의 값을 가지는 사각형 안에‘ 1’을 표시함 . ‘1’로 표시된 사각형들에서 부울식의 공통점을 찾아내어 부울 함수를 간소화하는데 , 사각형을 연결시킬 때는 인접한 사각형끼 리는 한 변수의 변화만 있게 만듦 예를 들어 , xy와 x’y’ 는 두 변수 모두 다른 값을 가지기 때문에 x와 y가 부울 변수일 때 xy와 x’y’ 는 서로 인접하지 않음 Discrete Mathematics Chapter 11. 부울 대수 22 11.3 부울함수의간소화11.3 부울함수의간소화 (1) 두 변수에 대한 카노우맵 두 변수를 x와 y라할때 , 그에 필요한 사각형은 변수들이 가질 수 있는 모든 경우인 x.y. , x.y , xy . , xy 한 것임 Discrete Mathematics Chapter 11. 부울 대수 23 11.3 부울함수의간소화11.3 부울함수의간소화 . x가 0이고 y가 0일 때는 그에 해당되는 부울식은 x.y. 이됨 . 다른 사각형들도 그 위치에 따라 부울식의 값이 정해짐 예) f(x,y) = x.y. + x.y + xy . 인 경우 이 함수를 카노우 맵으로 나타내면 Discrete Mathematics Chapter 11. 부울 대수 24 11.3 부울함수의간소화11.3 부울함수의간소화 카노우맵의 사각형에 해당되는 논리값이 1이면‘1’로 표시 , 0 이면 그냥 공백으로 남겨둠 ‘1’로 표시된 사각형이 인접할 경우 , 그들을 함께 묶어서 표현하는 방법은 다음과 같음 “두 변수에 대한 카노우맵의 예 ” 1) 서로 인접한 1이 없어서 묶을 수가 없으므로 각각 따로 표현하면 x.y. +xy 가됨 2) y의 값이 0이든 1이든 관계없이 x의 값이 0일때 , 시말 해 x.일때 1의 값을 가지므로 x. 가됨 3) 위의 묶음은 (2)의 경우와 같고 , 아래쪽으로의 묶음은 x 의 값에 관계없이 y. 이므로, 부울식은 x. +y. 가됨 4) x 와 y 의 값에 관계없이 항상 1이므로 부울식은 1이됨 25 11.3 부울함수의간소화11.3 부울함수의간소화 Discrete Mathematics Chapter 11. 부울 대수 26 11.3 부울함수의간소화11.3 부울함수의간소화 (2) 세 변수에 대한 카노우맵 . 변수가 세 개인 경우에는 23＝8개의 사각형이 필요함 . 세 변수에 대한 카노우맵 그림은 아래와 같음 Discrete Mathematics Chapter 11. 부울 대수 27 11.3 부울함수의간소화11.3 부울함수의간소화 세 변수에 대한 카노우맵을 그릴 때 유의해야 할 사항 . yz에 대한 사각형에서 00, 01 다음에 10이 아니라 11이라는 것임 . 두 변수가 한꺼번에 변하는 것은 인접할 수가 없기 때문에 01 옆 에는 10이 아닌 11이옴 . 왼쪽 끝의 사각형들은 오른쪽 끝의 사각형들과 인접되어 있다고 생각해야 함 예) 카노우맵이 아래 그림과 같은 경우에는 서로 연결되어 있다 고 생각하므로 4개의 사각형을 1개로 묶어서 표시하면 z.가됨 Discrete Mathematics Chapter 11. 부울 대수 28 11.3 부울함수의간소화11.3 부울함수의간소화 Discrete Mathematics Chapter 11. 부울 대수 29 11.3 부울함수의간소화11.3 부울함수의간소화 Discrete Mathematics Chapter 11. 부울 대수 30 11.3 부울함수의간소화11.3 부울함수의간소화 (3) 네 변수에 대한 카노우맵 . 네 변수에 대한 카노우맵도 세 변수에 대한 카노우맵과 같이 01 다 음에 11이옴 . 왼쪽 끝 사각형들과 오른쪽 끝 사각형들이 인접하고 있다고 보며 , 위쪽 사각형들과 아래쪽 사각형들 역시 인접하고 있다고 봄 Discrete Mathematics Chapter 11. 부울 대수 31 11.3 부울함수의간소화11.3 부울함수의간소화 Discrete Mathematics Chapter 11. 부울 대수 32 11.3 부울함수의간소화11.3 부울함수의간소화 Discrete Mathematics Chapter 11. 부울 대수 33 11.3 부울함수의간소화11.3 부울함수의간소화 Discrete Mathematics Chapter 11. 부울 대수 34 11.4 논리회로설계11.4 논리회로설계 . 부울 함수로 표현된 식은 컴퓨터에서 사용되는 기본적인 논리 회 로를 설계하는 데 활용함 . 컴퓨터 회로를 설계하는 데 있어서 입력과 출력은 논리 회로의 게 이트(gate) 들을 상호 연결함으로써 구성할 수 있음 . 입력은 부울 변수로 , 출력은 부울 함수로 , 부울 연산자는 게이트로 표현함 . 논리값이 1일 때는 회로의 스위치가 연결된 (on) 상태이고, 0 일때 는 연결되지 않은 (off) 상태를 나타냄 Discrete Mathematics Chapter 11. 부울 대수 35 11.4 논리회로설계11.4 논리회로설계 Discrete Mathematics Chapter 11. 부울 대수 36 11.4 논리회로설계11.4 논리회로설계 (2) 논리합 회로 (OR gate) . 논리합 회로는 논리합 (OR) 조건을 만족시키는 회로로서 입력 A와 B 중 적어도 하나가 1인 경우에 출력 Y가 1이 되는 논리 회로임 . 논리합 연산자는‘＋’로 표현함 . OR 게이트는 스위치가 병렬로 연결되어 있으므로 두 스위치 중 하 나만 1이 되면 회로가 연결됨 Discrete Mathematics Chapter 11. 부울 대수 37 11.4 논리회로설계11.4 논리회로설계 (3) 논리부정 회로 (NOT gate) . 논리부정 회로는 논리부정 (NOT) 조건을 만족시키는 회로로서 입 력 A가 1일 경우에는 출력 Y가 0이됨 . 입력 A가 0일 경우에는 출력 Y가 1이됨 . 논리부정 연산자는 . 또는 -로 표현됨 Discrete Mathematics Chapter 11. 부울 대수 38 11.4 논리회로설계11.4 논리회로설계 . 그 외에 많이 쓰이는 게이트들은 XOR 게이트는‘익스클루시브 (Exclusive) OR ’게이트라고 읽음 . 두 부울 변수가 서로 다른 값을 가질 경우에만 출력이 1이됨 . XOR 게이트의 기호는 OR 게이트의 왼쪽에 활 모양의 곡선을 추가 한 것임 NAND 게이트는 AND 게이트를 부정하는 것임 NOR 게이트는 OR 게이트를 부정하는 것임 Exclusive-NOR 게이트는 exclusive-OR 게이트를 부정 하는 것임 Discrete Mathematics Chapter 11. 부울 대수 39 11.4 논리회로설계11.4 논리회로설계 Discrete Mathematics Chapter 11. 부울 대수 40 11.4 논리회로설계11.4 논리회로설계 Discrete Mathematics Chapter 11. 부울 대수 41 11.4 논리회로설계11.4 논리회로설계 NAND 게이트와 NOR 게이트에 드 모르간의 법칙을 적용하여 표현이 가능함 Discrete Mathematics Chapter 11. 부울 대수 42 11.4 논리회로설계11.4 논리회로설계 Discrete Mathematics Chapter 11. 부울 대수 43 11.4 논리회로설계11.4 논리회로설계 . 부울식을 간소화함으로써 예제 ⑪ -14 (2) 의 복잡한 회로를 (1) 의 간단한 회로로 표현할 수 있음 . 회로를 설계하기 전에 먼저 부울식을 간소화하는 과정이 필요함 Discrete Mathematics Chapter 11. 부울 대수 44 11.4 논리회로설계11.4 논리회로설계 Discrete Mathematics Chapter 11. 부울 대수 45 11.4 논리회로설계11.4 논리회로설계 Discrete Mathematics Chapter 11. 부울 대수 46 11.5 논리회로의응용11.5 논리회로의응용 . 논리 회로의 응용 범위는 넓음 . 어느 제품이든지 회로가 들어가는 것은 모두 논리 회로를 응용한 것임 . 일상생활에서 사용하는 TV를 비롯한 가전 제품들이 대부분 논리 회로를 이용한 것임 . 논리 회로는 엘리베이터를 비롯한 수없이 많은 제품에 응용됨 (1) 전자레인지 . 우리가 가정에서 사용하는 전자레인지에 이용되는 논리 회로를 생 각해 봄 . 전자레인지는 우리가 사용하지 않을 때에는 문이 닫혀 있고 (AND), 타이머가 준비되어 있으며 (AND), 시작 버튼을 누르면 (AND) 전자 레인지가 작동됨 . 논리 회로는 우리 생활과 매우 밀접한 관계가 있음 Discrete Mathematics Chapter 11. 부울 대수 47 11.5 논리회로의응용11.5 논리회로의응용 (2) 전자투표기 . 3명으로 구성된 어떤 위원회에서 의사 결정을 할 때‘찬성’또는 ‘반대’중의 하나로 투표를 하는데 2명 이상이‘찬성’을 할 경 우 안건이 통과됨 . 안건이 통과되는지의 여부를 즉석에서 결정할 수 있는 소규모 전자 투표기의 논리 회로는 아래 그림으로 표현됨 . 전자 투표 회로에서 x, y, z 중 2개씩 묶어서 AND 회로들을 구성됨 . 3개의 AND 게이트 중 어느 2개만 1이 되기만 하면 다음 단계인 OR 게이트에서는 1이 나옴 . 이 논리 회로는 우리가 원하는 것을 만족시킴 Discrete Mathematics Chapter 11. 부울 대수 48 11.5 논리회로의응용11.5 논리회로의응용 (3) 가산기 컴퓨터의 중앙처리장치(CPU) 에 있는 산술논리장치(Arithmetic Logic Unit : ALU) 내에는 숫자들을 더하는 기능을 가진 가산기 (Adder)가 내장됨 Discrete Mathematics Chapter 11. 부울 대수 49 요약요약 Discrete Mathematics Chapter 11. 부울 대수 50 요약요약 Discrete Mathematics Chapter 11. 부울 대수 51 요약요약 Discrete Mathematics Chapter 11. 부울 대수 52 응용응용 . 논리 회로의 생활 속의 응용 . 이루 다 말할 수 없을 정도로 많다 . . 어느 제품이든지 회로가 들어가는 것은 모두 논리 회로를 응용한 것임 . TV를 비롯한 가전 제품들이 대부분 논리 회로를 이용 . 엘리베이터를 비롯한 수없이 많은 제품 Discrete Mathematics Chapter 11. 부울 대수 53 부울 대수 개요 .부울대수와관련된전반적인논제들을학습함 .부울식의기본연산과부울식의법칙및표현방법을설명함 .최소항들의합으로표현되는곱의합을통한부울함수를살펴봄 .부울함수를카노우맵을이용하여간소화하는방법과논리합, 논리곱, 논리부정등의게이트를사용하여부울함수의연산을실행하기위한논리회로를학습함 .논리회로응용분야인전자레인지, 전자투표기, 가산기의경우에대하여살펴봄개요 .부울대수와관련된전반적인논제들을학습함 .부울식의기본연산과부울식의법칙및표현방법을설명함 .최소항들의합으로표현되는곱의합을통한부울함수를살펴봄 .부울함수를카노우맵을이용하여간소화하는방법과논리합, 논리곱, 논리부정등의게이트를사용하여부울함수의연산을실행하기위한논리회로를학습함 .논리회로응용분야인전자레인지, 전자투표기, 가산기의경우에대하여살펴봄 CONTENTS CONTENTS 11.1 부울식 11.2 부울식의 표현 11.3 부울 함수의 간소화 11.4 논리 회로 설계 11.5 논리 회로의 응용 11. 부울대수11. 부울대수 부울 대수 (Boolean algebra) . 1854년 영국의 수학자 부울 (Boole) 이 쓴《사고의 법칙 연구 (An Investigation of the Laws of Thought) 》에서 수학적 논리 형태로 처음 소개됨 . 1938년 섀넌 (Shannon) 이 부울 대수의 기본 개념을 이용하여 회로 함수에 대한 설계로 발전시킴 . 전기 장치나 컴퓨터 회로는 켜짐과 꺼짐의 두 가지 상태로 나타냄 . 스위치나 회로는 닫힘과 열림의 두 가지 상태 중 하나인 참 또는 거짓 , 1 또는 0으로 표현될 수 있음 . 0과 1의 조합으로 연산되는 것을 부울 대수라고 함 Discrete Mathematics Chapter 11. 부울 대수 4 11.1 부울식11.1 부울식 Discrete Mathematics Chapter 11. 부울 대수 5 11.1 부울식11.1 부울식 Discrete Mathematics Chapter 11. 부울 대수 6 11.1 부울식11.1 부울식 Discrete Mathematics Chapter 11. 부울 대수 7 11.1 부울식11.1 부울식 . 부울식에서 부울 변수 x, y, z 가 가질 수 있는 값인 0 또는 1을 정해줌 으로써 각 부울식에 대한 값을 구할 수 있음 . 두 부울식이 같은 진리표 (truth table) 를 가질 경우 두 부울식을 동치 (equivalent) 라함 . 두 함수 f1과 f2가 동치인 경우 f1 ＝ f2로 표시함 Discrete Mathematics Chapter 11. 부울 대수 8 11.1 부울식11.1 부울식 Discrete Mathematics Chapter 11. 부울 대수 9 11.1 부울식11.1 부울식 Discrete Mathematics Chapter 11. 부울 대수 10 11.1 부울식11.1 부울식 Discrete Mathematics Chapter 11. 부울 대수 11 11.1 부울식11.1 부울식 Discrete Mathematics Chapter 11. 부울 대수 12 11.2 부울식의표현11.2 부울식의표현 부울 변수들에 대한 함수를 부울 함수 (Boolean function) 라 하며 , n개의 부울 변수 x1, x2, …, xn에 대한 부울 함수는 f (x1, x2, …, xn)으로 표시함 부울 함수로 표시하면 Discrete Mathematics Chapter 11. 부울 대수 13 11.2 부울식의표현11.2 부울식의표현 부울 함수 (Boolean function) . 부울 변수와 부울 연산자로 구성된 부울식으로 표현할 수 있음 . n개의부울 변수가 있을 때그 변수들로부터 얻을 수있는 조합은 00…0, 00…1, …, 11…1로 2n개임 . 0은 그에 해당되는 원소가 없는 경우임 . 1은 있는 경우로 생각함 최소항 (Minterm) : n개 부울 변수로 만들어지는 진리표에서 변수의 각 조항 N개의 변수 . 2n 개의 최소항 각 최소항들은 n개의 부울 변수의 곱으로 나타낸다 . Discrete Mathematics Chapter 11. 부울 대수 14 11.2 부울식의표현11.2 부울식의표현 Discrete Mathematics Chapter 11. 부울 대수 15 11.2 부울식의표현11.2 부울식의표현 Discrete Mathematics Chapter 11. 부울 대수 16 11.2 부울식의표현11.2 부울식의표현 . 곱의 합 (sum of products) 또는 논리합 표준형 (Disjunctive Normal Form : DNF) 은 부울 함수를 나타내는 데 있어서 최소항들 의 합으로 표현하는 것임 . 최소항들은 부울 변수의 곱으로 표현됨 . 부울 함수는 부울 변수의 곱의 합으로 표현됨 부울 함수 최소항들 중에서 1의 값을 갖는 최소항들의 부울합을 식으로 표현하는 함수 (곱의 합 , sum of products) Discrete Mathematics Chapter 11. 부울 대수 17 11.2 부울식의표현11.2 부울식의표현 Discrete Mathematics Chapter 11. 부울 대수 18 11.2 부울식의표현11.2 부울식의표현 Discrete Mathematics Chapter 11. 부울 대수 19 11.3 부울함수의간소화11.3 부울함수의간소화 . 부울 변수의 최소항들로부터 얻어진 부울 함수는 좀 더 간단한 형태의 식으로 만들 수 있음 . 간소한 형태의 식이란 같은 기능이나 결과를 도출하면서도 더 적은 변수와 연산자를 사용한 식을 말함 . 부울 함수식을 간소하게 표현하는 방법 (1) 부울식의 기본 법칙 사용 (2) 카노우맵을 사용 . 부울식의 법칙을 이용하여 부울 함수를 간소하게 하는 방법은 부울식의 기본 법칙을 이용 하는 것으로 , 그 과정이 복잡하고 간소화에 대한 확인이 쉽지 않음 Discrete Mathematics Chapter 11. 부울 대수 20 11.3 부울함수의간소화11.3 부울함수의간소화 Discrete Mathematics Chapter 11. 부울 대수 21 11.3 부울함수의간소화11.3 부울함수의간소화 . 카노우맵을 그릴 때는 부울 변수들로부터 나타내어지는 모든 경 우의 최소항들을 사각형으로 연결시켜서 , 최소항들 중 1의 값을 가지는 사각형 안에‘ 1’을 표시함 . ‘1’로 표시된 사각형들에서 부울식의 공통점을 찾아내어 부울 함수를 간소화하는데 , 사각형을 연결시킬 때는 인접한 사각형끼 리는 한 변수의 변화만 있게 만듦 예를 들어 , xy와 x’y’ 는 두 변수 모두 다른 값을 가지기 때문에 x와 y가 부울 변수일 때 xy와 x’y’ 는 서로 인접하지 않음 Discrete Mathematics Chapter 11. 부울 대수 22 11.3 부울함수의간소화11.3 부울함수의간소화 (1) 두 변수에 대한 카노우맵 두 변수를 x와 y라할때 , 그에 필요한 사각형은 변수들이 가질 수 있는 모든 경우인 x.y. , x.y , xy . , xy 한 것임 Discrete Mathematics Chapter 11. 부울 대수 23 11.3 부울함수의간소화11.3 부울함수의간소화 . x가 0이고 y가 0일 때는 그에 해당되는 부울식은 x.y. 이됨 . 다른 사각형들도 그 위치에 따라 부울식의 값이 정해짐 예) f(x,y) = x.y. + x.y + xy . 인 경우 이 함수를 카노우 맵으로 나타내면 Discrete Mathematics Chapter 11. 부울 대수 24 11.3 부울함수의간소화11.3 부울함수의간소화 카노우맵의 사각형에 해당되는 논리값이 1이면‘1’로 표시 , 0 이면 그냥 공백으로 남겨둠 ‘1’로 표시된 사각형이 인접할 경우 , 그들을 함께 묶어서 표현하는 방법은 다음과 같음 “두 변수에 대한 카노우맵의 예 ” 1) 서로 인접한 1이 없어서 묶을 수가 없으므로 각각 따로 표현하면 x.y. +xy 가됨 2) y의 값이 0이든 1이든 관계없이 x의 값이 0일때 , 시말 해 x.일때 1의 값을 가지므로 x. 가됨 3) 위의 묶음은 (2)의 경우와 같고 , 아래쪽으로의 묶음은 x 의 값에 관계없이 y. 이므로, 부울식은 x. +y. 가됨 4) x 와 y 의 값에 관계없이 항상 1이므로 부울식은 1이됨 25 11.3 부울함수의간소화11.3 부울함수의간소화 Discrete Mathematics Chapter 11. 부울 대수 26 11.3 부울함수의간소화11.3 부울함수의간소화 (2) 세 변수에 대한 카노우맵 . 변수가 세 개인 경우에는 23＝8개의 사각형이 필요함 . 세 변수에 대한 카노우맵 그림은 아래와 같음 Discrete Mathematics Chapter 11. 부울 대수 27 11.3 부울함수의간소화11.3 부울함수의간소화 세 변수에 대한 카노우맵을 그릴 때 유의해야 할 사항 . yz에 대한 사각형에서 00, 01 다음에 10이 아니라 11이라는 것임 . 두 변수가 한꺼번에 변하는 것은 인접할 수가 없기 때문에 01 옆 에는 10이 아닌 11이옴 . 왼쪽 끝의 사각형들은 오른쪽 끝의 사각형들과 인접되어 있다고 생각해야 함 예) 카노우맵이 아래 그림과 같은 경우에는 서로 연결되어 있다 고 생각하므로 4개의 사각형을 1개로 묶어서 표시하면 z.가됨 Discrete Mathematics Chapter 11. 부울 대수 28 11.3 부울함수의간소화11.3 부울함수의간소화 Discrete Mathematics Chapter 11. 부울 대수 29 11.3 부울함수의간소화11.3 부울함수의간소화 Discrete Mathematics Chapter 11. 부울 대수 30 11.3 부울함수의간소화11.3 부울함수의간소화 (3) 네 변수에 대한 카노우맵 . 네 변수에 대한 카노우맵도 세 변수에 대한 카노우맵과 같이 01 다 음에 11이옴 . 왼쪽 끝 사각형들과 오른쪽 끝 사각형들이 인접하고 있다고 보며 , 위쪽 사각형들과 아래쪽 사각형들 역시 인접하고 있다고 봄 Discrete Mathematics Chapter 11. 부울 대수 31 11.3 부울함수의간소화11.3 부울함수의간소화 Discrete Mathematics Chapter 11. 부울 대수 32 11.3 부울함수의간소화11.3 부울함수의간소화 Discrete Mathematics Chapter 11. 부울 대수 33 11.3 부울함수의간소화11.3 부울함수의간소화 Discrete Mathematics Chapter 11. 부울 대수 34 11.4 논리회로설계11.4 논리회로설계 . 부울 함수로 표현된 식은 컴퓨터에서 사용되는 기본적인 논리 회 로를 설계하는 데 활용함 . 컴퓨터 회로를 설계하는 데 있어서 입력과 출력은 논리 회로의 게 이트(gate) 들을 상호 연결함으로써 구성할 수 있음 . 입력은 부울 변수로 , 출력은 부울 함수로 , 부울 연산자는 게이트로 표현함 . 논리값이 1일 때는 회로의 스위치가 연결된 (on) 상태이고, 0 일때 는 연결되지 않은 (off) 상태를 나타냄 Discrete Mathematics Chapter 11. 부울 대수 35 11.4 논리회로설계11.4 논리회로설계 Discrete Mathematics Chapter 11. 부울 대수 36 11.4 논리회로설계11.4 논리회로설계 (2) 논리합 회로 (OR gate) . 논리합 회로는 논리합 (OR) 조건을 만족시키는 회로로서 입력 A와 B 중 적어도 하나가 1인 경우에 출력 Y가 1이 되는 논리 회로임 . 논리합 연산자는‘＋’로 표현함 . OR 게이트는 스위치가 병렬로 연결되어 있으므로 두 스위치 중 하 나만 1이 되면 회로가 연결됨 Discrete Mathematics Chapter 11. 부울 대수 37 11.4 논리회로설계11.4 논리회로설계 (3) 논리부정 회로 (NOT gate) . 논리부정 회로는 논리부정 (NOT) 조건을 만족시키는 회로로서 입 력 A가 1일 경우에는 출력 Y가 0이됨 . 입력 A가 0일 경우에는 출력 Y가 1이됨 . 논리부정 연산자는 . 또는 -로 표현됨 Discrete Mathematics Chapter 11. 부울 대수 38 11.4 논리회로설계11.4 논리회로설계 . 그 외에 많이 쓰이는 게이트들은 XOR 게이트는‘익스클루시브 (Exclusive) OR ’게이트라고 읽음 . 두 부울 변수가 서로 다른 값을 가질 경우에만 출력이 1이됨 . XOR 게이트의 기호는 OR 게이트의 왼쪽에 활 모양의 곡선을 추가 한 것임 NAND 게이트는 AND 게이트를 부정하는 것임 NOR 게이트는 OR 게이트를 부정하는 것임 Exclusive-NOR 게이트는 exclusive-OR 게이트를 부정 하는 것임 Discrete Mathematics Chapter 11. 부울 대수 39 11.4 논리회로설계11.4 논리회로설계 Discrete Mathematics Chapter 11. 부울 대수 40 11.4 논리회로설계11.4 논리회로설계 Discrete Mathematics Chapter 11. 부울 대수 41 11.4 논리회로설계11.4 논리회로설계 NAND 게이트와 NOR 게이트에 드 모르간의 법칙을 적용하여 표현이 가능함 Discrete Mathematics Chapter 11. 부울 대수 42 11.4 논리회로설계11.4 논리회로설계 Discrete Mathematics Chapter 11. 부울 대수 43 11.4 논리회로설계11.4 논리회로설계 . 부울식을 간소화함으로써 예제 ⑪ -14 (2) 의 복잡한 회로를 (1) 의 간단한 회로로 표현할 수 있음 . 회로를 설계하기 전에 먼저 부울식을 간소화하는 과정이 필요함 Discrete Mathematics Chapter 11. 부울 대수 44 11.4 논리회로설계11.4 논리회로설계 Discrete Mathematics Chapter 11. 부울 대수 45 11.4 논리회로설계11.4 논리회로설계 Discrete Mathematics Chapter 11. 부울 대수 46 11.5 논리회로의응용11.5 논리회로의응용 . 논리 회로의 응용 범위는 넓음 . 어느 제품이든지 회로가 들어가는 것은 모두 논리 회로를 응용한 것임 . 일상생활에서 사용하는 TV를 비롯한 가전 제품들이 대부분 논리 회로를 이용한 것임 . 논리 회로는 엘리베이터를 비롯한 수없이 많은 제품에 응용됨 (1) 전자레인지 . 우리가 가정에서 사용하는 전자레인지에 이용되는 논리 회로를 생 각해 봄 . 전자레인지는 우리가 사용하지 않을 때에는 문이 닫혀 있고 (AND), 타이머가 준비되어 있으며 (AND), 시작 버튼을 누르면 (AND) 전자 레인지가 작동됨 . 논리 회로는 우리 생활과 매우 밀접한 관계가 있음 Discrete Mathematics Chapter 11. 부울 대수 47 11.5 논리회로의응용11.5 논리회로의응용 (2) 전자투표기 . 3명으로 구성된 어떤 위원회에서 의사 결정을 할 때‘찬성’또는 ‘반대’중의 하나로 투표를 하는데 2명 이상이‘찬성’을 할 경 우 안건이 통과됨 . 안건이 통과되는지의 여부를 즉석에서 결정할 수 있는 소규모 전자 투표기의 논리 회로는 아래 그림으로 표현됨 . 전자 투표 회로에서 x, y, z 중 2개씩 묶어서 AND 회로들을 구성됨 . 3개의 AND 게이트 중 어느 2개만 1이 되기만 하면 다음 단계인 OR 게이트에서는 1이 나옴 . 이 논리 회로는 우리가 원하는 것을 만족시킴 Discrete Mathematics Chapter 11. 부울 대수 48 11.5 논리회로의응용11.5 논리회로의응용 (3) 가산기 컴퓨터의 중앙처리장치(CPU) 에 있는 산술논리장치(Arithmetic Logic Unit : ALU) 내에는 숫자들을 더하는 기능을 가진 가산기 (Adder)가 내장됨 Discrete Mathematics Chapter 11. 부울 대수 49 요약요약 Discrete Mathematics Chapter 11. 부울 대수 50 요약요약 Discrete Mathematics Chapter 11. 부울 대수 51 요약요약 Discrete Mathematics Chapter 11. 부울 대수 52 응용응용 . 논리 회로의 생활 속의 응용 . 이루 다 말할 수 없을 정도로 많다 . . 어느 제품이든지 회로가 들어가는 것은 모두 논리 회로를 응용한 것임 . TV를 비롯한 가전 제품들이 대부분 논리 회로를 이용 . 엘리베이터를 비롯한 수없이 많은 제품 Discrete Mathematics Chapter 11. 부울 대수 53