부울대수(Boolean Algebra)

Slides:



Advertisements
Similar presentations
법의 이념과 철학의 이해 법의 이념은 무엇일까 ? 정의 : 각자에게 각자의 몫을 주는 것 - 평등의 의미가 내포되어 있음 법적 안정성 : 법의 규정이 명확하고 잦은 변경 이 없어야 함 개인의 자유와 권리를 공공복지와 조화롭게 추구 – 사회질서와 안전유지 + 사회정의.
Advertisements

식품사업부 8 월 기도회 2006 년 8 월 9 일. 7 월 감사제목 1. 7 월에도 매장에서 안전사고와 고객클레임 없이 무사히 영업을 하게 해주셔서 감사 합니다. 2. 지난 번 폭우때 매장의 안전과 재산을 지켜주시고 직원들의 건강을 지켜주셔서 감사합니다. 3. 어려운.
 수학 10- 나  1 학년 2 학기  Ⅰ. 도형의 방정식 1. 평면좌표 (1/24) 두 점 사이의 거리 수업 계획 수업 활동.
수학과 김 지하 제 5 장 문제해결의 지도 5.1 문제와 문제해결의 정의.
5 학년 6 반 김진석.  애니메이션은 라틴어의 아니마 에서 온 것이다. 아니마 는 생명 영혼 정신을 가르키는 것리다.  애니메이션의 원리는 그림을 움직이는 환등기로 만드는데, 환등기는 인간이 가지고 있는 눈의 잔상 을 이용해 만들어 졌다.  최초의 애니메이션 작품은.
CHAPTER 5 KARNAUGH MAPS( 카노 맵 ) This chapter in the book includes: Objectives Study Guide 5.1Minimum Forms of Switching Functions 5.2Two- and Three-Variable.
디 지 털 공 학디 지 털 공 학 한국폴리텍 V 대학.
C-aC-bA-bB-aB-bB-cA-aA-c A. Head Section. A-b B-a B-b B-c C A-a A-c Top page.
4장 축하중 축하중 부재의 변형을 구하는 방법 지점반력(부정정 문제). 열응력. 응력집중. 비탄성 변형. 잔류응력.
지적기초측량 경일대학교/부동산지적학과.
1.다음 동물들을 조류와 포유류로 분류하여 빈 곳에 써 넣어라.
1. 비정규노동이란 2. 비정규노동의 확대 원인 3. 비정규노동자의 삶 4. 비정규노동의 문제
제7장 빈곤아동 담당교수 : 이 상 신.
컴파일러 입문 제 5 장 Context-Free 문법.
Compiler Lecture Note, Inroduction to FL theory
3장. 디지털 회로 Lecture #3.
Ⅲ. 5S • 3정.
해시 함수.
제2장 부울대수와 논리 게이트 내용 2.1 논리신호 2.2 기본 논리함수 : NOT 게이트(INV 게이트)/ AND 게이트/ OR 게이트 2.3 부울대수 : 부울대수의 정의와 사용 / 부울대수의 기본법칙/ 쌍대성/ 드모르강 정리 2.4 만능 게이트 : NAND.
울산 남구 달동 주상복합 신축공사 ㈜ 선엔지니어링종합건축사사무소.
지역간 격차.
전산회계1급 기출 50회 신성대학교 세무부동산과 김상진.
Computer System Architecture
5 불 대수 IT CookBook, 디지털 논리회로.
Discrete Math II Howon Kim
2. 형식언어 (Formal Language)
Computer System Architecture
논리회로 설계 기초 (1) Lecture #1.
제3장 부울식의 간략화 내용 3.1 부울식의 대수적 간략화
오일석, C와 ALPS, 장. 논리적으로 생각하기 © 오일석, 전북대학교 컴퓨터공학.
수학 I 2. 방정식과 부등식.
3. 게이트레벨 최소화.
1장. 디지털 논리 회로 다루는 내용 논리 게이트 부울 대수 조합 논리회로 순차 논리회로.
Ⅷ. 도형의 닮음 1. 도형의 닮음 2. 삼각형과 평행선 3. 닮음의 응용.
주요 내용 형식 언어와 문법 정규식과 정규 집합 유한 상태 기계 정규 문법과 유한 상태 기계와 정규집합.
컴퓨터 구조 2장. 논리회로의 활용.
제 11장 교락법과 일부실시법.
5. 관계대수와 관계해석 관계자료 연산(operation)
9장. 동적 프로그래밍Dynamic Programming (DP)
이산수학 논리∙명제에서 알고리즘까지 √ 원리를 알면 IT가 맛있다 ehanbit.net.
이재상 기본 논리회로와 불의 대수 이재상
우리생활속의 확률 이용사례탐구 한림초등학교영재학급 6학년 김수민.
6장 연산 장치 6.1 개요 6.2 연산장치의 구성요소 6.3 처리기 6.4 기타 연산장치.
3. 게이트레벨 최소화.
김포 한강베네치아 상가분양 3층~5층 오피스텔 226세대 1층~2층 상가 분양문의 : 이효철( )
과학 탐구 토론 대회 1학년 2반 박승원 1학년 5반 권민성.
Ⅶ. 원 의 성 질 1. 원 과 직 선 2. 원 주 각 3. 원 과 비 례.
우리는 부모를 닮지만, 왜 똑같지는 않을까? 유전적 다양성 독립 연관과 교차 무작위 수정.
수학8가 대한 92~95 쪽 Ⅳ. 연립방정식 1. 연립방정식과 그 풀이 및 활용 >끝내기전에(9/9) 끝내기 전에.
도구를 사용할 때의 일(2) 도구를 사용해도 마찬가지야. 지레 지레를 사용할 때의 일.
탐구하는 수학연습문제 수학 8나 대한 114쪽 Ⅲ. 도형의 닮음
T-Tree MMDB 강원대학교 컴퓨터 과학과 양 기 운
관계 기본 개념 관계의 표현 관계의 성질 관계의 연산 관계의 폐포 동치 관계 부분순서 관계.
3. 정규 언어(Regular Language)
Discrete Math II Howon Kim
Chapter 5. 자료의 연산과 논리회로 e-learning Computers.
검색모델의 종류 불리안 모델 벡터 공간 모델 퍼지 집합 모델 확률 모델.
평 면 도 형 도형의 작도 삼각형의 작도와 결정조건 도형의 합동 작도와 삼각형의 합동 학습내용을 로 선택하세요
디지털회로설계_강의안5 7. 가산기와 감산기 회로.
선천이상 (congenital anomalies)
제 5장 문제 해결의 지도 5.(2)문제의 종류 김헌태.
제 6 장  상향식 파싱.
이산수학(Discrete Mathematics)
진리 나무 Truth-tree  ∧ ∨ → ↔  =.
Basic Function 김윤성 박로빈 이지호 천영재
엔화 대환/대출 자금용도 대상 이자 차액 효과 (A,B,C) 환율 리스크 헷징 (A,B) 엔화의 평균환율 (A,B,C)
수학교육론 (6.1~6.2(2)) 발표자: 신건일.
Chapter 3. 집합론.
논증의 타당성/부당성 검증 Verification/Falsification
표준화 이론 표준형 구조나무 표준화 정리  ∧ ∨ → ↔  =.
Presentation transcript:

부울대수(Boolean Algebra) 1 Lattice(격자,속) 2 Lattice로서의 부울대수 3 부울대수 4 부울식과 표준형

1. Lattice (격자,속) 정의)상계(upper bound), 최소상계(least upper bound:LUB) 하계(lower bound), 최대하계(greatest lower bound:GLB) 부분순서집합 (A, ), B ⊂ A B의 상계: x ∈ A, for all a ∈ B, a x 인 x B의 최소상계: B의 모든 다른 상계 y에 대해 x y인 B의 상계 x B의 하계: x ∈ A, for all a ∈ B, x a 인 x B의 최대하계: B의 모든 다른 하계 y에 대해 y x인 B의 하계 x

1. Lattice (격자,속) ex) Dm : m의 약수들의 집합 D36 = {1,2,3,4,6,9,12,18,36} B={4,6,12}의 상계:12,36 LUB(B):12 하계:1,2 GLB(B):2 C={6,9}의 상계: 18,36 LUB(C):18 하계:1,3 GLB(B):3 36 12 18 6 9 4 2 3 1

1. Lattice (격자,속) 정의) lattice : 부분순서집합(L, R)((L, ))에서 집합의 임의의 원소 a, b에 대해 집합 {a,b}의 최소상계와 최대하계가 각각 하나씩 존재하는 (L,R) 최소상계 LUB({a,b})를 a∨b로 표시, a와 b의 결합(논리합) (join) 최대하계 GLB({a,b})를 a∧b로 표시, a와 b의 만남(논리곱) (meet) ex) (ρ(S),⊆) : 부분순서집합 A, B ∈ ρ(S) A∨B = A∪B : 결합(A⊆A∪B, B⊆A∪B) A∧B = A ∩ B : 만남(A ∩ B⊆A, A ∩ B⊆B), ρ(S)는 lattice

1. Lattice (격자,속) ex) L = (N,R) aRb ⇔ a | b (b는 a로 나누어 떨어진다) a∨b = LCM(a,b) (LCM : 최소공배수) a∧b = GCD(a,b) (GCD : 최대공약수) N은 ´나누어 떨어짐의 관계´ 에 대하여 lattice ex) n : 양정수 Dn : n개의 약수들의 집합 a∨b = LCM(a,b) a∧b = GCD(a,b) Dn은 ´나누어 떨어짐의 관계´ 에 대하여 lattice

1. Lattice (격자,속) ex) lattice가 아닌 부분순서집합

1. Lattice (격자,속) (정의) 부분lattice (sublattice) (L, ):lattice S = , S⊂L, a,b ∈ S ⇒ (a∨b∈S)∧(a∧b∈S) 이면 S를 L의 부분lattice라 함 (L에 관한 연산 ∨와 ∧에 대해서 S가 닫혀있다) ex) (L) (Sb) (Sc) (Sd) lattice L Sd는 부분lattice Sb, Sc는 부분lattice 아님 ∵a∨b ∈ Sb a∨b Sc a∧b Sb I I I e f e f e f c a b a c b a b a b o o o ∈ ∈

1. Lattice (격자,속) (정의) 두 lattice L, L´ ∀a,b ∈ L L, L´ : 동형 lattice(isomorphic lattice) if ∃전단사 함수 f : L L´ such that f(a∨b) = f(a) ∨ f(b) f(a∧b) = f(a) ∧ f(b) f: 동형사상(isomorphism)

1. Lattice (격자,속) ex) A = {1,2,3,6} ρ({a,b}) ={ , {a}, {b}, {a, b}} aRb ⇔ a|b f(1) = f(2) = {a} f(3) = {b} f(6) = {a,b} 6 {a,b} 2 3 {a} {b} 1

1 Lattice (격자,속) lattice의 성질 1. a a∨b이고 b a∨b (a∨b는 a와 b의 상계) 2. a c이고 b c이면 a∨b c (a∨b는 a와 b의 최소상계) 3. a∧b a이고 a∧b b (a∧b는 a와 b의 하계) 4. c a이고 c b이면 c a∧b (a∧b는 a와 b의 최대하계) 2.c는 {a,b}의 상계 4. c는 {a,b}의 하계 (정리) L : lattice, a,b∈L (a) a∨b = b ⇔ a b (b) a∧b = a ⇔ a b (c) a∧b = a ⇔ a∨b = b

1. Lattice (격자,속) (정리) L :lattice 1. 멱등법칙(idempotent law) a∨a = a a∧a = a 2. 교환법칙(commutative law) a∨b = b∨a a∧b = b∧a 3. 결합법칙(associative law) a∨(b∨c) = (a∨b)∨c a∧(b∧c) = (a∧b)∧c 4.흡수법칙(absorption law) a∨(a∧b) = a a∧(a∨b) = a

1. Lattice (격자,속) (정리) L : lattice a,b,c,d ∈ L 1.a b 이면 (a) a∨c b∨c (b) a∧c b∧c 2.a c이고 b c ⇔ a∨b c (c상계, a∨b는 최소상계이므로) 3.c a이고 c b ⇔ c a∧b (c는 하계, a∧b는 최대하계이므로) 4.a b이고 c d이면 (a) a∨c b∨d (b) a∧c b∧d

1. Lattice (격자,속) (정의) 유계lattice (bounded lattice) (unit element) (zero element) 최대원소(greatest element) : a∈L x∈L xRa 일때의 a 최소원소 (least element) : a∈L x∈L aRx 일때의 a (ex) (z,≤)은 최대원소와 최소원소를 가지지 않으므로 유계lattice 아님 (ex) (ρ(S),⊆)의 최대원소는 S, 최소원소는 이므로 유계lattice (정리) 유계lattice L, 임의의 원소 a (1) 0 a이고 a 1 (2) a ∧ 1 = a, a ∨ 1 = 1 (1는 ∧ 에 대한 항등원) (3) a ∧ 0 = 0, a ∨ 0 = a (0는 ∨ 에 대한 항등원) A A

1. Lattice (격자,속) (정의) 분배lattice (distributive lattice) L : lattice a,b,c ∈ L (임의의 a,b,c) 분배법칙 a ∧ (b∨c) = (a∧b) ∨ (a∧c) a ∨ (b∧c) = (a∨b) ∧ (a∨c)을 만족시키는 L을 분배lattice라 함 비분배lattice (nondistributive lattice) : 분배lattice가 아닌 lattice (ex) (ρ(A),⊆)는 집합의 연산 ∪와 ∩가 분배법칙을 만족하므로 분배lattice (ex) 1 1 c a a b c b (1) (2)

1. Lattice (격자,속) (1) a∧(b∨c) = a∧1 = a a∨(b∧c) = a∨0 = a (a∧b)∨(a∧c) = 0∨0 = 0 (a∨b)∧(a∨c) = 1∧1 = 1 멱등법칙 b∧(a∨c) = b∧1 = b (b∧a)∨(b∧c) = 0∨0 = 0 ∴ 비분배lattice (2) a∧(b∨c) = a∧1 = a a∨(b∧c) = a∨0 = a (a∧b)∨(a∧c) = b∨0 = b (a∨b)∧(a∨c) = a∧1 = a b∧(c ∨ a) = b∧1 = b (b∧c)∨(b∧a) = 0∨b = b 성립 c∧(a∨b) = c∧a = 0 (c∧a)∨(c∧b) = 0∨0 = 0 성립

1. Lattice (격자,속) (정의) 유계lattice L, a∈L a의 보원(complement) : a´∈L, a∧a´ = 0, a∨a´ = 1인 a´ 보lattice(complemented lattice): 모든 원소가 적어도 하나의 보원을 가지고 있는 유계lattice (L,∨,∧,´,0,1) (ex) (ρ(S),⊂) :lattice ∧ : ∩ A ∈ ρ(S) ∨ : ∪ A의 여집합 A(Ac) 최대원소 S A∨A = S 최소원소 A∧A = ∴ (ρ(S),⊂):유계lattice (ρ(S),⊂)는 보lattice 모든 원소가 보원을 가짐 ∴ (ρ(S),⊂):보lattice

1. Lattice (격자,속) (정리) L : 유계분배 lattice 보원이 존재하면 유일하다 pf) ∀a∈L 보원을 a´,a″라 하면 a∨a′= 1 a∧a′= 0 a∨a″= 1 a∧a″= 0 a′= a´ ∨ 0 = a´∨(a∧a″) = (a´∨a)∧(a´∨a″) = 1∧(a´∨a″) = a´∨ a″ a″= a″∨ 0 = a″∨(a∧a´) = (a″∨a)∧(a″∨a´) = 1∧(a″∨a´) = a″∨ a´ a′= a´ ∨ a″= a″∨a′= a″ ∴ a´= a″

2. Lattice로서의 부울대수 부울대수 : 논리회로의 설계, 다른 여러 공학에 이용,회로설계과정에서 사용될 gate수 최소화, 기본적인 논리소자들을 조합하여 특정기능을 가진 논리장치설계 관계(Relation) 반사적(reflexive) 반대칭적(antisymmetric) 추이적(transitive) 부분순서집합 최소상계(least upper bound) 최대하계(greatest lower bound) lattice 최대원소 1(greatest element) 최소원소 0(least element) 분배법칙 분배 lattice 유계 lattice 보원(complement) 최대원소 1 최소원소 0 보원 보 lattice 분배법칙 부울대수

3. 부울대수 (정리) 유한집합 S1 = {x1,x2, …, xn}, S2 = {y1,y2, …, yn} lattice (ρ(S1),⊆)과 (ρ(S2),⊆)는 동형, 동일한 Hasse diagram lattice (ρ(S),⊆)는 |S|에 의해 결정 2|S| 개의 원소 가짐 (ex) S1 = {a,b,c} S2 = {2,3,5} (ρ(S1),⊆) (ρ(S2),⊆) S1 S2 {b,c} {3,5} {2,5} {a,b} {a,c} {2,3} {3} {5} {b} {c} {2} {a}

3. 부울대수 lattice Bn : n개의 원소로 구성된 집합에 대응하는 lattice (ρ(S),⊆)의 Hasse diagram 을 0과 1로 이루어진 label로 표현한 격자 lattice (ρ(S),⊆)는|S|= n일 때 (Bn, )과 동형 (ex) 111 011 110 101 010 001 100 000 B3

3. 부울대수 (정의)부울대수(Boolean algebra) : 음이 아닌 정수 n에 대하여 Bn과 동형인 유한 lattice (ρ(S),⊆) : 부울대수 D6 = {1,2,3,6} D6 :부울대수, B2와 동형 D30 : 부울대수, B3와 동형 ( 8 = 23 ) D20 : 부울대수 아님 6 = 2n 유한 lattice L이 2n개의 원소를 가지고 있지 않으면 부울대수가 될 수 없다. |L| = 2n이면 부울대수 일 수도 있고 아닐 수 있다. 6 11 2 3 10 01 1 00

3. 부울대수 부울대수 (B,∨,∧,´,0,1) : 적어도 2개의 원소를 가지는 유계lattice, 보lattice이면서 분배lattice인 lattice 부분순서집합 (B, ) 최대원소 1 : (B, )의 최대원소 (unit element) 최소원소 0 : (B, )의 최소원소 (zero element) a∈B의 보원 a´ (ex) D70 = {1,2,5,7,10,14,35,70} a∨b = LCM(a,b) a∧b = GCD(a,b) a´ = 70/a 70 35 14 10 7 5 2 1

3. 부울대수 (ex) B1 = {0,1} 0∨1 = 1 0∧1 = 0 °부울대수에서 성립하는 법칙 (1) 교환법칙 0∨1 = 1 0∧1 = 0 °부울대수에서 성립하는 법칙 (1) 교환법칙 a∨b = b∨a a∧b = b∧a (2) 분배법칙 a∨(b∧c) = (a∨b)∧(a∨c) a∧(b∨c) = (a∧b)∨(a∧c) 1 ∨ 0 1 0 0 1 1 1 1 0´ = 1 ∧ 0 1 0 0 0 1 0 1 1´ = 0

3. 부울대수 (3) 항등법칙 a∨0 = a a∧1 = a (4) 보법칙 a∨a′= 1 a∧a′= 0 (정리) a,b,c∈B (1)멱등법칙(idempotent law) a∨a = a a∧a = a (2)유계법칙(boundness law) a∨1 = 1 a∧0 = 0 (3)흡수법칙(absorption law) a∨(a∧b) = a a∧(a∨b) = a

3. 부울대수 (4)결합법칙(associative law) (a∨b)∨c = a∨(b∨c) (a∧b)∧c = a∧(b∧c) (5) De Morgan´s law (a∨b)´ = a´∧b′ (a∧b)´ = a´∨b´ (정리) a∈B (1) 보원의 유일성(uniqueness of complement) a∨x = 1 이고 a∧x = 0 이면 x = a′ (2) 이중 보법칙(invoution law) (a´)´ = a (3) 0´ = 1 이고 1´ = 0 쌍대성 원리(principle of duality)

4. 부울식과 표준형 부울대수 (B,∨,∧,´,0,1) (정의) 부울식(Boolean expression) E(x1,x2, ㆍㆍㆍ ,xn) where x1,x2, ㆍㆍㆍ ,xn ∈ B x1,x2, ㆍㆍㆍ ,xn 은 부울식 기호 0과 1은 부울식 3. E1(x1,x2, ㆍㆍㆍ ,xn)과 E2(x1,x2, ㆍㆍㆍ ,xn)이 부울식이면 E1(x1,x2, ㆍㆍㆍ ,xn) ∨ E2(x1,x2, ㆍㆍㆍ ,xn) E1(x1,x2, ㆍㆍㆍ ,xn) ∧ E2(x1,x2, ㆍㆍㆍ ,xn)도 부울식 4. E(x1,x2, ㆍㆍㆍ ,xn)이 부울식이면 (E(x1,x2, ㆍㆍㆍ ,xn))´ 도 부울식

4. 부울식과 표준형 (정의) 부울함수(Boolean function) 부울대수 (B,∨,∧,´,0,1) 에서 함수 f : Bn B 가 부울변수 x1,x2, ㆍㆍㆍ ,xn에 대한 부울식 E(x1,x2, ㆍㆍㆍ ,xn)으로 표현될 때의 함수 f (부울식에 의해 결정되는 함수 f : Bn B) f : Bn B Bn : B x B x ㆍㆍㆍ x B B = {0,1} f : 회로설계에서의 요구사항 부울식을 이용하여 부울함수 만듦

4. 부울식과 표준형 (ex) x1 x2 x3 f(x1,x2,x3) 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 (ex) x1 x2 . xn f(x1,x2,…, xn) x1 x2 x3 f(x1,x2,x3) = (x1∨(x2'∧x3)) 0 0 0 0 (0∨(1∧0)) = (0∨0) = 0 0 0 1 1 (0∨(1∧1)) = (0∨1) = 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1

4. 부울식과 표준형 ◎ 주어진 부울함수를 생성하는 부울식을 찾는 방법 (정의) 최소항(민텀(minterm)), 기본곱(fundamental product) b∈Bn ⇒ b 는 길이가 n인 열 c1c2ㆍㆍㆍcn where ck = 0 or 1 최소항 Eb = x1∧x2ㆍㆍㆍ ∧ xn(부울식) where ck = 1일 때 xk = xk ck = 0일 때 xk = xk′ (정리) f,f1,f2 : Bn B S(f) = { b∈Bn | f(b) = 1 } (a) S(f) = S(f1)∪S(f2) ⇒ ∀b∈Bn f(b) = f1(b)∨f2(b) (b) S(f) = S(f1)∩S(f2) ⇒ ∀b∈Bn f(b) = f1(b)∧f2(b)

4. 부울식과 표준형 (Pf) b∈Bn b∈S(f) 이면 f(b)=1 S(f)=S(f1)∪S(f2)이므로 b∈S(f1)이거나 b∈S(f2), 또는 둘 다에 속한다. f1(b) ∨ f2(b) = 1 b S(f)이면 f(b) = 0 b S(f1) ∧ b S(f2) 그러므로 f1(b) = 0 ∧ f2(b) = 0 f1(b) ∨ f2(b) = 0 ∴ f(b) = f1(b) ∨ f2(b) ∈ ∈ ∈

4. 부울식과 표준형 = (정리) 임의의 함수 f : Bn B는 부울식에 의해 생성된다. pf) f : Bn B S(f)={b∈Bn | f(b) = 1}라 하자 S(f) ={b1,b2,ㆍㆍㆍ,bk} for all i, fi : Bn B fi(bi)= 1 fi(b) = 0 (b bi) S(fi) = {bi} S(f) = S(f1)∪S(f2)∪ㆍㆍㆍ∪S(fn) ∴f = f1∨f2∨ㆍㆍㆍfn 각각의 fi는 최소항 Ebi에 의해 생성 ∴f는 Eb1∨Eb2∨ㆍㆍㆍ∨Ebn에 의해 생성됨(논리합 정규형) (부울변수에 대한 최소항 중에서 1의 값을 갖는 최소항들의 부울합) =

4. 부울식과 표준형 *부울식을 그림으로 표현 논리 다이어그램 (logic diagram) or gate and gate inverter 부울식에 대한 논리 다이어그램은 전자회로를 구성하는 방법 제공 많은 부울식들이 동일한 함수 생성 전자회로 구성의 다른 방법 x x∨y y x x∧y y x′ x