4. 이산수학 4

1. 대칭차집합

A∪B에서 A∩B를 뺀것. 표시는 A(+)B라고 표시한다.

ex) A= {1,2,3,4,5} 일때 B={1,3,5,7,9}일때 A(+)B의 값은?

A∪B = {1,2,3,4,5,7,9}

A∩B = {1,3,5}

A(+)B = {2,4,7,9}

2. 집합연산의 카디날리티

카디날리티란?

그 집합의 원소의 개수를 나타낸다. 표시할때는 n(A) or |A| 라고 나타낸다.

1. |A∪B| = |A| + |B| - |A∩B|

2. |A∪B∪C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

[그림]

이해가 잘 되지않아 그림으로 만들어서 순차적으로 진행해본다

|A+B+C|를 했을때 겹친 횟수를 적었다.

3. 집합연산의 대수법칙

(논리적 동치관계의 기본법칙과 비슷하다.)

교환법칙:    A∪B = B∪A, B∩A = A∩B

결합법칙:    (A∪B)∪C = A∪(B∪C), (A∩B)∩C = A∩(B∩C)

분배법칙:    A∪(B∩C) = (A∪B)∩(A∪C), A∩(B∪C) = (A∩B)∪(A∩C)

드모르간 법칙: (A∪B)^c = A^c∩B^c, (A∩B)^c = A^c∪B^c

항등법칙: A∪∮=A ,A∩∮=∮,A∪U=U, A∩U=A

4. 분할(Partition)

집합 S의 분할이란 공집합이 아닌 S의 부분집합의 모임 (모임이기때문에 표시할때 집합으로 감싸주어야한다.)

4 - 1. 분할의 조건

1)부분집합에 공집합이 포함되면 안됨

2) 교집합(혹은 중복되는 것)이 존재하면 안됨

3) 합쳤을때 분할하기 전 집합이 나와야함

ex) 집합 A={1,2,3}모든 분할 구하기

{{1,2,3}}

{{1,2},3}

{1,{2,3}}

{{1,3},2}}

{{1},{2},{3}}

5. 곱집합(Cartesian Product)

A,B에 대하여 A원소 B원서의 모든 순서쌍을 갖춘 것을 곱집합 AxB이라 한다.

ex) A={1,2} B={3,4}

AxB={(1,3),(1,4),(2,3),(2,4)}

BxA={(3,1),(3,2),(4,1),(4,2)}

AxB =/ BxA 순서도 같아야하기때문에 AxB와 BxA는 다르다. (a,b)=/(b,a)

6. 관계의 성질

6 - 1. 관계

AxB의 부분집합을 A에서 B로의 관계라고 한다.

a는 b와 R인 관계에 있다. aRb or (a,b)∈R

관계에 있지 않으면 R, ∈의 가운데에 /를 그어준다

6 - 2. 반사관계

임의의 a라는 원소가 A∋a에 대하여 (a,a)∈R이 성립하는 경우

ex) E = {1,2,3}                -> 한 원소에 대하여 반드시 반사가 존재해야한다.

R1 = {(1,1),(2,2),(3,3)}

R2 = E*E

R3 = {(1,1),(1,2),(2,2),(3,3),(3,2)}        ->반사를 모두 포함하고 다른 것들이 존재하더라도 반사관계이다.

6 - 3.대칭관계

(a,b)∈R일때, (b,a)∈R이 성립하는 경우 (대칭관계가 되려면 모두 대칭이거나 하나만 대칭이여도 된다.)

ex) E = {1,2,3}

R1 = {(1,1)}            -> 스스로 대칭이므로 대칭관계가 성립한다.

 R2 = {(1,1),(2,1),(1,2)}    -> 다른 원소도 대칭이 있으므로 대칭관계가 성립한다.

R3 = E*E

6 - 4. 반대칭관계

(a,b)∈R이고 (b,a)∈R이면 a=b가 성립하는 경우,즉 서로가 같을때 이외에 대칭이 존재하면 안되는 경우

ex) E = {1,2,3}

R1={(1,1),(2,1),(3,2)}        -> 스스로가 같은것 이외에 대칭인것이 없으므로 반대칭관계가 성립한다.

R2={(1,1),(2,2),(3,3)}

R3={(1,2)}