태그 보관물: automated-theorem-proving

automated-theorem-proving

Principia Mathematica 스타일 형식화에 적합한 자동 정리 증명 패러다임은 무엇입니까? 것이 어렵다는 것을

나는 Russell ‘s Principia Mathematica (PM)와 논리적 실증주의에서 영감을 얻은 책을 소유하고있다. 공리를 결정하고 그것들로부터 이론을 추론함으로써 특정 영역을 공식화하려고 시도한다. 요컨대, PM이 수학을 위해 시도한 것을 그 영역을 위해 시도합니다. PM과 마찬가지로 자동 정리 증명 (ATP)이 가능하기 전에 작성되었습니다.

나는 현대의 ATP 시스템에서 이러한 공리를 표현하려고 노력하고 있으며, 처음에는 저자가 직접 추론 한 이론을 추론하려고 시도한다. 나는 이전에 ATP 시스템을 사용하지 않았으며 각각의 강점, 약점 및 의도 된 응용 프로그램과 함께 다양한 옵션 (HOL, Coq, Isabelle 등)을 감안할 때 내 특정에 적합한 것을 결정하는 것이 어렵다는 것을 증명합니다 목적.

저자의 형식주의는 PM을 반영한다. 클래스 (세트?), 클래스 클래스 등 최대 6 단계의 계층 구조가 있습니다. 1 차, 아마도 더 높은 차수가 있습니다. PM과의 관계를 고려할 때, PM에 대한 몇 가지 이론이 다른 사람들에 의해 MetaMath에서 입증 되었기 때문에 Metamath를 처음 조사했습니다. 그러나 Metamath는 물론 ATP 시스템이 아닌 증명 검증기입니다.

다양한 ATP 시스템에 대한 설명을 통해 교회 유형 이론, 건설적 유형 이론, 직관 론적 유형 이론, 유형 / 비 유형 집합 이론, 자연적 추론, 람다 미적분학 유형, 다형성, 재귀 함수 이론, 평등의 존재. 요컨대, 각 시스템은 매우 다른 언어를 구현하는 것으로 보이며 다른 것을 공식화하는 데 적합해야합니다. 수학 공식화를위한 기존 라이브러리는 내 목적과 관련이 없다고 가정합니다.

ATP를 선택할 때 고려해야 할 특성이 나이 질문을 읽은 후에 할 수있는 다른 조언에 대한 조언은 대단히 감사하겠습니다. 참고로 여기 책의 샘플 페이지가 있습니다. 불행히도 PM과 마찬가지로 Peano-Russell 표기법입니다.

책의 페이지

그 책 –

“생물학의 공리 학적 방법”(1937), JH Woodger, A. Tarski, WF Floyd

공리는 단순한 것으로 시작합니다. 예를 들어

x

α

α

x

y

x

z

α

y

S=Dfx^α^{α⊂P‘→x:.(y):yPx.⊃.(∃z).z∈α.P‘→y∩P‘→z≠Λ}

다시, 이것은 Peano-Russell 표기법 (Principia의 표기법)입니다.

나중에 공리에는 생물학적 내용이 있습니다.

7.4.2 멘델 리안 클래스의 두 멤버의 게임이 쌍으로 결합하여 접합자를 형성 할 때, 주어진 쌍 결합의 확률은 다른 쌍의 확률과 동일합니다.

이것은 내가 이해 한 바에 따르면 멘델의 유전학에 대한 가정이었습니다.

3 줄 길이이고 이전에 정의 된 내용을 기반으로하기 때문에이 표기법을 생략합니다.

정리의 예-

이것은 멘델의 유전학에서 의미있는 해석을하는 것으로 보인다. 생물학의 역사학자는 아니지만 나는 이해할 수 없다. 이 책에서는 손으로 추론했습니다.

감사!



답변

Principia Mathematica 는 20 세기 초 수학적 논리에서 발견 된 다양한 역설에 크게 반응했습니다. 그러나 ‘읽을 수없는 걸작’으로 종종 칭찬을받은 작품 자체는 다소 어색하고 더 현대적인 기초가 만들어졌습니다. 대부분의 수학을 설명하기 위해 몇 가지 선택 사항이 있습니다. 범주 이론은 하나이고 유형 이론은 람다 미적분의 확장으로 일부 프로젝트에서 인기가 있었지만 가장 잘 이해되고 가장 기초적인 것은 아마도 이론입니다.

ZFC

 ZFC

ZFC

NBG

NBG

ZFC

NBG

ZFC

. 이 이론이 제 생각에 자동화 된 추론에 가장 적합한 이유는 효과적이고 건전하며 완전한 증거 미적분을 인정하는 1 차 논리로 표현할 수 있기 때문이며 유한 액 소화는 1 차 분해능으로 사용할 수 있다는 의미입니다. 깔끔한 결과 : 진술이 결정 가능한 경우, 결국 증거를 찾을 수 있습니다.

제안 논리는 표현력이 충분하지 않으며 고차원 논리는 표현력이 높지만 효과적이고 건전하며 완전한 증거 미적분을 인정하지 않습니다. 이론이 정립 된 1 차 논리를 사용하면 고차원 논리 이론을 표현하고 매핑 할 수 있으므로 결정적인 근거 (Gödel에게 감사 할 수 있음)의 가능성을 제외하고는 고차원 논리 이론을 표현하고 매핑 할 수 있습니다. 종종 반 결정 가능한 것으로 설명됩니다.

NBG

이제 현대식 교정 조교 들은 종종 Principia Mathematia 의 패러다임에 대한 기초에 덜 신경을 쓰고 일상 업무를 증명하는 정리에 더 유용하므로 고차원 논리, SAT / SMT 해석, 유형 이론 및 기타 이론의 일부를 지원합니다. 보다 비공식적이고 덜 기초적인 접근법. 그러나 당신이 Principia Mathematica 와 같은 일을하려고한다면 , axiomatizable first order set 이론으로 증명 된 1 차 분해능 정리가 이상적입니다.

NBG

NBG

NBG

당신이 손에 가지고 작업 하는 경우 이 설정 이론의 관점에서 이론을 정의하려고 시도하는, 당신은 설정 이론의 측면에서 조건을 만들 수 있습니다 집합 이론에서 분리 된 관계형 술어의 정의를 찾는 것입니다. 다시, 이것의 예는 우리가 집합 이론에서 Peano 산술을 정의하는 방법이며, 그 자체로는 숫자, 덧셈, 곱셈 또는 평등에 대한 정의가 없습니다. 평등과 같은 관계에 대한 이론적 정의 정의의 예로서, 다음과 같이 멤버쉽 측면에서 정의 할 수 있습니다.

상당히 경고 : 이것에 대한 학습 곡선은 실제로 매우 가파 릅니다. 당신이 이것을 추구하려는 의도라면, 내 경험과 마찬가지로 전체 문제를 파악하기 몇 년 전에 자신을 찾을 수 있습니다. 모든 것을위한 기초 언어로 이론을 포함시키는 거대한 과제를 수행하기 전에 덜 기초적인 접근 방식으로 이론을 검토 할 수 있습니다. 결국, 셀 수없는 유전자 조합에 대해 추론 필요 는 없습니다 .


답변

몇 가지 사항 :

  1. ∩,⊂
  2. Andrej가 제안한 바와 같이 현대의 모든 대화 형 증거 조수는 반드시 진술을 공식화하고 증명하는 표현력을 갖습니다. 실제로 산술을 포함한 일부 진술이있는 것처럼 보이므로 이미 산술 진술을 다루는 광범위한 이론을 가진 Isabelle , Coq 또는 HOL 과 같은 시스템을 사용하는 것이 좋습니다 . 현대에 중점을 둔 것은 우연의 일치가 아닙니다 .Automath 이후 유용성에 큰 진전이 있었으며, 저는 90 년대 이후 적극적으로 개발되지 않은 것을 사용하여 자신이 장애를 겪고 있다고 생각합니다. 일하다!)

  3. 마지막으로, ITP와 ATP는 다소 어려운 학습 곡선을 가지고 있으므로 을 작성하는 것처럼 이러한 이론을 시스템에 입력 할 수있을 것으로 기 대해서는 안됩니다

    LATEX

답변