Um assistente de prova é um programa aplicativo que ajuda humanos a construir provas verificadas por máquina.
Ao codificar uma lógica em um assistente de prova, como Coq ou Isabelle, é necessário fazer uma escolha entre usar uma incorporação superficial e profunda . Em uma incorporação superficial, as fórmulas lógicas são escritas diretamente na lógica do provador do teorema, enquanto em uma incorporação...
Pergunta: Como as 'táticas' funcionam nos assistentes de prova? Eles parecem ser formas de especificar como reescrever um termo em um termo equivalente (para alguma definição de 'equivalente'). Presumivelmente, existem regras formais para isso, como posso aprender o que são e como funcionam? Eles...
Vou recapitular as anotações do curso no CIS 500: Software Foundations e os exercícios são muito divertidos. Estou apenas no terceiro exercício, mas gostaria de saber mais sobre o que está acontecendo quando uso táticas para provar coisas comoforall (n m : nat), n + n = m + m -> n =...
A maioria dos assistentes de prova (todos?) Tem bugs corrigidos na ocasião. No entanto, daqueles que eu vi esses bugs geralmente são difíceis de encontrar sem querer, e os resultados provados antes que o bug seja corrigido geralmente se mantêm após a correção. Três perguntas, em ordem de...
Suponha que eu quisesse formalizar a prova de Turing sobre o problema da parada, para que uma máquina pudesse verificá-la. Alguns dos conhecidos sistemas automatizados de prova de teoremas incluem Mizar, Coq e HOL4. Fiz o download e experimentei o Coq, mas ele não possui uma biblioteca para...
Parece que George Gonthier e seus colaboradores terminaram de formalizar o Teorema da Ordem Estranha . Em seu trabalho anterior sobre o Teorema das Quatro Cores, Gonthier inventou vários novos algoritmos (principalmente variantes de BDDs e algoritmos gráficos) que eram especialmente passíveis de...
No artigo "A COMPLEXIDADE DOS PROBLEMAS DE SATISFIABILIDADE", de Thomas J. Schaefer, o autor mencionou que This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the...
Existe algum projeto em andamento para verificar formalmente os teoremas e as provas da teoria da complexidade usando um assistente de prova como Coq? Existem limites para fazer
Existe uma maneira de provar o seguinte teorema em Coq? Theorem bool_pirrel : forall (b : bool) (p1 p2 : b = true), p1 = p2. EDIT : Uma tentativa de dar uma breve explicação sobre "o que é irrelevância para a prova" (corrija-me alguém se eu estiver errado ou impreciso) A idéia básica é que, no...
Muitas vezes queremos definir um objeto acordo com algumas regras de inferência. Estas regras denotar uma função de geração de que, quando ele é monótona, produz um ponto fixo menos . Tomamos para ser a "definição indutiva" de . Além disso, a monotonicidade de nos permite argumentar com o...
Olhando para o blog da teoria dos tipos de homotopia, é fácil encontrar muitas bibliotecas formalizando a maior parte da teoria dos tipos de homotopia em Agda e Coq. Alguém sabe se existe alguma tentativa semelhante de formalizar o HoTT em Idris
Ao tentar provar algumas propriedades básicas usando tipos coindutores no Coq, continuo com o seguinte problema e não consigo contorná-lo. Eu destilei o problema em um script Coq simples da seguinte maneira. O tipo de árvore define árvores possivelmente infinitas com ramos rotulados com elementos...
Como convencer a Coq de que a função recursiva fornecida abaixo termina? A função usa dois argumentos indutivos. Intuitivamente, a recursão termina porque um dos argumentos é decomposto. Especificamente, a função aceita duas árvores como entrada. Inductive Tree := | Tip: Tree | Bin: Tree ->...
Considerando os tópicos abordados em uma conferência como a STOC, existem pesquisadores de algoritmo ou complexidade usando ativamente o COQ ou Isabelle? Se sim, como eles estão usando isso em suas pesquisas? Suponho que a maioria das pessoas não usaria essas ferramentas porque as provas seriam de...
Eu gostaria de escrever provas matemáticas usando algum assistente de prova. Tudo será escrito usando lógica de primeira ordem (com igualdade) e dedução natural. O pano de fundo é a teoria dos conjuntos (ZF). Por exemplo, como eu poderia escrever a seguinte prova? Axiom:∀ x ∀ y( x = y↔ ∀ z( z∈ x ↔...
Venho programando há vários anos, mas não estou familiarizado com o CS teórico. Recentemente, tenho tentado estudar linguagens de programação e, como parte disso, verificação de tipo e inferência. Minha pergunta é: se eu tentar escrever um programa de inferência e verificação de tipo para uma...
Lembro-me de ler um post do blog exibindo duas versões da mesma prova, uma escrita por um humano e a outra por uma máquina, e pedi aos leitores para dizer qual é qual. Tentando pesquisar no Google novamente, não consigo encontrar as palavras-chave corretas; a maioria das coisas me direciona para...