FERREIRA, Francicleber Martins. Modelos minimais e hierarquia de expressividade. 2007. 122 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2007. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T15:45:38Z No. of bitstreams: 1 2007_dis_fmferreira.pdf: 752533 bytes, checksum: 98c57917ae2bd6af5de38f25d9ce7c39 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-15T15:38:19Z (GMT) No. of bitstreams: 1 2007_dis_fmferreira.pdf: 752533 bytes, checksum: 98c57917ae2bd6af5de38f25d9ce7c39 (MD5) / Made available in DSpace on 2016-07-15T15:38:19Z (GMT). No. of bitstreams: 1 2007_dis_fmferreira.pdf: 752533 bytes, checksum: 98c57917ae2bd6af5de38f25d9ce7c39 (MD5) Previous issue date: 2007 / 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.

FERREIRA, Francicleber Martins. Modelos minimais e hierarquia de expressividade. 2007. 109 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2007. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-29T18:55:46Z No. of bitstreams: 1 2007_dis_fmferreira.pdf: 752533 bytes, checksum: 98c57917ae2bd6af5de38f25d9ce7c39 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-29T18:56:33Z (GMT) No. of bitstreams: 1 2007_dis_fmferreira.pdf: 752533 bytes, checksum: 98c57917ae2bd6af5de38f25d9ce7c39 (MD5) / Made available in DSpace on 2016-06-29T18:56:33Z (GMT). No. of bitstreams: 1 2007_dis_fmferreira.pdf: 752533 bytes, checksum: 98c57917ae2bd6af5de38f25d9ce7c39 (MD5) Previous issue date: 2007 / 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.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / 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.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2017-04-06T12:58:28Z No. of bitstreams: 2 Dissertação - Marby Zuley Bolaños Ortiz - 2017.pdf: 1515856 bytes, checksum: 739fa4d4c051b1c82f2f7ed1e4427c73 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-04-06T12:58:41Z (GMT) No. of bitstreams: 2 Dissertação - Marby Zuley Bolaños Ortiz - 2017.pdf: 1515856 bytes, checksum: 739fa4d4c051b1c82f2f7ed1e4427c73 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-04-06T12:58:41Z (GMT). No. of bitstreams: 2 Dissertação - Marby Zuley Bolaños Ortiz - 2017.pdf: 1515856 bytes, checksum: 739fa4d4c051b1c82f2f7ed1e4427c73 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-03-30 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / In this work, we estudied three special subgroups of bounded index in G: The intersection of subgroups definables of G, the small type-definable subgroup and the small invariant subgroup of G, called connected components of G and denoted G0G00 e G¥. We give an exposition of theorem of Gismatullim, where he proved the existence of G¥ in a theory with NIP. / Neste trabalho estudamos três subgrupos de um grupo G com índices limitados em G: A interseção de todos os subgrupos definíveis de G , o menor subgrupo tipo-definível e o menor subgrupo invariante de G, chamados componentes conexas de G, denotados respectivamente G0G00 e G¥. Apresentamos uma demonstração da existência de G¥ em uma teoria NIP, baseados na prova feita por Gismatullin em 2011.