https://chocobear.tistory.com/162

논리학, 그 열 번째 이야기 | 명제논리에서의 건전성 정리와 완전성 정리 ( Soundness Theorem and Completeness Theorem for Propositional Logic )이번 글에서는 이론의 성질인 완전성과 건전성에 대해 이야기해보려고 한다. 완전성과 건전성은 형식 체계의 성질로, 형식 체계가 굳이 이를 만족할 필요는 없지만, 완전성과 건전성을 만족하는 보통은 완전성과 건전성을 만족하는 형식 체계를 사용한다. 완전성과 건전성은 다음과 같이 정의한다. Definition 1. 구문론적 귀결 관계인 $\vdash$와 의미론적 귀결 관계인 $\models$를 포함하는 형식 체계가 있다고 하자. 이러한 형식 체계의 임의의 wff의 집합 $G$와 wff $\mathscr{C}$에 대하여 $G \vdash \mathscr{C}$가 $G \models \mathscr{C}$를 함의한다면, 이 형식 체계가 건전 (Sound)하다고 한다. 또한, 이 역이 성립하는 형식 체계를 완전 (C..chocobear.tistory.com

제가 보고 있는 완전성 논리 관련 게시물입니다. 여기서 완전성을 증명하기 전에 lemma를 하나 준비하는데,


B가 원자명제 wff이고 b1,...,bn이 B를 구성한다고 하면,

이때, b'k=bk if bk가 참

           =~bk if bk가 거짓

으로 각각의 b'k들을 정의하고 B'를 B가 bk들로 구성한 것처럼 b'k들로 구성하면,

w1,...,wnㅑB'가 성립한다.


는 정리입니다. 이를 귀납법으로 증명하는데, 

귀납가설을 적용하면 왜 b',...,b'nㅑφ이 되는지 잘 이해가 안됩니다.


비슷한 내용으로 최원배의 논리적 사고의 기초 책에서도

b'1,...b'n ㅏ B  if B가 참일

b'1,...,b'n ㅏ ~B if B가 거짓일 때, 

이 경우가 항상 성립한다고 하는데 


여기서의 증명은 B가 참일 때와 B가 거짓을 때를 나눠 귀납으로 증명합니다

B가 참일 때,

b'1,...,b'nㅏB가 성립하고, 우리가 보일 것은 b'1,...,b'nㅏ~~B가 성립한다는 것이다,

라고 한다음 그냥 ~~B=B이고 이미 가정에서 B가 참이기 때문에 성립한다고 되어있는데 

이러한 언급은 B가 참이기 때문에 참이라고 말하는 것과 다른 것 같지 않아 첫번째 게시물로 증명으로 완전성을 공부하려 합니다.


첫번째 게시물에서  귀납가설을 적용하면 왜 b',...,b'nㅑφ이 되나요?