Lógica para Computação

Informações Gerais =

• Professores responsáveis
• Oferecimentos

Professores responsáveis

• Celso Kaestner
  • O prof. Celso ministrou a disciplina no períodos 2007.1, 2007.2, 2008.1 e 2008.2 no curso de Engenharia de Computação. Em virtude de ter assumido o cargo de Assessor da Pró-Reitoria de Pesquisa e Pós-Graduação da UTFPR, esta disciplina será assumida pelo professor Adolfo Neto a partir do primeiro semestre de 2009.
• Adolfo Neto
  • A partir de 2009.1, o professor Adolfo lecionará a disciplina para os cursos de Engenharia de Computação e Bacharelado em Sistemas de Informação.

• Murilo Vicente da Silva
  • A partir de 2010.1, o professor Murilo passou a lecionar a disciplina para os alunos dos cursos de Engenharia de Computação e Bacharelado em Sistemas de Informação que não foram aprovados nas turmas regulares.

Oferecimentos

• Lógica para Computação - Turma S71 - 2010.1
• Lógica para Computação - Turma S73 - 2010.1

• Lógica para Computação - Turma S71 - 2009.2
• Lógica para Computação - Turma S73 - 2009.2
• Lógica para Computação - Turmas S71 e S73 - 2009.1
• Alunos destaque em Lógica para Computação
• Dados de aprovação/reprovação em Lógica para Computação

Ementa

• Lógica Proposicional.
• Linguagem e Semântica.
• Sistemas Dedutivos.
• Aspectos Computacionais.
• O Princípio da Resolução.
• Lógica de Predicados.
• Substituição e Resolução.
• Introdução ao PROLOG.
• Aplicações em Computação: Introdução à Especificação e Verificação de Programas.

Pré-requisitos

• Conhecimentos básicos de matemática do ensino médio, principalmente álgebra matemática.

Ou, baseado em http://portal.mec.gov.br/index.php?option=com_docman&task=doc_download&gid=841&Itemid= :

• Eixo cognitivo:
  • Dominar linguagens (DL): dominar a norma culta da Língua Portuguesa e fazer uso da linguagem matemática.

• Competência exigida:
  • Modelar e resolver problemas que envolvem variáveis socioeconômicas ou técnico-científicas, usando representações algébricas.
    • H19 - Identificar representações algébricas que expressem a relação entre grandezas.
    • H20 - Interpretar gráfico cartesiano que represente relações entre grandezas.
    • H21 - Resolver situação-problema cuja modelagem envolva conhecimentos algébricos.
    • H22 - Utilizar conhecimentos algébricos/geométricos como recurso para a construção de argumentação.
    • H23 - Avaliar propostas de intervenção na realidade utilizando conhecimentos algébricos.

• Objetos de conhecimento:
  • Conhecimentos algébricos: gráficos e funções; funções algébricas do 1.º e do 2.º graus, polinomiais, racionais, exponenciais e logarítmicas; equações e inequações; relações no ciclo trigonométrico e funções trigonométricas.
  • Conhecimentos algébricos/geométricos: plano cartesiano; retas; circunferências; paralelismo e perpendicularidade, sistemas de equações.

Objetivos da disciplina

Os objetivos da disciplina Lógica para Computação são "desenvolver conceitos de lógica proposicional e de predicados, prova automática de teoremas e programação em lógica".

O papel desta disciplina é o de mostrar como uma lógica pode ser vista como uma linguagem de especificação tanto de sistemas como de suas propriedades.

Sendo assim, pode-se entender a disciplina como o estudo das lógicas proposicional e predicativa do ponto de vista da verificação de propriedades por elas expressas, permitindo que o aluno seja capaz de identificar o tipo de lógica que pode ser usada para especificar um sistema ou propriedade, bem como realizar a modelagem de sistemas e propriedades por meio da lógica escolhida.

Bibliografia

Bibliografia Básica

• SILVA, Flávio S. C. da; FINGER, Marcelo; MELO, Ana C. V. de. Lógica para Computação. São Paulo: Thomson Learning, 2006.
  • Este livro conquistou o primeiro lugar do Prêmio Jabuti 2007 na categoria Ciência Exatas, Tecnologia e Informática.
  • Respostas dos Exercícios do livro "Lógica para Computação"

• HUTH, Michael; RYAN, Michael. Lógica em Ciência da Computação: modelagem e argumentação sobre sistemas. Segunda edição. Editora LTC: 2008. 326 p.
  • Tradução de:
    • HUTH, Michael; RYAN, Michael. Logic in Computer Science: modelling and reasoning about systems. Segunda edição. Cambridge University Press: 2004. 427 p.
    • Página do livro original (contém errata): http://www.cs.bham.ac.uk/research/projects/lics/

• SOUZA, João N. de. Lógica para Ciência da Computação. Segunda edição. Rio de Janeiro: 2008.
  • Leia resenha bastante crítica de Walter Carnielli sobre a primeira edição deste livro publicada na revista Espiral: http://www.eca.usp.br/njr/espiral/noosfera18b.htm. Leia também, de Carnielli e Coniglio, uma crítica mais detalhada: A lógica e o consortio daemoniorum. Disponível em: <ftp://ftp.cle.unicamp.br/pub/arquivos/educacional/consortio-daemoniorum.pdf>. Acesso em: 09 dez. 2008.

Slides

• Introdução à Lógica
• Lógica Proposicional

Referências

• KAESTNER, Celso. Página dos oferecimentos de "LÓGICA PARA COMPUTAÇÃO". 2008. Disponível em: <http://www.dainf.ct.utfpr.edu.br/~kaestner/Logica.htm>. Acesso em: 09 dez. 2008.

Vídeos

• Great Scientists Aristotle (sobre a vida de Aristóteles)
• O futebol dos filósofos, Monty Python
• Raymond Smullyan tocando Bach
• Entrevista com Newton da Costa - Itajubá em Foco

Links Diversos

• KOWALSKI, Robert. How to be Artificially Intelligent – the Logical Way. Disponível em: <http://www.doc.ic.ac.uk/~rak/>. Acesso em: 09 dez. 2008.
• http://en.wikipedia.org/wiki/Automated_theorem_proving
• http://pt.wikipedia.org/wiki/L%C3%B3gica
  • Atenção especial a http://pt.wikipedia.org/wiki/L%C3%B3gica#Testes_de_L.C3.B3gica
• Regras de dedução natural, Desidério Murcho
• Frases sobre Lógica
• Disciplinas de Lógica no Brasil e no Mundo

Lógica de Predicados

Links interesssantes:

• Lógica de Predicados, Prof. Dr. Silvio do Lago Pereira
• Semântica de Lógica de Predicados
• The Philosophical Importance of Mathematical Logic, Bertrand Russell (1911)

Material Adicional

Porque estudar lógica

• Why Logic is Important for Computer Science and Mathematics
• Why Study Formal Logic?

Programação em Lógica

• Livro de Eloi Favero (UFPA) sobre Prolog
  • Exercícios resolvidos em Prolog
• http://pt.wikipedia.org/wiki/Prolog
• http://en.wikipedia.org/wiki/Prolog
• Linguagem Prolog, SANDRA CORTINOVI
• http://www.scholarpedia.org/article/PROLOG
• http://portal.acm.org/citation.cfm?id=1057820
• http://en.wikipedia.org/wiki/Declarative_programming
• Links (alguns quebrados) para materiais sobre Prolog
• Alguns exemplos de programas em Prolog
• SWI-Prolog Reference Manual
• Dicas sobre o SWI Prolog
• Artigo sobre o SWI Prolog na Wikipedia
  • Artigo sobre o SWI Prolog na Wikipédia lusófona
• Learn Prolog Now
• JPL - A Java Interface to Prolog
• JIProlog - Java Internet Prolog
• Linha de Código - Descobrindo o Prolog
• Prolog (UEM)
• Vítor Santos Costa's Home Page
• YAP Prolog

Sistemas Computacionais de Auxílio ao Aprendizado de Lógica

Simuladores de lógica digital

• TkGate
  • Roda em Linux! Testado no Fedora 11 por Adolfo Neto

• KSimus
  • Descrição em http://www.linuxjournal.com/content/digital-and-analog-circuit-simulation-ksimus

Para diversos métodos relacionados à lógica proposicional

• NICOLADELLI, José Martim. ASA-CalcPro. Disponível em: <http://www.asacalcpro.com.br>. Acesso em: 17 fev. 2009.
  • Vínculo direto para o download do programa: http://www.asacalcpro.com.br/asa.exe
• Logicamente: http://www.dimap.ufrn.br/logicamente/

Tablôs

• NICOLADELLI, José Martim. ASA-Tableaux. Disponível em: <http://www.asacalcpro.com.br>. Acesso em: 09 dez. 2008.
  • Vínculo direto para o download do programa: http://www.asacalcpro.com.br/InstallTableaux/ASA-Tableaux.exe

• Método dos tableaux analíticos em LISP: http://www.dainf.ct.utfpr.edu.br/~kaestner/Logica/tableau-method.lsp.

• WDTP - Wagner Dias Tableau Prover (para tablôs analíticos e tablôs KE)

• Tree Proof Generator, by Wolfgang Schwarz - um demonstrador de teoremas online baseado em tablôs analíticos (árvores de prova) para lógicas clássica proposicional e de predicados.

Tablôs KE

• ENDRISS, Ulle. WinKE: A Proof Assistant for Teaching Logic. Disponível em: <http://staff.science.uva.nl/~ulle/WinKE/>. Acesso em: 12 dez. 2008.

• NETO, Adolfo. KEMS: Um provador de teoremas multi-estratégia baseado no método KE. Disponível em: <http://www.dainf.ct.utfpr.edu.br/~adolfo/KEMS>. Acesso em: 12 dez. 2008.

Dedução Natural

• JAPE. Disponível em: <http://jape.org.uk>. Acesso em: 19 ago. 2009.
  • Ver instruções (desatualizadas) em português neste link: http://www.cos.ufrj.br/~mario/logica/jape.htm

• BRODA, K.;EISENBACH, S.; KHOSHNEVISAN, H.; VICKERS, S. Pandora: Proof Assistant for Natural Deduction using Organised Rectangular Areas. Disponível em: <http://www.doc.ic.ac.uk/pandora/>. Acesso em: 15 dez. 2008.
  • A learning support tool designed to guide the construction of natural deduction proofs.

Tabelas-verdade

• Construtor de tabelas-verdade: Java applet
• http://turner.faculty.swau.edu/mathematics/materialslibrary/truth/
• http://www.math.csusb.edu/notes/quizzes/tablequiz/tablepractice.html
• http://www-cs-students.stanford.edu/~silver//truth/
• http://en.wikipedia.org/wiki/Truth_table
• GOTTSCHALL, Christian. Gateway to Logic. Disponível em:<http://logik.phl.univie.ac.at/~chris/gateway/formular-uk.html>. Acesso em: 12 mar. 2009.

Formas normais

• Applet para converter fórmulas para formas normais
• Programas em Prolog (por Jomi Fred Hübner) para diversas tarefas, entre os quais um (transform.pl) para conversão para forma normal conjuntiva

Lógica de Predicados

• Tarski's World:
  • http://ggww2.stanford.edu/GUS/tarskisworld/index.jsp

Programação em Lógica

• Interpretador SWI-Prolog:
  • http://www.swi-prolog.org/

Outras linguagens de programação utilizadas para programação de sistemas lógicos

• Linguagem CLISP: http://clisp.cons.org/ (freeware).
• Python: http://www.python.org/

Algoritmo de Wang

• Algoritmo de Wang em LISP: http://www.cse.buffalo.edu/~shapiro/Reasoning/wang.html.

Resolução

• SHAPIRO, Stuart C. Procedimento de Resolução em LISP: http://www.cse.buffalo.edu/~shapiro/Reasoning/resolution.html (ou ainda sem packages em http://www.dainf.ct.utfpr.edu.br/~kaestner/Logica/resolution-method.lsp).

A organizar

• Provador de teoremas YACAS:
  • http://yacas.sourceforge.net/
    • um sistema geral para computar sistemas lógicos (freeware em Applet Java)
    • an easy to use, general purpose Computer Algebra System, a program for symbolic manipulation of mathematical expressions.

• Software para iPhone/iPod

Listas de sistemas

• Tools for logic in computer science
• Logic software and logic education, list maintained by Hans van Ditmarsch

Exemplos de especificação formal

• Exemplos de especificação formal em VDM-SL

Razões para Estudar Lógica

• Adquirir conhecimentos para trabalhar em empresas como:
  • http://www.grupo-aes.com.br/site/home/