Logic and Proof

방학들어 대학원 스터디의 본격적인 시작!
시간 날때마다 정리해 보자.


Propositional Logic
Proposition(명제)는 True 혹은 False 값을 가지는 문장이다.
Proposition은 Proposition과  논리연산자들을 이용해서 재귀적으로도 정의된다.(negation, and, or, xor, implication 등등)
여기서 기억해둬야 할것은 p->q가 (not p) and q와 동일하다는것!

어떤 proposition이 항상 참인 것을 tautology라고 하며,
항상 거짓인 것을 contradiction,
그냥 일반적인 나머지 proposition을 contingency라 한다.

명제 p와 q에 대해서 p<->q 가 tautology면, p랑 q는 논리적으로 동등(logically equivalent)하다고 말한다.

논리식에 대해 동등함을 나타내는 여러 법칙들이 있는데, 이건 보면 아니까 생략!(드모르간, 결합, 분배 등등)



Predicate Logic
Predicate(서술?)는 변수를 가지는 명제이다. 

이산수학에서는 두 logic이 왜 나오는지를 명확히 설명하지는 않는 것 같은데,
뭐 인공지능에서 배웠으니까 정리할겸 써보자.

propositional logic으로는 실세계의 명제를 논리로 표현할 수는 있지만, 동일한 형태의 명제라도 그냥 다른 명제일 뿐 내부 상태가 없기 때문에 공통점을 찾을 수 없으며, 그것으로 추론 규칙을 적용할 수 없다. 
무슨 말인고 하니..

P : 나는 빵을 먹는다
Q : 너는 밥을 먹는다

라는 P,Q 명제가 있을때 이것들은 개개의 명제일뿐 전혀 공통점이 없으며 추론하는데 사용될 수도 없는 것이다.

따라서!
변수를 가지는(내부 상태를 가지는) predicate logic이 나온 것이며,, propositional logic에서는 최소 단위가 명제이다.
하지만 predicate logic은 object constant(어떠한 대상을 직접 가리키는 것), functional constant(어떤 대상을 지칭하는 것) 그리고 그러한 constant간의 관계인 relation constant를 가지고 있으며
어떠한 object들의 관계인 relation constant가 명제가 된다.

예를 들어,
Eat(x, y)라는 relation constant에 "x eats y"라는 의미를 부여하였을 경우,
위의 예를 Eat(나, 빵)과 Eat(너, 밥)으로 간단하게 표현할 수 있다.

그리고 보다 정밀한(?) 논리적 추론을 위해서 Quantification이라는 걸 하게 된다. 한글로 옮기기엔 애매;
이건 Quantifier와 variable을 통해 이루어 지며,
어떠한 predicate에 변수가 있으면 그것을 constant로 바꿔 주거나,
혹은 Quantifier를 사용해서 그 변수를 bound 시켜줘야 한다.

Quantifier는 for all, there exist를 나타낸다.

그렇게 변수들을 bound 시켰을 경우, propositional logic에서 사용했던 논리 동등 규칙들을 그대로 사용할 수 있게 된다.

이 때 주의할 점은, quantifier의 순서인데 순서에 따라 의미가 달라지므로 주의해야 하며,
왼쪽부터 차례대로 해석하면 틀리지 않고 할 수 있다.



Proof
너무나 친숙한 말이긴 한데 수학적으로 정의하자니 난감하다.

인공지능에서는 Rule of Inference(추론 규칙)를 기계적으로 적용하여 증명하고자 하는 Theorem을 만드는 것이라고 배웠는데,
음. 그래. 그말이 맞는 말 같다.

이산수학에서는 몇가지 증명 방법을 제시한다.
1) Direct Proof
2) Proof by contraposition
3) Vacuous proof
4) Trivial proof
5) Proof by contradiction

p->q를 증명할 경우,
1번은 말그대로 p로 q를 만들면 된다.
2번은 contraposition이 한글로는 대우이다. 중1때 배웠던 방법이다. not q이면 not p가 됨을 보인다.
3번은 직역하면 멍청한 증명.. p->q에서 p가 false가 되면 전체적으로는 참이 되는 성질을 이용한다.
     그런데, p이면 q라는 걸 보이라고 했는데 p가 거짓인 걸 보인다니. 생각해보면 말도 안된다. 그래서 멍청한 증명이라 하나보다. 4번은 직역하면 당연한 증명. q가 참인것을 보여주면 된다. 
5번은 학창시절에 귀류법이라고 배운것. 명제를 부정한다음에 반례(counterexample)를 들어서 증명한다.


1단원 정리끝!