> For the complete documentation index, see [llms.txt](https://emperorvv.gitbook.io/cs-curriculum/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emperorvv.gitbook.io/cs-curriculum/class3_-discrete_mathematics-discrete-mathematics/ch1-2.md).

# 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이다.

```javascript
// 덧셈에 대한 항등원 : 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
```