Hell World Coding and Math Hell World Coding and Math

Math

• [정수론] 합동식3. 중국인의 나머지 정리

  Math/Number Theory 2023. 8. 3. 22:02

  이전 글에서 합동식 $ax \equiv b \bmod n$을 푸는 방법을 알아보았다. 우선, 해가 존재할 조건은 바로 $d = \mathrm{gcd}(a, n)$에 대해 $d \mid b$인 것이다. 또, $x_0$이 위의 합동식의 한 해일 때 $x = x_0 + (n/d)t$ $($단, $t = 0, 1, ..., d-1$$)$가 다른 해임을 알아보았다. 이번 글에서는 여러개의 연립 합동식을 푸는 방법을 알아볼 것이다. 연립 합동식 이제, 다음과 같은 서로 다른 $r$개의 합동식을 생각해보자. $$a_1x \equiv b_1 \bmod m_1$$ $$a_2x \equiv b_2 \bmod m_2$$ $$...$$ $$a_rx \equiv b_r \bmod m_r$$ 이 연립 합동식을 풀어볼 것이다..

  Read More
• [계산논리] 명제논리의 증명 2. Hilbert System을 이용한 증명

  Math/Logic 2023. 7. 25. 21:50

  증명의 의미 이전 글에서 공부한 내용을 다시 살펴보자. 정해진 공리들을 이용해 주어진 명제식을 참으로 만드는 과정을 증명이라고 하였다. 그리고, 공리들을 이용해 명제식을 참으로 치환할 수 있으면, 해당 명제는 증명 가능하다고 한다. 이를 다음과 같이 표현한다. $$\vdash_{a} P$$ Hilbert system을 살펴보기 전, 이 표기를 약간 확장해보자. 증명의 확장 어떤 명제식 $P$와 $Q$에 대하여, $P \vdash Q$를 다음과 같이 정의하자 : 정의된 공리와 더불어 $P = T$임을 이용하여 명제식 $Q$가 참임을 증명할 수 있다 여기에서 약간 더 확장해서, 명제식들의 집합 $\Gamma = \left\{P_1, ... , P_n \right\}$에 대해 $\Gamma \vdash Q$..

  Read More
• [계산논리] 명제논리의 증명 1. 공리를 이용한 증명

  Math/Logic 2023. 7. 11. 22:00

  지금까지 우리는 어떤 명제식의 참/거짓을 판단하기 위해 진리표를 이용했다. 즉, 명제변수가 갖는 진리값에 따라 명제식이 어떤 값을 갖는지를 확인했던 것이다. 그리고, 명제변수가 어떤 값을 갖든 상관없이 참이 되는 명제식을 항진명제라고 했다. 이번 글에서는, 어떠한 명제식이 참임을 보이는 다른 방법을 알아볼 것이다. 명제논리의 공리 공리$($axiom$)$란, 증명할 필요 없이 자명하게 참이 되는 명제를 말한다. 명제논리에서 사용되는 몇가지 공리를 소개하겠다. Axiom 1. Commutativity Axiom 7. Contradiction $p \wedge q = q \wedge p$ $p \vee q = q \vee p$ $p \wedge \neg p = F$ Axiom 2. Associativity ..

  Read More
• [정수론] 합동식2. 선형 합동식

  Math/Number Theory 2023. 7. 6. 21:43

  디오판토스 방정식 디오판토스 방정식은, 정수만을 해로 가질 수 있는 다항 부정방정식이다. 대표적으로 $x^2 + y^2 = z^2$과 같은 방정식이 있으며, 이는 당연히 $x=3,y=4,z=5$와 같은 해를 갖는다. 그 중에서 $ax+by=c$와 같은 형태의 디오판토스 방정식은 해의 존재성과 관련하여 한가지 정리가 있다. Theorem. 선형 디오판토스 방정식 $ax+by=c$는 $d=\mathrm{gcd}(a,b)$에 대해 $d \vert c$일 때만 해를 갖는다. Proof. 필요충분조건이므로, 두 경우에 대해 모두 증명해보겠다. $d=\mathrm{gcd}(a,b)$라면, 어떤 정수 $r, s$에 대해 $a=dr, b=ds$로 나타낼 수 있다. 이때, $ax+by=c$의 해가 존재한다면, 어떤 정수..

  Read More
• [계산논리] 명제논리의 문법 4. Satisfy

  Math/Logic 2023. 7. 5. 18:06

  명제식의 모델 이전 글에서, 우리는 모델과 valuation에 대해 알아보았다. 간단하게 정리하자면, valuation은 명제 변수에 특정한 논리값을 대입하는 것을 말한다. 그리고 모델은 명제식을 참으로 만드는 valuation을 말한다. 이제, 어떤 명제식의 모델을 기호로 나타내는 방법을 알아보자. 명제식 $P \in WFF$와 어떤 valuation $v$에 대해 $v(P) = 1$이면, $v$는 $P$의 모델이며, 다음과 같이 나타낸다. $$v \vDash P$$ 여러의 valuation이 명제식 $P$의 모델인 경우, 집합을 이용하여 $\left\{v_1, ..., v_n\right\} \vDash P$와 같이 나타낼 수 있다. 즉, valuation의 집합 $\Gamma$에 대해 $\Gamma ..

  Read More
• [정수론] 합동식1. 합동식의 정의

  Math/Number Theory 2023. 7. 4. 21:41

  합동식의 정의 Definition. 양의 정수 $n$과 두 정수 $a, b$에 대하여 만약 $n \vert (a-b)$라면, 법 $n$에 대하여 $a$와 $b$는 합동이라고 하며, 기호로는 $a \equiv b \bmod n$ 으로 나타낸다. 즉, 정수 $n$이 $a-b$를 나눈다면, 즉 $a-b$가 $n$으로 나누어 떨어진다면 $n$에 대하여 $a$와 $b$는 합동인 것이다. 반대로 $a-b$가 $n$으로 나누어 떨어지지 않는다면 $a$와 $b$는 합동이 아니다. 다르게 표현한다면, $\exists k \in \mathbb{Z}\, \mathrm{s.t.} \, a - b = nk$ 라면 $a \equiv b \bmod n$ 이다. 몇가지 예시를 생각해보자. $3 - 24 = -21$인데, $7 \ve..

  Read More
• [계산논리] 명제논리의 문법 3. 명제식의 의미와 모델

  Math/Logic 2023. 7. 1. 18:24

  명제식의 의미 이전 글에서 명제식을 정의했다. https://hellworld.tistory.com/20 명제식은 참/거짓, 참과 거짓이 될 수 있는 명제변수, 연결사로 명제변수를 묶은것으로 정의된다. 그리고 진리표를 그려서 명제식의 값을 판단해보았다. 이번 글에서는 명제식을 이해할 수 있는 다른 방법을 소개할 예정이다. 우선, 이전 글에서 소개했던 명제식과 그에 해당하는 진리표를 그려보자. $A$ $B$ $((A \rightarrow B) \wedge \neg A)$ 0 0 1 0 1 1 1 0 0 1 1 0 이 진리표의 의미를 좀 더 자세히 분석해보도록 하겠다. 왼쪽 두 줄은 명제변수 $A$와 $B$가 가질 수 있는 값의 모든 경우의 수를 나타낸 것이다. 명제변수는 참/거짓 $($또는 true/fal..

  Read More
• [계산논리] 명제논리의 문법 2. 명제식의 정의와 진리표

  Math/Logic 2023. 2. 16. 22:10

  이전 글에서 명제 변수의 의미와 몇 가지 연결사에 대해 알아보았다. 연결사 부분만 한 눈에 보기 좋게 다시 정리해보자면 아래와 같다. 연결사 $($복습$)$ 1. $\neg$, NOT 명제의 참, 거짓을 뒤집는다. $\neg$$($참인 명제$)$ = 거짓 $\neg$$($거짓인 명제$)$ = 참 2. $\vee$, OR 두 명제를 '또는'의 의미로 연결한다. 둘 중 하나만 참이면 참이다. $($참인 명제$)$ $\vee$ $($참인 명제$)$ = 참 $($참인 명제$)$ $\vee$ $($거짓인 명제$)$ = 참 $($거짓인 명제$)$ $\vee$ $($참인 명제$)$ = 참 $($거짓인 명제$)$ $\vee$ $($거짓인 명제$)$ = 거짓 3. $\wedge$, AND 두 명제를 '그리고'의 의미로 ..

  Read More