명동 스터디 : 기초를 숙련한지 너무 오래되어 컴퓨터공학부 커리큘럼의 필수 과목과 관련된 공부를 통해 기초를 숙련하고 숙련된 기초를 통해 프로젝트 진행을 하기 위한 4명의 스터디 모임
기원 : ki-w0n.tistory.com
백범 : https://long-shift-6b9.notion.site/dbf9ea3ec9fd49379e43c127e470123a
찬형 : https://memo.chanhyung.kim/407d7b36c9204fb3813a42eac8674897
병묵 : https://manso98.notion.site/23723aa1c0bb44828b52fc57efa6639e
명동 스터디 첫번째 커리큘럼 일정(2024.07.29 ~2024.11.16)
- 컴퓨터 과학 기초(07.09 ~ 07.21)
- 이산수학(07.29 ~ 08.17)
- 자료 구조(08.19 ~ 09.07)
- 컴퓨터 구조(09.09 ~ 10.12)
- DB(10.07 ~ 10.26)
- 네트워크(10.28 ~ 11.16)
목차
증명의 이해
증명은 어떤 사실이 참(T)임을 보이는 것으로 증명에 사용되는 모든 내용들이 타당해야만 정당한 증명이 됩니다.
증명(proof)
논리적 법칙을 이용하여 주어진 가정으로부터 결론을 유도하는 추론 방법입니다.
공리(axiom)
논리학이나 수학 등의 이론체계에서 가장 기초적인 근거가 되는 명제입니다.
정의(definition)
말이 지니는 의미 내용에 착오가 일어나지 않도록 뚜렷이 정한 절차를 뜻합니다.
정리(theorem)
수학적 논증의 추론 결과에 따라 참으로 증명된 명제입니다.
여러가지 증명 방법
- 직접 증명법 : 명제의 조건을 그대로 이용하여 증명이 가능한 경우
p->q가 참(T)임을 증명하기 위해 전체 p를 참(T)으로 가정했을 때, 결론 q도 참(T)임을 증명하는 방법
ex)p->q : 두 정수 m, n이 홀수이면 m과 n의 곱은 홀수이다.
p : 두 정수 m, n은 홀수이다.
q : m과 n의 곱은 홀수이다.
m = 2k+1(k∈Z), n= 2k+1(l∈Z)
mn = (2k+1)(2l+1) = 4kl + 2k + 2l + 1 = 2(2kl + k + 1) + 1 = 2a+1 (2kl + k + l을 a로 치환)
=>홀수 정의에 따라 계살 결과 2a + 1 은 홀수이다. - 간접 증명법 : 가정 p가 참(T)이라고 가정할 때 p에 따르는 명제로부터 논리법칙을 이용하여 결론 q를 연역하여 p=>q가 참(T)임을 증명하는 방법입니다.
- 모순 증명법 : 귀류법이라고 불리기도 하며 p->q에서 참으로 가정하고 결론인 q를 부정했을때 거짓이 되는 것을 이용하여 p->q가 참임을 증명하는 방법입니다.
모순 증명법은 결론에 해당하는 명제 q를 부정(NOT)하여 증명하는 방식으로 진리값이 거짓(F) 증명해야 하는 본 명제 p->q가 참(T)이라고 확인할 수 있는 증명 방법 입니다.
ex)p->q : 두 정수 m, n은 홀수이다.
p : m과 n의 곱은 홀수이다.
¬q : m과 n의 곱은 홀수가 아니다.(짝수이다.)
p∧¬q : 두 정수 m, n은 홀수이고, m과 n의 곱은 홀수가 아니다.(짝수이다.)
m = 2k+1(k∈Z), n= 2l+1(l∈Z)
mn = (2k+1)(2l+1) = 4kl + 2k + 2l + 1 = 2(2kl + k + 1) + 1 = 2a+1 (2kl + k + l을 a로 치환)
=> 홀수의 정의에 따라 2a + 1은 홀수이다. 그러므로 p∧¬q '정수 m, n은 홀수이고, m과 n의 곱은 홀수가 아니다.'는 거짓(F).
결국 ¬(p∧¬q)는 참(T)이고, 이 명제와 동치인 본 명제 '두홀수의 곱은 홀수이다'는 참(T)입니다.
- 대우 증명법 : 명제를 대우 명제로 바꾼 후 증명이 가능한 경우
p->q와 이에 대한 대우 명제 ¬q->¬p가 서로 논리적으로 동치라는 점을 확용하여 간접 증명하는 방법 입니다.
ex)p->q : 두 정수 m과 n의 곱이 홀수이면, m과 n은 모두 홀수이다.
p : 두 정수 m과 n의 곱이 홀수이다.
q : m과 n은 모두 홀수이다.
¬p : 두 정수 m과 n의 곱은 홀수가 아니다.(짝수이다.)
¬q : m과 n 중 적어도 하나는 홀수가 아니다.(짝수이다.)
¬q->¬p : m과 n 중 적어도 하나는 홀수가 아니다.(짝수이면), 두 정수 m과, n의 곱은 홀수가아니다.(짝수이다.)
대우 명제의 조건에 해당하는 명제 ¬q는 m과 n 중 하나만 짝수인 경우와 m과 n 모두 짝수인 경우 모두 고려하여 증명해야합니다.
그래서 두 경우 모두에 대하여 대우 명제가 참(T)가 증명되면, 명제 ¬q->¬p가 참(T)입니다.
1) m과 n 중 하나만 짝수인 경우
m = 2k(k∈Z), n= 2l + 1(l∈Z) -> mn=2k(2l+1) = 4kl+2k = 2(2kl+k)
위 결과처럼 m과 n 중 하나만 짝수인 경우, m과 n의 곱 mn은 짝수이다. 그러므로 두 정수 m 과 n 중 하나만 짝수이면 m과 n의
곱은 홀수가아니다
2) m과 n 모두 짝수인 경우
m = 2k(k∈Z), n= 2l(l∈Z) -> mn = 2k * 2l = 4kl =2(2kl)
1)과 마찬가지로 m과 n이 모두 짝수인 경우 m과 n의 곱 mn이 짝수이다. 그러므로 두 정수 m과 n 모두 짝수이면 m과 n의 곱은
홀수가 아니다.
- 존재/반례 증명법 : 명제를 대우 명제로 바꾼 후 증명이 가능한 경우
1) 존재 증명법 : 명제가 참(T)이 되는 예를 찾아서 증명하는 방법
2) 반례 증명법 : 명제가 모순이 되는 예를 찾아 증명하는방법 - 수학적 귀납법 : 자연수에 관한 명제 P(n)이 모든 자연수(또는, 어떤 자연수보다 큰 모든 자연수)에 대하여 성립함을 보이는
증명법
수학적 귀납법의 세단계 증명
1. 기본 가정 : 명제의 논의영역 D의 첫 번째 값 d에 대하여, P(d)가 참(T)임을 보인다.
2. 귀납 가정 : 논의 영역 속하는 임의 값 k에 대하여 P(k)가 참(T)이라고 가정한다.
3. 귀납 증명 : 기본 가정과 귀납 가정을 이용해 논의 영역에 속하는 값 k+1에 대하여, P(k+1)이 참(T)임을 증명한다.
집합의 개념
집합(Set) : 집합은 순서가 없는 서로다른 원소들의 모임입니다.
유한 집합 : 수학에서 유한 집합이란 집합의 원소의 개수가 한정되어 원소의 개수가 무한개가 아닌 집합을 의미합니다.
무한 집합 : 수학에서 무한집합은 원소의 개수가 무한히 많은 집합으로, 원소의 개수가 유한한 유한 집합이 아닌 모든 집합입니다. 무한 집합은 크게 가산 무한 집합과 비가산 집합으로 나눌 수 있습니다.
집합의 표기 방법
- 원소 나열법 : 집합의 원소들을 { } 사이에 하나씩 나열 하는 방법 (ex. A = {a, b, c, d, e, f}
- 조건 제시법 : 집합 원소들이 가지고 있는 특정한 성질을 조건식을 통해 제시하는 방법 (ex. A = {x | p(x) | x<5}
- 벤 다이어그램 : John Venn이 고안한 diagram으로 집합과 집합, 집합과 원소간의 관계를 그림으로 표현
집합의 종류
- 전체 집합 : 집합론에서의 전체 집합은 모든 대상(자기 자신 포함) 원소로 포함하는 집합.
- 공집합 : 원소가 없는 집합.
- 상등 : 두 집합 A와 B가 서로 같다는 것은 각 원소가 모두 같다는 것을 의미하며 A=B로 표시합니다.
- 부분집합 : B집합의 모든 원소가 A집합에 속하는 집합이다. A ⊃ B로 표시합니다.
- 진부분집합 : 자기 자신을 제외한 부분집합을 말하며 A = {1, 2}인 경우 A의 부분집합은 {}, {1}, {2}, {1, 2}이지만 진 부분집합은 {}, {1}, {2} 입니다.
집합의 연산
합집합(union, A ∪ B) : 집합론에서, 둘 또는 더 많은 집합의 합집합은 그 집합의 모든 원소를 한군데 합쳐놓은 집합입니다.
교집합(intersection, A ∩ B) : 집합론에서, 두 집합 A와 B의 교집합은 그 두집합이 공통으로 포함하는 원소로 이루어진 집합입니다.
서로소(disjoint, A ∩ B = ∅) : 공통으로 포함하는 원소가 없는 두 집합의 관계입니다.
차집합(difference, A-B) : 집합 A에서 B집합의 원소를 뺀 집합
대칭차집합(symmertric difference, A⨁B) : 두 집합 A-B와 B-A의 합집합
곱집합(product set, A X B) : 각 집합 원소를 각성분으로 하는 튜플들의 집합입니다. A X B ={(a, b) | a ∈ A, b ∈ B}입니다.
A = {1, 2}, B = {a, b, c}
A X B + {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
집합의 대수법칙
| 법칙 | 집합연산 |
| 멱등법칙(idempotent law) |
A∪A=A
A∩A=A
|
| 항등법칙(identity law) | A∪∅=A A∩∅=∅ A∪U=U A∩U=A |
| 교환법칙(commutatuve law) |
A∪B=B∪A
A∩B=B∩A
|
| 결합법칙(associative law) |
(A∪B)∪C=A∪(B∪C)
(A∩B)∩C=A∩(B∩C)
(A⊕B)⊕C=A⊕(B⊕C)
|
| 분배법칙(distributive law) |
A∪(B∩C)=(A∪B)∩(A∪C)
A∩(B∪C)=(A∩B)∪(A∩C)
|
| 흡수법칙(absorption law) |
(A∩B)∪A =A
(A∪B)∩A=A
|
| 보법칙(complement law) | (Ac)c=A |
| 역법칙(inverse law) | A∪Ac=U A∩Ac=∅ Uc=∅ ∅c=U |
| 드 모르간의 법칙(de morgan's law) | (A∪B)c=Ac∩Bc (A∩B)c=Ac∩Bc |
| 그 외 | A−B=A∩Bc A−A=∅ A−∅=A |
'DevOps > IT Knowledge' 카테고리의 다른 글
| 명동 스터디_이산수학_5(관계) (0) | 2024.08.18 |
|---|---|
| 명동 스터디_이산수학_4(행렬) (0) | 2024.08.17 |
| 명동 스터디_이산수학_2(명제와 논리) (0) | 2024.08.03 |
| 명동 스터디_이산수학_1(수의 표현과 연산) (0) | 2024.07.30 |
| 명동 스터디_컴퓨터 과학 기초_5 (1) | 2024.07.19 |
| 명동 스터디_컴퓨터 과학 기초_4 (0) | 2024.07.18 |
