Tag Archives: Completeness

일계논리와 Peano 산술

일계논리 문장의 집합 \(\varSigma\)가 완전하다(complete)는 것은 임의의 문장 \(\alpha\)에 대하여 \(\alpha\) 또는 \((\lnot \alpha )\) 중 하나가 \(\varSigma\)의 논리적 귀결인 것이다. 완전성 정리에서는 형식계의 완전성을 말하기 때문에 완전성이라는 용어를 조금 다르게 사용한다. 그러나 두 상황에서 완전성이라는 개념은 서로 깊은 연관이 있다. 왜냐하면 \(\varSigma\)가 완전할 때 임의의 문장 \(\alpha\)에 대하여 \(\alpha\) 또는 \((\lnot \alpha )\)가 \(\varSigma\)로부터 증명될 수 있기… Read More »

일계논리의 건전성과 완전성

일계논리언어 \(\mathcal{L}\)에서 논리식 \(\phi\)가 논리적으로 유효하다(logically valid)는 것은 임의의 \(\mathcal{L}\)-구조 \(M\)과 \(M\)에서의 임의의 값매김에 대하여 \(\phi\)의 값이 \(\mathrm{T}\)가 되는 것을 의미한다. 만약 \(\phi\)가 문장이면 \(\phi\)의 참거짓 여부는 값매김에 영향을 받지 않고 오직 구조에 의해서만 결정된다. 그러므로 다음을 얻는다. 문장 \(\phi\)가 논리적으로 유효할 필요충분조건은 임의의 \(\mathcal{L}\)-구조 \(M\)에 대하여 \(M \models \phi\)인 것이다. 위 정리에 의하면, 논리식 \(\phi\)가 논리적으로 유효하지… Read More »

명제논리의 건전성, 완전성, 긴밀성

명제논리에 대하여 논할 때는 두 가지 관점에서 논하게 된다. 하나는 구문론적 관점이며 다른 하나는 의미론적 관점이다. 구문론에서는 문자열의 의미는 따지지 않고 오직 기호 사이의 형식적 관계에만 관심을 가진다. 반면 의미론에서는 논리변수의 진릿값 배정에 따른 논리식의 진릿값과 논리식 사이의 논리적 귀결에 대해 관심을 가진다. 이들 두 관점은 완전히 서로 다른 것처럼 보이지만, 사실은 밀접한 연관을 가지고 있다. 즉 가정이… Read More »