완전성(논리)

수리논리학과 금속논리학에서 성질을 갖는 모든 공식들이 그 성질을 사용하여 도출될 수 있는 경우, 즉, 그 이론들 중 하나일 경우, 형식체계는 특정 성질에 관해 완전하다고 불린다.또한 "완전"이라는 용어는 조건 없이 사용되며, 맥락에 따라 다른 의미를 가지며, 대부분 의미론적 타당성의 속성을 가리킨다.직관적으로, 시스템은 이 특별한 의미에서 완전하다고 불립니다. 만약 그것이 진실인 모든 공식을 도출해 낼 수 있다면 말이죠.

완전성과 관련된 기타 속성

완전성과 반대의 속성을 건전성이라고 합니다.시스템은 각각의 이론이 그 속성을 가지고 있는 경우 속성과 관련하여 건전합니다(대부분의 의미적 타당성).

완전성의 형태

표현적인 완전성

공식 언어는 그것이 의도하는 주제를 표현할 수 있다면 표현적으로 완전한 언어이다.

기능의 완전성

정식 시스템과 관련된 일련의 논리접속은 그것이 모든 명제함수를 표현할 수 있다면 기능적으로 완전하다.

시멘틱 완전성

의미적 완전성은 정식 시스템에 대한 건전성의 반대이다.형식 시스템은 그것의 모든 반복이 이론일 때 tautologness 또는 "의미적으로 완전하다"에 관하여 완전한 반면, 형식 시스템은 모든 이론이 반복일 때 "건전하다"는 것이다(즉, 그것들은 의미론적으로 유효한 공식이다: th와 일치하는 시스템의 언어의 모든 해석에서 진실이다.e 시스템 규칙).그것은,

$\displaystyle \mathcal {S}\varphi \to \vdash _{\mathcal {S}}\varphi .}$^[1]

예를 들어, 괴델의 완전성 정리는 1차 논리에 대한 의미적 완전성을 확립한다.

뛰어난 완성도

형식계 S는, 전제 δ의 세트 마다, δ로부터 의미적으로 따르는 공식을 δ로부터 도출할 수 있으면, 강한 의미에서 완전 또는 완전하다.즉, 다음과 같습니다.

$\displaystyle \Gamma \models _{\mathcal {S}}\varphi \to \Gamma \vdash _{\mathcal {S}}\varphi .}$

레퓨테이션 완전성

정규계 S는 불만족한 공식 집합마다 거짓을 도출할 수 있으면 reflation-complete이다.그것은,

$\displaystyle \Gamma \models _{\mathcal {S}}\bot \to \Gamma \vdash _{\mathcal {S}}\bot }$^[2]

모든 강력한 시스템도 레퓨테이션 완료입니다.직관적으로 강한 완전성은 공식 세트 $d{\displaystyle \mathrm{}}$ ${$ $displaystyle$\$Gamma$가 주어졌을 때 $d{\displaystyle \mathrm{}}${ $displaystyle$ \ $Gamma$의 모든 의미론적 결과$d{\displaystyle }$ { $displaystyle$\$varphi$}를$$ 계산할 수 있음을 의미하며, reflation-completicity는 공식 $세트{\displaystyle \mathrm{}}$$d$$${ display $style$ \ Gamma }와 $}$의 공식 d dddddddddddddddddddddddddddddddddddddd $d{\displaystyle }$$isplaystyle \varphi$ $\}$ $。「\$$displaystyle$$\varphi$$$$」$가 의미론적인 $결과$인지 아닌지를 확인할 수 $있습니다$.

반증-완전 시스템의 예로는 혼 절에 대한 SLD 해결, 등가 1차 논리에 대한 중첩, 절 ^[3]집합에 대한 로빈슨의 해결 등이 있다.후자는 완전하지 않습니다.예를 들어${\displaystyle }${ ${\displaystyle a}$ ${\displaystyle \}a}$ a$$ b \ $displaystyle$\ {$a$ \ $lor$ b$}$는 1차 로직의 프로포지션 서브셋에서도 $유지$되지만${\displaystyle b}$b \ $displaystyle$$$a \$lor$$$b는$$ { a$}$에서${\displaystyle }$해상도로 도출할 수 없습니다.${\displaystyle 단},{\displaystyle }$ {${\displaystyle }$a ,${\displaystyle b}$ b${\$ { $displaystyle$\ {$a$ , \ $lnot ( a$ \ $lor$ b ) \ } \ $vdash$\$bot }$는 도출할 수 있습니다.

구문적 완전성

형식계 S는 구문적으로 완전하거나 연역적으로 완전하거나 최대 완전하다(폐쇄식) θ가 시스템 언어의 각 문장(폐쇄식)에 대해 S의 정리일 경우.이것은 부정완전성이라고도 불리며 의미완전성보다 강하다.다른 의미에서 정식 시스템은 모순을 도입하지 않고 증명할 수 없는 문장이 추가될 수 없는 경우에만 구문적으로 완전하다.진리함수적 명제논리와 1차 술어논리는 의미론적으로는 완전하지만 구문론적으로는 완전하지 않다(예를 들어, 단일 명제변수 A로 구성된 명제논리문은 정리가 아니며 부정도 아니다).괴델의 불완전성 정리는 페아노 산술과 같이 충분히 강력한 재귀 체계는 일관성과 구문적으로 완전할 수 없다는 것을 보여준다.

구조 완전성

초직관적 및 모달 논리학에서, 모든 허용 가능한 규칙이 파생될 수 있다면 논리는 구조적으로 완전하다.

레퍼런스