[이산수학] - Chapter1. Sets and Logic (1)

목차

1.1 Sets - 집합

1.2 Propositions - 명제

1.3 Conditional Propositions and Logical Equivalence - 조건 명제와 논리적 동치

1.4 Arguments and Rules of Inference 

1.5 Quantifiers - 한정사

1.6 Nested Quantifiers

 

1.1 Sets

• 집합이란? 간단히 말해 objects의 collection이다.
• 이 object는 elements or members가 될 수 있다.
• 너무 이해하기 어렵다면 집합이란 A = {1,2,3,4} 이다. (four elements)
• Z = integers Set
• Q = rational numbers Set
• R = real numbers Set
• X가 유한한 집합이라면 |X| 는 X의 element 개수라고 칭한다. (cardinality)
• X와 Y가 집합일때 X의 모든 원소가 Y의 모든원소에 포함될때 X ⊆ Y 즉, X는 Y의 subset이라고 한다.
• 여기서 만약 x가 Y와 X의 subset이지만 Y랑은 같지 않을 때 X ⊂ Y 즉, X는 Y의 proper subset이라고 한다.
• P(X) = power set (모든 subset의 Set)
• Ex) A = {a,b,c} 
• P(A) = { 공집합, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} } => 총 2^3 = 8개

---

• Disjoint - 서로소에 대해서 알아보자
• 집합 X, Y가 disjoint == X∩Y = 공집합
• Pairwise disjoint - 쉽게 말해 서로소 집합의 집합 (disjoint의 집합)
• Ex) X = {1,4,5}, Y = {2,6}
• S = { {1,4,5}, {2,6}, {3}, {7,8} }  - pairwise disjoint
• 잠깐!!! 여기서 collection(family)란, 집합들의 집합이다.

---

• Union과 Intersection
• 임의의 family S
• ∪S = { x | x ∈ X for some X ∈ S }
• // x는 X의 element이고 X는 S의 element이다.
• 원소 x는 S에 있는 집합 X중 at least one 속해야 한다.
• //단, 중복 불가
• ∩S = { x | x ∈ X for all X ∈ S }
• // x는 X의 element이고 X는 S의 element이다.
• 원소 x는 S에 있는 모든 집합에 속해야 한다.

---

• Partition
• 1) pairwise disjoint
• 2) nonoverlap
• 3) nonempty // 의문점 : nonempty가 공집합인가??? 공집합이 있는 pairwise disjoint는 partition이 될 수 없나??
• 4) union -> X
• {X}도 X의 partition이다!
• Ex) X = { 1, 2, 3, 4 }, S1 = 공집합, S2 = { 1, 2, 3 }, S3 = { 4 } 
• S = { S1, S2, S3 }
• S1 ∩ S2 ∩ S3 = nothing (pairwise disjoint이기 때문에)
• Ex) X = { 1, 2, 3, 4, 5, 6, 7, 8 }
• S = { { 1, 4, 5 }, { 2, 6 }, { 3 }, { 7, 8 } } ( S is pairwise disjoint, S is a partition of X ) 

---

• X x Y = { (x,y) | x ∈ X and y ∈ Y }
• | X x Y | = |X|*|Y|

---

• Symmetric difference
• A △ B = ( A ∪ B ) - ( A ∩ B ) 

---

• 정리하자면
• pairwise disjoint는 family S의 원소 즉, 집합들끼리 서로소이다!
• family의 union과 intersection을 기억하자!
• 하나의 집합을 partition을 통해 family를 만들 수 있다! 
• 단, 위에 4가지 조건에 항상 성립해야한다.

---

Quiz.

C = { X1, X2, ..., Xn } 일 때

1) C가 pairwise disjoint라면 모든 X의 intersection은 공집합이다? T / F

2) 거꾸로 모든 X의 intersection이 공집합이라면 C는 pairwise disjoint인가? T / F

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

정답!!!

1) T - pairwise disjoint의 원소들의 교집합은 공집합이다.

2) F - 반례) { { 1, 2 }, { 2, 3 }, { 3, 1 } }