ch1-2

1. 이산수학

1.1. 이산수학이란

이산수학(Discrete mathematics, 離散數學)에서 이산이란 연속성이 없는 분리된 상태를 의미한다. 한마디로 붙어있지 않고 떨어진 값들을 다루는 학문이다. 이렇게 다루는 이유는 컴퓨터는 애초에 bit(0과 1)로 데이터를 처리하고 On/Off(1/0)의 전기신호로 연산을 하기 때문이다.

1.2. 이산수학에서 다루는 것들

• 연산과 수

• 문제해결을 위한 논리와 증명

• 데이터 관리와 집합

• 자료 처리를 위한 행렬과 관계

• 명령 정의를 위한 함수

• 효과적 문제 해결과 자료 관리를 위한 그래프와 트리

• 회로 설계와 부울 대수

• 결과 예측을 위한 확률

• 효율성을 위한 알고리즘

2. 수의 표현

2.1. 수체계

중고등학교에서 우리가 배웠던 것처럼 수는 형태에 따라 분류를 하고 이름을 붙이는 데 이를 수 체계라 한다.

2.1.1. 자연수

def : 0보다 큰! 양의 정수

기수와 자리수를 이용해 표현할 수 있는데 10진수 589는 5 * 10^2 + 8 * 10^1 + 9 * 10^0 이런식으로 전개해서 표현할 수 있다. 더 확장해서 일반식으로 만들어서 수체계의 각 형태를 표현하기도 한다.

2.1.2. 정수

def : 양의 정수, 0, 음의 정수

2.1.3. 유리수

def : 두 정수 a, b로 이루어진 분수 b/a (단 a != 0)

2.1.4. 무리수

def : 유리수로 표현할 수 없는 수

2.1.5. 실수

def : 자연수, 정수, 유리수, 무리수를 모두 포함하는 수 체계

2.1.6. 복소수

def : √-1, 즉 제곱하여 -1이 되는 가공의 수를 허수(i)라 하는데 이 허수와 실수를 포함하는 수체계

c = a + bi 형태로 표현되며 실수부(a)와 허수부(b)가 있다.

2.2. 수의 연산

수체계 S에 속하는 어떤 수 a,b를 연산자 O로 연산한 결과 c가 S에 속하면 "S는 연산 O에 닫혀 있다"고 표현한다. 즉 모든 자연수는 어떻게 덧셈을 해도 자연수 이므로 "자연수는 덧셈에 대해 닫혀 있다."고 말할 수 있다.

2.2.1. 사칙 연산에 대한 닫힘성질(기호 O가 닫혀있다는 뜻)

수	+	-	*	/
자연수	O	X	O	X
정수	O	O	O	O
유리수	O	O	O	O
무리수	X	X	X	X
실수	O	O	O	O
복소수	O	O	O	O

무리수의 경우

• 덧셈 : -√3 + √3 = 0(유리수)

• 뺄셈 : √3 - √3 = 0(유리수)

• 곱셈 : (√3)^2 = 3(유리수)

• 나눗셈 : √3 / √3 = 1(유리수)

모든 연산에 대해 유리수가 될 수 있는 반례가 있으므로 닫혀있지 않다.

2.2.2. 덧셈과 곱셈 연산 특징

1. 교환법칙 : x + y = y + x, xy = yx

2. 결합법칙 : (x + y) + z = x + (y + z), (xy)z = x(yz)

3. 분배법칙 : x(y + z) = xy + xz

2.2.3. 항등원과 역원

• 항등원\

  해당 연산자에 대해 어떤 수 a와 연산한 결과가 a가 되게 하는 수\

  예를 들어 덧셈에서는 0이다.

• 역원\

  해당 연산자에 대해 어떤 수 a와 연산한 결과가 그 연산자의 항등원이 되게 하는 수\

  예를 들어 덧셈에서는 역원이 -a이다.

// 덧셈에 대한 항등원 : 0
a + 0 = a
// 덧셈에 대한 역원 : -a
a + (-a) = 0
// 곱에 대한 항등원 : 1
a * 1 = a
// 곱에 대한 역원 : (1/a)
a * (1/a) = 1

2.2.4. 시그마(Σ)

일정한 규칙이 있는 수열의 합을 시그마 기호를 사용하여 구한다. 예를들어 20이하의 홀수의 합은 다음과 같다. 10 Σ(2i - 1) = 1 + 3 + 5 ... + 17 + 19 i=1

2.2.5. 프로덕트(∏)

일정한 규칙이 있는 수열의 곱은 프로덕트 기호를 사용하여 구한다. 10 ∏(2i - 1) = 1 3 5 ... 17 19 i=1

2.2.6. 팩토리얼(!)

n! = n * (n-1) * ... * 2 * 1

2.2.7. 몫과 나머지 연산자

몫(Quotient)연산자는 몫이 얼만지를 나타낸다.

5 | 20 = 4

나머니(Remainder)연산자는 나머지가 얼마인지를 계산한다.

20 mod 3 = 2