ROSEN Discreta

C A P Í T U L O

1
1.1 Lógica
Proposicional
1.2 Equivalências
Proposicionais
1.3 Predicados e
Quantificadores
1.4 Quantificadores
Agrupados
1.5 Regras de
Inferência
1.6 Introdução a
Demonstrações
1.7 Métodos de
Demonstração
e Estratégia

Os Fundamentos:
Lógica e Demonstrações

A

s regras da lógica especificam o significado de sentenças matemáticas. Propositalmente, essas regras nos ajudam a entender proposições tais como “Existe um inteiro que não é a soma de dois quadrados” e “Para cada inteiro positivo n, a soma dos inteiros positivos menores que ou iguais a n é n(n + 1) / 2”, bem como a raciocinar sobre elas. Lógica é a base de todo raciocínio matemático e de todo raciocínio automatizado. Ela tem aplicações práticas no desenvolvimento de máquinas de computação, em especificação de sistemas, em inteligência artificial, em programação de computadores, em linguagens de programação e em outras áreas da ciência da computação, bem como em outros campos de estudo.
Para entender matemática, precisamos entender o que torna um argumento matemático correto, ou seja, uma demonstração. Primeiro, demonstramos que uma afirmação é verdadeira e a chamamos de teorema. Um conjunto de teoremas sobre determinado tópico organiza o que conhecemos sobre esse tópico. Para aprender um tópico de matemática, uma pessoa precisa construir ativamente argumentos matemáticos nesse tópico, e não apenas ler algumas exposições. Além disso, conhecer a demonstração de um teorema, com freqüência, torna possível modificar o resultado em alguma outra situação;; demonstrações são essenciais para o desenvolvimento de novas idéias. Estudantes de ciência da computação freqüentemente se surpreendem em relação ao quanto as demonstrações são importantes em sua área. De fato, elas são essenciais quando queremos verificar se