Tag Archives: 집합

데코수학/ 집합론/ 러셀 역설

개념

데코수학/ 집합론/ 집합 2

개념

  • 대칭차집합
    • A Δ B := (A ∖ B) ∪ (B ∖ A) = (A ∪ B) ∖ (A ∩ B)
  • 서로소
    • A, B = 서로소 ⇔ A ∩ B = ∅
    • A, B가 서로소이면 A ⊆ Bc, B ⊆ Ac
  • 비둘기집 원리
    • a1, a2, … an+1 ∈ U, U = Uk=1n Ak, Ak = 각각 서로소 ⇒ ∃k, |Ak| ≥ 2
    • n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다
  • 집합족
    • 집합을 원소로 가지는 집합
    • F = { { … }, { … }, { … } }
  • 첨수집합족
    • 집합을 첨수로 표기하는 집합 족
    • F = { Aγ | γ ∈ ℝ }
  • 집합족의 합집합
    • ∪F = { x | ∃X ∈ F, x ∈ X }
    • x ∈ ∪F ⇔ ∃A ∈ F, x ∈ A
    • F = { Aγ | γ ∈ Γ }, ∪F = { x | ∃γ ∈ Γ, x ∈ Aγ }
    • ∪F = ∪k=1 Ak  (k=1부터 무한대, 무한개의 원소)
    • ∪F = ∪k=1n A(k=1부터 n까지, 유한개의 원소)
  • 집합족의 교집합 표현
    • ∩F = { x | ∀x ∈ F, x ∈ X }
    • k=1 Ak
    • k=1n Ak
    • k∈ℕ Ak

집합식

  • x ∈ A Δ B ⇔ x ∈ A ⊻ x ∈ B
  • A Δ B = B Δ A
  • A Δ (B Δ C) = (A Δ B) Δ C
  • |A ∪ B| = |A| + |B| – |A ∩ B|
  • |A ∪ B ∪ C| = |A| + |B| + |C| – |A ∩ B| – |B ∩ C| – |C ∩ A| + |A ∩ B ∩ C|
  • ∪∅ = ∅
  • ∩∅ = U, U는 전체집합
  • (∪F)c = ∩A∈F Ac
  • (∩F)c = ∪A∈F Ac
  • S ∩ (∪A∈F A) = ∪A∈F (S ∩ A)
  • S ∪ (∩A∈F A) = ∩A∈F (S ∪ A)

데코수학/ 집합론/ 집합 1

개념

  • 순진한 정의
    • 집합: 구별 가능한 것들의 모임
    • 원소: 집합에 들어 있는 대상들
    • 공집합: a ∉ ∅
  • 원소 나열법
    • A = { a, b, c }
  • 조건 제시법
    • a ∈ { p(x) | q(x) }
  • 상등
    • A = B ⇔ ∀z, z ∈ A ⇔ z ∈ B
    • { a, a, b } = { a, b }
  • 부분집합
    • A ⊆ B ⇔ ∀z, z ∈ A ⇒ z ∈ B
  • 집합의 크기
    • | A | : A의 원소의 개수 (A는 유한집합)
  • 멱집합(power set)
    • P(A) : A의 부분집합들을 모은 집합
    • { x | x ∈ A }
    • | A | = 2 ⇒ | P(A) | = 2n
  • 합집합
    • A ∪ B = { x | x ∈ A ∨ x ∈ B }
  • 교집합
    • A ∩ B = { x | x ∈ A ∧ x ∈ B }
  • 차집합
    • A ∖ B = { x | x ∈ A ∧ x ∉ B }
  • 여집합
    • AC = U ∖ A
  • 공집합은 모든 집합의 부분집합
  • 공집합은 unique 하다

집합식

  • A ⊆ B ∧ B ⊆ A ⇔ A = B
  • A ⊆ B ∧ B ⊆ C ⇒ A ⊆ C
  • A ∪ A = A
  • A ∩ A = A
  • A ∪ B = B ∪ A
  • A ∩ B = B ∩ A
  • A ∪ (B ∪ C) = (A ∪ B) ∪ C
  • A ∩ (B ∩ C) = (A ∩ B) ∩ C
  • A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
  • (AC)C = A
  • C = U, UC = ∅
  • (A ∪ B)C = AC ∩ BC
  • (A ∩ B)C = AC ∪ BC
  • A ⊆ B ⇔ A ∪ B = B
  • A ⊆ B ⇔ A ∩ B = A
  • A ⊆ B ⇔ A ∖ B = ∅
  • A ⊆ B ⇔ BC ⊆ AC
  • A ∪ U = U
  • A ∩ U = A
  • A ∪ ∅ = A
  • A ∩ ∅ = ∅

데코수학/ 집합론/ 수학적 귀납법

개념

  • 논리 중에서 자연수에 의존하는 논리가 수학적 귀납법
    • P(1)이 만족하고, P(k)가 참이고 P(k+1)이 만족하면, 모든 자연수에 대하여 P(n) 성립하는 논리
      • 초기항과 다음 항을 정의하는 식이 맞다면 무한루프가 돌아서 모든 자연수에 대하여 참이 성립한다.
    • P(1), P(k) ⇒ P(k+1), k ∈ ℕ ⇔ ∀n ∈ ℕ, P(n)
  • 정렬 원리
    • A ⊆ ℕ, (A ≠ ∅) ⇒ ∃minA

수학적 귀납법을 이용한 수식 정의

  • n! = n(n-1)!, 0! = 1
  • xn = x ⋅ xn-1
  • f(n)(x) = d/dx f(n-1)(x), f(0)(x) = f(x)
  • nCk = n! / k!(n-k)!
  • nCk = n-1Ck-1 + n-1Ck, 1C0 = 1, 1C1 =1
  • Σk=0n K = n(n+1) / 2
  • Σk=0n K2 = n(n+1)(2n+1) / 6
  • Σk=0n K3 = n2(n+1)2 / 4
    • 수열합 자체도 귀납법으로 공식을 이끌어 낼 수 있는데, k의 합을 알면 k2의 합을 알 수 있고, k와 k2의 합을 알면 k3의 합을 알 수 있다.


데코수학/ 집합론/ 술어논리

개념

  • 전칭
    • ∀p(x), q(x)
    • 모든 p(x)에 대하여 q(x)를 만족하면 참
    • Ex) 모든 자연수는 0이상이다 : ∀ x는 자연수, x ≥ 0
  • 특칭
    • ∃p(x), q(x)
    • 어떤 p(x)에 대하여 q(x)를 만족하면 참
    • ∃ 다음에 !를 붙이면 (∃!) 참인 것이 단 1개만 존재한다는 의미
  • 쌍대원리
    • ∀ ↔ ∃
  • 괴델의 완전성 정리
    • 술어논리의 법칙들은 증명이 가능하다
  • 논리는 수학에 언어를 제공한다.
    • ∃k0 ∈ A, ∀a ∈ A, k0 ≤ a : k0는 a의 최소값
    • ∃p ∈ ℕ, ∀a, b ∈ ℕ, p = ab ⇒ a=1 ∨ b=1 : p는 1이거나 소수이다.
    • ∀a, b ∈ A, a = b : a는 한 원소로 된 집합이다. (또는 공집합)
    • ∀ε > 0, ∃N ∈ ℕ, n ≥ N ⇒ | an – a | < ε : limn→∞ an = a

논리식

  • ¬∀p(x), q(x) ≡ ∃p(x), ¬q(x)
    • ¬∃p(x), q(x) ≡ ∀p(x), ¬q(x)
  • ∀p(x), q(x) ≡ ∀x, p(x) → q(x)
    • ∃p(x), q(x) ≡ ∃x, p(x) ∧ q(x)
  • ∀p(x), q(x) ∧ ∀p(x), r(x) ≡ ∀p(x), q(x) ∧ r(x)
  • ∀x, p(x) ∧ ∀x, q(x) ≡ ∀x, p(x) ∧ q(x)
    • ∃x, p(x) ∨ ∃x, q(x) ≡ ∃x, p(x) ∨ q(x)
  • ∀x, ∀y, p(x, y) ≡ ∀y, ∀x, p(x, y)
    • ∃x, ∃y, p(x, y) ≡ ∃y, ∃x, p(x, y)


데코수학/ 집합론/ 명제논리 2

개념

  • 카르노맵이란 논리식을 간단하게 바꾸는 방법. 아래와 같이 생긴 표를 사용한다.
    • 표에서는 인접한 것끼리 1번만 변하는 형태로 열을 쓴다. 그래야 묶을 수 있음.
p \ qr 00 01 11 10
0        
1        
  • 쌍대원리
    • 모든 명제논리 법칙들에 대하여 ∨ ↔ ∧ , t ↔ c, ⇒ ↔ ⇐ 바꿔도 법칙이 성립한다.
  • XOR (⊻)
    • p와 q가 다를 때만 참

논리식

  • p ⇒ p ∨ q
  • p ∧ q ⇒ p
  • (p → q) ∧ (q → r) ⇒ p → r
  • (p ∨ q) ∧ ¬q ⇒ p
  • (p → q) ∧ p ⇒ q
  • (p → q) ∧ ¬q ⇒ ¬p
  • p ∨ (p ∧ q) ≡ p
  • p ∧ (p ∨ q) ≡ p
  • (p → q) ∧ (r → s) ⇒ (p ∨ r → q ∨ s)
  • (p → q) ∧ (r → s) ⇒ (p ∧ r → q ∧ s)
  • ¬(p ∨ q ∨ r) ≡ ¬p ∧ ¬q ∧ ¬r
    • 항의 개수가 무한히 많아도 성립한다.
    • ¬(p1 ∨ p2 … ∨ pn) ≡ ¬p1 ∧ ¬p2 … ∧ ¬pn
  • p ⊻ q ≡ (¬p ∧ q) ∨ (p ∧ ¬q)
  • p ⊻ q ≡ q ⊻ p
  • p ⊻ (q ⊻ r) ≡ (p ⊻ q) ⊻ r
  • p ⇒ q 일 때
    • r ∨ p ⇒ r ∨ q
    • r ∧ p ⇒ r ∧ q





데코수학/ 집합론/ 명제논리 1

개념

  • 4대 논리학자 – 아리스토텔레스, 라이프니츠, 프레게, 괴델
  • 시대가 지나다보니 논리가 기호화됨. 그래서 수학처럼 계산할 수 있게 되어서 기호논리학이 수학의 일부가 됨.
  • 명제 (p, q, r)
    • 참이거나 거짓, 둘 중 하나의 진리값을 가지는 식이나 문장
  • 명제함수
    • 변수 x에 값을 대입하면 명제가 되는 식이나 문장
  • 동치 (p ≡ q)
    • 명제 p와 q의 진리값이 같은 경우
  • 명제의 연산 – 부정(not), 논리합(or), 논리곱(and), 조건문(if p, q)
    • 부정은 원래 명제의 부정
    • 논리합은 p, q 중 하나 이상이 참인 경우 참, 그 외엔 거짓
    • 논리곱은 p, q 가 모두 참이고, 그 외엔 거짓
    • 조건문은 p가 거짓이면 무조건 참, p와 q가 참이면 참
p q ¬p p ∨ q p ∧ q p → q p ↔ q
0 0 1 0 0 1 1
0 1 1 1 0 1 0
1 0 0 1 0 0 0
1 1 0 1 1 1 1
  • 항진명제(t)
    • 모든 경우에 참(1)인 명제
  • 모순명제(c)
    • 모든 경우에 거짓(0)인 명제
  • 함의
    • 같다는 것보다는 좀 더 약한 개념 (ex 부등호)
    • p ⇒ q : p → q ≡ t

논리식

  • p → q ≡ ¬p ∨ q
  • p ↔ q ≡ (p → q) ∧ (q → p)
  • p ⇔ q : p ≡ q
  • p ∨ t ≡ t
  • p ∧ t ≡ p
  • p ∨ c ≡ p
  • p ∧ c ≡ c
  • p ∨ ¬p ≡ t
  • p ∧ ¬p ≡ c
  • p ⇒ t
  • c ⇒ p
  • p ∨ p ≡ p
  • p ∧ p ≡ p
  • ¬(¬p) ≡ p
  • p ∨ q ≡ q ∨ p
  • p ∧ q ≡ q ∧ p
  • ¬(p ∨ q) ≡ ¬p ∧ ¬q
  • ¬(p ∧ q) ≡ ¬p ∨ ¬q
  • p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r
  • p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r
  • p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
  • p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
  • p → q ≡ ¬q → ¬p (대우)
  • p → q ≡ p ∧ ¬q → c (귀류법)