오늘 한 일
코딩 봉사
이산수학 강의
과제
복습
내일 할 일
모각코 회의
계산이론 강의
이산수학 + 계산이론 예제 풀기
스위프트 강의
책 읽기
-------------------------------
비형식적 증명 : 알만한 것들은 일일이 적지 않고 그냥 넘김.
action : 증명할 수 없다. 참이라고 전제한다.
보조정리(lemma) : 다른 결과를 증명하는 데 도움이 되는 정리
계(corollary) : 증명된 정리로부터 직접적으로 귀결
가설(conjecture)
전칭한정사를 생략할 때가 종종 있다.
전칭예시화 : 정의역에 속하는 임의의 수 C가 참이면 참.
P(C) -> Q(C)
trivial : 결론이 참임이 자명
vacuos : 공허한 증명. 가정이 거짓.
모순에 의한 증명 : ㄱp -> q : T에서 q가 F면, ㄱp가 T여야 전제가 T.
=> p가 참임을 보이고 싶을 때, ㄱp가 F임을 보여서 증명.
p->q임과, q->p임을 증명해서 필요충분조건임을 증명.
닫힌 구간 : [a, b] = {x|a <= x <= b}
열린 구간 : (a, b) = {x|a < x < b}
P(A) : 멱집합, 거듭제곱 집합. 모든 부분집합의 집합.
A = {a,b}
p(A) = {공집합, {a}, {b}, {a, b}}
튜플 : 순서를 가지고 있는 쌍. (a,b)와 (c,d)가 순서를 가진 쌍이라면, a=c and b = d와 필요충분 조건이다.
카타시안 곱 : A x B = {(a, b) | a 삼지창 A ㅅ b 삼지창 B}
A = {a,b}
B = {1,2,3}
AxB = {(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)}
진리집합 : P(x)를 true로 하는 것들을 정의역으로 하는 집합
즉, A -> B에서, A에 속하면서도 B를 만족하는 원소를 모아놓은 집합
membership table에서 속할 땐 1 아닐 땐 0
(U위에 n 아래엔 i = 1)
UAi = A1 U A2 ... An
교집합의 경우도 있다.
수열 : 순서가 있는 배열. 시퀀스의 합.
String : 문자의 유한수열
점화관계 : an을 이전 항들을 이용해서 표현
초기항 : 재귀관계를 시작하는 항
피보나치 : f0 = 0 + f1 = 1
f1 = 1 + f2 = 1
f2 = 1 + f3 = 2
...
fn = n + fn+1 = n+1
닫힌 공식 : 점화관계로부터 수열의 일반항 an을 찾아내는 것
f(a) = b에서
b는 image
a는 b의 preimage
단사(injection) : 일대일 함수. 정의역이 다르면 대응되는 치역의 값도 모두 다름.
전사(surjection) : 치역과 공역이 같음.
전단사(bijections) : 일대일 대응
합성함수 f o g가 존재하려면 f의 range가 g domain의 subset이여야 한다.
그래프 : 순서쌍의 집합
(원래는 x보다 위에 있어야 함)
┌x┓ : x보다 작거나 같은 최대의 정수
(원래는 x보다 아래에 있어야 함)
└x┛ : x보다 크거나 같은 최소의 정수
(j는 m부터 시작, n으로 끝)
대문자 파이aj : am x am+1 x ... x an
cardinality : 집합의 크기. 유한집합에서 집합의 크기 -> 원소의 개수. 무한집합에선? countable(자연수, 정수, 유리수)과 uncountable(실수)
|A| = |B| : 전단사 함수.
|A| <= |B| : 단사 함수
|A| < |B| : |A| <= B ㅅ |A| != |B|
셀 수 있는 것의 유한집합에서 집합의 크기 아레프
무한 : 엄청 큰 상태가 아니라, 계속해서 커지고 있는 상태이다.
행렬에선 교환법칙 성립x
n차 항등행렬(identity matrix) : 대각선은 1이고 나머지는 0.
A^0 = In
전치(Transpose) : 행과 열을 바꾸겠다.
A = A^T
zero-one Metrix : 0과 1로만 이루어져 있다.
b1ㅅb0 : and. meet
b1vb0 : or. join
부울 곱(boolean product) : 행렬끼리 곱할 때, 곱하기는 join, 더하기는 meet로 함. A⊙B로 표기. A^[r] 이건 부울 곱을 r번 하는 것.