부울대수(Boolean Algebra)

Presentation on theme: "부울대수(Boolean Algebra)"— Presentation transcript:

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

2 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

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

4 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

5 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

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

7 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 ∈ ∈

8 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)

9 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

10 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

11 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

12 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

13 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

14 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)

15 1. Lattice (격자,속) (1) a∧(b∨c) = a∧1 = a a∨(b∧c) = a∨0 = a
(a∧b)∨(a∧c) = 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 = 성립

16 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

17 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″

18 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 분배법칙 부울대수

19 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}

20 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

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

22 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

23 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 ∧ 1´ = 0

24 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 = a∧0 = 0 (3)흡수법칙(absorption law) a∨(a∧b) = a a∧(a∨b) = a

25 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)

26 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))´ 도 부울식

27 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 : 회로설계에서의 요구사항 부울식을 이용하여 부울함수 만듦

28 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
(ex) x1 x2 . xn f(x1,x2,…, xn) x1 x2 x3 f(x1,x2,x3) = (x1∨(x2'∧x3)) (0∨(1∧0)) = (0∨0) = 0 (0∨(1∧1)) = (0∨1) = 1

29 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)

30 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) ∈ ∈ ∈

31 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의 값을 갖는 최소항들의 부울합) =

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