Minimal Model and hierarchy of expressive power / Modelos minimais e hierarquia de expressividade
AUTOR(ES)
Francicleber Martins Ferreira
DATA DE PUBLICAÇÃO
2007
RESUMO
Neste trabalho, o conceito de Modelo Minimal e seu uso na semÃntica de certas lÃgicas sÃo estudados. NÃs analisamos o poder expressivo de diversas lÃgicas que usam o conceito de Modelo Minimal para definir sua relaÃÃo de satisfaÃÃo. Os principais teoremas estudados foram o Teorema de LÃwenheim-Skolem e o Teorema de Definibilidade de Beth. No CapÃtulo 1, nÃs damos algumas motivaÃÃes e revisamos alguns conceitos bÃsicos de LÃgica. No CapÃtulo 2, nos estudamos a LÃgica de Menor Ponto Fixo|LFP. NÃs exibimos uma prova de que o Teorema de Beth nÃo vale para LFP. NÃs usamos teorias infinitas para provar isso. Utilizando um resultado de Hodkinson para L!!1!, nÃs mostramos que o Teorema de Beth continua nÃo valendo mesmo para teorias finitas de LFP. NÃs continuamos estudando problemas de definibilidade para LFP e demonstramos que, para tipos especiais de definiÃÃes implÃcitas formadas por Sistemas Recursivos, que funcionam como definiÃÃes recursivas em determinados contextos, existe uma definiÃÃo explÃcita. NÃs promavos ainda que o Teorema de LÃowenheim-Skolem Descendente vale para qualquer conjunto de fÃrmulas de LFP, independentemente de sua cardinalidade. No CapÃtulo 3, a CircunscriÃÃo de McCarthy e as Teorias Circunscritivas Aninhadas de Lifschitz, uma generalizaÃÃo da primeira. NÃs abordamos o poder expressivo de CircunscriÃÃo e a falha do Teorema de LÃowenheim-Skolem Descendente. NÃs tambÃm investigamos questÃes de definibilidade no contexto de CircunscriÃÃo. NÃs encerramos esse capÃtulo mostrando que as Teorias Circunscritivas Aninhadas possuem poder expressivo comparÃvel com o da LÃgica de Segunda-Ordem. No CapÃtulo 4, nÃs estendemos uma lÃgica criada por van Benthem dando origem a duas outras lÃgicas, a saber, U-MIN e I-MIN. NÃs provamos que ambas sÃo equivalentes entre si em poder expressivo e daà em diante chamamos U-MIN de MIN. NÃs introduzimos a LÃgica Si-MIN de minimalizaÃÃo simultÃnea e provamos que Si-MIN à equivalente a U-MIN e I-MIN e tambÃm à LÃgica de Segunda-Ordem. NÃs entÃo propomos o fragmento MIN de MIN, cujo poder expressivo situa-se entre o da LÃgica de Segunda-Ordem e o de LFP. No CapÃtulo 5, nÃs reunimos nossas conclusÃes e apontamos trabalhos futuros.
ASSUNTO(S)
logic definability ciencia da computacao expressive power lÃgica recursivas definitions conjuntos indutivos definiÃÃes recursivas inductive sets minimalidade minimalidade definibilidade expressividadde.
ACESSO AO ARTIGO
http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=1359Documentos Relacionados
- Hierarchy and tax legal system
- Entre o \"encardido\", o \"branco\" e o \"branquíssimo\": raça, hierarquia e poder na construção da branquitude paulistana
- Diversity and hierarchy: Nietzsche psychology as hierarchical typology
- Sobre a busca de superfícies minimais e seu emprego nas estruturas de membrana.
- Hierarquia, disciplina e a adoÃÃo de inovaÃÃo em uma organizaÃÃo militar.