[이산수학🔗] 집합론과 디지털적인 수의 세계 (3장)

포스팅에 참고하는 교재 : 4차 산업혁명 시대의 이산수학 개정판 (생능출판)

 

3.1 집합의 표현

1) 집합

• 집합은 원소(element)라 불리는 서로 다른 객체들의 모임으로 현대 수학에서 가장 기초가 되는 개념
• 집합의 개념은 수학이나 컴퓨터 분야뿐만 아니라 과학이나 공학 분야 등에서 폭넓게 사용됨.
• 집합의 개념은 19세기 말 독일의 수학자 칸토어(Georg Cantor, 1845~1918)에 의해 처음으로 제안됨.
• 저명한 수학자들은 그의 집합론에  관한 연구의 정당성을 인정하지 않았으나, 오늘날 집합론은 수학적 사고의 중요한 기초임.
• 수학적 객체들은 집합에 관하여 정의될 수 있으므로 수학의 기본 개념임.
• 어떤 객체가 그 집하에 속하는지 아닌지를 분명히 구분할 수 있어야 함.
• 집합을 표시할 때는 알파벳 대문자 A, B, C 등으로 표시한다.
• 집합을 구성하는 원소는 소문자 a, b, c 등으로 표시한다.
• 집합에 속한 원소들로 구성되어 있는데, 집합을 s라 하고 하나의 원소를 a라고 하면  a ∊ S는 a가 집합 S가 원소임을 나타냄.
• a ∉ S는  a가 집합 S가 원소가 아님을 나타냄.
• 전체 집합(universal set) : 집합론에서 관심을 두는 모든 원소의 집합 (표기 :  U)
• 공집합(empty set) : 어떠한 원소도 가지지 않는 집합 (표기 : { } , ∅ ) 

2) 집합을 표현하는 방법

- 원소 나열법 : 집합의 원소들을 { }  사이에 하나씩 나열하는 방법
- 조건 제시법

• 집합의 원소들이 갖는 특정한 성질을 기술하여 나타내는 방법
• 조건 제시법의 표현 S = {x | p(x) }
• x는 원소를 대표하는 변수이고, p(x)는 원소들이 가지고 있는 성질임.

3) 카디날리티 (Cardinality)

- 집합 S 내에 있는 원소들의 개수
- 집합의 원소 수라 하고 |S|로 표기한다.
- 유한 집합(finite set) : 집합 S의 원소의 개수가 유한한 경우
- 무한 집합(infiite set) : 유한 집합이 아닌 집합 
- 집합 S1에서 집합 S2로의 일대일 대응인 함수가 존재할 때 S1과 S2는 같은 카디날리티를 가짐.
- 유한 집합인 경우 만약 S1이 S2의 진부분 집합일 때에는 S1과 S2는 서로 다른 카디날리티를 가짐.
 

4) 가산적 집합(countable set) 또는 가산적으로 무한한 집합(countably infinite set) 

: 정수의 집합과 일대일의 대응 관계에 있는 집합들
 

5) 전체 집합의 표기와 기호

• Z : 정수의 집합
• N : 자연수의 집합
• R :  실수의 집합
• Q :  유리수의 집합
• Sn : 1부터 n까지의 자연수의 집합

 

6) 부분 집합(subset)

- 부분 집합(subset)

• 두 집합 A, B에서 집합 A의 모든 원소가 집합 B의 원소에 속하면 A ⊆ B
• 이때 집합 A는 집합 B의 부분집합.

- 진부분 집합(proper subset) :  A ⊆ B이고, A ≠ B
 

7) 여집합 (complement)

전체 집합 U와 그것의 부분 집합 A에서 집합 U에 속하나 A에 속하지 않는 원소들의 집합을 A의 여집합이라고 한다.

 

3.2 집합의 연산

1) 벤 다이어그램

- 주어진 집합들 사이의 관계와 집합의 연산에 대하여 쉬운 이해 가능

- 전체 집합 U는 사각형으로 표현하고 주어진 집합들을 U의 부분 집합들이므로 사각형 안의 원으로 표현한다.

 

2) 집합 연산

- 합집합(Union) : 집합 A 또는 집합 B에 속하는 모든 원소들의 집합으로 A∪B로 표현

- 교집합(Intersection) : 두 집합 A, B에 대하여 집합 A에도 속하고, 집합 B에도 속하는 모든 원소들의 집합으로 A∩B로 표현

- 서로소(Disjoint) : 집합 A와 집합 B가 공통된 원소를 하나도 갖지 않은 경우 

- 차집합(Difference) : 두 집합 A, B에 대하여 집합 A에 속하고, 집합 B에 속하지 않는 모든 원소들의 집합으로 A-B로 표현

- 대칭 차집합 (Symmetric Difference)

: 집합 A, B에 대하여  A∪B의 원소 중에서  A∩B에 속하지 않는 모든 원소들의 집합으로 A⊕B로 표현

- 곱집합(Cartesian Product) : A×B

• 두 집합 A, B에 대해 x⊆A, y⊆B인 모든 순서쌍 (x, y)의 집합
• 순서쌍은 순서로 구분되는 원소들의 쌍으로서 (a, b)와 같이 나타냄.
• 순서쌍 (a, b)는 쌍의 원소들 간의 순서에 의해 구분이 된다. 

 

2) 집합 연산의 카디날리티

 

; 집합 S의 카디날리티(Cardinality)란 그 집합의 원소의 개수를 나타내며 |S|로 표기한다.

- 집합의 연산에 의해 새로 만들어진 집합들에 대한 카디날리티 표현

• |A∪B| = |A| + |B| - |A∩B|
• |A∩B| =  |A| + |B| - |A∪B|
• |A∪B∪C| = |A| + |B| + |C| - |A∩B| - |B∩C| - |A∩C| + |A∩B∩C|
• |A-B| = |A| -  |A∩B|
• |A×B| = |A| * |B|

- 집합의 대수 법칙

- 쌍대(duality)

• 집합에 관한 명제에서 그 명제 안에 있는 교집합과 합집합을 전체 집합에 대한 여집합으로 바꾸어서 만든 새로운 명제를 원래 명제의 쌍대라고 한다.
• 전체 집합을 공집합으로, 공집합을 전체집합으로, 교집합을 합집합으로, 합집합을 교집합으로 바꾸면 만들 수 있다

 

3.3 집합류와 멱집합

1) 집합류(Class)

- 집합의 집합으로서 부분집합의 모임
- 집합 A에 대하여 A의 원소의 개수가 n개일 때 A의 부분 집합의 개수는 2^n개로 표현
- 집합 A의 카디날리티로 표현하면  아래와 같다.

 

2) 멱집합(power set)

- 임의의 집합 S에 대하여, S의 모든 부분 집합을 원소로 가지는 집합을 S의 멱집합(power set)이라 한다.
- 통상 P(S)로 표시하는데, 아래와 같이 표기할 수도 있다.

- 멱집합을 구할 때의 유의점

• 멱집합을 구한 다음에는 멱집합의 원소의 개수가 2^|A|인지 확인한다.
• 멱집합의 원소는 모두 집합이다. 그러므로 ∅를 제외한 모든 원소는 집합을 표시하는 중괄호 { } 안에 쓰인다.
• 원래 집합 A의 원소 중 집합의 원소가 있을 때에는 그 집합 자체가 하나의 원소이므로 멱집합에서는 추가적인 집합 표기가 필요하다.

- 표기

• 집합 A에 대하여 P(A)의 원소들을 나타내기 위하여 A 밑에 첨자(index)를 붙여 표기한다.
• 첨자가 붙은 집합류에서 그들의 합집합과 교집합의 연산은 다음과 같이 표기한다.

 

 

3.4 집합의 분할

1) 분할

- S를 공집합이 아닌 임의의 집합이라고 할 때 집합 S의 분할(partition) π는 다음과 같은 3가지 조건을 만족시켜야 한다.

2) 블록(Block)

- 분할의 원소를 분할을 블록이라 함.
- 분할은 집합을 구성하는 원소가 서로소이고 각 원소들의 합집합이 원래의 전체 집합이 되어야 함.
 

3.5 수의 표현과 진법의 변환

1) 컴퓨터에서의 수의 표현

- 고정소수점(fixed point), 부동소수점(floating point)
- 이진법(binary)으로 표현 : 연산속도 향상, 효율적인 저장
 

2) 기억 요소

- 최소단위 비트(bit), 0 또는 1의 2개의 상태
- 2진법, 8진법, 16진법 등
- 1byte = 8bits, 2자리의 16진수 표현 및 기억, 픽셀인 경우 밝기 또는 색 표현
 

3) 수의 표현

- 고정소수점 표현 : 2Bytes, 4Bytes
- 부동소수점 표현

• Single precision(단정도) : 4Bytes
• Double precision(배정도) : 8Bytes

 

4) 진법

- 10진법 : 0~9까지의 수를 사용하며, 10을 한 자리의 기본 단위로 하는 진법
- 2진법 : 0과 1의 조합으로 숫자를 표시하는 진법
- 8진법 : 0~7까지의 수로 표시하는 진법
- 16진법 : 10진법에서 사용하는 0~9까지의 10개의 숫자와 A~F까지의 6개의 영문자를 추가하여 수를 표시하는 진법
- 진수를 변환하면 유한한 표현이 무한한 표현이 될 수 있다. ex) 10진수 0.1 -> 2진수로 변환
- 컴퓨터에서의 표현은 4Bytes, 8Bytes 등 워드 크기에 맞는 유한 개의 자릿수로 표현해야 하므로 이로 인한 오류가 발생. 
- 일반적인 진법의 변환 : 정수부분 변환, 소수부분 변환
- 진수 변환 방법 : 아래 포스팅 참고
https://0yeonjae2.tistory.com/entry/IT%EA%B0%9C%EB%A1%A0-%EA%B0%9C%EB%85%90%EC%A0%95%EB%A6%AC-2-%EB%8D%B0%EC%9D%B4%ED%84%B0-%ED%91%9C%ED%98%84%EA%B3%BC-%EB%94%94%EC%A7%80%ED%84%B8-%EB%85%BC%EB%A6%AC

[IT개론] 데이터 표현과 디지털 논리

 

5) 수의 표현 - 부동소수점

- 16진수로 표현된 수를 4Bytes(단정도)로 된 메모리에 저장하는 경우 (IBM 계열)
정규화된 형태로 기억시킴(Normalized form)
가수부(normalized mantissa), 밑(base), 지수부(exponent)로 표현

 
- 여러 가지 실수형 자료형

• 컴파일러 vc++ : float(4), double(8), long double(8 bytes)
• 컴파일러 gcc : float(4), double(8), long double(16 bytes)

 
- IEEE 754 표준에 의한 Double형 표현

• 부호(1비트), 지수(11비트), 가수(52비트)
• 최솟값 : -1.79*(10^308) , 최댓값 : 1.79*(10^308)
• 표현할 수 있는 범위는 크지만, 정확한 값을 표현하기에는 한계가 있다.

 
- 유효숫자 : 유효숫자를 늘리기 위해서는 가수부의 길이가 중요하다.
; IEEE 754 표준에 의한 유호숫자 범위

• float (4바이트) : -3.4 * (10^38) ~ 3.4*(10^38) ; 유효숫자 7자리
• double (8바이트) : -1.79*(10^308) ~ 1.79*(10^308) ; 유효숫자 15자리

6) 수의 표현 - 고정소수점

- 컴파일러에 따른 정수형 자료형 크기

• 컴파일러 vc++ : char(1), short(2), int(4), long(4 bytes)
• 컴파일러 gcc : char(1), short(2), int(4), long(4 bytes)

- Unsigned인 경우 값의 범위

• char(1바이트) : (2^8) -1 ; 0~255
• short(2바이트) : (2^16) -1 ; 0~65535
• int, long(4바이트) : (2^32) -1 ; 0~4294967295

- 음수까지 포함한 정수형 : 2의 보수로 표현
ex) 1000 (-8), 1110 (-2), 0111 (7)
- 음수 값을 경우 포함한 경우 값의 범위

• char(1바이트) : -2^7 ~ (2^7) -1 ; -128~127
• short(2바이트) : -2^15 ~ (2^15) -1 ; -32768~32767 
• int, long(4바이트) : -2^31 ~ (2^31) -1 ; -2147483648 ~ 2147483647

이진수	Unsigned	Signed Magnitude	2’s Complement
0000	0	0	0
0001	1	1	1
0010	2	2	2
0011	3	3	3
0100	4	4	4
0101	5	5	5
0110	6	6	6
0111	7	7	7
1000	8	0	-8
1001	9	-1	-7
1010	10	-2	-6
1011	11	-3	-5
1100	12	-4	-4
1101	13	-5	-3
1110	14	-6	-2
1111	15	-7	-1
	0~15 (16개)	-7~7 (15개)	-8~7 (16개)

 

3.6  2진수의 덧셈과 뺄셈

1) 보수(complement) :  진수를 나타내는 수 r의 보수와 (r-1)의 보수가 있다.

- (r-1)의 보수

• (r-1)의 값에서 수의 각 자리의 숫자를 뺀다.
• ex) 10진수 123의 9의 보수는 876이다.
• 2진수에서 보수를 사용할 때 1의 보수를 쉽게 구하려면 각 자리수의 0과 1을 서로 바꾸면 된다.
• ex) 2진수 1010의 1의 보수는 0101이다.

- r의 보수

• (r-1)의 보수를 구하여 가장 낮은 자리에 1을 더한다.
• ex) 10진수 123의 10의 보수는 877이다. (876+1)
• ex) 2진수 1010의 2의 보수는 0110이다.

2) 2의 보수로 해석하고 뺄셈 수행

 

3.7 집합론의 응용과 4차 산업혁명과의 관계

1) 무한집합의컴퓨터 모델 이론에의 기여

무한집합이라고 해서 모두 같은 카디날리티를 가지지 않으며 모든 정수들의 집합과 모든 실수들의 집합은 일대일로대응될수 없다는 '대각선화' 이론은 튜링 머신(Turing Machine) 이론에 결정적으로 기여했다.
 

2) 집합과 4차 산업혁명과의 관계 : 튜링 머신을 통한 인공지능

앨런 튜링은 원하는 계산을 '프로그래밍할 수 있는' 계산 기계를 만들 수 있는 이론적 가능성을 확립한 추상적인 정리를 만들었다. 무한집합에서의 '대각선화'가 그의 이론을 크게 뒷밤침하였고 최근의 인공지능 컴퓨터 개발에도 기여했다. 또한 튜링은 오늘날 4차 산업혁명의 핵심 기술인 인공지능의 성능을 입증할 수 있는 기준을 제시하였다.