Introducao a Logica

Introducao a Logica

• 1. Lógica para Computação (IF61B) Introdução à Lógica Slides da disciplina “Lógica para Computação”, ministrada pelo Prof. Celso Antônio Alves Kaestner, Dr. Eng. (kaestner@dainf.ct.utfpr.edu.br) entre 2007 e 2008. Alterações feitas em 2009 pelo Prof. Adolfo Neto (adolfo@utfpr.edu.br) Versão original disponível em http://www.dainf.ct.utfpr.edu.br/~kaestner/Logica/LogicaProposicional.ppt
• 2. Lógica para Computação (IF61B) Introdução • Três citações* 1. É razoável esperar que a relação entre a computação e a lógica matemática produza tantos frutos ... quanto a que se instalou entre a Análise Matemática e a Física no curso do século XIX (John McCarthy, 1963). (*) extraídas de “Logique: Méthodes pour l´informatique fondamentale”, de Paul Gochet e Pascal Gribomont, Hermes, Paris, 1990. 12/06/09 Prof. Celso A A Kaestner 2
• 3. Lógica para Computação (IF61B) Introdução • Três citações 1. Ao longo da maior parte do século XX, a Lógica Matemática foi principalmente utilizada para a introspecção. Como ferramenta para a criação de provas na prática cotidiana, ainda não teve sua chance. Para que possa realizar todas as potencialidades parece ser necessário conceber o objetivo da Lógica como sendo não de mimetizar o pensamento humano, mas como o de fornecer um substituto a este último na forma de um cálculo (Edsger Dijkstra). 12/06/09 Prof. Celso A A Kaestner 3
• 4. Lógica para Computação (IF61B) Introdução • Três citações 1. As conexões entre a Lógica e a Informática crescem e se aprofundam rapidamente. Ao lado da demonstração automática, da programação em lógica, da especificação e verificação de programas, outros setores revelam uma fascinante interação mútua com a Lógica, como a teoria de tipos, a teoria do paralelismo, a inteligência artificial, a teoria da complexidade, as bases de dados, a semântica operacional e as técnicas de compilação (José Meseguer). 12/06/09 Prof. Celso A A Kaestner 4
• 5. Lógica para Computação (IF61B) Introdução • História da Lógica: http://pt.wikipedia.org/wiki/História_da_lógica • Lógica: http://pt.wikipedia.org/wiki/Lógica Obs.: Artigos da Wikipédia (pt) em geral são pouco confiáveis, mas contém rerefências para material de melhor qualidade. 12/06/09 Prof. Celso A A Kaestner 5
• 6. Lógica para Computação (IF61B) Introdução • O que é Lógica ? 1. O estudo da Lógica é o estudo dos métodos e princípios usados para distinguir o raciocínio correto do incorreto (“Introdução à Lógica”, Irving M. Copi, Ed. Mestre Jou, São Paulo, 1968); 2. A Lógica formal é uma ciência que determina as formas corretas (ou válidas) de raciocínio (“Noções de Lógica Formal”, Joseph Dopp, Ed. Herder, São Paulo, 1970); 12/06/09 Prof. Celso A A Kaestner 6
• 7. Lógica para Computação (IF61B) Introdução • O que é Lógica ? 1. Lógica é o estudo de argumentos. Um argumento é uma seqüência de enunciados na qual um dos enunciados é a conclusão e os demais são premissas, as quais servem para provar, ou pelo menos fornecer alguma evidência para a conclusão (“Lógica”, John Nolt e Dennis Rohatyn, Makron Books, São Paulo, 1991). 12/06/09 Prof. Celso A A Kaestner 7
• 8. Lógica para Computação (IF61B) Introdução • O que é Lógica ? 1. Lógica, hoje, designa uma vasta área do conhecimento, com implicações em praticamente todas os demais domínios da investigação. Da antiga disciplina que estudava quot;o raciocínio corretoquot;, ou as quot;formas válidas de inferência (ou de raciocínio)quot;, a lógica transformou-se em uma disciplina que alcançou resultados que, em termos de complexidade e profundidade,nada ficam devendo aos maiores resultados da matemática. Aliás, a lógica é, presentemente, uma disciplina de características matemáticas... (“Lógica: uma visão geral da lógica atual”, Newton C.A. da Costa e Décio Krause, em preparação). 12/06/09 Prof. Celso A A Kaestner 8
• 9. Lógica para Computação (IF61B) Introdução • No artigo intitulado “Truth of a proposition, evidence of a judgment, validity of a proof” o lógico-matemático P. Martin-Löf constata que não se pode expor a Lógica (ou uma lógica) sem utilizar 5 noções primitivas: 1. A noção de proposição; 2. A noção de verdade de uma proposição; 3. A noção de asserção ou julgamento; 4. A noção de evidência ou de prova de um julgamento; 5. A noção de correção ou validade de uma prova. 12/06/09 Prof. Celso A A Kaestner 9
• 10. Lógica para Computação (IF61B) Introdução • Outros conceitos: 1. Termos gerais (ou universais) X termos singulares (ou individuais); 1. Designação por intenção X por extensão; – Intenção: qualidades ou propriedades que constituem o conceito; – Extensão: consiste dos elementos (exemplos) que constituem o conceito. 12/06/09 Prof. Celso A A Kaestner 10
• 11. Lógica para Computação (IF61B) Introdução • Conceito de proposição (desde Platão): • Combinação de um substantivo e de um verbo, constituindo um sentença declarativa à qual se pode atribuir um valor verdade (no caso clássico, verdadeiro ou falso): “O homem aprende”; “O céu é azul”; “Hoje é terça-feira”. • Observe que estão excluídas, entre outras, sentenças interrogativas, auto-referentes, etc. 12/06/09 Prof. Celso A A Kaestner 11
• 12. Lógica para Computação (IF61B) Introdução • A tradição aristotélica: lógica é o estudo da concepção, do julgamento, e do raciocínio; – Os conceitos são expressos por termos gerais; – Os julgamentos são expressos por proposições; – Os raciocínios são seqüências de proposições. • Em Aristóteles as proposições são constituídas por dois termos gerais ligados pelo verbo ser na forma “é” ou “não é” (ligação chamada de cópula lógica). • As proposições são relacionadas logicamente de acordo com o “quadrado lógico” ou “ tábua de oposições”. 12/06/09 Prof. Celso A A Kaestner 12
• 13. Lógica para Computação (IF61B) Introdução Tábua de oposições contrárias A E subalternas subalternas s con it ória trad trad itór ias con I O subcontrárias 12/06/09 Prof. Celso A A Kaestner 13
• 14. Lógica para Computação (IF61B) Introdução • Tipos de proposições e exemplos: – A: afirmação universal (todo homem é mortal); – E: negação universal (nenhum homem é mortal); – I: afirmação particular (algum homem é mortal); – O: negação particular (algum homem não é mortal). • Relacionamento entre proposições : – A e E são ditos contrários; se a proposição A é verdadeira então E é falsa; – A e O e também E e I são contraditórios: não podem ser nem verdadeiros nem falsos conjuntamente; – I e O são sub-contrários: não podem ser ambos falsos; – I é subalterno de A, e O é subalterno de E; se A é verdadeira, I também o é, e se E é verdadeira então O também o é. 12/06/09 Prof. Celso A A Kaestner 14
• 15. Lógica para Computação (IF61B) Introdução • Relacionamento entre proposições: – A existência de quatro tipos de proposições não é coincidência: representam as quatro relações possíveis entre as extensões dos termos gerais; – O matemático Euler representou as quatro relações lógicas na forma de diagramas de conjuntos (diagramas de Venn-Euler). • Se S é o termo sujeito e se P é um predicado então as proposições correspondem aos diagramas a seguir. 12/06/09 Prof. Celso A A Kaestner 15
• 16. Lógica para Computação (IF61B) Introdução • Proposição A: inclusão total P (todo S é P) S • Proposição E: exclusão total (nenhum S é P) P S • Proposição I: inclusão parcial de S em P SP (algum S é P) • Proposição O: exclusão parcial de S em P S P (algum S não é P) 12/06/09 Prof. Celso A A Kaestner 16
• 17. Lógica para Computação (IF61B) Introdução • Os raciocínios lógicos ocorrem na forma de seqüências de proposições geradas por inferências imediatas obtidas da tábua de oposições. • Um silogismo é um discurso no qual, estando dadas certas proposições premissas, uma nova proposição conclusão é obtida necessariamente e unicamente a partir das premissas. • Usualmente os silogismos são apresentados da seguinte forma: » Premissa maior » Premissa menor » Conclusão • O termo menor (S) é o sujeito da conclusão, o termo maior (P) é o predicado da conclusão, e o termo comum às premissas é o termo médio (M). 12/06/09 Prof. Celso A A Kaestner 17
• 18. Lógica para Computação (IF61B) Introdução • Exemplos: – Todos os mamíferos são vertebrados (premissa maior) – Todos os homens são mamíferos (premissa menor) portanto – Todos os homens são vertebrados (conclusão). • Neste caso o termo menor S é “todos os homens”, o termo maior P é “vertebrados”, e o termo médio M é “mamíferos”. • Este silogismo tem portanto a forma: MP SM • Todas as proposições são do tipo A. SP 12/06/09 Prof. Celso A A Kaestner 18
• 19. Lógica para Computação (IF61B) Introdução • Considerando que há 4 tipos de proposições (A,E,I e O) então há 43 = 64 silogismos por figura (ver abaixo) , ou seja 256 silogismos no total; • As figuras do silogismo são: 1ª figura 2ª figura 3ª figura 4ª figura Premissa maior MP PM MP PM Premissa menor SM SM MS MS Conclusão SP SP SP SP 12/06/09 Prof. Celso A A Kaestner 19
• 20. Lógica para Computação (IF61B) Introdução • Nem todos os silogismos são válidos; o estudo da Lógica por Aristóteles, e posteriormente na idade média, buscou separar os silogismos válidos, ou seja, aqueles em que a conclusão segue necessariamente das premissas; • Pode-se deduzir a validade ou não de um silogismo a partir dos diagramas de Venn-Euler correspondentes; • Exemplo: – Nenhum peixe (M) é mamífero (P) <tipo E>; – Todos os robalos (S) são peixes (M) <tipo A>; M portanto S P – Nenhum robalo (S) é mamífero (P) <tipo E>. MP<E> • Ou, esquematicamente: SM<A> SP<E> 12/06/09 Prof. Celso A A Kaestner 20
• 21. Lógica para Computação (IF61B) Introdução • Exemplo: – Todos os animais venenosos (M) são perigosos (P) <tipo A>; – Algumas serpentes (S) são animais venenosos (M) <tipo I>; portanto – Algumas serpentes (S) são perigosas (P) <tipo I>. • Esquematicamente: MP<A> SM<I> M S P SP<I> 12/06/09 Prof. Celso A A Kaestner 21
• 22. Lógica para Computação (IF61B) Introdução • Em alguns casos os diagramas de Venn-Euler apresentam o inconveniente de admitir, para um mesmo silogismo, várias representações geométricas; • Exemplo: M S P MP<E> SM<I> SP<O> M S P M S P 12/06/09 Prof. Celso A A Kaestner 22
• 23. Lógica para Computação (IF61B) Introdução • Verdade e validade (ou correção): – Um silogismo é válido (correto) se e somente se (sse) a verdade da conclusão segue necessariamente da verdade das premissas; – Os silogismos portanto “transmitem” a verdade das premissas à conclusão; – Esta definição exclui a possibilidade de que um silogismo válido possa ter premissas verdadeiras e conclusão falsa; – Isto não exclui a possibilidade de que a conclusão de um silogismo válido seja falsa; neste caso alguma das premissas é falsa. • Exemplo: – Todos os animais marinhos são peixes; – Todas as baleias são animais marinhos; portanto – Todas as baleias são peixes. 12/06/09 Prof. Celso A A Kaestner 23
• 24. Lógica para Computação (IF61B) Introdução Exercícios introdutórios: 1. Consulte os links indicados e navegue sobre assuntos relacionados à história da Lógica e à sua definição; 2. Pesquise a definição de paradoxo e exemplifique este conceito; 3. Encontre uma “charada” e apresente sua solução. 12/06/09 Prof. Celso A A Kaestner 24
• 25. Lógica para Computação (IF61B) Introdução • Exercícios sobre lógica aristotélica: 1. Indique a forma do silogismo (termos, figura, diagrama), e indique se mesmo é válido ou não: a) Todos os gregos são homens; Todos os atenienses são gregos; Todos os atenienses são homens. b) Todos os socialistas são marxistas; Alguns governantes são marxistas; Alguns governantes são socialistas. c) Todas as ações penais são atos cruéis; Todos os processos por homicídio são ações penais; Todos os processos por homicídio são atos cruéis. 12/06/09 Prof. Celso A A Kaestner 25
• 26. Lógica para Computação (IF61B) Introdução d) Alguns papagaios não são animais nocivos; Todos os papagaios são animais de estimação; Nenhum animal de estimação é nocivo. e) Nenhum ator dramático é um homem feliz; Alguns comediantes não são homens felizes; Alguns comediantes não são atores dramáticos. f) Todos os coelhos são corredores muito velozes; Alguns cavalos são corredores muito velozes; Alguns cavalos são coelhos. 12/06/09 Prof. Celso A A Kaestner 26
• 27. Lógica para Computação (IF61B) Introdução 2. Escreva na forma típica, indique termos, figura, diagrama, e verifique a validade: a) Nenhum submarino de propulsão nuclear é um navio mercante, assim nenhum vaso de guerra é navio mercante, visto que todos os submarinos de propulsão nuclear são vasos de guerra; b) Alguns conservadores não são defensores de tarifas elevadas, porque todos os defensores de tarifas elevadas são republicanos, e alguns republicanos não são conservadores; c) Nenhum indivíduo obstinado que jamais admite um erro é bom professor; portanto, como algumas pessoas bem informadas são indivíduos obstinados que nunca admitem um erro, alguns bons professores não são pessoas bem informadas. 12/06/09 Prof. Celso A A Kaestner 27