01. 이산수학을 위한 기본 개념

1.1 이산수학이란?

이산수학의 개념

이산(discrete)은 연속(continuos)이라는 개념과 비교되는 개념으로 서로 구별될 수 있는 부분들로 이루어진 것

수학(mathematics)이란 수학적 대상의 성질들을 연구하는 학문

 

-> 이산수학이란? 이산수학적 대상의 성질들을 연구하는 학문

 

1.2 이산수학의 전형적인 문제: 마술카드

비트로 표현할 수 있는 경우의 수, 진법 변환 방법 등 같은 방식으로 풀 수 있음

 

1.3 자연수와 정수의 성질

정수론: 원칙적으로 정수의 성질들을 연구하는 분야

 

자연수: 1부터 시작하여 1씩 증가하는 연속된 숫자들

 

자연수에 대한 공리 

 

자연수에 대한 성질

a,b,c를 자연수라고 할 때 덧셈의 교환, 결합법칙 / 곱셈의 교환, 결합법칙 / 분배법칙 이 성질들을 만족함

 

항등원: 어떤 연산에 대해 닫혀있는 집합이 존재할 때, 이 집합의 원소와 이항 연산을 했을 때 다시 그 원소를 값으로 갖는 원소가 유일한 경우, 이 원소를 항등원이라 함

 

정렬순서 원리: 어떤 집합에 대해서 공집합이 아닌 임의의 모든 부분집합들은 각각 하나의 최소 원소를 갖는다

 

정수: 자연수와 이들의 음수, 그리고 0으로 이루어진 수 체계

 

소수: 1과 자시 자신만을 갖는 1보다 큰 정수

 

합성수: 소수가 아닌 1보다 큰 양의 정수

 

에라토스테네스의 체: 어떤 수에 대해서 그 수를 초과하지 않는 모든 소수를 찾아내는 방법

 

1.4 행렬

행렬

행렬(matrix): 행과 열로 나열하는 것 / 스칼라(scalar): 행렬의 각 성분은 실수

• 행렬의 합은 대응하는 성분끼리의 합 - 덧셈의 교환, 결합, 항등법칙 성립
• 행렬의 곱 AB는 A의 열의 개수와 B의 행우 개수가 같아야 계산 가능 - 곱셈의 결합, 분배법칙 성립

 

영행렬: 각 성분이 0인 행렬

 

특수 행렬

n차 정방 행렬: 행과 열의 수가 n으로 같은 행렬 - 행(혹은 열)의 개수를 정방 행렬의 차수라 함

 

대각 행렬: 주대각 원소(n차 정방 행렬에서 대각선상에 위치한 원소)를 제외한 나머지가 원소가 모두 0인 행렬

ex) 대각 행렬

• 단위 행렬 또는 항등 행렬 - 주대각 원소들은 모두 1, 나머지 원소들은 모두 0인 정방 행렬
• 스칼라 행렬 - 주대각 원소들이 모두 같은 값을 갖는 대각 행렬

 

전치 행렬: A가 임의의 mxn 행렬일 때 A의 행과 열을 바꾸어서 얻어진 nxm 행렬

 

대칭 행렬: 정방 행렬에서 자신과 자신의 전치 행렬이 똑같은 행렬

 

상삼각 행렬: 주대각 원소의 아래쪽에 있는 모든 원소들이 0인 정방 행렬

하삼각 행렬: 주대각 원소의 위쪽에 있는 모든 원소들이 0인 행렬

삼각 행렬: 상삼각 행렬이건 하삼각 행렬

 

띠 행렬: 주대각 원소와 평행한 몇 줄의 원소들만 값을 갖고, 그 이외의 모든 원소들은 모두 0인 행렬

 

특이 행렬: A란 A의 역행렬이 존재하지 않는 행렬로 det(A) = 0이 되는 행렬

 

정칙 행렬: A란 A의 역행렬이 존재하지 않는 행렬로 det(A) ≠ 0이 되는 행렬

 

역행렬: 정방 행렬 A에 대해서 AB = BA = I를 만족하는 정방 행렬 B가 존재할 때 A는 가역이라 하고, B가 A의 역행렬

가역 = 역행렬이 존재

 

증가 행렬: 주어진 행렬 A의 오른쪽에 추가적으로 첨가하여 만든 행렬

 

직교 행렬: A-1 = AT를 만족하는 행렬

 

부울 행렬