1 |
[en] ON SOME RELATIONS BETWEEN NATURAL DEDUCTION AND SEQUENT CALCULUS / [pt] ALGUMAS RELAÇÕES ENTRE CÁLCULO DE SEQUENTES E DEDUÇÃO NATURALCECILIA REIS ENGLANDER LUSTOSA 19 March 2015 (has links)
[pt] Segerberg apresentou uma prova geral da completude para lógicas
proposicionais. Para tal, um sistema de dedução foi definido de forma que suas
regras sejam regras para um operador booleano arbitrário para uma dada lógica
proposicional. Cada regra desse sistema corresponde a uma linha na tabela de
verdade desse operador. Na primeira parte desse trabalho, mostramos uma
extensão da ideia de Segerberg para lógicas proposicionais finito-valoradas e
para lógicas não-determinísticas. Mantemos a ideia de definir um sistema de
dedução cujas regras correspondam a linhas de tabelas verdade, mas ao invés de
termos um tipo de regra para cada valor de verdade da lógica correspondente,
usamos uma representação bivalente que usa a técnica de fórmulas separadoras
definidas por Carlos Caleiro e João Marcos. O sistema definido possui tantas
regras que pode ser difícil trabalhar com elas. Acreditamos que um sistema
de cálculo de sequentes definido de forma análoga poderia ser mais intuitivo.
Motivados por essa observação, a segunda parte dessa tese é dedicada à
definição de uma tradução entre cálculo de sequentes e dedução natural, onde
procuramos definir uma bijeção melhor do que as já existentes. / [en] Segerberg presented a general completeness proof for propositional logics.
For this purpose, a Natural Deduction system was defined in a way that its rules
were rules for an arbitrary boolean operator in a given propositional logic. Each
of those rules corresponds to a row on the operator s truth-table. In the first
part of this thesis we extend Segerbergs idea to finite-valued propositional logic
and to non-deterministic logic. We maintain the idea of defining a deductive
system whose rules correspond to rows of truth-tables, but instead of having
n types of rules (one for each truth-value), we use a bivalent representation
that makes use of the technique of separating formulas as defined by Carlos
Caleiro and João Marcos. The system defined has so many rules it might be
laborious to work with it. We believe that a sequent calculus system defined in
a similar way would be more intuitive. Motivated by this observation, in the
second part of this thesis we work out translations between Sequent Calculus
and Natural Deduction, searching for a better bijective relationship than those
already existing.
|
2 |
[pt] SISTEMAS DE PROVA E GERAÇÃO DE CONTRA EXEMPLO PARA LÓGICA PROPOSICIONAL MINIMAL IMPLICACIONAL / [en] SYSTEMS FOR PROVABILITY AND COUNTERMODEL GENERATION IN PROPOSITIONAL MINIMAL IMPLICATIONAL LOGIC23 November 2021 (has links)
[pt] Esta tese apresenta um novo cálculo de sequente, correto e completo para a Lógica Proposicional Minimal Implicacional (M →). LMT → destina-se a ser usado para a busca de provas em M →, em uma abordagem bottom-up. A Terminação do cálculo é garantida por uma estratégia de aplicação de regras que força uma maneira ordenada no procedimento de busca de provas de tal forma que todas as combinações possíveis são exploradas. Para uma fórmula inicial α, as provas em LMT→ têm um limite superior de |α|.2 |α|+1+2·log2|α|, que juntamente com a estratégia do sistema, garantem a decidibilidade do mesmo. As regras do sistema são concebidas para lidar com a necessidade de repetição de hipóteses e a natureza de perda de contexto da regra → esquerda , evitando a ocorrência de loops e o uso de backtracking. Portanto,
a busca de prova em LMT → é determinística, sempre executando buscas no sentido forward. LMT → tem a propriedade de permitir a extração de contramodelos a partir de buscas de prova que falharam (bicompletude), isto é, a árvore de tentativa de prova de um ramo totalmente expandido produz um
modelo de Kripke que falsifica a fórmula inicial. A geração de contra-modelo (usando a semântica Kripke) é obtida como consequência da completude do sistema. LMT→ é implementado como um provador de teoremas interativo baseado no cálculo proposto aqui. Comparamos nosso cálculo com outros
sistemas dedutivos conhecidos para M →, especialmente com Tableaux no estilo Fitting, um método que também tem a propriedade de ser bicompleto. Também propomos aqui uma tradução de LMT → para o verificador de prova Dedukti como uma forma de avaliar a correção da implementação que desenvolvemos,
no que diz respeito à especificação do sistema, além de torná-lo mais fácil de comparar com outros sistemas existentes. / [en] This thesis presents a new sequent calculus called LMT→ that has the properties to be terminating, sound and complete for Propositional Implicational Minimal Logic (M →). LMT→ is aimed to be used for proof
search in M →, in a bottom-up approach. Termination of the calculus is guaranteed by a strategy of rule application that forces an ordered way to search for proofs such that all possible combinations are stressed. For an initial formula α, proofs in LMT→ has an upper bound of |α|.2 |α|+1+2·log2|α|, which together with the system strategy ensure decidability. System rules are conceived to deal with the necessity of hypothesis repetition and the contextsplitting nature of → left, avoiding the occurrence of loops and the usage of backtracking. Therefore, LMT→ steers the proof search always in a forward, deterministic manner. LMT→ has the property to allow extractability of counter-models from failed proof searches (bicompleteness), i.e., the attempt proof tree of an expanded branch produces a Kripke model that falsifies the initial formula. Counter-model generation (using Kripke semantics) is achieved as a consequence of the completeness of the system. LMT→ is implemented as an interactive theorem prover based on the calculus proposed here. We compare our calculus with other known deductive systems for M →, especially
with Fitting s Tableaux, a method that also has the bicompleteness property. We also proposed here a translation of LMT→ to the Dedukti proof checker as a way to evaluate the correctness of the implementation regarding the system specification and to make our system easier to compare to others.
|
Page generated in 0.0234 seconds