동치관계, 분할

개념

  • 집합을 쪼개서 집합족으로 만드는 것을 분할이라고 한다.
  • T가 X의 분할이면 아래의 조건을 모두 만족한다.
    • A, B ∈ T (A ≠ B) ⇒ A ∩ B = ∅
    • UT = X (U는 합집합)
    • ∅ ∉ T
  • 동치관계 ε : X → X에 대하여 X/ε는 X의 분할이다.
    • X는 상집합(Quotient Set)
    • 이것을 역으로 생각해 본다면, 분할된 집합은 어떤 상집합이 존재한다고 생각해 볼 수 있다.
  • 분할 T에 대한 관계
    • a(X/T)b ⇔ ∃A ∈ T, a,b ∈ A
  • X/T : X → X는 X 위 동치관계
  • 공집합이 아닌 집합 위에는 동치 관계가 있다.

관계식

  • X/(X/T) = T
  • 동치관계인 것들
    • a = b
    • a ≡ b (mod n)
      • ⇔ ∃k ∈ ℤ, a-b = k ⋅ n

관계, 동치관계

개념

  • 수식은 연산과 관계로 표현 됨.
    • a + b = c 에서 ‘+’는 연산 ‘=’ 은 관계
  • 관계와 함수는 순서쌍의 집합
  • 관계 R, 집합 A, B에 대하여 관계식은 아래와 같이 쓴다.
    • R : A → B
      • A = { a1, a2, a3 }, B = { b1, b2, b3 }
    • R = { {a1, b2), {a3, b1), (a3, b3) }
      • 두 집합 A, B가 있고 어떤 A에서 B로 가는 어떤 관계 조건을 만족하는 순서쌍의 집합을 R이라고 이해하면 된다.
      • 위 상황에서는 그 조건에 만족하는 순서쌍이 (a1, b2), (a3, b1), (a3, b3) 이라는 것.
  • 관계를 R로 표시하고 아래와 같은 집합에서 철수와 영희가 배우자 관계일 때 다음과 같이 한다.
    • 집합 A = { 철수, 영희, 진수 }
    • R배우자 = { (철수, 영희), (영희, 철수) }
      • 위의 관계는 특히 대칭인 관계인데, (철수, 영희), (영희, 철수)가 존재하기 때문
      • 일반적인 관계 R에서 aRbbRa가 성립하면 대칭인 관계라고 한다.
  • 역관계
    • 어떤 관계 R에 대하여 순서쌍을 거꾸로 쓴 집합. 역함수와 같다. R-1
    • R에 대하여 R-1 := { (y, x) | (x, y) ∈ R }
  • 정의역 (Domain)
    • Dom(R) = { a | (a, b) ∈ R }
  • 치역 (Image)
    • Im(R) = { b | (a, b) ∈ R }
  • 다음과 같은 상황에서 정의역과 치역은 다음과 같다.
    • R : A → B
      • A = { a1, a2, a3 }, B = { b1, b2, b3 }
      • R = { (a1, b2), (a3, b1), (a3, b3) }
      • Domain(R) = { a1, a3 }
      • Im(R) = { b1, b2, b3 }
  • 동치관계
    • 아래 조건을 모두 만족하는 관계를 동치관계라 부른다.
    • ε : X → X
      • ∀x ∈ X, x ε x (반사율)
      • x ε  y ⇒ y ε x (대칭율)
      • x ε y ∧ y ε z ⇒ x ε z (추이율)
    • 닮음도 동치관계
  • 동치류, 상집합(Quotient Set)
    • ε : X → X, x ε X 일 때
      • x/ε = { a | a ε x } 인 것을 동치류라고 한다.
      • X/ε = { x/ε | x ∈ X} 인 것을 상집합이라고 한다. (동치류를 모아 놓은 집합)
    • 다음과 같은 조건이 있다고 할 때
      • X = { a, b, c, d, e, f }
        • a, b, f는 11살
        • c는 12살
        • d, e 는 13살
      • ε : X → X, a ε b := a와 b는 동갑이다.
    • 동치류는 다음과 같다.
      • a/ε = { a, b, f }
      • b/ε = { a, b, f }
      • c/ε = { c }
      • d/ε = { d, e }
      • e/ε = { d, e }
      • f/ε = { a, b, f }
    • 상집합은 다음과 같다.
      • X/ε = { { a, b, f }, { c }, { d, e } }

관계식

  • Dom(R-1) = Im(R)
    • 역관계의 정의역은 원래 관계의 치역과 같다.
  • Im(R-1) = Dom(R)
    • 역관계의 치역은 원래 관계의 정의역과 같다.
  • x/ε ≠ ∅, x/ε ⊆ X
    • (반사율) 자기 자신이 동치이기 때문에, 동치인 집합이 공집합일 수는 없다.
  • x ε y ⇔ x/ε ∩ y/ε ≠ ∅
    • x, y가 동치관계일 때 x의 동치류와 y의 동치류의 교집합은 공집합이 아니다.
  • x ε y ⇔ x/ε = y/ε
    • x, y가 동치관계일 때 x의 동치류와 y의 동치류는 같다.

[영화] 보헤미안 랩소디

마지막 Live Ade 공연을 위한 영화. 영화 보고 유튜브에서 실제 공연을 봤는데, 피아노 위의 펩시 컵 위치까지 똑같이 재현해서 놀랐음. 퀸 노래를 좋아한다면 볼만할 듯. 이미 볼 사람은 다 본 것 같지만.

CODE

컴퓨터가 동작하는 것에 대한 것에 다루는 컴퓨터 교양서. Programming, Software 등이 표지에 써 있길래 Low 레벨 프로그래밍 책인가 싶어 사서 읽어 봤는데, 이 책은 Software 보다는 Hardware에 대한 책이었다는 것을 깨닫게 되었음.

책 중간의 Flip-Flop 까지는 이해가 됐지만, –소프트웨어나 하드웨어나 컴퓨터를 구성하는 논리 구조 자체는 동일하기 때문에 논리 회로까지는 쉽게 이해가 가능– 그 이후 더 복잡한 회로 이야기와 하드웨어 이야기는 거의 이해하지 못했다. 그래도 책 자체의 내용이 충실하기도 하고 알아두면 교양은 될 것 같아 다음에 기회가 되면 차근차근 다시 읽어봐야겠다는 생각은 했음.

곱집합

개념

  • 순서쌍
    • (a, b) = { { a }, { a, b } }
  • 카테시안(곱집합)
    • 데카르트의 이름을 따서 지은 이름
    • A x B = { (a, b) | a ∈ A, b ∈ B }
  • 카테시안은 순서쌍 개념이기 때문에, 교환법칙과 결합법칙이 성립하지 않는다.
    • A x B ≠ B x A
    • A x (B x C) ≠ (A x B) x C
  • 직선을 ℝ, 원을 S1이라 할 때
    • ℝ x ℝ : 평면
    • S1 x ℝ: 원주면
    • ℝ x ℝ  x ℝ : 3차원 유클리드 공간
    • S1 x S1: 도넛면, 토러스

카테시안식

  • A x (B ∪ C) = (A x B) ∪ (A x C)
  • A x (B ∩ C) = (A x B) ∩ (A x C)
  • A x (B ∖ C) = (A x B) ∖ (A x C)
  • (A x B) ∩ (C x D) = (A ∩ C) x (B ∩ D)
  • (A x B) ∪ (C x D) ⊆ (A ∪ C) x (B ∪ D)
  • (A x B)c = (Ac x Bc) ∪ (Ac x B) ∪ (A x Bc)
  • A ⊆ B ⇒ A x C ⊆ B x C
  • (A, B ≠ ∅) ⇔ A ⊆ C ∧ B ⊆ D

러셀 역설

개념

집합 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)