본문 바로가기

이산수학

 (8)
Lattice 1. Lattices as Partially Ordered Sets Definition 1 A partially ordered set (or poset) $\langle L, \preceq \rangle$이 만약 모든 L pair에 대해 lub와 glb를 가지면 lattice라고 부른다. lub는 보통 a+b, glb는 보통 a*b로 표시된다. ex1) L = {a, b, a+b, a*b} ex2) $x \preceq y \iff x \text{ divides } y$ ex3) $x \preceq y \iff x \subseteq y$ 모두 lattice에 해당! Theorem 1 $\langle L, \preceq \rangle$이 lattice라고 하고, x*y가 glb, x+y가 lub를 나타낼 때..
Algebra 1. Definition Definition 1 algebra는 다음의 3가지 component로 구성된다. 1) carrier라고 불리는 집합 A 2) carrier로 정의되어지는 Operators 3) carrier의 구별되는 elements, constants(추후 다루겠지마느 identity나 zero 같은 것들을 의미한다.) 2. Closed with respect to operations Definition 2 $\circ$, $\triangleright$ 를 set T의 binary, unary operation이라고 정의하자 T'를 T의 subset이라고 한다면 T'는 closed with respect to $\circ$ $\Leftarrow a,b \in T' \land a \circ ..
Counting, Recurrence Relation, Infinite Sets 1. Infinite Sets 1-1. Finite Sets Definition 1 집합 A가 finite하려면 A가 empty하거나 특정 자연수 n에 대해 {1, 2, ..., n} 집합과 집합 A이 bijection 관계에 있어야 한다. n은 A의 cardinality이다. cardinality A는 |A|로 표시된다. 1-2. Pigeonhole Principle Theorem 1(Pigeonhole Principle) 만약 A와 B가 finite set이고, |A| = m, |B| = n이고, m > n이면, 함수 $f : A \rightarrow B$는 injection이 아니다. 즉 B의 image 중 둘 이상의 pre-image를 가지는 것이 무조건 있다. Example 1 Theorem :..
Function 1. Function 1-1. Definition Definition 1 A와 B를 set라고 할 때, $\forall x \in A$에 대해 unique한 $y \in B$가 있는 경우 A relation f from A to B를 function이라고 부른다. $f \subseteq A \times B$ 이다. 모든 x에 대한 함숫값이 있어야 하고, 그 함숫값은 하나만 존재해야 한다. 1-2. Terminology f : $A \rightarrow B$ 그리고 f(a) = b일 때, A = the domain of f B = the codomain of f b = image of a under f a = pre-image of b under f The range R = $\{b|(a, b) \in f..
Relation & Function 1. Relation 1-1. Partition and Covering of a set $\pi = \{A_1, A_2, ... , A_m\}$ 일 때, $A_i (1 \le i \le m)$이 S의 non-empty subset이고, $\bigcup_{i=1}^m A_i = S$이면 set $\pi$를 covering of S라고 부른다. $A_1, A_2, ... , A_m$을 S를 cover라고 부른다. 만약 $\pi$의 element들이 서로 disjoint라면 $\pi$를 S의 partition이라고 부른다. $A_1, A_2, ... , A_m$을 S를 the blocks of the partition이라고 부른다. 1-2. Quotient Set R이 equivalence relation o..
Relation Generalized Unions and Intersections union과 intersection은 commutative하고 associative하기 때문에, 임의대로 순서를 정하고 grouping해도 된다. big U, big ∩ notations Relation A와 B의 관계는 AxB의 부분 집합으로 표현 가능하다. Complementary Relations : 전체 AxB 집합에서 R 집합의 원소를 제외한 집합을 의미한다. Inverse Relation : 원래의 relation의 순서를 반대로 한 relation A 집합과 A 집합 그 자신과의 Relation을 구한 것을 a relation on the set A라고 한다. Identity relation = {(a,a) | a ∈ A} P..
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로 바꾸는 것 해당 기법들을 통해서 q..
Predicate Logic 술어논리 Predicate symbol => 대문자로 표현되고, 문장을 return한다. 대상 간의 관계 혹은 대상의 특성을 알림. assign(=). Function symbol => 한 대상과 다른 대상에 대입시킴. boolean 값을 return. boolean(==). term : Constant symbols, variable 그 자체나 functional symbol과의 결합으로 주어짐. => 그렇다면 predicate symbol은? variable과 propositional function(ex. "x > 3")의 결합 p(x) 자체는 proposition이 아니다. 왜냐면 참과 거짓을 모르기 때문. 하지만 x에 특정 값이 배정된다면, 이는 proposition이 된다. Quantifier..

티스토리툴바