논리적 귀결
논리적 귀결은 논리적으로 결론을 짓는다 라는 뜻이다. 이를 보일려면 어떻게 해야할까?
예를들어
위와 같이 이렇게 오메가와 델타사이에 논리적인 귀결이 있다 했을 때 이를 표현하기를
3가지로 귀결관계임을 나타낼 수 있고 이를 표기법으로 나타낸다면
이와 같이 나타낼 수 있다. 이 표기법은 델타가 참이면 오메가도 참이다를 내포하고 있고 예를들면
진리표를 이용하면 델타가 참일땐 P와Q 모두가 True여야 하기에 오메가도 자동으로 참이 된다.
추론(infernce)
1.귀납적 추론: 관측된 여러개의 사실들을 일반화하여 일반적인 패턴또는 명제를 도출하는 추론방식이며 대표적으로 기계학습이 있다.
2.연역적 추론: 참인 사실들 또는 명제들로 부터 새로운 참인 사실 또는 명제를 도출하는 추론방식이다. 대표적으로 논리자체에서 추론을 하며 위에서 먼저 보았던 논리적 귀결이 있다. 델타가 참인 사실을 통해 오메가라는 참인 명제를 알아냈기에 연역적 추론이라 부를수 있다.
추론규칙(inference rule)
추론 규칙이란 주어진 논리식들(△(델타))로 부터 새로운 논리식(w(오메가))을 만들어내는 기계적으로 적용되는 규칙이라 하며 이를 표기하는 법은
이다. 논리적 귀결과는 다른 ㅏ를 썼고 둘의 차이점은 논리적 귀결은 논리적으로 끝이났다를 표현을 하며 추론 규칙은 새롭게 만들어진 논리식을 표현한 것이다.
1. 긍정 논법
명제 p와q가 있다고 하고 이것을 가지고 논리식으로 만든뒤 p라는 명제를 추가시키면 새는 날 수있다 라는 논리식을 만들고 새이다 라는 것을 호출하면 기계적으로 적용하여 날 수 있다가 나온다 이를 표기한 것이 p ㅏ q이다.
2. 부정 논법
이번에는 처음에는 똑같이 p->q라는 논리식을 만들고 난뒤 q를 부정한 것을 추가하면 이미 주어진 논리식 새이다->날 수 있다 라는 상태에서 날 수 없다 라는 것을 추가하면 기계적으로 날 수 없는 것은 새가 아니다 라는 새로운 논리식이 나온다.
3. 삼단 논법
유명한 추론 규칙중 하나인 삼단 논법이다. 이미 주어진 명제들p와q그리고 r을 이용하여 논리식들을 만든다.
그렇게 되면 새이다->날개가 있다, 날개가 있다-> 날 수 있다. 이 두개의 논리식을 가지고 기계적으로 적용을 하면 새이면 날개가 존재하고 날개가 있다면 날 수 있기에 새이면 날 수 있다 라는 새로운 논리식이 만들어진다.
논리 융합
논리 융합은 두개의 논리합절이 같은 기호의 긍정과 부정의 리터럴을 서로 포함하고 있을 때, 해당 리터럴을 제외한 나머지 리터럴들을 논리합절로 만들어 내는 것을 논리 융합이라 하며 논리합절은 논리식으로 있지 않고 하나의 리터럴로 존재해도 된다. 그리고 논리 융합은 일반화된 추론 규칙들 긍정 논법, 부정 논법, 삼단 논법의 규칙을 모두 포함한 추론규칙 이기도 하다 표기법은
1. 긍정 논법을 논리 융합규칙으로 표현한 것.
2. 부정 논법을 논리 융합 규칙으로 표현한 것.
3. 삼단 논법을 논리 융합 규칙으로 표현한 것.
추론 규칙의 정당성과 완전성
1. 추론 규칙의 정당성(sound)란 주어진 논리식(△)이 있을 때, 추론 규칙에 의해 새롭게 생성된 논리식(w)이 논리적으로 귀결하면 그 추론 규칙은 정당한다고 정의내린다. 즉 저렇게 정당성을 가진 추론규칙은 항상 참이 나온다.
표기법은
2. 추론 규칙의 완전성(complete)란 주어진 논리식들이 있을 때, 논리적으로 귀결하는 것들을 추론규칙이 생성할 수 있다면 그 추론 규칙은 완전하다고 할 수 있다. 이게 무슨 말이냐 위에서 정당성으로 만들어진 추론 규칙에서 역을 하면 된다는 소리이다. 처음부터 주어진 것들을 가지고 새로운 논리식을 만드는 것이 아니라 먼저 귀결함을 확인하고 그 귀결한 것들을 가지고 새로운 추론 규칙을 생성 할 수 있다면 완전하다고 표현한다.
표기법은
정리증명
어떤 공리(추론을 할 때, 참인 것으로 주어지는 논리식)가 주어지면 그 공리들에 추론 규칙을 적용하여 정리를 얻도록 하고 그 정리가 참인 것을 보이는 것이 정리증명이다.
이 정리 증명에는 구성적 증명(공리들에 추론 규칙들을 적용하여 증명을 만들어서 보이는 증명)과 논리융합 반박(증명할 정리를 부정한 다음 논리융합 방법을 적용하여 모순이 발생하면 정리가 참인 증명방법)이있다.
논리융합 반박을 이용한 정리증명의 예
위와 같이 공리가 주어지고 정리가 있을 때 논리융합 반박을 이용을하면 먼저 정리에 해당하는 것을 부정하고 주어진 공리들과 논리융합을 시행한다 시행하다보면 R이 남을텐데 이 R과 정리에 해당하는 R의 부정을 논리융합을 하면 nil이 나오는데 이것은 항상 거짓을 반환하기에 모순이 발생한다. 그래서 이 논리융합 반박으로 증명이 성공 하였다라고 할 수 있다.