Estruturas discretas

Estruturas Discretas

1.1. L´gica proposicional o

1.
1.1.

Fundamentos
Como raciocinamos? L´gica proposicional o

A l´gica ´ a base de todo o racioc´ o e ınio. Portanto se quisermos estudar e fazer matem´tica a precisamos de dominar os princ´ ıpios b´sicos da l´gica. Citando Language, Proof and Logic (de a o Jon Barwise e John Etchemendy): “(...) all rational inquiry depends on logic, on the ability of people to reason correctly most of the time.” “(...) there is an overwhelming intuition that the laws of logic are somehow more irrefutable than the laws of the land, or even the laws of physics.” Porque deve um estudante de Inform´tica estudar l´gica? Porque precisa de dominar ferraa o mentas l´gicas que lhe permitam argumentar se um problema pode ou n˜o ser resolvido num o a computador, traduzir proposi¸˜es l´gicas da linguagem comum em diversas linguagens computaco o cionais, argumentar se um programa est´ correcto e se ´ eficiente. Os computadores baseiam-se a e em mecanismos l´gicos e s˜o programados de modo l´gico. Os inform´ticos devem ser capazes o a o a de compreender e aplicar novas ideias e t´cnicas de programa¸˜o, muitas das quais requerem e ca conhecimento dos aspectos formais da l´gica. o Todos n´s raciocinamos enunciando factos e tirando conclus˜es baseadas nesses factos. O o o in´ de uma conclus˜o ´ habitualmente indicada por uma palavra como ıcio a e Ent˜o, Logo, Portanto, Consequentemente, ... . a Para chegarmos a uma conclus˜o aplicamos uma regra de inferˆncia (ou regra de dedu¸ao). a e c˜ A mais comum ´ a chamada regra modus ponens (modo que afirma): sendo A e B afirma¸˜es, e co se A e “se A ent˜o B” s˜o ambas verdadeiras, ent˜o podemos concluir que B ´ verdadeira. a a a e [Como aprendeu a regra modus ponens em crian¸a ?] c Outra regra muito comum ´ a modus tollens (modo que nega): sendo A e B afirma¸˜es, se e co “se A ent˜o B” ´ verdadeira e B ´ falsa, ent˜o podemos concluir que A ´ falsa. a e e a e Por exemplo: – Se ele foi a Coimbra