CÉSAR GARCIA DAUDT – Nº 180164
1. Qual a importância dos seguintes lógicos para a ciência da computação?
a) Alan Turing
b) Alonzo Church
c) Kurt Gödel
Alan Turing:
Turing tem importância no ramo da ciência da computação por causa de seus trabalhos
realizados na área de Teoria da Computabilidade, ou seja, a preocupação e análise do que pode ser
ou não feito em um computador. Além disso, suas idéias da Máquina de Turing (que, apesar de
hipotética, consegue delinear e explicar o funcionamento de qualquer máquina real baseada nesta) e
do Teste de Turing (intuito de testar a presenca ou não de “inteligência” em um programa de
computador) são presença em ramos importantes da computação, como a Inteligência Artificial e a
já citada Teoria da Computabilidade.
Alonzo Church:
Church possui estudos que contribuíram para a teoria da recurso e computação, área de
importância fundamental de toda a ciência da computação. Dentre as maiores contribuições do
matemático/lógico, está o cálculo lambda, um sistema formal relacionado à teoria das funções. Toda
a gama de linguagens de programação funcionais tem influência direta do trabalho de Alonzo
Church.
Kurt Gödel:
Gödel tem como sua contribuição mais importante o Teorema da Incompletude, onde mostra
que qualquer sistema axiomático não pode ser suficiente para incluir a aritmética dos números
inteiros não pode ser simultaneamente completo e consistente, o que tem aplicações nas áreas de
Complexidade Computacional.
Fontes para questão 1:
http://en.wikipedia.org/wiki/Alan_Turing
http://pt.wikipedia.org/wiki/Alonzo_Church
http://pt.wikipedia.org/wiki/Kurt_G%C3%B6del
http://en.wikipedia.org/wiki/Turing_machine
http://pt.wikipedia.org/wiki/Teste_de_Turing
http://pt.wikipedia.org/wiki/Computabilidade
http://en.wikipedia.org/wiki/Alonzo_Church
http://pt.wikipedia.org/wiki/C%C3%A1lculo_lambda
http://en.wikipedia.org/wiki/Kurt_G%C3%B6del
http://pt.wikipedia.org/wiki/Teorema_da_Incompletude_de_G%C3%B6del
http://pt.wikipedia.org/wiki/Completude
2. Explicar o significado do seguinte:
a) Correção de sistemas lógicos (sistemas de prova)(soundness)
b) Completude de sistemas lógicos (sistemas de prova)(completeness)
c) Consistência em sistemas lógicos.(consistency)
Correção:
É uma propriedade de sistemas lógicos que indica que um sistema a possui se e só se suas
regras de inferência demonstram apenas fórmulas válidas do ponto de vista semântico. Isto
geralmente esta relacionado à preservação da verdade por parte das regras deste sistema.
Completude:
Todo sistema que dotado desta propriedade, tem a garantia que toda sentença válida pode ser
formalmente derivada, o que acaba por relacionar o universo semântico e sintático em um
determinado cálculo lógico.
Consistência:
Sistemas com esta propriedade excluem a existência de contradições, no sentido de que não
é possível nestes sistemas fazer uma prova de alguma proposição como verdadeira e depois mostrála contraditória.
Fontes para questão 2:
http://en.wikipedia.org/wiki/Consistency
http://en.wikipedia.org/wiki/Soundness
http://pt.wikipedia.org/wiki/Corre%C3%A7%C3%A3o
http://pt.wikipedia.org/wiki/Completude
http://en.wikipedia.org/wiki/Completeness