머신러닝을 위한 이산수학

집합의 개념

집합

어떤 조건에 의해 대상을 분명하게 정할 수 있을 때, 그 대상들의 모임

 

원소

집합을 이루는 개별 대상

 

집합의 표현 2가지

원소 나열법

ex) {1,2,3,4,5}: 순서 상관 없음

조건 제시법

ex) {x|x는 5이하의 자연수}

 

집합을 그림으로 표현

벤다이어그램

ex)

A={2,3,5,7}

 

원소의 개수

n(A)로 표현하며

다음 A집합의 부분집합의 개수는 2**n이다. 

n은 2,3,5,7이므로 총 4개이므로 부분집합의 개수는 2**4이다.

 

공집합

원소가 없는 집합

ex)∅, {}

 

부분집합

집합 A의 모든 원소가 집합 B에 속할 때, A가 집합 B의 부분집합

A⊂B

공집합과 자기 자신에 대해서 부분집합임

A⊂A, ∅⊂A 공집합은 {}이므로 무조건 부분집합일 수밖에 없음

 

※진부분집합 부분집합에서 자기를 제외한 나머지를 말할 때 씀

 

 

명제

진릿값: 참,거짓을 나타내는 값

ex) 0,1. T,F 등등

명제proposition: 진릿값을 부여할 수 있는 문장이나 식

ex) p,q,r  모든 사람은 돈이 많다 :거짓 명제

 

논리연산자

논리연산자

명제에 적용되는 연산자

부정 연산자 

ex) ~, ㄱ 으로 표현 (~p)

명제 p에 대해 'p가 아니다'를 의미하는 연산자

진릿값의 반대

 

F인 진리집합은 공집합을 말함

 

논리곱: p^q 명제 p와 q에 대해'p그리고q'를 의미

논리합: pvq 명제p와 q에 대해 'p또는q'를 의미

 

배타적논리합: 𝑝⨁𝑞 명제p와q에 대해 둘 중 하나만 참일 때 참이고 나머지는 거짓이 되는 연산

ex)

p: 철수는 한 해 저축으로 차를 산다.

q: 철수는 한해 저축으로 유럽 여행을 간다.

𝑝⨁𝑞: 철수는 한 해 저축으로 차를 사거나 유럽 여행을 간다. 하지만 둘다는 불가능하다.

조건과 진리집합

조건

x에 대한 참,거짓을 판별할 수 있는 명제를 말함

ex) x<10:참 거짓 판단 불가능 

만약, 전체집합 U가 N(자연수)이면 x={1,2,3,4,5,6,7,8,9}인 경우 참이라고 말함

 

진리집합

조건을 참으로 만드는 원소의 집합

x={1,2,3,4,5,6,7,8,9}를 말함

명제 p가 거짓이라면 진리집합이 공집합 ({})이라는 말이다.

 

조건 명제의 진리표

p -> q의 진리판단(참,거짓 판단)은 P⊂Q, P가 Q의 부분집합인가에 따라 판단한다(P가Q의 부분집합이여야지만 참)

 

※p,P,q,Q 차이 유의하며 p는 P의 원소, 부분집합이라고 생각

참일 경우 작대기 두개 화살표를 쓴다

 

 

필요조건 충분조건

p:|x|≤4, q:-1≤x≤3일 때 p는 q이기 위한 필요조건 q는 충분조건이다

 

※ 필요조건 충분조건이 머신러닝에서 어떻게 쓰이는가

머신러닝은 f'(x)=0인 값을 구하면 minum과 maximum을 구할 수 있다.

이때 x는 필요조건이며

f(x)에 x를 대입하여 0이 실제 0이 나오는 x들만 충분조건이라고 볼수 있다.

 

ex)

𝑓(𝑥)=−𝑥5 +16𝑥4 −100𝑥3 +304𝑥2 −448𝑥+256

𝑓′(𝑥) = −5𝑥4 + 64𝑥3 − 300𝑥2 + 608𝑥 − 448

𝑓′(𝑥) = 0 일 때 x는 𝑥 = 2, 14/5 , 4

 

이 x들을 대입해보면 아래와 같은 값이 나옴

𝑓(𝑥) = 0, 3456/3125, 0

 

이를 보면 f'(x)=0을 만족시키는 x들을 필요조건 f(x)에 0을 만족시키는 x들은 충분조건이라고 볼 수 있다.

 

Boolean Algebra

부울 대수(boolean algebra): 집합{0,1}과 NOT,AND,OR 연산으로 구성되는 식과 그에 대한 연산

 

각각 연산 예시 및 기호

NOT 연산(complement): ㄱ, ~

ex) 0=1,1=0

OR 연산,불린 합: v

ex) 1+1=1,1+0=1, 0+1=1, 0+0=0

AND 연산, 불린 곱: ^

ex) 1*1=1, 1*0=0, 0*1=0, 0*0=0

 

 

논리 게이트(logic gates): 부울 대수를 이용하여 회로를 설계할 때 회로의 기본 단위

XOR을 선을 그어서 그래프에 나타낼 수 없음

따라서 비선형 결정 경계를 그어야함 그렇게 하기 위해서 NAND OR을 새로 이용하여 계산하게 됨

 

AND

OR

 

NAND(NOT AND)

 

NOR(NOT OR)

 

XOR(풀기 위해서 NAND와 OR을 추가 사용 마지막에는 AND로 result를 냄)

이를 통해서 인공지능이 비선형결정경계도 예측할 수 있게 됨