Lógica para Computação
(→Tabelas-verdade) |
(→Tabelas-verdade) |
||
Linha 228: | Linha 228: | ||
* http://en.wikipedia.org/wiki/Truth_table | * 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. | * 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 === | ||
+ | |||
+ | * [http://www.izyt.com/BooleanLogic/applet.php Applet para converter fórmulas para formas normais] | ||
+ | * [http://bit.ly/9eEoEt Programas em Prolog (por Jomi Fred Hübner) para diversas tarefas, entre as quais conversão para formas normais] | ||
=== Lógica de Predicados === | === Lógica de Predicados === |
Edição de 14h35min de 28 de abril de 2010
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.
Oferecimentos
- 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.
- Modelar e resolver problemas que envolvem variáveis socioeconômicas ou técnico-científicas, usando representações algébricas.
- 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 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.
- 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/
- Tradução de:
- 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
Bibliografia Complementar
Referências fortemente relacionadas à Computação
- BRODA, Krysia; EISENBACH, Susan; KHOSHNEVISAN, Hessam; VICKERS, Steve. Reasoned Programming. Prentice-Hall, 1994. Disponível em: <http://www.doc.ic.ac.uk/pandora/firstyearbook.pdf>. Acesso em: 12 dez. 2008.
- CHANG, Chin-Liang; LEE, Richard Char-Tung. Symbolic logic and mechanical theorem proving. Boston: Academic Press, 1987. 331 p. ISBN 0121703509 (enc.)
- CASANOVA, MARCO A.; GIORNO, F.A.C.; FURTADO, A.L. Programação em Lógica e a Linguagem Prolog. São Paulo: Edgard Blücher, 1987.
- HOARE, Charles Antony Richard; SHEPHERDSON, J. C. (Ed.) Mathematical logic and programming languages. Englewood Cliffs: Prentice-Hall, c1985. 184 p. (Prentice hall international series in computer science) ISBN 0135614651 (enc.).
- LOVELAND, Donald W. Automated Theorem Proving: A Logical Basis. Fundamental Studies in Computer Science, Volume 6, North-Holland Publishing. 1978.
- GALLIER, Jean H. Logic for Computer Science: Foundations of Automatic Theorem Proving. 2003. Disponível em: <http://www.cis.upenn.edu/~jean/gbooks/logic.html>. Acesso em: 20 fev. 2009.
- CLOCKSIN, W.; MELLISH, C. Programming in Prolog. Springer Verlag, 1982.
- LLOYD, J. W. Foundations of Logic Programming. Springer Verlag, 1987.
- CHANG, C. L.; LEE, R. C-T. Symbolic Logic and Mechanical Theorem Proving. Academic Press, 1987.
- FITTING, Melvin. First-Order Logic and Automated Theorem Proving. Springer, 2006.
- Site do autor do livro: http://comet.lehman.cuny.edu/fitting/
- NICOLADELLI, José Martim. ASA-CALCPRO: Uma ferramenta de cálculo proposicional e sua utilização no ensino. Dissertação de Mestrado em Engenharia Elétrica e Informática Industrial. Universidade Tecnológica Federal do Paraná, 2005. Disponível em: <http://arquivos.cpgei.ct.utfpr.edu.br/Ano_2005/dissertacoes/Dissertacao_372_2005.pdf>. Acesso em: 14 set. 2009.
Livros com abordagem mais filosófica ou matemática
- CARNIELLI, Walter; EPSTEIN, Richard L. Pensamento Crítico: O poder da lógica e da argumentação. São Paulo: Rideel, 2009.
- COSTA, Newton C. A.; KRAUSE, Décio. Lógica. Florianópolis: 2009. Disponível em: <http://www.cfh.ufsc.br/~dkrause/pg/cursos/Rosto.pdf>. Acesso em: 14 set. 2009.
- SANT'ANNA, Adonai S. O que é um Axioma. Barueri: Manole, 2003.
- MORTARI, Cezar A. Introdução à lógica. São Paulo: UNESP, 2001. 393 p. ISBN 85-7139-337-0
- CONIGLIO, Marcelo; CARNIELLI, Walter A.; BIANCONI, Ricardo. Lógica e Aplicações (em andamento). Disponível em: <http://www.cle.unicamp.br/prof/coniglio/LIVRO.pdf>. Acesso em: 12 dez. 2008.
- CARNIELLI, Walter A.; EPSTEIN, Richard L. Computabilidade, funções computáveis, lógica e os fundamentos da matemática. São Paulo: Editora UNESP, 2006.
- NOLT, John Eric; ROHATYN, Dennis. Lógica. São Paulo: Makron, 1991. 596 p. ISBN 0-07-460872-X
- DETLOVS, Volnis; PODNIEKS, Karlis. Introduction to Mathematical Logic. Disponível em: <http://www.ltn.lv/~podnieks/mlog/ml.htm>. Acesso em: 20 fev. 2009.
- MATES, Benson. Lógica elementar. São Paulo: Companhia Editora Nacional, 1968. 298 p.
- MATES, Benson. Elementary logic. 2. ed. New York: Oxford University Press, 1972. 237 p.
- COSTA, Newton Carneiro Affonso da. Ensaio sobre os fundamentos da lógica. São Paulo: Hucitec, 1980.
- HAMILTON, A. G. Logic for Mathematicians. Cambridge University Press: 1988.
- SMULLYAN, Raymond. First-order logic. Dover: 1967. Disponível parcialmente em: <http://books.google.com.br/books?id=AYcr1yKq1BcC&printsec=frontcover&client=firefox-a&source=gbs_v2_summary_r&cad=0#v=onepage&q=&f=false>. Acesso em: 16 set. 2009.
Livros de Divulgação
- BERLINSKI, David. O advento do algoritmo: a idéia que governa o mundo. São Paulo: Globo, 2002.
- SMULLYAN, Raymond. O enigma de Sherazade; e outros incríveis problemas das Mil e uma noites à lógica moderna. Rio de Janeiro: Jorge Zahar Ed., 1998.
Livros relacionados à disciplina
- SIPSER, Michael. Introdução à Teoria da Computação. São Paulo: Thomson Learning, 2007.
- WITTGENSTEIN, Ludwig. Tractatus Logico-Philosophicus. São Paulo: Editora da Universidade de São Paulo, 1994.
A classificar e colocar no formato ABNT
- Duffy, David A. (1991). Principles of Automated Theorem Proving, John Wiley & Sons.
- Wos, Larry; Overbeek, Ross; Lusk, Ewing; Boyle, Jim (1992). Automated Reasoning: Introduction and Applications (2nd edition ed.), McGraw-Hill.
- Alan Robinson and Andrei Voronkov (eds.), ed. (2001). Handbook of Automated Reasoning Volume I & II, Elsevier and MIT Press.
Artigos
- CARNIELLI, Walter A.; CONIGLIO, Marcelo E. 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.
- MARTIN-LÖF, Per. Truth of a proposition, evidence of a judgement, validity of a proof. Synthese, 73, pp. 407-420, 1987. Disponível em: <http://www.postech.ac.kr/~gla/cs433/papers/ml-truth.pdf> (cópia) e <http://www.springerlink.com/content/r11317743775t005/> (original, exclusivo para assinantes).
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
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
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)
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 as quais conversão para formas normais
Lógica de Predicados
- Tarski's World:
Programação em Lógica
- Livro de Eloi Favero (UFPA) sobre Prolog
- 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
- 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
- Interpretador SWI-Prolog:
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.
- http://yacas.sourceforge.net/
Listas de sistemas
- Tools for logic in computer science
- Logic software and logic education, list maintained by Hans van Ditmarsch