오래 못 할 짓 하지 않기

경우의 수는 솔직히 쉬워서 뭘 해야할지 모르겠음.. ex) 3개의 영어와, 3개의 숫자로 만들 수 있는 문자열의 경우의 수는? 영어 알파벳 26개, 숫자 0~9 : 10개 26*26*26*10*10*10 = 17,576,000 ● 그냥 조건없는 함수 : set n개 -> m개 로 던질 때 n^m : 첫번째 애가 던질 수 있는 경우의 수 =m개 두 번째 애가 "... :m개 ...n번째 애가 :m개 ● 일대일 함수 : nPm 첫번째 애가 던질 수 있는 경우의 수 =m개 두 번째 애가 "... :m-1개 ...n번째 애가 :m-n+1개 혹은 겹치는 게 있으면 아래와 같다. 겹치는 게 있는 경우엔 아래와 같이 수행을 해야한다. 예시를 보자. 첫 비트 시작이 1이고, 끝 비트 2개가 00으로 끝나는 8비트 숫자..

재귀함수에서 해야하는 것 - Basis Step : Function에서 zero ( =초기단계 ) 의 상태(값)를 명시하기 - Recursive Step : 각 값을 찾을 수 있는 규칙 제시하기 이렇게 규칙을 제시해줘야 함 어떠한 경우에도 n=0이거나 범위에서 가장 작은 값을 초기 단계로 생각하면 됨 - Set에서도 재귀적으로 된다 1) 2) 저렇게 확장시켜나갈 수도 있다고 한다. 시그마 옆에 별 붙어있는 건, 그 안에 있는 원소 개수 상관없이 어떻게 이어붙어셔 만드는 건 다 자기거라는 거 String의 길이 l(wx) = 괄호를 봤을 때, 어떻게든 갖고있는 순서에 조합만 더 넣는 건 되기 때문에 ()는 일단 가능. 그리고 그 순서 그대로 그 안에 들어가는 것들은 같은 집합에 있는 원소면 가능 ex) (..

귀납법 수학적 귀납법의 논리 n = 1 일때 p(1)이 참임을 보임 (Basic Step) n = k 일때 p(k)이 참임을 가정 (Inductive Step - 1) Assume) n = k+1 일 때 p(k+1)이 참임을 보임 (Inductive Step - 2) get result) ex) 무한의 사다리타기 1. 우리가 0번 째 반판에서 > 첫 번째 발판에 도달 가능. 2. 그럼 우리가 N번째 발판에 도달했다면 > N+1번째 발판에도 도달 가능하다! P(1) is true , then P(a) → P(a+1) Validity of Mathematical Induction : 그냥 귀납법이 성립하면 반례는 나오지 않을 것이라는 , 중간에 " 이거 아닌 거 있는데요? " 이거 안 된다는 내용 예제 1)..

Cardinality = Size of set Set A와 B가 일대일 대응( bijection )이면, | A | = | B | 라고 한다. Set A와 B가 일대일 함수 ( injection )이면, | A | ≤ | B |. 라고 한다 Countable Set의 원소의 개수가 유한개 이거나 양의 정수 같이 한 sequence에 나열할 수 있으면(손으로 꼽을 수 있으면) Countable이라고 한다. 이러한 양의 정수들의 Cardinalty 는 무한대이긴 하지만 셀 수 있는 무한대 = countably infinite라고 하며 기호로는 ℵ 이렇게 표시한다. 집합 S가 countably infinite 이면 |S| = ℵ0 이렇게 표현한다~ Uncountable(가산집합) != 무한집합 무한이 아니더라..

함수 : A와 B는 공집합이 아니면 A → B 이고 f: A → B라는 뜻은 A의 원소가 B 원소에 딱 하나에 할당된다는 것을 뜻한다. 따라서 원소 b가 f 함수에 의해 a원소에 의해 할당된 유일한 원소일 때 ' f(a)=b ' 이렇게 표현한다. 1) 두 원소는 하나의 쌍으로만 있어야 함수라고 할 수 있다 받는 건 겹쳐도 되는데 주는 놈이 2개를 보내면 안 됨 용어들 f: A → B 라고 할 때 1) f 는 A에서 B로 'maps'하거나 'mapping' 한다고 한다. 2) A는 f의 'Domain' , B는 f의 'Codomain' 3) f(a) = b 이면, - b는 (f함수 아래 있는) a의 'image'이고 - a는 b의 'preimage'이다. 4) 함수 f의 범위 = 'images in A'이..

정리는 내가 모르거나 헷갈릴 만한 것들만 함. 그 외 내용은 고등학교에서 배운 것과 동일 집합의 특징 1. 순서가 중요하지 X ex) S= {A,B,C,D} = {B,C,A,D} 2. 중복 허용 X ex) S= {A,B,C,D} ={A,A,A,B,C,C,D,D,D} 3. 규칙이 명확하면 모두 나열할 필요없이 그냥 ...으로 표현 가능 ex) S = {A,B,C,D,...,Z} 알파벳 위에 +가 붙으면 , 그 조건에서 양수인 것 으로 해석하면 된다. 집합에 관해서도 명제를 사용할 수 있다. 공집합도 집합이다 러셀의 역설 (그냥 어떤 사람이 이상한 가설 내뱉길래 반박하려고 만든 거임) X = { X ∣ X ∈ /X } 이때 X∉X 라면, 조건을 만족하므로 X∈X가 된다. 반대로 X∈X 라면, 조건을 만족하지..

전제를 2가지 설정해보자 1. '모든 남자는 호전적이다.' 2. '소크라테스는 남자이다' 이 두 가지 전제가 참이라고 했을 때 " 소크라테스는 호전적이다 " 라고 할 수 있을까? 여러 전제가 참일 때 우리는 새로운 결과를 어떻게 도출해낼 수 있을까 ? 가 이번 챕터의 시작이다. 위 예시를 식으로 바꾸면 아래와 같다. ㅡㅡㅡㅡ막대선을 기준으로 위가 전제, 아래가 결론으로 나뉜다. 논증 = 명제의 연속 그 결과로 나오는 것 = 결론 Tautology = 항상 참이 되는 명제 (라는 뜻) (예시1) 결론을 제외한 나머지들을 뜯어서 하나하나 보아야 한다. 재료로는 1) P , 2) P → Q가 있다. 이 두 가지가 참이면 Q도 참이 된다는 것을 정리해보면 이런 형태가 나온다. 참고로 → 이거는 P → Q일 땐,..

Predicate : 단정하다. 요소 1) 변수 : x, y, z 2) predicates = 단정할 문장(내 식대로 해석했음) : P(x) , M(y) 3) 수량/범위 : 모든 or 임의의 P(x1,x2,...,xn) : 'x1부터 n은 (P라는 문장)하다~ ' 라는 뜻임 P(q) : q>0이다. ... P(-3)랑 P(0) 는 q가 0보다 작으므로 거짓 P(3)은 참 그냥 predicate는 판단문이라고 생각하면 된다. 그 안에 변수가 들어오면 , 그 변수가 P에 들어오면 참일까? 라고 판단하는 거 Quantifier 1. 모든 값에 대한 / For all / U / (A뒤집은 모양) '>> 하나라도 True가 안 되는 게 있으면 False' '== 반례가 하나라도 있으면 끝 ' 2. 임의의 값에 대..

명제의 개수에 따라서 그래프의 세로가 2승이 됨 ex) 명제 3개 --> 봐야 하는 게 2^3개 계산 우선순위 적용 위 문장을 명제로 만들어보자. 더보기 If p or q then not r = ( p Ú q) ¬ r 이런 게 주로 1.2과에 있음 1.3 방정식 드모르간 법칙 Tautologies, Contradictions, and Contingencies More Logical Equivalences 보고 이해하기 (1번 5번은 드모르간이라고 생각하면 쉽다함) Imply 랑 or로 바꾸는 거 연습해보기. 여러 규칙들도 적용 가능하다. + ) 우리가 생각하는 = 은 2줄이 아니라 3줄인 애가 그 역할을 함. 이거 아마 시험에 나올 듯 P → Q == ¬P ∨ Q 식을 간략화 할 때 P → Q 는 어떻게..

Proposition ( 명제 ) : 참과 거짓을 가를 수 있는 선언문. ( * 참이어야 할 필요없음 ) Ex) 1+1은 0이다 (거짓) / Navigator (부정) = ¬ : 특 ) binary operator 이다. Conjunction (결합) = ∧ : and 와 같은 역할을 한다. Disjunction ( 분해 ) = ∨ : or 와 같은 역할을 한다. Exclusive or = ⊕ : xor 다른 경우에 T , 같으면 F Implication ( 영향 ) = → : 조건이라고 생각하면 간단할 것 같다. ex) P → Q : P이면, Q이다 / P일 때 , Q이다 쉽게 외우는 법 : 조건이 참이면 뒤에 결과를 따라감. 조건이 거짓이면 결과는 참 ex) 만나면 밥 사줌 = 안 만나면 절대 사줄 ..