matematica

Notas de

´
Matematica Discreta

LURDES SOUSA

Departamento de Matem´tica a Escola Superior de Tecnologia de Viseu
Instituto Polit´cnico de Viseu e 2006

—–

´
Indice

I - C´lculo Proposicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 a 1 Proposi¸˜es e conectivos l´gicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 co o
2 F´rmulas bem formadas e semˆntica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 o a
3 Equivalˆncia l´gica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 e o
4 Argumentos correctos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5 Formas normais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
6 Conjuntos de conectivos l´gicos completos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 o 7 Sistemas Formais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
8 Sobre demonstra¸˜es e implica¸˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 co co
9 Exerc´ ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

II - C´lculo de Predicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 a 1 Predicados e quantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2 F´rmulas bem formadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 o 3 Semˆntica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 a 4 F´rmulas equivalentes . . . . . . . . . . . . . . . . . .