2 기본 구조들: 집합, 함수, 수열, 합, 행렬 1

//이 자료는 Discrete mathmatics and its application 7th edition에서 나오는 예제를 간추린 것입니다. 저는 코딩에 관심 있는 학생이며, 타인의 지적재산을 단지 학습을 위해 사용할 뿐 개인의 금리적 이윤을 위한 상업적인 용도로 쓰지 않습니다. 만약 저작권 관련 문제가 될 시 즉시 문서를 삭제하겠습니다.//

 이산 수학의 상당 부분이 이산 구조에 대한 연구에 도움이 되고 있습니다. 이산 객체들을 표현하기 위해 사용됩니다. 많은 수의 중요한 이산 구조들은 객체들의 컬렉션인ㅡ 집합으로 이루어져 있습니다. 집합으로 이루어진 이산 구조들 중에는 조합이 있고, 객체들의 비정렬된 컬렉션으로 셈에서 널리 사용됩니다. 관계는, 집합의 순서쌍으로 객체들간의 관계들을 나타냅니다. 그래프는 꼭지점(vertex)과 연결선(edge)들의 집합입니다. 그리고 유한 상태 머신은 연산 기계를 모델하기 위해 사용됩니다. 이 들이 곧 다뤄질 내용 들 중에 일부분입니다.

 함수의 개념은 이산수학에서 정말 중요합니다. 함수는 첫 집합의 각 요소들에 두번째 집합의 각 요소들을 할당합니다. 두 집합은 반드시 구분되는 집합일 필요는 없습니다. 함수는 이산수학에서 중요한 역할을 맡고 있습니다. 알고리즙의 연산 복잡성을 나타내기 위해 사용되기도 하고, 집합의 크기를 연구하기 위해, 객체들을 세기위해, 그리고 무수히 많은 다른 분야에도 사용됩니다. 수열이나 문자열과 같은 종종 사용되는 구조들은 함수의 특수한 모양 중 하나입니다. 이번 챕터에서는 수열이, 요소들의 정렬된 리스트를 표현하기 위해 사용되는 것에 대해 알아볼 것입니다. 또, 수열의 중요한 형식들과 수열의 항을 정의하는 법을 알아 볼것입니다. 또한 처음 시작 몇 항에서 정보를 얻어 수열을 알아내는 방법에 대해서 다룰겁니다.

 우리가 배울 이산수학에서는, 숫자로 이루어진 수열의 몇개의 연속적인 항을 더하기도 할 겁니다. 수열의 몇 항을 더하는것은, 숫자 집합의 다른 인덱스에도 발생하는, 상당히 일반적인 활동입니다. 이렇게 항들을 더하기 위해 특별한 표기법도 발전되었습니다. 이 장에서는 합계에 대한 표기법도 소개될 것이고 이산수학에서 사용되는 특정 형식의 합의 수식을 만들기도 할 것입니다. 예로, 숫자들이 증가식으로 정리가 되어있는지 분석하는 방법을 합을 통해서 알아볼것입니다.

 무한 집합의 상대적인 크기도 집합에서 사용되는 크기 표기법인 복잡도cardinality 를 통해 비교하는 법을 알아 볼것입니다. 무한 집합이 양의 정수와 같은 크기일 때 우리는 가산적이다 라고 표현합니다. 이 장에서는 유리수가 셀 수 있다(가산적)는 놀라운 결과도 직접 확인 해 볼 것입니다. 반면에 실수는 가산적이지 않다는 것도요. 또한 이렇게 설명된 개념들을 통해 프로그래밍 언어를 통해 프로그램 될 수 없는 함수들이 존재할 수 있다는 것 또한 보여줄 것입니다.

 행렬은 이산수학에서 이산 구조들의 다양성을 보여주기 위해 사용됩니다. 또한 행렬에 대한 기본적인 것들과 관계와 그래프를 표현하기위한 행렬 산술을 살펴볼 것입니다. 행렬 산술은 이런 이산구조들을 포함한 다양한 문제들을 푸는데 사용될 것입니다. 

집합

집합은 객체들을 함께 묶기위해 사용됩니다. 자주, 객체들은 같은 프로퍼티들을 가지고 있습니다. 예로, 특정 학교의 모든 학생들은 집합을 이루고 있습니다. 비슷하게, 각 학교에서 이산수학을 배우는 모든 학생들도 집합을 이루고 있습니다. 게다가, 앞서 두개의 교집합을 통해 한 학교에서 특정 학교에서 이산수학을 듣는 학생들을 추려낼 수 있습니다. 이제 집합에 대한 정의를 알아봅니다. 이 정의는 직관적으로 이해를 도와주는 정의이며, 집합 이론의 정식적인 정의는 아닙니다.

 정의 1

 집합이란 요소elements 또는 멤버member로 불리는 객체object들의 비정렬된 컬렉션이다. 집합은 그의 요소들을 포함하고 있다고 말한다. 이때 표기는 a ∈ A, a는 집합 A의 원소이다를 뜻합니다. a는 집합 A의 원소가 아니다는 다음과 같이 표기 합니다. a ∉ A

집합을 표현하는 방법에는 원소나열법roster method과 조건 제시법set builder 가 있습니다. 

예제 4

100보다 작은 양의 정수를 표현하라. 

***{1, 2, 3, ... ,99} 또는 {x|x<100, x는 양의 정수} 

정의 4

S를 집합이라하자. 집합 S에 n 개의 구별되는 원소들이 있을 때, 음수가 아닌 n개의 정수, S는 유한 집합이라 하며 n은 집합 S의 복잡도cardinality(또는 원소수)라고 한다. 집합 S의 복잡도cardinality는 |S|로 표기된다.

예제 10

10보다 작은 홀수인 양의 정수들 집합을 A라하자. 그러면 |A| = 5

예제 12

공집합null set 은 원소들을 가지고 있지 않다. 따라서 |∅| = 0 이다.

 정의 5

만약 집합 S가 유한이 아니라면, 집합 S는 무한이라고 한다.

예제 13

양의 정수는 무한이다.

 복잡도cardinality에 관한 확장된 표기법을 2.5 챕터에서 알아볼 것입니다. 어려운 주제들이지만, 놀라운 결과들을 담고있습니다.

멱집합Power Sets

정의 6

집합 S가 있다고 하자. S의 멱집합power set은 S의 모든 부분집합들로 이루어진 하나의 집합이다. S의 power set은 다음과 같이 표기된다. P(S) //Weiestrass p 를 쓰는데 HTML 특수기호엔 없는것같다.

예제 14

집합 {0, 1, 2}의 멱집합power set은?

*** {∅, {0}, {0,1}, {0,2}, {0,1,2}, {1}, {1,2}, {2}}

곱집합 또는 데카르트 곱Cartesian Products

컬렉션에 있는 원소들의 순서는 자주 중요하게 취급됩니다. 집합은 비정렬이기 때문에, 정렬된 컬렉션을 표현하기 위한 다른 구조체가 필요합니다. 이 것은 정렬된 n-튜플n-tuples로 표현가능합니다.

정의 7

정렬된 n-튜플n-tuple (a1, a2, ... ,an) 은 정렬된 컬렉션입니다. n-튜플은 a1을 첫 원소로 가지고 그다음 두번째 원소로 a2, 결국에는 an을 n 번째 원소로 가집니다.

두 정렬된 n-튜플이 같은지 비교할 때 각각의 대응되는 원소들의 쌍이 같은지 비교합니다. 다르게 표현하면, (a1, a2, ... ,an) = (b1, b2, ... ,bn)은 ai=bi for i= 1,2, ... ,n 과 biconditional statement입니다. 정렬된 2-튜플은 정렬된 쌍 또는 순서쌍이라고 부릅니다. 정렬된 쌍 (a,b)와 (c,d)는 a=c 그리고 b=d일 때 같습니다. (a,b)와 (b,a)는 다릅니다. 다만 a=b일 때는 같습니다.

이산적인 구조들 중 많은 경우는 집합의 데카르트 곱Cartesian product 표기법에 근거를 둡니다. 우선 두 집합의 데카르트 곱을 먼저 정의하겠습니다.

정의 8

A와 B를 집합이라 하자. A와 B의 데카르트 곱Cartesian product 은, A x B로 표기된다. A x B는 모든 순서쌍 또는 정렬된 쌍 (a,b)의 집합이다. 여기서 a∈A 이고 b ∈B 이다. 따라서, 

A x B = {(a,b) | a∈A ∧ b∈B}

예제 16

A를 대학 내의 모든 학생들의 집합이라하고, B는 대학에서 제공하는 모든 강의들의 집합이라 하자. 데카르트 곱 A x B는 무엇이고 어떻게 사용될 수 있습니까?

***데카르트 곱 A x B는 (a, b) 형식의 모든 순서쌍으로 이루어져 있습니다. 여기서 a는 대학교 학생이고 b는 학교에서 제공되는 강의입니다. 집합 A x B는 대학에서 강의를 수강할 수있는 학생들의 모든 조합을 보여줄 수 있습니다.

예제 17 

집합 A = {1, 2} 이고 집합 B = {a, b, c} 입니다. 두 집합의 데카르트 곱은 무엇입니까?

*** A x B = {(1,a), (1,b), (1,c), (2,a), (2,b), (2,C)}

두 집합 이상의 데카르트 곱도 또한 정의 될 수 있습니다.

정의 9 

집합 A1, A2, ... , An의 데카르트 곱은 다음과 같이 표기될 수 있습니다. A1 x A2 x ... x An. 이는 정렬된 n-튜플의 집합입니다. (a1, a2, ... ,an) 여기서 ai은 Ai에 속해있습니다. (i= 1, 2, ... ,n) 다르게 표현하면,

A1 x A2 x ... x An = {(a1, a2, ... ,an) | ai∈Ai for i = 1, 2, ... ,n}

예제 19

A x B x C 를 구해보세요. 여기서 A= {0,1}, B= {1,2}, C={0,2} 입니다.

*** 데카르트 곱 A x B x C는 순서세쌍 (a, b, c)로 이루어져있습니다. 여기서 a∈A, b∈B, c∈C입니다. 따라서, A x B x C = {(0,1,0}, {0,1,2}, {0,2,0}, {0,2,2}, {1,1,0}, {1,1,2}, {1,2,0}, {1,2,2}}

 기본적으로 A, B, C가 집합이라 할 때 (A x B) x C는 A x B x C와 다르다. 후에 예제로 살펴 볼 것입니다.

 또한 자신의 데카르트 곱 A^2은 A x A를 의미합니다. 비슷하게, A^3 은 A x A x A를 의미합니다. 일반적으로 A^n {(a1, a2, ..., an)| ai∈A for i = 1,2, ... ,n }.

예제 20

집합 A ={1, 2}라 하자. 그러면 A^2 = {(1,1), (1,2), (2,1), (2,2)} 이고 A^3 = {(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2)}이다.

 데카르트 곱 A x B의 부분집합을 R이라 하자. 이 부분집합 R은 집합 A에서 B로의 관계relation 라고 합니다. R의 원소들은 순서 쌍이며, 이 순서쌍의 첫 원소는 A에 속하며 두번째 원소는 B에 속합니다. 예로, R = {(a,0}, (a,1), (a,3), (b,1), (b,2), (c,0), (c,3)}는 관계relation 입니다. 집합 {a, b, c} 에서  {0, 1, 2, 3}로의 관계이다. A에서 자신으로의 관계를 보고 A로의 관계라고도 표현합니다.

예제 21

집합 {0, 1, 2, 3} 자신으로의 관계는 무엇입니까? 여기서 순서쌍 (a, b)는 a <= b 입니다.

*** 부분집합 R은 다음과 같은 순서쌍을 포함할 수 있습니다. (0,0), (0,1), (0,2), (0,3), (1,1), (1,2), (1,3), (2,2), (2,3), (3,3)  

정량자를 이용한 집합 표기법 

때로는 정량자 진술의 정의역을 특정한 표기법을 이용해 형식적으로 제한하기도 합니다. 예로,  ∀x∈S(P(x))는 집합 S의 모든 원소들에 대한 P(x)의 전체 정량자를 뜻합니다. 다르게말하면, ∀x∈S(P(x))는 ∀x(x∈S→P(x))의 축약형입니다. 즉, ∃x∈S(P(x))는 ∃x(x∈S ∧ P(x))의 축약형입니다.

예제 22

진술 ∀x∈R(x^2≥0)과 ∃x∈Z(x^2=1)의 의미는 무엇입니까?

*** 진술 ∀x∈R(x^2≥0)는 실수에 속한 모든 x에 대하여 그 제곱은 0보다 크거나 같다를 뜻합니다. 짧게는 어떤 실수의 제곱도 음수가 아니다. 라 표현가능합니다. 이는 참입니다.

후자의 진술인 경우, 정수에 속한 어떤 원소가 그 제곱이 1과 같다 를 뜻합니다. x=1인 경우가 존재하므로, 이는 참입니다.   

진리 집합과 정량자

이제부터는 집합론과 술어 논리에서의 개념들을 함꼐 사용할 것입니다. 술어를 P, 정의역을 D라 주어졌을 때, P의 진리 집합을 D에 속한 원소들 x의 집합이라고 합니다. 여기서 P(x)는 참입니다. P(x) 의 진리집합을 다음과 같이 표기합니다. {x∈D|P(x)} //이제까지 set builder 에서 한 것 들입니다. 

예제 23

술어 P(x), Q(x), R(x)의 진리 집합은 무엇입니까? 여기서 정의역은 정수들의 집합이고 P(x)는 "|x|=1", Q(x)는 "x^2=2", R(x)는 "|x| = x" 입니다.

*** P의 진리집합은 {x∈Z||x|=1} Q의 진리집합은 {x∈Z|x^2x=2} R의 진리집합은 {x∈Z||x|=x} 표기될 수 있습니다. 순서대로 {-1, 1}, 공집합, 음수가 아닌 정수들 입니다.