Chinese Remainder Theorem (CRT) 중국인의 나머지 정리 x≡1(mod3),x≡2(mod5),x≡3(mod7) 을 만족하는 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 ϕ [Query] ϕ의 Boolean Variable들에 값(T/F)을 잘 할당하여 ϕ의 값이 True가 될 수 있는가? (즉, ϕ이 만족 가능한가?) SAT Problem (SATisfiability; 만족 문제) [Input] CNF Boolean Expression ϕ * CNF (Conjunctive Normal Form; 논리곱 정규형) = POS (Product of Sum) - Clause들이 논리곱(∧)으로 연결되어 있는 형태를 의미한다. - Clause란, Litera..
Modulo Operation 모듈로 연산 - Operand A,B에 대해, AmodB 는 A를 B로 나누었을 때의 나머지를 구하는 연산을 의미한다. ex) 5mod3=2 ex) 79mod2=1 - 즉, AmodB의 값은 반드시 0 이상, B 미만의 값이 도출된다. Congruent Expression (Congruence; 합동식) a≡b(modp) ⟺a≡b(p) \(\iff a \; \mathrm{mod} \; p \; = ..
Terminology Summary 용어 정리 Set (집합) Set (집합) - Element(원소)들의 모임으로, Membership(소속성)을 제외한 어떤 구조도 갖지 않는다. Set Operation (집합 연산) - Intersection(∩, 교집합) - Union(∪, 합집합) - Difference(-, 차집합) Complementation (여집합) ˉS (혹은 Sc) : 집합 S의 여집합 ˉS={x:x∈U,x∉S} (단, U는 전체 집합) Empty Set (공집합, ∅) - 아무 원소도 가지지 않은 집합이다. Subset (부분집합) S_{1} ⊆ S_{2} : 집합 S_{..
Fundamental Laws of Boolean Algebra 불대수의 기본 법칙 * 여기서, T는 True값을, F는 False값을 의미한다. 1. Identity Laws (항등법칙) P∧T⟺P P∨F⟺P 2. Domination Laws (지배법칙) P∨T⟺T P∧F⟺F 3. Idempotent Laws (멱등법칙) P∨P⟺P P∧P⟺P 4. Double Negation Laws (이중부정법칙) ¬(¬P)⟺P 5. Commutative Laws (교환법칙) \(P \lor Q \iff Q \lor P..
Logically Equivalent 논리적 동치 - P↔Q 가 Tautology(항진명제)이면, P, Q는 "논리적으로 동치"라 표현한다. - "P⟺Q" 또는 "P≡Q"라 표기한다. ex) ¬(P∨Q)⟺¬P∧¬Q(DeMorgan‘sLaws) ex) P→Q⟺¬P∨Q * 논리적 동치 관계의 증명 1. 진리표를 이용하는 방법 : 변수의 개수가 증가함에 따라 결과가 기하급수적으로 증가하는 문제가 있다. 2. 기증명된 논리적 동치관계를 이용해서 증명하는 방법 Sample QUIZ Q.1 Prove the propo..
Logical Operator 논리 연산자 - 하나의 명제를 논리 연산자를 이용하여 여러 단순 명제로 도출시켜(분할시켜), 여러 단순 명제의 Truth value(진리값)들로 부터 알고자하는 명제의 진리값을 알 수 있다. * Truth Table (진리표) - 명제들의 진리값 간의 관계를 나타내는 표 1. Negation (부정) : ¬, - 현재 진리값의 반대값을 취하게 하는 연산자이다. (NOT연산) P ¬P T F F T 2. Conjunction (논리곱) : ∧ - 두 진리값이 동시에 True값인 경우를 제외한 모든 경우에는 False를 도출시키는 연산자이다. (AND 연산) P Q \(P \land ..
Proposition 명제 - True나 False중 어느 한 값으로 표현이 가능한 문장 * Propositional Logic (명제 논리) - 내부 구조가 없는 논리 명제에 논리합, 부정 등과 같은 논리 연산을 가하여 구성한 논리 명제들을 다루는 논리체계이다. - H/W설계 시, Gates나 Circuit의 정확한 동작을 정의 및 관리하는 데 이용된다.
