opid's document

˚ 행렬(Matrix)    n×m 

정의 : 실수를 n행, m열로 나열된 배열을 말한다.

1) 행렬의 스칼라 곱(Scalar Multiplication) : 행렬 A에 실수 k를 곱하는 연산

2) 행렬의 곱셈

˚ 행렬의 종류

1) 영행렬(Zero Matrix)    O

2) 2차 정사각행렬(n-square Matrix) : 행과 열이 같은 행렬

3) 대각행렬(Diagonal Matrix) : 정사각행렬에서 대각원소 이외의 모든 원소가 0인 행렬

4) 단위행렬(Unit Matix, Identity Matrix) : 대각행렬에서 대각원소가 모두 1인 행렬

5) 전치행렬(Transpose Matrix) 

: m × n 행렬의 행과 열을 바꾼 n × m 행렬

6) 대칭행렬(Symmetric Matrix) : 인 행렬

7) 부울행렬(Boolean Matrix, Zero-One Matrix) : 모든 원소가 0,1로 구성된 행렬

* 부울행렬 연산자

(1) 합(join) : A∨B=

(2) 교차(meet) : A∧B=

(3) 부울곱(boolean product) : A⊙B

* 부울행렬 연산의 특징

(1) A∨A=A, A∧A=A

(2) A∨B=B∨A , A∧B=B∧A

(3) (A∨B)∨C=A∨(B∨C)

(4) A∨(B∧C)=(A∨B)∧(A∨C)

˚ 행렬식(Determinant) |A| or det(A)

정의 : n차 정사각행렬에 대응하는 수를 구하는 식

1) 소행렬(Minor Matrix)

n차 정사각행렬에서 r번쨰 행과 s번째 열을 제거해서 얻은 (n-1)×(n-1)행렬

2) 소행렬식 det(A)

n차 정사각행렬의 소행렬 에 대한 행렬식

3) 여인수(Cofactor) , 여인수행렬(Cofactor Matrix)

n차 정사각행렬 에서 원소 에 관련된 수와 그 수들에 대한 행렬

4) 여인수를 이용한 행렬식

˚ 역행렬(Inverse Matrix) 

정사각행렬 A에 대해 AB=BA=I를 만족하는 행렬 B

1) 행렬식을 이용한 역행렬

2) 수반행렬

여인수행렬 에 대한 전치행렬

3) 가역행렬(Invertible Matrix 또는 Nonsingular Matrix)

역행렬이 존재하는 행렬

4) 특이행렬(Singular Matrix)

역행렬이 존재하지 않는 행렬

* 행렬식을 이용한 역행렬에서 의 분모가 0이 되면 특이행렬이 된다.

˚ 연립 1차 방정식(System at linear Equation) : 1차 방정식 m개로 구성된 방정식

1) 첨가행렬(Augmented Matrix)

2) 1차 방정식의 해를 구하는 방법

(1) 가우스 소거법(Gaussion Elimination)

① 가우스 소거법(Gaussion Elimination)

계수행렬의 대각원소들이 모두 1로 만들고, 대각원소를 기준으로 아래쪽 원소들은 모두 0으로 만든 후 위쪽 원소들은 계수들로 남겨놓은 형태의 첨가행렬

② 가우스 조르단 소서법(Gauss Jordan Elimination)

가우스행렬의 계수 부분을 단위행렬로 만들어 구하는 방법

˚ 수의 종류

1) 자연수 N : 0보다 큰 정수

2) 정수 Z : 양의 정수, 0, 음의 정수로 구성된 수

3) 유리수 Q : 두 정수 a,b로 a/b(분수)의 꼴로 나타낸 수이며, b≠0 이고 b=1이면 정수가 된다. 

*하한항(lowset) : 분모와 분자 사이에 1 이외의 공약수가 존재하지 않는 유리수

4) 무리수 I : 실수 중 유리수가 아닌 수. a/b(b≠0)로 나타낼 수 없는 수.

5) 실수 R : 무리수와 유리수를 모두 포함하는 수.

6) 복소수 C : x² = -1을 포함하는 수 체계

˚ 수의 연산

1) 닫힘 성질

2) 수의 특징

3) ∑(시그마) : 일정한 규칙을 나열한 수를 더할 때 쓰는 기호

4) ∏(프로덕트) : 일정한 규칙을 나열한 수를 곱할 때 쓰는 기호

5) 나머지 연산 : 정수 n을 d로 나누어 나오는 몫 q와 나머지 r이 있을때, r을 구하는 연산.

n mod d = r     n mod d = 0 ⇔ d|n

˚ 보수

1) 컴퓨터에서의 데이터 표현

양수인 경우 부호비트가 0, 음수인 경우 1이 된다.

* 부호화-절대치 표현 : 부호와 데이터의 절댓값을 그대로 표현

1의 보수 : 음수 표현에만 사용 된다.

   2진법에 있어서 보수를 취할 때 각 자리의 반대수 (0→1, 1→0)를 취하는 보수.

2의 보수 : 음수 표현에만 사용되고, 절대치 비트에대한 1의 보수에 1을 더한다.

˚ 집합

집합이란? 영어 대문자(A, B, C, D, … )로 표기하며 어떤 조건들에 의해 분류되서 모인 요소들의 모임.

집합의 표기방식

1) 원소나열법 : 집합에 포함되는 원소를 일일이 나열하는 방법

ex) A={1,2,3,4}

2) 조건제시법 : 집합에 포함되는 원소의 공통적인 성질을 조건식으로 제시하는 방법

ex) A={x|x<5, x∈N}

집합과 원소의 포함관계 : 1 ∈ A 또는 5 ∉ A

기수(Cardinality) : 집합 A가 포함하는 원소의 수    |A| = 4

상등(Equal) : 두 개의 집합의 원소가 동일할 때 '상등'한다고 한다.    A=B⇔(a∈A∧a∈B)

˚ 집합의 종류

1) 전체집합(Universal Set) U : 논의 대상이 되는 원소 전체를 포함하는 집합

2) 공집합(Empty Set) { } or ∅ : 원소를 포함하지 않은 집합, |∅|=0

3) 부분집합(Subset) A⊆B : A의 모든 원소가 B에 포함되는 경우, |A|≤|B|

4) 진부분집합(Proper Subset) A⊂B : B에 대하여 A의 요소 모두는 포함되어 있지 않은 부분 집합, |A|<|B|

˚ 집합의 연산

1) 합집합(Union) : 집합 A,B에 대하여 A에 속하거나 B에 속하는 원소로 되는 집합.

A∪B={x|x∈A∨x∈B}

2) 교집합(Intersection) : 집합 A,B에 대하여 A와 B에 동시에 속하는 원소로 되는 집합.

A∩B={x|x∈A∧x∈B}

3) 여집합 또는 보집합(Complement) : 전제집합에 속하지만 A를 제외 한 나머지.

A′={x|x∈U∧x∉A}=U-A

4) 차집합(Difference) : 집합 A,B에 대하여 A에 속하지만 B에 속하지 않는 집합.

A-B={x|x∈A∧x∉B}

5) 대칭차집합(Symmetric Difference) : 집합 A,B에 대하여 A-B 또는 B-A에 속하는 집합.

A⊕B={x|(x∈A∧x∉B)∨(x∈A∧x∉B)}={x|(x∈A-B)∨(x∈B-A)}

6) 서로소(Disjoint) : 집합 A,B에 대하여 공통으로 속하는 원소가 하나도 없는 경우.

A∩B=∅

˚집합의 대수법칙

* 흡수법칙 증명

A∪(A∩B) = (A∪∅)∩(A∪B)    항등법칙

  = A∪(∅∩B)            분배법칙

  = A∪∅                  지배법칙

  = A                        항등법칙

˚ 공리(Axion)

하나의 이론에서 증명 없이 참(T)이 되는 명제

ex) a=b면, a+c=b+c다.

˚ 정의(Definition)

 논의의 대상을 보편적인 것으로 하기 위해, 사용되는 용어 또는 기호의 의미를 확실하게 규정한 문장이나 식.

ex)한 내각의 크기가 직각인 삼각형을 직각삼각형이라 한다.

˚ 정리(Theorem)

공리와 정의를 통해 증명이 된 명제

ex) 피타고라스의 정리 : 직각삼각형은 빗변의 길이를 한 변으로 하는 정사각형의 넓이와

나머지 두 변의 길이를 각각 한변의 길이로 한 정사각형 두 개의 넓이의 합과 같다.

˚ 증명(proof)

어떤 명제가 참임을 확인하는 과정

˚ 직접증명법(Direct Proof)

명제를 변형하지 않고 함축명제 p→q가 T을 증명하는 방법이다.

예제) 모든 정수에 대해 짝수에서 홀수를 뺀 수가 홀수임을 증명하라.

풀이) p : x는 짝수다.

q : x에서 홀수 y를 뺀 수는 홀수다.

p→q : 짝수인 x에서 홀수인 y를 뺀 수는 홀수다.

정수 m,n이 있을 때, 짝수 x는 x=2m, 홀수 y는 y=2n+1 으로 표현할 수 있다.

x에서 y를 뺀 식을 표현하면 다음과 같다.

x - y = 2m - ( 2n + 1 ) = 2m - 2n - 1 = 2 ( m - n ) - 1

m-n을 변수 a로 치환하면, x-y=2a-1로 홀수가 된다.

∴ 명제 p→q "짝수인 x에서 홀수인 y를 뺀 수는 홀수다"는 참이다.

˚ 간접증명법(Indirect Proof)

직접 증명하지 않고, 간접으로 증명하는 방법으로, 대우증명법, 모순증명법, 반례증명법, 존재증명법이 있다.

1) 대우증명법(Proof by Conterposition)

함축명제 p→q와 ￢q→￢p가 동치임을 이용하여 증명하는 방법.

2) 모순증명법(Proof by Conteadiction)

함축명제 p→q와 ￢(p∧￢q)가 동치임을 이용하여 증명하는 방법.

3) 반례증명법(Proof by Counter-Example)

주어진 명제에 모순이 되는 예를 찾아 증명하는 방법.

4) 존재증명법(Existence Proof)

주어진 명제가 참이 되는 예를 찾아 증명하는 방법.

˚ 수학적 귀납법(Mathematical Induction)

자연수 n에 관한 명제 p(n)이 임의의 자연수에 대하여 만족하는 것을 세 단계의 과정으로 증명하는 방법이다.

1) 기본가정 : p(논의영역의 초깃값)가 성립한다.

2) 귀납가정 : 명제 p(k)가 성립한다면, p(k+1)도 성립한다고 가정한다.

3) 귀납단계 : 기본가정과 귀납가정을 이용해 p(n)이 성립함을 증명한다.

* 귀납이란? 여러 가지 특정 사실들로부터 일반적인 사실을 유도해내는 추론 방법

---

이산수학

저자

박주미 지음

출판사

한빛미디어 | 2011-08-29 출간

카테고리

컴퓨터/IT

책소개

논리적 사고를 높여주는 예제로 배우는『이산수학』. 컴퓨터 연산을...

---

˚ 명제

1. 명제(Proposition)

참(Ture)인지 거짓(False)인지를 명확하게 판별할 수 있는 문장이나 수식 : p,q,r, …로 표현

2. 진릿값(Truth Value)

참이나 거짓을 가르키는 말 : 0, 1

3. 논리 연산자(명제의 결합)

1) NOT    부정(Negation) : 'not p' or 'p의 부정'

문장 p가 명제일 때 ~p, ￢p도 명제.

2) AND    논리곱(Conjunction) : 'p and q' or 'p 그리고 q'

p, q 모두 T 일 때 p∧q는 T

3) OR    논리합(Disjunction) : 'p or q', 'p 또는 q'

p, q 모두 F 일 때만 F, p∨q

4) XOR     배타적 논리합(Exclusive OR) : 'p ⊕ q'