Predicate Logic & Set

A formal proof of a conclusion C 알고 있는 premises들로 결론을 추론해내는 것

 

P1 -> P2 -> ... -> C

 

Inference Rules for Quantifiers

 

Universal instantiation => Universal Quantifier를 임의의 원소 c로 바꾸는 것

 

Universal Generalization => 임의의 원소 c를 Universal Quantifier로 바꾸는 것

 

Existential instantiation => Existential Quantifier를 특정한 원소 c로 바꾸는 것

 

Existential Generalization => 특정한 원소 c를 Existential Quantifier로 바꾸는 것

 

해당 기법들을 통해서 quantifier가 있는 premises의 결론을 구할 수 있음,

 

Proof Methods for Implications

 

P -> Q

 

1. Direct proof : Assume P is true, and prove Q

2. Indirect proof: Assume ~Q is true, and prove ~P

3, Vacuous proof: Prove ~P by itself.

4. Trivial proof : Prove Q by itself

5, Proof by contradiction : Show ~(P -> Q) -> F

6. Proof by cases : Show P -> (A and B), and A -> Q and B-> Q

 

5의 대표적인 예시 sqrt(2)가 무리수인가? 증명.

 

Exisitence Proof

 

ExP(x)를 증명하는 문제

 

특정한 원소인 a일 때, P(a)가 참인가를 증명하는건 constructive proof

 

ex) n = j^3 + k^3 and I^3 + m^3

Prove that there exists a positive integer n 

 

 

그게 아닌 경우 nonconstructive.

 

ex) There are infinitely many prime numbers

 

Uniqueness Proof

: 특정한 특징을 가진 원소가 고유한 것을 증명하는 문제

 

두가지를 증명해야 한다.

 

1. (Existence) Element x with a desired property exists

2. (Uniqueness) If y != x, then y does not have the desired property.

또는 y가 해당 특징을 가지고 있을 때 x와 동일하다는 것을 증명하면 됨.

 

ex) Every integer has a unique additive inverse

 

 

Set

Definition of Set : 집합은 순서가 없는, 구별되는 원소들.

 

{a, b} {a, a, b} {b, a} {b, b, b, a} 모두 동일한 집합

 

Naive set theory : 무엇이든 집합의 원소가 될 수 있음 => Russell's paradox가 생김

 

Define S to be S = {x|x ∉ x}. Is S a member of itself?

 

만약 S가 S의 원소라면, x는 x에 포함되지 않는 원소라는 정의를 지키지 못함.

만약 S가 S의 원소가 아니라면 , x는 x에 포함되지 않는 원소이기 때문에 S의 원소가 됨.

 

이러한 역설이 생기기 때문에 Set의 원소 중 자기 자신은 해당 set의 원소가 되지 못한다!

 

builder notation => predicate symbol P에 대해, {x|P(x)} predicate P가 참이 되는 x의 집합

 

집합의 개수는 무한할 수 있다.

하지만 무한 집합의 크기는 다를 수 있음!(countable한 무한 집합, uncountable한 무한 집합이 있음)

ex) |R| > |Z| = |N|

 

Empty set : 공집합, ∅

x ∈ S : ("x is in S")

x ∉ S : ("x is not in S")

S ⊆ T : ("S is a subset if T") ("T is a superset of S")

A = B : A ⊆ B and B ⊆ A

S ⊂ T : S ⊆ T and S != T

 

Sets themselves may be elements of a set (But set itself can't be a member of them)

 

Cardinality : unique한 원소들의 개수

|S| : S 집합의 cardinality

 

Cardinality가 자연수와 0의 합집합에 존재하지 않는다면 무한집합!

 

power set of S는 S의 모든 부분 집합들의 집합을 뜻함.

 

|power set of S| = 2^(|S|)

 

|power set of N| = 2^(|N|) > |N| 이기 때문에 무한 집합들도 사이즈가 다르다는 것을 알 수 있다.

 

 

an ordered n-tuple : 순서가 있는, n개의 원소를 가진 모임.

 

(1, 2) != (2, 1) != (2, 1, 1)

{1, 2} = {2, 1} = {2, 1, 1}

 

Cartesian product AxB = {(a, b) | a ∈ A and b ∈ B}

ex) A = {1, 2}

B = {a, b}

A x B = {(1, a), (2 a), (1, b), (2, b)}

 

Union

 

A ∪ B = {x|x ∈ A OR x ∈ B}

A ∪ B는 A와 B 모두의 superset이다.

 

Intersection

 

A ∩ B = {x|x ∈ A AND x ∈ B}

A ∩ B는 A와 B 모두의 subset이다.

 

Disjointedness

 

A ∩ B = emptyset

 

Cardinality of Union

 

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

 

Set Difference

 

A - B = {x|x ∈ A and x ∉ B}

 

Universal set = Universe of discourse(U)

 

Complement of set A' = U - A

 

DeMorgan's Equivalence

 

(A ∪ B)' = A' ∩ B'

 

Proof of A = B

 

A = B : A ⊆ B and B ⊆ A

 

오른쪽 두 항을 모두 증명해야 함!