이산수학 (Discrete Mathematics)
집합과 연산
(Sets and Operations)
Discrete Mathematics by Yang-Sae Moon Page 2
강의 내용
집합 (Sets)
집합 연산 (Set Operations)
Sets and Operations
Introduction to 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).
Sets
원소 나열법 ( 예 : {…, -3, -2, -1, 0, 1, 2, 3,
…})
조건 제시법 ( 예 : {x | x is an integer})
Discrete Mathematics by Yang-Sae Moon Page 4
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!
Sets
Definition of Set Equality
Two sets are declared to be equal if and only if they con- tain 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}
Sets
Discrete Mathematics by Yang-Sae Moon Page 6
Infinite Sets ( 무한 집합 )
Conceptually, sets may be infinite (i.e., not finite, with- out 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 | pZ, qZ, q0} The rational numbers. (유리수의 집 합 )
R = The Real numbers, such as 3.141592… (실수의 집 합 )
Infinite sets come in different sizes!
( 무한집합이라도 크기가 다를 수 있다 .)
We will cover it later.
Sets
Venn Diagrams
0
-1 1
2 3
4 5
6 7
8 9
Integers from -1 to 9
Positive integers less than 10
Even integers from 2 to 9 Odd integers from 1 to 9
Primes <10
Sets
Discrete Mathematics by Yang-Sae Moon Page 8
원소 (Elements or Members)
xS (“x is in S”) is the proposition that object x is an le- ment or member of set S. (x는 S 의 원소이다 .)
e.g. 3N, ‘a’{x | x is a letter of the alphabet}
Can define set equality in terms of relation:
(원소 기호를 사용한 두 집합의 동치 증명 )
S = T x(xS xT) x(xT xS) x(xS xT)
“Two sets are equal iff they have all the same members.”
xS (xS) “x is not in S” (x는 S 의 원소가 아니다 .)
Sets
공집합 (Empty Set)
(“null”, “the empty set”) is the unique set that contains no elements. ( 공집합 () 이란 원소가 하나도 없는 유일한 집합이다 .)
= {} = {x|False}
{}
공집합
공집합을 원소로 하는 집합
Sets
Discrete Mathematics by Yang-Sae Moon Page 10
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 (xS xT)
S, S S (모든 집합은 공집합과 자기 자신을 부분집합으로 가진다 .)
S T (“S is a superset of T”) means TS.
Note S = T (S T) (S T)
S T means (S T), i.e. x(xS xT)
Sets
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 의 진부분집합이라 한다 .)
S T
Venn Diagram equivalent of S T
Example:
{1,2} {1,2,3}
Sets
Discrete Mathematics by Yang-Sae Moon Page 12
Sets are Objects, Too!
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}} !!!!
Sets
Cardinality and Finiteness
|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?
N Z R 2
Sets
Discrete Mathematics by Yang-Sae Moon Page 14
Power 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 의 크기가 자연수 집합보다 크다 ?!)
Sets
Ordered n-tuples
Ordered n-tuples are like sets, except that duplicates matter, and the order makes a difference.
(Ordered n-tuple 에서는 원소의 중복이 허용되고 , 순서도 차이를 나타낸다 .)
For nN, 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.
순서가 중요함 ( 의미를 가 짐 )
중복이 허용됨 ( 의미를 가 짐 )
Sets
Discrete Mathematics by Yang-Sae Moon Page 16
Cartesian Products
For sets A, B, their Cartesian product A B = {(a, b) | aA bB }.
(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, |AB|=|A||B|.
Note that the Cartesian product is not commutative:
AB: AB=BA (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) | aiAi, i = 1, 2, 3, …, n}
Sets
강의 내용
집합 (Sets)
집합 연산 (Set Operations)
Sets and Operations
Discrete Mathematics by Yang-Sae Moon Page 18
Union Operator ( 합집합 )
For sets A, B, their union AB is the set containing all el- ements that are either in A, or (“”) in B (or, of course, in both). (A 또는 B 에 속하거나 양쪽에 모두 속하는 원소들의 집합 )
Formally, AB = {x | xA xB}.
Note that AB contains all the elements of A and it contains all the elements of B:
A, B: (AB A) (AB 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}
Set Operations
2 3 5 7
Intersection Operator ( 교집합 )
For sets A, B, their intersection AB is the set containing all elements that are simultaneously in A and (“”) in B.
(A 와 B 양쪽 모두에 속하는 원소들의 집합 )
Formally, AB = {x | xA xB}.
Note that AB is a subset of A and it is a subset of B:
A, B: (AB A) (AB B) 예제 :
{a,b,c}{2,3} =
{2,4,6}{3,4,5} = {4}
2
3
6 4
Set Operations
Discrete Mathematics by Yang-Sae Moon Page 20
Disjointedness ( 서로 소 )
Two sets A, B are called disjoint (i.e., unjoined) iff their intersection is empty. (AB=)
( 교집합이 공집합이면 이들 두 집합은 서로 소라 한다 .)
Example: the set of even integers is disjoint with the set of odd integers.
Set Operations
Inclusion-Exclusion Principle
( 포함 - 배제 원 리 )How many elements are in AB?
|AB| = |A| |B| |AB|
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| = |IM| = |I| |M| |IM|
중복 제거
Set Operations
Discrete Mathematics by Yang-Sae Moon Page 22
Set Difference ( 차집합 )
For sets A, B, the difference of A and B, written AB, is the set of all elements that are in A but not B.
(A 에는 속하나 B 에는 속하지 않는 원소들의 집합 )
Formally, A B = x xA xB
예제 :
{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 Operations
Set Difference – Venn Diagram
AB is what’s left after B “takes a bite out of A”
Set A Set B Set
AB
Chomp!
( 갉아먹어 !)
Set Operations
Discrete Mathematics by Yang-Sae Moon Page 24
Set Complements ( 여집합 )
The domain can itself be considered a set, call it U.
(정의역 자체도 집합이다 .)
We say that for any set AU, the complement of A, writ- ten A, is the complement of A w.r.t. U, i.e., it is UA.
예제 : If U=N, {3, 5} = {0, 1, 2, 4, 6, 7, …}
An equivalent definition, when U is clear: A = x xA
U A
A
Set Operations
Set Identities ( 집합의 항등 ) (1/2)
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 Operations
Discrete Mathematics by Yang-Sae Moon Page 26
Set Identities ( 집합의 항등 ) (2/2)
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
Set Operations
Proving Identity Sets ( 항등의 증명 )
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 equiva- lences. ( 조건 제시법과 논리적 동치 관계 활용 )
Method 3: Use a membership table. ( 구성원 표를 사용 )
Set Operations
Discrete Mathematics by Yang-Sae Moon Page 28
Proving Identity Sets (Example of Method 1)
Example: Show A(BC)=(AB)(AC).
Show A(BC)(AB)(AC).
Assume xA(BC), & show x(AB)(AC).
We know that xA, and either xB or xC. (by assumption)
− Case 1: xB. Then xAB, so x(AB)(AC).
− Case 2: xC. Then xAC , so x(AB)(AC).
Therefore, x(AB)(AC).
Therefore, A(BC)(AB)(AC).
Show (AB)(AC) A(BC). …
Set Operations
Proving Identity Sets (Example of Method 2)
Example: Show (AB)=A B.
(AB) = {x | x AB}
= {x | ¬(x AB)}
= {x | ¬(xA xB)}
= {x | xA xB}
= {x | xA xB}
= {x | x A B}
= A B
Set Operations
Discrete Mathematics by Yang-Sae Moon Page 30
Proving Identity Sets (Example of Method 3)
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 (AB)B = AB.
Set Operations
AA BB AABB ((AABB))BB AABB
0 0 0 0 0
0 1 1 0 0
1 0 1 1 1
1 1 1 0 0
Generalized Unions and Intersections
Since union & intersection are commutative and associa- tive, 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}
ABC = {0, 1, 2, 3, 4, 6, 8, 9}
ABC = {0}
Set Operations
Discrete Mathematics by Yang-Sae Moon Page 32
Generalized Union ( 합집합의 일반화 )
Binary union operator: ABn-ary union:
A1A2…An = ((…((A1 A2) …) An) (grouping & order is irrelevant)
“Big U” notation:
Or for infinite sets of sets:
Set Operations
in1 Ai
XA
A
Generalized Intersection ( 교집합의 일반화 )
Binary intersection operator: ABn-ary intersection:
A1A2…An((…((A1A2)…)An) (grouping & order is irrelevant)
“Big Arch” notation:
Or for infinite sets of sets:
Set Operations
in1 Ai
XA
A
Discrete Mathematics by Yang-Sae Moon Page 34
컴퓨터에서 집합의 표현
표현 방법
전체 집합 U 가 유한집합이라 가정하고 , U 의 원소들을 a1, a2, …, an 과 같이 순서를 매긴다 .
U 의 부분집합 A 를 길이 n 의 비트열 (bit string) 로 표현한다 .
− ith bit = 1 if aiA, 0 otherwise
예제 :
U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
홀수 정수를 포함하는 부분집합을 표현하는 비트열 = 1010101010
짝수 정수를 포함하는 부분집합을 나타내는 비트열 = 0101010101
집합 연산과 컴퓨터 연산의 관계
합집합 (union) = Bitwise OR
교집합 (intersection) = Bitwise AND
여집합 (complement) = Bitwise NOT
Set Operations
강의 내용
집합 (Sets)
집합 연산 (Set Operations)
Sets and Operations