기술 블로그

알고리즘 컴퓨터 프로그래밍의 기초/ 기반입니다. 알고리즘은 input, output, definiteness(명확성), correctness(정확성), finiteness(유한성), effectivenesS(효율성), generality(일반성) 등이 있습니다. 결정성은 각 단계의 중간 결과는 유일하고 그리고 입력과 이전 단계의 결과에 의해서만 결정됩니다. 의사코드 (3개의 수 중 최대의 수 찾기) Algorithm to find the largest of three numbers a, b, c Input : a, b, c Output : large(the largest of a, b, and c) procedure max3(a, b, c:integers) { large := a if (b > large..

수열이란? 일정한 규칙에 따라 한 줄로 배열된 수의 열. a₁, a₂, a₃,…, aₙ의 꼴로 배열한 것으로, ｛aₙ｝로 나타냄. 문자열(String) 이란? 문자열의 유한 sequence입니다. 그런데 항상 순서있는 유한 sequence입니다. 이것을 우리가 string이라고 합니다. 집합 X를 공집합이 아닌 집합이라고 하고 집합 X 상에서의 String은 유한 수열입니다. 집합 X가 {a, b, c} 로 이루어져 있을 때 a = bbaccc 이랗게 표현된 수열이라면 연속적으로 중복된 문자들은 지수승으로 인해서 표현을 할 수 있습니다. b^2 * a* c^3으로 표현할 수 있습니다. |a| 은 길이를 나타냅니다. |a|의 개수를 의미하며 bbaccc로 총 6개의 문자가 나열되어 있기 때문에 길이는 6이..

집합은 근본적으로 원소들의 순서가 중요하지 않습니다. {a, b, c} 가 순서가 바뀌어도 별 상관이 없습니다. 또한 집합에서 모든 원소는 서로 다르다라는 것이 중요합니다. 집합 내 원소들이 중복이 발생하면 그 중복은 의미가 없습니다. 원소 a와 원소 b가 같다면 {a, b, c} = {a, c} = { b, c } = { a, a, b, a, b, c, c, c, c } 전부 다 같습니다. 모든 원소는 같은 하나의 원소로 생각하기 때문입니다. N = 자연수의 집합 Z = 정수의 집합 Z+ = 양의 정수의 집합 R = 실수의 집합 R+ = 양의 실수의 집합 C = 복소수의 집합 Q = 유리수의 집합 실수에서 구간, 즉 범위를 나타내는 표기법이 있습니다. -[a, b] = {x | a

n이 정수이면 n^2 >= n 임을 증명하라 경우에 의한 증명 n = 0, n >= 1 , n = 0 이 성립 - n >=1 일때, 양변을 n으로 곱하면 n^2 >= n 이 성립 - n = 0 이므로 n^2 >= n 이 성립\ 따라서 세 경우 모두에 대해 성립하므로 증명하였다. 유일성 증명 -유일하게 하나의 값만이 주어진 특성을 만족하는 경우를 유일성이라고 하고 이에 대한 증명을 유일성 증명이라고 합니다. 유일성 증명 과정 존재성 : x가 주어진 특성을 가짐을 보인다. 유일성 : 만일 y != x 이면 y는 주어진 특성을 가지지 않음을 보인다. 즉 하나의 원소만이 주어진 특성을 갖는지 보이면 됩니다. 예시 a와 b는 실수이고 a != 0 이라면, ar + b = 0을 만족하는 유일한 실수 r이 존재함을 ..

전칭예시화 ∀xP(x)가 주어졌을 때, ∀xP(x)가 true라면 domain에 속하는 임의의 값 c에 대하여 p(c) 가 true임을 보이는데 활용된다. 전칭일반화 ∀xP(x)가 주어졌을 때, domain에 속하는 모든 값 c에 대하여 p(c)가 true이면 ∀xP(x)가 true임을 보일 때 사용하는 추룐 규칙이다. 존재예시화 ∃xP(x)가 주어졌을 때, ∃xP(x)가 true라면, domain 안에 p(c)를 ;true로 하는 값 c가 적어도 하나 있다는 것을 나타내는 추론 규칙이다. 존재일반화 ∃xP(x)가 주어졌을 때, 특정값 c에 대하여 p(c)가 true이면 ∃xP(x)가 true라는 추론규칙이다. 예시 다음 가정이 "Maria has taken a course in computer scie..

중첩된 한정자 ∀x ∀y P(x,y) 임의의 양의 두 실수의 합은 양수이다. L(x, y)를 'x가 y를 사랑한다' 라고 하자. 다음 문장을 기호로 표현. 모든 사람은 어떤 사람을 사랑한다. ∀ x ∃ y L(x, y) -모든 사람 x에 대하여, x가 y를 사랑하는 어떤 사람 y가 존재한다. ∃x ∀y L(x, y) -어떤 사람 x가 존재하는데, 모든 y에 대해서 x가 y를 사랑한다. -어떤 사람은 모든 사람을 사랑한다. 한정 기호의 순서는 중요합니다. 한정 기호의 순서를 바꾸면 의미 또한 바뀝니다. ∀x ∀y P(x, y) ∀y ∀x P(x, y) ∀x ∃y P(x,y) ∃x ∀y P(x,y) ∃x ∃x P(x,y) ∃y ∃x P(x,y) 모든 x에 대하여 P(x,y)를 true로 하는 적어도 하나의 ..

존재한정자 ∃ ( there exist)의 의미로 e를 대문자로 표현하고 좌우로 바꾼 것입니다. 따라서 어떤 x에 대해서 ∃xP(x) : 도메인 D의 어떤 x에 대해서 하는 것입니다. 명제 x의 p(x)가 참이 되도록 하는 domain에 속하는 적어도 하나의 값이 존재하면 ∃x는 참이 되는 것입니다. 존재한정자의 의미는 Domain의 모든 원소를 x1, x2, ... xn으로 나열할 수있다면 ∃xP(x)는 다음과 동일합니다. 구속 변수와 자유 변수 구속 변수와 자유 변수 변수 X에 QUANTIFIER가 적용되거나 특정 값이 할당되면 x를 구속변수라고 합니다. 변수 x에 quantifier가 적용되지 않거나 특정 값이 할당되지 않으면 이를 자유변수라고 합니다.

시스템 명세란? 시스템 공학자나 소프트웨어 공학자는 영어와 같은 자연언어로 요구 사항을 접수 받아 논리에 기반한 정확하고 모호하지 않은 명세서를 작성합니다. 일관성있는 명세가 되기 위해서는 각 명제가 참 이 되도록 명제 변수에 진리 값을 할당할 수 있다면, 명제들의 목록은 일관성이 있다고 봅니다. 즉 시스템 명세는 모순이 나오게 하는 상호 배치되는 요구 사항을 포함해서는 안됩니다. 예시 - 진단 메세지는 버퍼에 저장되거나 또는 재전송된다. - 진단 메세지는 버퍼에 저장되지 않는다. - 진단 메세지는 버퍼에 저장된다면, 재전송된다. 풀이 p : "진단 메세지는 버퍼에 저장된다." q : "진단 메세지는 재전송된다." 시스템 명세 문장들 - p U q - ~ p - p -> q p가 거짓이고 q가 참이면 위..

p q p -> q T T T T F F F T T F F T p -> q의 진리표를 처음부터 완벽히 이해하는 사람은 없을 것입니다. p가 F면 q의 진리값과 상관없이 왜 p -> q는 t일까? 이런 질문을 할 것으로 보이는데요. 논리학에서는 전제가 거짓이면 결론의 값과 상관없이 참이라고 간주합니다. 모든 명제는 참이거나 거짓입니다. p -> q의 진리값도 반드시 참 혹은 거짓이어야 하는데요. 하지만 가정부터 거짓이라면 우리는 결론을 단정지을 수 없습니다. 하지만 이런 경우라도 반드시 진리값은 정해져야 하기 때문에 이를 우리는 T로 하자고 약속을 한 것입니다. 예시 P : 내일 비가 오면 Q : 소풍을 가지 않는다. 이런 조건문이 있습니다. p -> q는 참인 것을 아실 수 있을 것입니다. 그런데 내일 ..

논리적 동치 -p와 q가 n개의 명제들 p1,p2....pn으로 구성된 복합명제라고 하자. p1,p2,...pn의 어떤 진리값들이 주어졌을 때, 두 복합 명제 p와 q가 항상 같은 진리값을 가질 경우, p와 q는 논리적 동치라고 한다. p ≡ q or pq 라고 표기한다. 명제의 역, 이, 대우 p -> q에서 조건 p를 가정, 조건 q를 결론이라고 합니다. p와 q를 바꾸면 q -> p가 되는데 이것을 명제의 역이라고 합니다. p -> q를 부정하면 ~p -> ~q가 되는데 이것을 명제의 이라고 합니다. 가정과 결론도 바꾸고 부정도 하면 ~q -> ~p 가 되는데 이것이 바로 명제의 대우입니다. 예시 p : 날씨가 맑아지면 q : 소풍을 간다. 역 ( q -> p) : 소풍을 가면 날씨가 맑아진다. 이..