이산수학(Discrete Mathematics)  집합 연산 (Set Operations) 2013년 봄학기 강원대학교 컴퓨터과학전공 문양세

Union Operator (합집합) 1.7 Set Operations For sets A, B, their union AB is the set containing all elements that are either in A, or (“”) in B (or, of course, in both). (A 또는 B에 속하거나 양쪽에 모두 속하는 원소들의 집합) Formally, AB = {x | xA  xB}. Note that AB contains all the elements of A and it contains all the elements of B: A, B: (AB  A)  (AB  B) 예제: {a,b,c}{2,3} = {a,b,c,2,3} {2,3,5}{3,5,7} = {2,3,5,3,5,7} ={2,3,5,7} 2 3 5 7

2 3 5 6 4 Intersection Operator (교집합) 1.7 Set Operations For sets A, B, their intersection AB is the set containing all elements that are simultaneously in A and (“”) in B. (A와 B 양쪽 모두에 속하는 원소들의 집합) Formally, AB = {x | xA  xB}. Note that AB is a subset of A and it is a subset of B: A, B: (AB  A)  (AB  B) 예제: {a,b,c}{2,3} =  {2,4,6}{3,4,5} = {4} 2 3 5 6 4

Disjointedness (서로 소) 1.7 Set Operations Two sets A, B are called disjoint (i.e., unjoined) iff their intersection is empty. (AB=) (교집합이 공집합이면 이들 두 집합은 서로 소라 한다.) Example: the set of even integers is disjoint with the set of odd integers.

Inclusion-Exclusion Principle (포함-배제 원리) 1.7 Set Operations How many elements are in AB? |AB| = |A|  |B|  |AB| Example: How many students are on our class email list? Consider set E  I  M, I = {s | s turned in an information sheet} M = {s | s sent the TAs their email address} Some students did both! |E| = |IM| = |I|  |M|  |IM| 중복 제거

Formally, A  B = x  xA  xB 예제: Set Difference (차집합) 1.7 Set Operations For sets A, B, the difference of A and B, written AB, is the set of all elements that are in A but not B. (A에는 속하나 B에는 속하지 않는 원소들의 집합) Formally, A  B = x  xA  xB 예제: {1, 2, 3, 4, 5, 6}  {2, 3, 5, 7, 11} = {1, 4, 6} Z  N  {… , -1, 0, 1, 2, … }  {0, 1, … } = {x | x is an integer but not a natural number} = {x | x is a negative integer} = {… , -3, -2, -1}

Set AB Set A Set B Chomp! Set Difference – Venn Diagram 1.7 Set Operations AB is what’s left after B “takes a bite out of A” Chomp! (갉아먹어!) Set AB Set A Set B

A A U Set Complements (여집합) 1.7 Set Operations The domain can itself be considered a set, call it U. (정의역 자체도 집합이다.) We say that for any set AU, the complement of A, written A, is the complement of A w.r.t. U, i.e., it is UA. 예제: If U=N, {3, 5} = {0, 1, 2, 4, 6, 7, …} An equivalent definition, when U is clear: A = x  xA A A U

Set Identities (집합의 항등) (1/2) 1.7 Set Operations Identity Name A   = A A  U = A Identity laws A  U = U A   =  Domination laws A  A = A A  A = A Idempotent laws A = A Double complement law A  B = B  A A  B = B  A Commutative laws A  (B  C) = (A  B)  C A  (B  C) = (A  B)  C Associative laws

Set Identities (집합의 항등) (2/2) 1.7 Set Operations Identity Name A  (B  C) = (A  B)  (A  C) A  (B  C) = (A  B)  (A  C) Distributive laws A  B = A  B A  B = A  B De Morgan’s laws A  (A  B) = A A  (A  B) = A Absorption laws A  A = U A  A =  Complement laws

Proving Identity Sets (항등의 증명) 1.7 Set Operations To prove statements about sets, of the form A = B, here are three useful techniques: (집합의 항등 증명 방법에는 …) Method 1: Prove A  B and B  A separately. Method 2: Use set builder notation & logical equivalences. (조건 제시법과 논리적 동치 관계 활용) Method 3: Use a membership table. (구성원 표를 사용)

Proving Identity Sets (Example of Method 1) 1.7 Set Operations Example: Show A(BC)=(AB)(AC). Show A(BC)(AB)(AC). Assume xA(BC), & show x(AB)(AC). We know that xA, and either xB or xC. (by assumption) Case 1: xB. Then xAB, so x(AB)(AC). Case 2: xC. Then xAC , so x(AB)(AC). Therefore, x(AB)(AC). Therefore, A(BC)(AB)(AC). Show (AB)(AC)  A(BC). …

Proving Identity Sets (Example of Method 2) 1.7 Set Operations Example: Show (AB)=A  B. (AB) = {x | x  AB} = {x | ¬(x  AB)} = {x | ¬(xA  xB)} = {x | xA  xB} = {x | xA  xB} = {x | x  A  B} = A  B

Proving Identity Sets (Example of Method 3) 1.7 Set Operations Membership tables (구성원 표) Just like truth tables for propositional logic. (명제의 진리표와 유사) Columns for different set expressions. (열은 집합 표현을 나타냄) Rows for all combinations of memberships in constituent sets. Use “1” to indicate membership in the derived set, “0” for non-membership. (행에는 집합의 원소이면 1, 아니면 0을 표시) Prove equivalence with identical columns. (두 컬럼이 동일함을 보임) Example: Prove (AB)B = AB.

Generalized Unions and Intersections 1.7 Set Operations Since union & intersection are commutative and associative, we can extend them from operating on ordered pairs of sets (A, B) to operating on sequences of sets (A1, …, An) (합집합 및 교집합은 교환 및 결합법칙이 성립하므로, 두 집합에 대한 연산을 확장하여 세 개 이상의 집합에 대해서도 연산 적용이 가능하다.) Examples of generalized unions & intersections A = {0, 2, 4, 6, 8}, B = {0, 1, 2, 3, 4}, C = {0, 3, 6, 9} ABC = {0, 1, 2, 3, 4, 6, 8, 9} ABC = {0}

Generalized Union (합집합의 일반화) 1.7 Set Operations Binary union operator: AB n-ary union: A1A2…An = ((…((A1 A2) …) An) (grouping & order is irrelevant) “Big U” notation: Or for infinite sets of sets:

Generalized Intersection (교집합의 일반화) 1.7 Set Operations Binary intersection operator: AB n-ary intersection: A1A2…An((…((A1A2)…)An) (grouping & order is irrelevant) “Big Arch” notation: Or for infinite sets of sets:

컴퓨터에서 집합의 표현 표현 방법 예제: 집합 연산과 컴퓨터 연산의 관계 1.7 Set Operations 표현 방법 전체 집합 U가 유한집합이라 가정하고, U의 원소들을 a1, a2, …, an과 같이 순서를 매긴다. U의 부분집합 A를 길이 n의 비트열(bit string)로 표현한다. ith bit = 1 if aiA, 0 otherwise 예제: U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 홀수 정수를 포함하는 부분집합을 표현하는 비트열 = 1010101010 짝수 정수를 포함하는 부분집합을 나타내는 비트열 = 0101010101 집합 연산과 컴퓨터 연산의 관계 합집합(union) = Bitwise OR 교집합(intersection) = Bitwise AND 여집합(complement) = Bitwise NOT