ੈ✩‧₊˚Computer Science/이산수학

동치관계(equivalence relation)/동치류(Equivalence Class)

동치관계(Equivalence relation) 반사관계, 대칭관계, 추이관계가 모두 성립하는 관계 R A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive. 동치 동치관계에 있는 관계는 서로 "동치"라고 한다. notation은 a~b이다. Two elements a, and b that are related by an equivalence relation are called equivalent. The notation a ∼ b is often used to denote that a and b are equivalent elements with respect to a par..

관계의 표현(representing relations)

행렬로 표현 유한 집합 사이의 관계는 1-0 행렬로 표현 가능하다. A relation between finite sets can be represented using a zero-one matrix. 예제) 관계 R = {(2,1), (3,1),(3,2)} 일때 행렬로 표현해보기 (a,b) 임 반사관계(reflective relation)일 때의 행렬 : 대각선이 모두 1이다. diagonal is all 1 대칭관계(symmetric relation)일 때의 행렬 : m(i,j)와 m(j,i)가 모두 1 혹은 m(i,j)와 m(j,i)가 모두 0 반대칭관계(antisymmetric relation)일 때의 행렬 : m(i,j)와 m(j,i)가 다르기 때문에 동시에 1인 경우 빼고 다됨 방향 그래프(d..

관계(Relations) / 관계의 특징(Relations and their properties)

이항관계(binary relations) 정의 1 : A와 B라는 집합이 있을 때, A로부터 B까지의 이항 관계는 AXB의 부분집합이다. def 1 : Let A and B be sets. A binary relation from A to B is a subset of AXB 예시) A={0,1,2} B={a,b} A X B = {(0,a), (0,b), (1,a), (2,b)} set A 와 B의 관계를 graphically 하게 표현할 수 있다. 관계는 함수보다 더 general한 표현이다. 정의 2: A라는 집합에 대한 관계는 A X A 의 부분집합이다. def 2 : a binary relation on a set A is a subset of A X A 예시) A={1,2,3,4} R={(a,b..

베이즈 정리(Bayes' theorem)

베이즈 정리를 설명하기 전 배경 지식 조건부 확률(conditional probability) : 주어진 사건이 일어난 상태에서, 다른 사건이 일어날 확률 - 주어진 사건이 일어날 확률을 p(F)라고 할 때, 다른 사건 E가 일어날 확률은 p(E | F) 이다. (E occurs given that F occurs) - 조건부 확률 공식 (p(F) > 0) 으로 부터 베이즈 정리 유도 - 이 정의에 의해서 p(E) > 0 일때, 아래의 식도 도출해 낼 수 있다. - 두 식에 있는 분모를 이항하면, 아래의 식을 도출해 낼 수 있다. - p( E ∩ F ) 라는 값을 가지고 있기 때문에 두 식을 같다고 할 수 있다. ( Equating the two formula for p( E ∩ F ) shows tha..