Math/Logic
-
[계산논리] 명제논리의 증명 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$..
-
[계산논리] 명제논리의 증명 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 ..
-
[계산논리] 명제논리의 문법 4. SatisfyMath/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 ..
-
[계산논리] 명제논리의 문법 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..
-
[계산논리] 명제논리의 문법 2. 명제식의 정의와 진리표Math/Logic 2023. 2. 16. 22:10
이전 글에서 명제 변수의 의미와 몇 가지 연결사에 대해 알아보았다. 연결사 부분만 한 눈에 보기 좋게 다시 정리해보자면 아래와 같다. 연결사 $($복습$)$ 1. $\neg$, NOT 명제의 참, 거짓을 뒤집는다. $\neg$$($참인 명제$)$ = 거짓 $\neg$$($거짓인 명제$)$ = 참 2. $\vee$, OR 두 명제를 '또는'의 의미로 연결한다. 둘 중 하나만 참이면 참이다. $($참인 명제$)$ $\vee$ $($참인 명제$)$ = 참 $($참인 명제$)$ $\vee$ $($거짓인 명제$)$ = 참 $($거짓인 명제$)$ $\vee$ $($참인 명제$)$ = 참 $($거짓인 명제$)$ $\vee$ $($거짓인 명제$)$ = 거짓 3. $\wedge$, AND 두 명제를 '그리고'의 의미로 ..
-
[계산논리] 명제논리의 문법 1. 명제 변수와 연결사Math/Logic 2023. 2. 14. 16:05
명제란 무엇일까? 명제는 일반적으로 참과 거짓을 판단할 수 있는 '문장'을 말한다. 간단하게 예시를 들자면, '조지 루카스는 사람이다', '남산타워의 높이는 100km이다' 등이 있다. 첫 문장은 '참'이며, 두 번째 문장은 당연히 '거짓'이다. 이렇게 참과 거짓을 가릴 수 있는 문장을 명제라고 한다. 명제가 아닌 문장으로는 '학교에 가다', '불좀 꺼줄래?' 등이 있겠다. 이러한 문장 들은 참과 거짓을 가릴 수 없기에 명제라고 할 수 없는 것이다. 하지만, 수학에서 이런 '자연어'를 다루기에는 문제가 있다. 번거롭기도 하고, 자연어를 사용하면 문장의 의미가 모호해질 수 있기 때문이다. 따라서 명제를 수학적인 기호로 나타낸 것이 바로 명제식이다. 명제식은 '명제 변수'와 '연결사'로 구성된다. 명제 변수..