Seminários 2007.1

• 25/07/2007
  "On Games and the Polynomial-Space Completeness of Intuitionistic Propositional Logic - Part II",
  por Marcelo Correa, IM-UFF.
  Ver resumo em 16/07/2007.
  
  
• 16/07/2007 - segunda, excepcionalmente
  "On Games and the Polynomial-Space Completeness of Intuitionistic Propositional Logic - Part I",
  por Marcelo Correa, IM-UFF.
  Resumo:
  It will be presented an alternative proof of Ladner and Statman's result that intuitionistic propositional logic (IPL) is PSPACE-complete, combining proof and game-theoretical approaches and, so, gaining the main benefits obtained in each of them: the very informative aspect of a proof-theoretical framework and the stimulating and intuitive appeal of certain graph and semantical games. Comments will also be done on how to adapt this proof for the purely implicational fragment of intuitionistic Logic and the non-triviality of the adaptation of this approach for Classical Logic game-theoretical foundation, regarding that it is not the case that CoNP=PSPACE.
  It is worth to remark that the formulae forming the core of the reduction from the Geography game to IPL have been deeply changed since the last talk presented on this subject.
  
  
• 25/06/2007
  "Linguagem relacional com operador diferença - Parte II",
  por Renata de Freitas, IM-UFF.
  Resumo:
  Na Parte I (ver resumo em 13/06/2007), definimos o operador diferença, estendendo a linguagem relacional, e indicamos uma maneira de utilizar o operador diferença para representar pontos.
  Nesta segunda parte, vamos formular um cálculo para provar inclusões válidas na nova linguagem com pontos.
  
  
• 13/06/2007
  "Linguagem relacional com operador diferença - Parte I",
  por Renata de Freitas, IM-UFF.
  Resumo:
  Neste seminário vamos apresentar uma outra maneira de introduzir pontos na linguagem relacional, distinta daquela proposta por W.W.Wadge (ver o resumo do seminário do dia 09/05/07). Vamos também formular um cálculo para provar inclusões válidas na nova linguagem com pontos.
  
  
• 30/05/2007
  "Axiomatizando a Álgebra de Conjuntos",
  por Hugo Nobrega, bolsista PIBIC.
  Resumo:
  Como axiomatizar a álgebra de conjuntos? Há algum conjunto de fórmulas das quais podemos derivar todas as identidades dessa álgebra? Neste seminário vamos discutir essa importante questão, analisando conceitos de álgebras booleanas e culminando na aplicação do Teorema de Representação de Stone para solucionar o problema.
  
  
• 23/05/2007
  "Consertando um cálculo relacional - Parte III",
  por Petrucio Viana, IM-UFF.
  Ver resumo em 09/05/2007.
  
  
• 16/05/2007
  "Consertando um cálculo relacional - Parte II",
  por Petrucio Viana, IM-UFF.
  Ver resumo em 09/05/2007.
  
  
• 09/05/2007
  "Consertando um cálculo relacional",
  por Petrucio Viana, IM-UFF.
  Resumo:
  Uma leitura do artigo W.W.Wadge, A Complete Natural Deduction System for the Relational Calculus, University of Warwick, Technical Report CS-RR 05, mostra que o sistema ali apresentado é uma mistura do que G. Sundholm chama sistema de dedução natural e sistema de sequentes naturais. Este aspecto do sistema torna-o obscuro e coloca em dúvida o esboço da prova de completude apresentada por Wadge. Neste seminário, vamos apresentar um sistema de dedução natural para a linguagem relacional, inspirado no de Wadge, e provar sua completude, adaptando o conhecido método de construção de modelo canônico.