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

강의 내용 Sets and Operations 집합(Sets) 집합 연산(Set Operations)

Introduction to Sets 정의 Basic notations for sets 집합(set)이란 순서를 고려하지 않고 중복을 고려하지 않는 객체(object)들의 모임이다. A set is a new type of structure, representing an unordered collection (group) of zero or more distinct (different) objects. Basic notations for sets For sets, we’ll use variables S, T, U, … We can denote a set S in writing by listing all of its elements in curly braces { and }: {a, b, c} is the set of whatever three objects are denoted by a, b, c. Set builder notation: {x|P(x)} means the set of all x such that P(x). 원소 나열법 (예: {…, -3, -2, -1, 0, 1, 2, 3, …}) 조건 제시법 (예: {x | x is an integer})

Basic Properties of Sets Sets are inherently unordered: (순서가 중요치 않다!) No matter what objects a, b, and c denote, {a, b, c} = {a, c, b} = {b, a, c} = {b, c, a} = {c, a, b} = {c, b, a}. All elements are distinct (unequal); multiple listings make no difference! (중복은 의미가 없다!) If a=b, then {a, b, c} = {a, c} = {b, c} = {a, a, b, a, b, c, c, c, c}. This set contains at most two elements!

Definition of Set Equality Sets Two sets are declared to be equal if and only if they contain exactly the same elements. (동일한 원소들로 이루어진 두 집합은 동일하다.) In particular, it does not matter how the set is defined or denoted. (집합의 equality에서 정의나 표현은 중요치 않다.) For example: The set {1, 2, 3, 4} = {x | x is an integer where x > 0 and x < 5 } = {x | x is a positive integer whose square is >0 and <25}

Symbols for some special infinite sets: Conceptually, sets may be infinite (i.e., not finite, without end, unending). (집합은 무한할 수 있다.  무한집합) Symbols for some special infinite sets: N = {0, 1, 2, …} The Natural numbers. (자연수의 집합) Z = {…, -2, -1, 0, 1, 2, …} The Zntegers. (정수의 집합) Z+ = {1, 2, 3, …} The positive integers. (양의 정수의 집합) Q = {p/q | pZ, qZ, q0} The rational numbers. (유리수의 집합) R = The Real numbers, such as 3.141592… (실수의 집합) Infinite sets come in different sizes! (무한집합이라도 크기가 다를 수 있다.)  We will cover it later.

Positive integers less than 10 Venn Diagrams Sets 2 4 6 8 -1 1 Even integers from 2 to 9 3 5 7 9 Odd integers from 1 to 9 Primes <10 Positive integers less than 10 Integers from -1 to 9

원소(Elements or Members) Sets xS (“x is in S”) is the proposition that object x is an lement or member of set S. (x는 S의 원소이다.) e.g. 3N, ‘a’{x | x is a letter of the alphabet} Can define set equality in terms of  relation: (원소 기호를 사용한 두 집합의 동치 증명) S = T  x(xS  xT)  x(xT  xS)  x(xS  xT) “Two sets are equal iff they have all the same members.” xS  (xS)  “x is not in S” (x는 S의 원소가 아니다.)

공집합(Empty Set) Sets  (“null”, “the empty set”) is the unique set that contains no elements. (공집합()이란 원소가 하나도 없는 유일한 집합이다.)  = {} = {x|False}   {} 공집합을 원소로 하는 집합 공집합

Subsets(부분집합) and Supersets(모집합) S  T (“S is a subset of T”) means that every element of S is also an element of T. (S의 모든 원소는 T의 원소이다.) S  T  x (xS  xT)   S, S  S (모든 집합은 공집합과 자기 자신을 부분집합으로 가진다.) S  T (“S is a superset of T”) means TS. Note S = T  (S  T)  (S  T) S  T means (S  T), i.e. x(xS  xT)

S T Proper Subsets & Supersets S  T (“S is a proper subset of T”) means that S  T but T  S. Similar for S  T. (S가 T에 포함되나 T는 S에 포함되지 않으면, S를 T의 진부분집합이라 한다.) Example: {1,2}  {1,2,3} S T Venn Diagram equivalent of S  T

For example, let S={x | x  {1,2,3}} Sets are Objects, Too! Sets The objects that are elements of a set may themselves be sets. (집합 자체도 객체가 될 수 있고, 따라서 집합도 다른 집합의 원소가 될 수 있다.) For example, let S={x | x  {1,2,3}} then S={ , {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} } Note that 1  {1}  {{1}} !!!!

2 N Z R Cardinality and Finiteness Sets |S| (read “the cardinality of S”) is a measure of how many different elements S has. (|S|는 집합 S의 원소 중에서 서로 다른 값을 가지는 원소의 개수이다.) E.g., ||=0, |{1,2,3}| = 3, |{a,b}| = 2, |{{1,2,3},{4,5}}| = ____ If |S|N, then we say S is finite. Otherwise, we say S is infinite. What are some infinite sets we’ve seen? 2 N Z R

The power set P(S) of a set S is the set of all subsets of S. Power Sets (멱집합) Sets The power set P(S) of a set S is the set of all subsets of S. P(S) = {x | x  S} (P(S)는 집합 S의 모든 부분집합을 원소로 하는 집합) Examples: P({a,b}) = {, {a}, {b}, {a,b}}. P() = {}, P({}) = {, {}}. Sometimes P(S) is written 2S. Note that for finite S, |P(S)| = |2S|= 2|S|. It turns out that |P(N)| > |N|. There are different sizes of infinite sets! (자연수 집합의 power set의 크기가 자연수 집합보다 크다?!)

(Ordered n-tuple에서는 원소의 중복이 허용되고, 순서도 차이를 나타낸다.) Ordered n-tuples Sets Ordered n-tuples are like sets, except that duplicates matter, and the order makes a difference. (Ordered n-tuple에서는 원소의 중복이 허용되고, 순서도 차이를 나타낸다.) For nN, an ordered n-tuple or a sequence of length n is written (a1, a2, …, an). The first element is a1, etc. Note (1, 2)  (2, 1)  (2, 1, 1). Empty sequence, singlets, pairs, triples, quadruples, …, n-tuples. 중복이 허용됨(의미를 가짐) 순서가 중요함(의미를 가짐)

For sets A, B, their Cartesian product A  B = {(a, b) | aA  bB }. Cartesian Products Sets For sets A, B, their Cartesian product A  B = {(a, b) | aA  bB }. (a가 A의 원소이고 b가 B의 원소인 모든 순서쌍(pair) (a, b)의 집합이다.) E.g. {a,b}{1,2} = {(a,1),(a,2),(b,1),(b,2)} Note that for finite A, B, |AB|=|A||B|. Note that the Cartesian product is not commutative: AB: AB=BA (Cartesian product는 교환법칙이 성립하지 않는다.) E.g. {a,b}{1,2}  {1,2}{a,b} = {(1,a),(1,b),(2,a),(2,b)} A1  A2  …  An = {(a1, a2, …, an) | aiAi, i = 1, 2, 3, …, n}

강의 내용 Sets and Operations 집합(Sets) 집합 연산(Set Operations)

Union Operator (합집합) 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 (교집합) 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 (서로 소) 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 (포함-배제 원리) 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 (차집합) 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 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 (여집합) 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) 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) 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 (항등의 증명) 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) 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) 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) 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 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 (합집합의 일반화) 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 (교집합의 일반화) 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:

컴퓨터에서 집합의 표현 표현 방법 예제: 집합 연산과 컴퓨터 연산의 관계 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

강의 내용 Sets and Operations 집합(Sets) 집합 연산(Set Operations)