이산수학(Discrete Mathematics)

Presentation on theme: "이산수학(Discrete Mathematics)"— Presentation transcript:

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

2 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})

3 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!

4 Definition of Set Equality
1.6 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}

5 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 … (실수의 집합) Infinite sets come in different sizes! (무한집합이라도 크기가 다를 수 있다.)  We will cover it in $3.2.

6 Positive integers less than 10
Venn Diagrams 1.6 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

7 원소(Elements or Members)
1.6 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의 원소가 아니다.)

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

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

10 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

11 For example, let S={x | x  {1,2,3}}
Sets are Objects, Too! 1.6 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}} !!!!

12 2 N Z R Cardinality and Finiteness
1.6 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

13 The power set P(S) of a set S is the set of all subsets of S.
Power Sets (멱집합) 1.6 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의 크기가 자연수 집합보다 크다?!)

14 (Ordered n-tuple에서는 원소의 중복이 허용되고, 순서도 차이를 나타낸다.)
Ordered n-tuples 1.6 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. 중복이 허용됨(의미를 가짐) 순서가 중요함(의미를 가짐)

15 For sets A, B, their Cartesian product A  B = {(a, b) | aA  bB }.
Cartesian Products 1.6 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}