Chinese Remainder Theorem (CRT) 중국인의 나머지 정리 \(x \equiv 1\; \mathrm{(mod \; 3)},\\ x \equiv 2 \; \mathrm{(mod \; 5)},\\ x \equiv 3 \; \mathrm{(mod \; 7)}\) 을 만족하는 \(x\)를 구하는 문제에서 시작된 정리이다. (3으로 나누었을 때 나머지가 1이고, 5로 나누었을 때 나머지가 2이며, 7로 나누었을 때 나머지가 3인 수를 구하는 문제) - 여기서 3, 5, 7은 "쌍마다 서로소"이다. (3과 5는 서로소이고, 5와 7은 서로소이며, 3과 7은 서로소이다.) - 중국인의 나머지 정리는 어떤 수를 쌍마다 서로소인 n개의 수 각각에 대해 일정한 나머지를 만족하는 수는 그 n개의 최소공배..
GSAT (General SATisfiability) Problem 일반 논리식 만족 가능성 문제 [Input] Boolean Expression \(\phi\) [Query] \(\phi\)의 Boolean Variable들에 값(T/F)을 잘 할당하여 \(\phi\)의 값이 True가 될 수 있는가? (즉, \(\phi\)이 만족 가능한가?) SAT Problem (SATisfiability; 만족 문제) [Input] CNF Boolean Expression \(\phi\) * CNF (Conjunctive Normal Form; 논리곱 정규형) = POS (Product of Sum) - Clause들이 논리곱(\(\land\))으로 연결되어 있는 형태를 의미한다. - Clause란, Litera..
Modulo Operation 모듈로 연산 - Operand \(A, B\)에 대해, \(A \;\mathrm{mod}\; B\) 는 \(A\)를 \(B\)로 나누었을 때의 나머지를 구하는 연산을 의미한다. ex) \(5 \;\mathrm{mod}\; 3 = 2\) ex) \(79 \;\mathrm{mod}\; 2 = 1\) - 즉, \(A \;\mathrm{mod}\; B\)의 값은 반드시 \(0\) 이상, \(B\) 미만의 값이 도출된다. Congruent Expression (Congruence; 합동식) \(a \equiv b \; \mathrm{(mod \; p)}\) \(\iff a \equiv b \; \mathrm{(p)}\) \(\iff a \; \mathrm{mod} \; p \; = ..
Terminology Summary 용어 정리 Set (집합) Set (집합) - Element(원소)들의 모임으로, Membership(소속성)을 제외한 어떤 구조도 갖지 않는다. Set Operation (집합 연산) - Intersection(∩, 교집합) - Union(∪, 합집합) - Difference(-, 차집합) Complementation (여집합) \(\bar{S}\) (혹은 \(S^{c}\)) : 집합 \(S\)의 여집합 \(\bar{S} = \{x : x ∈ U, x \notin S\}\) (단, \(U\)는 전체 집합) Empty Set (공집합, \(\varnothing\)) - 아무 원소도 가지지 않은 집합이다. Subset (부분집합) S_{1} ⊆ S_{2} : 집합 S_{..
Logically Equivalent 논리적 동치 - \(P \leftrightarrow Q\) 가 Tautology(항진명제)이면, \(P\), \(Q\)는 "논리적으로 동치"라 표현한다. - "\(P \iff Q\)" 또는 "\(P \equiv Q\)"라 표기한다. ex) \(\neg (P \lor Q) \iff \neg P \land \neg Q \qquad (De Morgan`s Laws)\) ex) \(P \to Q \iff \neg P \lor Q\) * 논리적 동치 관계의 증명 1. 진리표를 이용하는 방법 : 변수의 개수가 증가함에 따라 결과가 기하급수적으로 증가하는 문제가 있다. 2. 기증명된 논리적 동치관계를 이용해서 증명하는 방법 Sample QUIZ Q.1 Prove the propo..
Logical Operator 논리 연산자 - 하나의 명제를 논리 연산자를 이용하여 여러 단순 명제로 도출시켜(분할시켜), 여러 단순 명제의 Truth value(진리값)들로 부터 알고자하는 명제의 진리값을 알 수 있다. * Truth Table (진리표) - 명제들의 진리값 간의 관계를 나타내는 표 1. Negation (부정) : \(\neg, ~\) - 현재 진리값의 반대값을 취하게 하는 연산자이다. (NOT연산) \(P\) \(\neg P\) \(T\) \(F\) \(F\) \(T\) 2. Conjunction (논리곱) : \(\land\) - 두 진리값이 동시에 True값인 경우를 제외한 모든 경우에는 False를 도출시키는 연산자이다. (AND 연산) \(P\) \(Q\) \(P \land ..
Proposition 명제 - True나 False중 어느 한 값으로 표현이 가능한 문장 * Propositional Logic (명제 논리) - 내부 구조가 없는 논리 명제에 논리합, 부정 등과 같은 논리 연산을 가하여 구성한 논리 명제들을 다루는 논리체계이다. - H/W설계 시, Gates나 Circuit의 정확한 동작을 정의 및 관리하는 데 이용된다.
