술어 논리-자연 추론

Question

Gentzen의 Natural Deduction의 추론 규칙 세트는 시스템의 어떤 규칙 없이도 여전히 완전 할 수 있다는 의미에서 중복성이 있습니까?

내 생각 : 나는이 질문을 보았고 시스템에 중복성이 있는지 여부에 관계없이 과감한 논쟁을 할 수 없었습니다. 구체적으로 Gentzen의 Natural Deduction의 추론 규칙에는 다음이 포함됩니다.$\forall$-소개, $\forall$-엘림, $\exists$-소개, $\exists$-엘림, $\wedge$-소개, $\wedge$-엘림, $\lor$-소개, $\lor$-엘림, $\Rightarrow$-소개, $\Rightarrow$-엘림, $\neg$-소개 및 $\neg$-엘림.

Answer 1

그러한 중복성은 없으며이를 증명하는 방법이 있습니다.

[편집 : 나는 그것을 더 직관적으로 만들기 위해 주장을 바꾸었다.]

연결에만 집중하자 $\land$간단하게. 그 표현이 무엇인지 모르는 사람의 마음 속에$A\land B$의미하지만 자연 공제 규칙을보고 알아 내고 싶습니다. 소개 및 제거 규칙을 읽을 수있는 한 가지 방법은$\land$표현의 논리적 강도에 하한과 상한 을 부과한다는 것 입니다.$A\land B$. 예를 들면

($\land$-intro) 보낸 사람 $A$ 과 $B$ 미루다 $A\land B$.

당신에게 말한다 $A\land B$이다 강력한 대부분의에 의 조합으로$A$ 과 $B$, 반면

($\land$-elim)에서 $A\land B$ 미루다 $A$ 또는 $B$.

당신에게 말한다 $A\land B$이다 강한로 적어도 두로$A$ 과 $B$.

이제 규칙 ($\land$-소개). 결과 시스템은 표현식의 논리적 강도에 대한 상한선이 없음을 알려줍니다.$A\land B$. 직관적으로$A\land B$적어도 다음과 같은 강력한 것이 될 수 있습니다 .$A$ 과 $B$. 하지만 해석을 방해하는 것은 없습니다.$A\land B$ 결과 시스템에서 가능한 가장 강력한 표현 : 논리적 모순 ($\bot$ 이 원자가 포함되어 있으면 $p\land\lnot p$ 신선한 변수를 위해 $p$). 특히 교체시$A\land B$ 으로 $\bot$ 에 ($\land$-elim), 당신은 소리 규칙을 얻습니다

에서 $\bot$ 미루다 $A$ 또는 $B$.

시스템 에서 해석에 모순되는 것은 아무것도 증명할 수 없습니다.$A\land B$모순으로. 예를 들어, 정리$q\rightarrow (q\land q)$ 증명할 수 없을 것입니다. $q\rightarrow \bot$ 유효하지 않습니다.

이 직감을 공식적인 주장으로 만들려면 번역을 고려하십시오. $\pi$ 모든 하위 공식을 대체합니다. $A\land B$ 공식에서 $\bot$. 그런 다음 증명 길이에 대한 유도를 통해 공식이$F$ 규칙없이 자연 공제에서 증명할 수 있습니다 ($\land$-intro), 다음 $\pi(F)$ ($\land$-intro)뿐만 아니라. 정리는$q\rightarrow (q\land q)$ ($\land$-intro), 그렇게 될 것입니다 $\pi(q\rightarrow (q\land q))=q\rightarrow \bot$, 유효하지 않습니다. 따라서 ($\land$-intro)가 불완전합니다.

다른 규칙의 생략에 대한 유사한 주장을 찾을 수 있습니다.